CodeForces 754C Vladik and chat —

　　虽然是xjbg的题目，但是并不很好做。

　　题意不难理解。读入有点麻烦。做法是先正着推每段对话的？可能是谁说的，然后反过来选择即可。正推时，其中vis数组表示谁已经被用过了，cnt表示该组当前可以选择几个，choose[i][j]表示第i段对话中，选择第j个名字作为说话者是不是可能的。

　　那么正推时就不难理解了，首先要这个名字没出现在他说的话中，然后1.这是第一段话，2.前一段对话中这个名字不是被选择作为说话者的，3.前一段对话选了好几个（因此我可以选择这个名字作为说话者而不重复，因为前一段对话可以选另外一个名字）。这三个条件任意一个满足即可。

　　然后反过来选择时，从最后一个开始，选择其可行的，当前这段对话这个名字是作为说话者了以后，前一段对话显然这个名字不能再作为说话者，因此需要更新choose数组。然后就写完了。（没有什么算法，但是也不好写。。）

　　具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <map>

 #include <vector>

 using namespace std;

 const int N =  + ;

 int cnt[N];

 int choose[N][N];

 int vis[N];

 string name[N];

 string ss[N];

 bool isok(char c)

 {

     if(c>='' && c<='') return ;

     if(c>='a' && c<='z') return ;

     if(c>='A' && c<='Z') return ;

     return ;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         memset(cnt,,sizeof(cnt));

         memset(choose,,sizeof(choose));

         map<string, int> M;

         int n;scanf("%d",&n);

         char s[];

         for(int i=;i<=n;i++)

         {

             scanf(" %s",s);

             string str = (string)s;

             M[str] = i;

             name[i] = str;

         }

         int m;scanf("%d",&m);getchar();

         int k = ;

         for(int i=;i<=m;i++)

         {

             int flag = ;

             memset(vis,,sizeof(vis));

             string str = "";

             string now = "";

             getline(cin, str);

             ss[i] = str;

             int sz = str.length();

             for(int j=;j<sz;j++)

             {

                 if(isok(str[j]))

                 {

                     now = now + str[j];

                 }

                 else if(now != "")

                 {

                     if(str[] != '?')

                     {

                         cnt[i] = ;

                         choose[i][M[now]] = ;

                         j = sz;

                         flag = ;

                     }

                     else

                     {

                         if(M[now] != )

                         {

                             vis[M[now]] = ;

                         }

                         now = "";

                     }

                 }

             }

             if(now != "" && M[now] != ) vis[M[now]] = ;

             if(flag) continue;

             int t = ;

             for(int j=;j<=n;j++)

             {

                 if(!vis[j] && (i== || cnt[i-] >  || !choose[i-][j]))

                 {

                     choose[i][j] = ;

                     cnt[i]++;

                     t = ;

                 }

             }

             k = k || t;

         }

         if(k) {puts("Impossible");continue;}

         vector<string> ans;

         for(int i=m;i>=;i--)

         {

             ss[i].erase(, ss[i].find(':'));

             for(int j=;j<=n;j++)

             {

                 if(choose[i][j])

                 {

                     if(i > ) choose[i-][j] = ;

                     ans.push_back(name[j] + ss[i]);

                     break;

                 }

             }

         }

         if(ans.size() != m) {puts("Impossible");continue;}

         for(int i=ans.size()-;i>=;i--) cout << ans[i] << endl;

     }

     return ;

 }

巴特西

CodeForces 754C Vladik and chat ——（xjbg）

最新文章

热门文章