526互联

Atcoder Grand Contest 016 E - Poor Turkeys

发布时间 2023-10-10 22:17:36作者: tzc_wk

先思考这样一个问题：对于一只火鸡 \(i\)，我们应该如何判断它最后是否能活下来。如果我们正着判断，我们其实并没有足够的证据表明每一次操作我们应该保留哪只火鸡，也就没法判断最终的答案。但是如果我们倒着考虑，我们发现，如果最后一次操作的两个火鸡都不是 \(i\)，那么这次操作选啥对答案没有影响，而如果最后一次操作包含 \(i\)，那么假设最后一次操作中 \(i\) 之外的那只火鸡为 \(j\)，那么在前 \(n-1\) 次操作中，\(j\) 也是要被保留的，这样我们才能将它留到最后一次操作把它杀了，否则最后一次操作杀的就是 \(i\)。同理考虑倒数第二次操作，如果可选对象恰好是 \(i,j\) 两只火鸡，那么 \(i,j\) 必然挂一个，我们就寄了。否则如果 \(i,j\) 在这次操作中都不存在，那么这次操作的结果对最终 \(i\) 的状态没有影响。否则 \(i\)（或者 \(j\)）之外的那只火鸡在前 \(n-2\) 次操作中也要被保留。这样我们可以归纳出这样一个判断 \(i\) 是否能被保留的算法：

从后到前考虑所有操作，并维护一个集合 \(S\)，初始 \(S=\{i\}\)，对于每次操作而言，如果 \(a_k,b_k\) 都在 \(S\) 中就 GG 了，否则如果 \(a_k,b_k\) 恰好一个属于 \(S\)，则向 \(S\) 中加入另一个，否则忽略这次操作。如果能顺利遍历所有操作则说明最后 \(i\) 能活下来。

同时结合上面的分析我们也可以知道，如果 \(i\) 可以活下来，那么对应的 \(S\) 中除了 \(i\) 之外的元素也是在保留 \(i\) 的过程中必须干掉的那些火鸡。

接下来考虑怎么判断两个火鸡 \(i,j\) 能不能同时活下来，结论是，如果 \(S_i\cap S_j=\varnothing\)，那么 \(i,j\) 可以同时活着。因为显然如果 \(S_i\cap S_j=\varnothing\)，那么这俩火鸡的保留过程互不干扰。否则如果某一个火鸡 \(k\) 满足 \(k\in S_i,k\in S_j\) 且 \(k\) 在两个火鸡的保留过程中死亡的时间不一样，说明这是不可能的，否则我们假设 \(k\) 是所有这样的火鸡中死亡时间最晚的，那么假设其死亡时间为 \(t\)，那么我们发现 \(a_t,b_t\) 中不同于 \(k\) 的那一者 \(k'\) 也满足 \(k'\in S_i,k'\in S_j\)，且其死亡时间更晚，矛盾。

这样判断是容易的，时间复杂度 \(O(n^3+nm)\)。

const int MAXN=400;
const int MAXM=1e5;
int n,m,a[MAXM+5],b[MAXM+5],res;
bitset<MAXN+5>c[MAXN+5];bool die[MAXN+5];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		c[i].set(i);
		for(int j=m;j;j--){
			if(c[i][a[j]]&&c[i][b[j]]){die[i]=1;break;}
			else if(c[i][a[j]]&&!c[i][b[j]])c[i][b[j]]=1;
			else if(!c[i][a[j]]&&c[i][b[j]])c[i][a[j]]=1;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<i;j++)res+=(!die[i]&&!die[j]&&!(c[i]&c[j]).count());
	printf("%d\n",res);
	return 0;
}