ARC 205 div.2

AtCoder Regular Contest 205 (Div. 2)

时隔四年再一次捡起来OI，想复健发现已经半身不遂了

A - 2x2 Erasing

看了一会发现是二维DP，放一下核心代码

	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			if(c=='#'){
				a[i][j]=1;
			}
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=2;j<=n;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			if(a[i][j]==0&&a[i-1][j]==0&&a[i][j-1]==0&&a[i-1][j-1]==0){
				dp[i][j]++;
			}
		}
	}
	while(q--){
		int u,d,l,r;
		cin>>u>>d>>l>>r;
		int ans=dp[d][r]-dp[d][l]-dp[u][r]+dp[u][l];
		cout<<ans<<"\n";
	}

B - Triangle Toggle

是图论，但是看了半天加边会对答案产生什么影响，用并查集考虑加边的两个点之间的关系什么的

最后发现要考虑每个点的 度 ，在进行操作的时候与点相邻黑色边的度的奇偶性保持不变

于是先考虑假如全涂黑能够有

\[\frac{N \times (N - 1)}{2}\]

条边，而每个点的黑边的度其奇偶性要和 $N-1$ 保持一致，即

\[N-1 \equiv d_i \pmod{2}\]

同时记录不满足上述条件的点，当然每两个点才会贡献一条边所以对答案的影响要除以 $2$

	int n,m;
	long long ans=0;
	cin>>n>>m;
	ans=(long long)n*((long long)n - 1)/2;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		deg[u]++;
		deg[v]++;
	}
	int p=(n-1)%2;
	long long k=0;
	for(int i=1;i<=n;i++){
		if((deg[i]%2)!=p){
			k++;
		}
	}
	ans=ans-(k/2);
	cout<<ans;

C - No Collision Moves

虽然没写出来，但是有大致思路（

为了避免冲突，我们要根据节点顺序构建约束图，如果某个人移动区间完全在另一个人内则没有合法结果，一个人的起点在另一个人的移动范围内则从这个人向另一个人连单向边，终点则反之。然后从入度为 $0$ 的点开始 BFS 输出点序就可以了。 自然如果没有入度为0的点则不存在合法结果。

关键在于构建约束图，因为 $N \leq 2 \times 10^5 $ 所以显然每个节点去朴素查找的 $O(n^2)$ 时间复杂度是不行的，可以考虑使用排序+二分查找或者是线段树等数据结构将每次查找的时间复杂度变为 $O(\log n)$ 这样总复杂度变成 $O(n \log n)$ 就应该能过