http://codeforces.com/contest/754/problem/C
题意:
现在有n个人,然后有m句话,有些话不知道说话人是谁,现在我们要去找能去说这句话的人,要求是前后两句话说话的人不能相同,如果后面话中出现的名字也不能作为说话人。输出一种情况即可。
思路:
用 f【i】【j】=1 表示 j 可以说第 i 句话,g【】【】用来记录路径,用于最后的输出。
先对每句话进行处理,分离出说话人和后面话中所包含的说话人。对于这句话,我们找到上一句话可以说话的人,在此基础上,判断接下来可以说话的人有谁。
话说这个字符串的处理还真是麻烦啊....
参考了http://blog.csdn.net/h1021456873/article/details/54947748的代码。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=100+5; 17 18 int n, m; 19 20 int f[maxn][maxn]; //f[i][j]表示j可以说第i句话 21 int g[maxn][maxn]; //记录状态,用于输出(相当于记录路径) 22 23 string name[maxn]; 24 string str[maxn]; //第i句话 25 string re[maxn]; //记录第i句话,不包括说话人 26 27 map<string, int> ID; 28 29 void print(int m, int x) 30 { 31 if(m==0) return; 32 print(m-1,g[m][x]); 33 cout<<name[x]<<re[m-1]<<endl; 34 } 35 36 int main() 37 { 38 //freopen("in.txt","r",stdin); 39 int t; 40 scanf("%d",&t); 41 while(t--) 42 { 43 ID.clear(); 44 bool flag=true; 45 46 scanf("%d",&n); 47 for(int i=0;i<n;i++) 48 { 49 cin>>name[i]; 50 ID[name[i]]=i; 51 } 52 scanf("%d",&m); 53 getchar(); 54 for(int i=0;i<m;i++) 55 { 56 getline(cin, str[i]); 57 re[i].clear(); 58 } 59 60 memset(f,0,sizeof(f)); 61 memset(g,0,sizeof(g)); 62 f[0][n]=1; 63 64 for(int i=0;i<m;i++) 65 { 66 string user, buf = str[i]; 67 int p=0; 68 for(; p<buf.size() && buf[p]!=':'; p++) 69 { 70 user+=buf[p]; 71 } 72 73 int q = p; 74 while(q<buf.size()) 75 { 76 re[i]+=buf[q++]; 77 } 78 79 set<int> mention; //记录当前这句话不能说的人 80 while(p<buf.size()) 81 { 82 string word; 83 while(p<buf.size() && isalnum(buf[p])) 84 { 85 word+=buf[p++]; 86 } 87 if(ID.count(word)) mention.insert(ID[word]); 88 if(p<buf.size()) p++; 89 } 90 91 if(user=="?") 92 { 93 for(int j=0;j<=n;j++) 94 { 95 if(!f[i][j]) continue; //寻找上一句可以说的人 96 for(int k=0;k<n;k++) 97 { 98 if(mention.count(k) || k==j) continue; //不在set中并且和上一句说话的不是同一个人 99 f[i+1][k]=1; 100 g[i+1][k]=j; 101 } 102 } 103 } 104 else 105 { 106 if(!ID.count(user)) 107 { 108 flag=false; 109 } 110 int id = ID[user]; 111 if(mention.count(id)) 112 { 113 flag=false; 114 } 115 else 116 { 117 for(int j=0;j<=n;j++) 118 { 119 if(!f[i][j]) continue; 120 if(id!=j) 121 { 122 f[i+1][id]=1; 123 g[i+1][id]=j; 124 } 125 } 126 } 127 } 128 } 129 130 if(flag==true) 131 { 132 int x=-1; 133 for(int j=0;j<n;j++) 134 if(f[m][j]) x=j; 135 136 if(x==-1) puts("Impossible"); 137 else print(m,x); 138 } 139 else puts("Impossible"); 140 } 141 return 0; 142 }