题解：P7005 [NEERC2013] Join the Conversation

Crazyouth · 2024-09-10 15:02:32 · 题解

前言

这个题建议评蓝，细节处理太多了，找一句话提及的人花了我一天。

分析

注意到这题很像一个最长上升子序列弱化，因此想到 dp。令 dp_i 表示以第 i 句话结尾的最长对话长度，不难发现它可以从第 i 句话所提及到不是自己的人里面转移。为了方便转移，我们令 lst_s 表示名字为 s 的人所发的话里面下标小于当前处理到的话的下标，且 dp 值最大的一句，在每句话处理后再处理 lst。

接下来就是处理每句话提及到的人了。依题意得，每个被提及的人名前必须带空格，因此考虑以空格作为分隔符，把句子拆成单词，然后弃掉所有不以 @ 开头的单词。由于题目并没有说提及的人名字后带空格，因此对于每个以 @ 开头的单词，需要将它的每个含第一个字符的字串分别进行查找，然后进行转移。

最后选择最大的 dp 值输出答案，并找到它转移过来的方向，倒着输出即可。

有一个小点要注意：使用 getline 的话必须让程序读取一个空行再正式输入每一句话。

AC Code

#include <bits/stdc++.h>
using namespace std;
int dp[50010],from[50010],pos[50010],fans[50010];
map<string,int> lst;
string s[50010],str;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,cnt=0;
    cin>>n;
    getline(cin,s[0]);
    for(int i=1;i<=n;i++) getline(cin,s[i]),dp[i]=1;
    for(int i=1;i<=n;i++)
    {
        int flag=0;
        string res="",name;
        for(int j=0;j<s[i].size();j++)
        {
            if(!flag&&s[i][j]==':')
            {
                flag=1;
                name=res;
                res="";
                continue;
            }
            if(flag&&s[i][j]==' ')
            {
                res="";
                continue;
            }
            res+=s[i][j];
            if(flag&&res[0]=='@'&&res!=name)
            {
                if(lst[res])
                {
                    if(dp[lst[res]]+1>dp[i])
                    {
                        dp[i]=dp[lst[res]]+1;
                        from[i]=lst[res];
                    }
                }
            }
        }
        if(!lst[name]||dp[lst[name]]<dp[i]) lst[name]=i;
    }
    int ans=0,idx;
    for(int i=1;i<=n;i++)
    {
        if(dp[i]>ans)
        {
            ans=dp[i];
            idx=i;
        }
    }
    cout<<ans<<'\n';
    int now=idx,cnt2=0;
    while(now)
    {
        fans[++cnt2]=now;
        now=from[now];
    }
    for(int i=cnt2;i;i--) cout<<fans[i]<<' ';
    return 0;
}