題意：

有n只雞，開始都活著。要按時間吃m次雞，每次選兩只，若兩只都活著則隨便吃一個，若只有一只活著就吃活的那個，如果死光了就不吃。問最后可能有多少對雞同時存活（不考慮順序）

$2\leq n\leq 400$

$1\leq m\leq 10^5$

題解：

妙啊思博題。考慮一直雞$x$，如果要活下來那么在最后一次二選一的時候另外一只雞也要活著，倒數第二次的時候另外那只雞也要活著……即按照時間倒過來，另外的一些雞必須要活著，$x$才能活下來，設這些必須活下來的雞為$x$的存活集合。那么兩只雞同時存活下來的條件就是當且僅當兩只雞都有可能存活且相互之間的存活集合沒有交集，否則必定有一只被吃。

直接暴力維護存活集合，時間復雜度$O(n^3+nm)$，不知道為什么跑的飛快

代碼：

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 using namespace std; 6 int n,m,ans=0,a[100001],b[100001]; 7 bool ok[1001],st[1001][1001]; 8 int main(){ 9 scanf("%d%d",&n,&m); 10 for(int i=1;i<=m;i++){ 11 scanf("%d%d",&a[i],&b[i]); 12 } 13 for(int i=1;i<=n;i++){ 14 st[i][i]=1; 15 for(int j=m;j;j--){ 16 int x=st[i][a[j]],y=st[i][b[j]]; 17 if(x&&y){ 18 ok[i]=true; 19 break; 20 }else{ 21 if(x)st[i][b[j]]=1; 22 if(y)st[i][a[j]]=1; 23 } 24 } 25 } 26 for(int i=1;i<n;i++){ 27 if(ok[i])continue; 28 for(int j=i+1;j<=n;j++){ 29 if(ok[j])continue; 30 int tmp=1; 31 for(int k=1;k<=n;k++){ 32 if(st[i][k]&&st[j][k]){ 33 tmp=0; 34 break; 35 } 36 } 37 ans+=tmp; 38 } 39 } 40 printf("%d",ans); 41 return 0; 42 }

?

轉載于:https://www.cnblogs.com/dcdcbigbig/p/9537686.html

總結

以上是生活随笔為你收集整理的[agc016e]poor turkeys的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。