【20190525】测试

食物中毒

错误原因：

没有意识到在药包里就会有几个相同的化学物质
int转long long的时候没有处理好导致出现负数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define rg register
 4 #define ll long long
 5 const int N=20+5,M=50+5,inf=0x3f3f3f3f;
 6 int n,m,yes,cnt=0;
 7 ll sta,a[M];
 8 template<class t>void rd(t &x)
 9 {
10     x=0;int w=0;char ch=0;
11     while(!isdigit(ch)) w|=x=='-',ch=getchar();
12     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
13     x=w?-x:x;
14 }
15  
16 void dfs(int x,ll ss){
17     if(yes) return;
18     ss^=a[x];
19     if((ss&sta)==sta) {yes=1;return;}
20     for(rg int i=x+1;i<=n;++i) dfs(i,ss);
21 }
22  
23 int main()
24 {
25     //freopen("medicine.in ","r",stdin);
26     //freopen("medicine.out","w",stdout);
27     while(scanf("%d%d",&n,&m)==2){
28         sta=0,yes=0;
29         memset(a,0,sizeof(a));
30         int x,y;
31         for(rg int i=1;i<=m;++i){
32             rd(x);
33             sta|=((ll)1<<(x-1));
34         }
35         for(rg int i=1;i<=n;++i){
36             rd(y);
37             for(rg int j=1;j<=y;++j){
38             rd(x);a[i]^=((ll)1<<(x-1));
39             }
40         }
41         for(rg int i=1;i<=n;++i)
42         {
43             dfs(i,0);
44             if(yes) break;
45         }
46         if(!yes) printf("Impossible
",++cnt);
47         else printf("Possible
",++cnt);
48     }
49     return 0;
50 }

食物中毒搜索+位运算

消息传递

图论全忘完了背不到模板意识不到题型基础知识不牢固

周年纪念

同上题得好好搞一下图论