[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
题意很简单……双方给N个人(N<=6)打三国杀1V1,你知道对手每个人能克制你哪些人,我们认为两个人对打,他能克你则他胜利,否则你胜利;某人的N个人死光就输了……你需要组织阵容按照顺序对抗对手……求有没有一个顺序,无论对手顺序如何,你都能胜……
N!枚举自己的顺序,然后N!枚举对方的顺序,O(N)验证即可……
注意字典序最小……

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <map>
 5 #include <algorithm>
 6 #include <iostream>
 7 
 8 using namespace std;
 9 
10 map<string,int> mp;
11 int n;
12 int res[10];
13 int my[10];
14 char buf[50];
15 char name[10][50];
16 string ans;
17 
18 void check() {
19     int enemy[] = {0,1,2,3,4,5,6,7,8,9};
20     do {
21         int i = 0;
22         int j = 0;
23         while (i < n && j < n) {
24             if ((1 << my[i]) & res[enemy[j]]) i ++else j++;
25         }
26         if (i == n) return;
27     } while (next_permutation(enemy,enemy + n));
28     string tmp;
29     for (int i = 0; i < n; i++) {
30         if (i) tmp += " ";
31         tmp += name[my[i]];
32     }
33     if (ans == "" || ans > tmp) ans = tmp;
34 }
35 
36 int main() {
37     int nn; scanf("%d",&nn);
38     for (int ii = 1; ii <= nn; ii++) {
39         mp.clear();
40         memset(res,0,sizeof(res));
41         scanf("%d",&n);
42         for (int i = 0; i < n; i++) {
43             scanf("%s",name[i]);
44             mp[string(name[i])] = i;
45         }
46         for (int i = 0; i < n; i++) {
47             int m; scanf("%d",&m);
48             for (int j = 0; j < m; j++) {
49                 scanf("%s",buf);
50                 int tmp = mp[string(buf)];
51                 res[i] |= 1 << tmp;
52             }
53         }
54         for (int i = 0; i < n; i++) {
55             my[i] = i;
56         }
57         ans = "";
58         do {
59             check();
60         } while (next_permutation(my,my + n));
61         printf("Case %d: ",ii);
62         if (ans == "") {
63             puts("No");
64         } else {
65             puts("Yes");
66             for (int i = 0; i < ans.length(); i++) putchar(ans[i]);
67             putchar(10);
68         }
69     }
70     return 0;
71 }
posted on 2011-10-07 20:15 sweetsc 阅读(532) 评论(0)  编辑  收藏 所属分类: ACM/ICPC

只有注册用户登录后才能发表评论。


网站导航: