比赛的时候口胡这道题口胡了一年，看完题解被教做人
题意：有n只火鸡，m个猎人按序来杀火鸡，从自己预先选的两只中杀一只，问有多少火鸡对可以同时存活
考虑对于每一只火鸡i，按时间逆序维护一个最小的集合Si，满足当前时间其中的所有火鸡都活着才能保证最后火鸡i活下
在当前操作的最前面加入新的操作x y对结果转移的影响
1.x y均不在集合中，显然与i的死活无关，不管
2.一个在集合中，不放设为x，则y在这个操作前必须活着才能保证这个操作后x活着
3.都在集合中，gg
从最后一步逆推到第一步，得到集合Si
从我们的递推过程不难发现Si中的火鸡最后都是必死无疑，而且如果有火鸡在预料之外送人头也会gg
那么i和j能在最后同时存活的充要条件就是Si∩Sj==?
bitset维护，完事
1 #include <bits/stdc++.h> 2 #define B bitset<500> 3 using namespace std; 4 int n,m; 5 int x[200000],y[200000]; 6 bool die[500]; 7 B a[500]; 8 int main() 9 { 10 scanf("%d%d",&n,&m); 11 for(int i=1;i<=m;i++) 12 scanf("%d%d",&x[i],&y[i]); 13 for(int i=1;i<=n;i++) 14 { 15 a[i][i]=1; 16 for(int j=m;j;j--) 17 if(a[i][x[j]] && a[i][y[j]]) 18 { 19 die[i]=1; 20 break; 21 } 22 else 23 if(a[i][x[j]]) 24 a[i][y[j]]=1; 25 else 26 if(a[i][y[j]]) 27 a[i][x[j]]=1; 28 } 29 int ans=0; 30 for(int i=1;i<n;i++) 31 if(!die[i]) 32 for(int j=i+1;j<=n;j++) 33 if(!die[j] && (a[i]&a[j]).none()) 34 ++ans; 35 printf("%d\n",ans); 36 return 0; 37 }
原文：http://www.cnblogs.com/wanglichao/p/7141860.html