CodeForces 754C Vladik and chat —

CodeForces 754C Vladik and chat ——（xjbg）

阅读量：6848 次

发布时间：2019-06-26

本文共 1995 字，大约阅读时间需要 6 分钟。

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

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

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

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

　　具体见代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
           7 #include 
           
             8 using namespace std; 9 const int N = 100 + 5; 10 11 int cnt[N]; 12 int choose[N][N]; 13 int vis[N]; 14 string name[N]; 15 string ss[N]; 16 17 bool isok(char c) 18 { 19 if(c>='0' && c<='9') return 1; 20 if(c>='a' && c<='z') return 1; 21 if(c>='A' && c<='Z') return 1; 22 return 0; 23 } 24 25 int main() 26 { 27 int T; 28 scanf("%d",&T); 29 while(T--) 30 { 31 memset(cnt,0,sizeof(cnt)); 32 memset(choose,0,sizeof(choose)); 33 map
            
              M; 34 int n;scanf("%d",&n); 35 char s[100]; 36 for(int i=1;i<=n;i++) 37 { 38 scanf(" %s",s); 39 string str = (string)s; 40 M[str] = i; 41 name[i] = str; 42 } 43 int m;scanf("%d",&m);getchar(); 44 int k = 0; 45 for(int i=1;i<=m;i++) 46 { 47 int flag = 0; 48 memset(vis,0,sizeof(vis)); 49 string str = ""; 50 string now = ""; 51 getline(cin, str); 52 ss[i] = str; 53 int sz = str.length(); 54 for(int j=0;j
             
               1 || !choose[i-1][j])) 85 { 86 choose[i][j] = 1; 87 cnt[i]++; 88 t = 0; 89 } 90 } 91 k = k || t; 92 } 93 94 if(k) {puts("Impossible");continue;} 95 vector
              
                ans; 96 for(int i=m;i>=1;i--) 97 { 98 ss[i].erase(0, ss[i].find(':')); 99 for(int j=1;j<=n;j++)100 {101 if(choose[i][j])102 {103 if(i > 1) choose[i-1][j] = 0;104 ans.push_back(name[j] + ss[i]);105 break;106 }107 }108 }109 if(ans.size() != m) {puts("Impossible");continue;}110 for(int i=ans.size()-1;i>=0;i--) cout << ans[i] << endl;111 }112 return 0;113 }

转载于:https://www.cnblogs.com/zzyDS/p/6273154.html

你可能感兴趣的文章