AtCoder Grand Contest 043-526互联

A - Range Flip Find Route

可以发现，一条路径的最小操作数等于路径上有多少 # 的块，令 \(f_{i,j}\) 表示到 \((i,j)\) 的最小操作次数，直接 DP 就行了。

注意路径上一个 \(1\) 的块会被算两次，需要除以 \(2\)。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int h,w;
char s[N][N];
int dp[N][N];
int main()
{
	scanf("%d%d",&h,&w);
	for(int i=1;i<=h;i++)
		scanf("%s",s[i]+1);
	memset(dp,63,sizeof(dp));
	dp[1][1]=s[1][1]=='#';
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
		{
			if(i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+(s[i-1][j]!=s[i][j]));
			if(j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+(s[i][j-1]!=s[i][j]));
		}
	printf("%d",(dp[h][w]+1)/2);
	return 0;
}

B - 123 Triangle

不妨将所有 \(a_i\) 减一，问题转化成了 \(a_i\in \{0,1,2\}\) 的问题。

先考虑 \(a_i\) 只有 \(0,1\) 的情况，\(x_{i,j} = | x_{i-1,j} - x_{i-1,j+1} | = x_{i-1,j} \operatorname{xor} x_{i-1,j+1}\)。

考虑 \(a_i\) 的贡献，问题大概就是从 \((n,i)\) 到 \((1,1)\) 的路径条数，这个就是 \(C_{n-1}^{i-1}\)，答案就是 \(\sum C_{n-1}^{i-1} [a_i=1] \mod 2\)。

考虑加入了 \(2\) 时的答案。可以分为两种情况：

如果 \(a\) 中有 \(1\)，则答案不可能是 \(2\)。因为如果某层如果所有的 \(1\) 都被消去了的话，则前一时刻必须所有位置都为 \(1\)；否则一定会有 \(1\) 留下来。
如果 \(a\) 中没有 \(1\)，则可以将所有 \(a_i=2\) 的位置转化成 \(a_i=1\) 的情况处理。

有一个结论，

\(C_n^k\bmod 2= \begin{cases} 1 (n\operatorname{and} k = k) \\ 0 \end{cases}\)

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
int n;
char s[N];
int a[N];
int cnt[3];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		a[i]=s[i]-'1';
	bool flag=false;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==1) flag=true;
		cnt[a[i]]+=(((n-1)&(i-1))==(i-1));
	}
	if(cnt[1]&1) printf("1");
	else if(!flag&&(cnt[2]&1)) printf("2");
	else printf("0");
	return 0;
}

C - Giant Graph

可以发现，最后的图肯定是一个分层图，且同层之间不会连边。

考虑一种贪心，我们肯定尽可能选层数越高的层最优。

考虑一个点 \((i,j,k)\) 是否选择，当且仅当所有层数比它高的都没有被选。可以将选看做所有后面的点都不选都是必败态，否则为非必败态，这就变成了一个组合问题。

全局的 SG 函数即为三张图分别的 SG 函数异或起来，我们需要对 \(\operatorname{SG}(x_i)\oplus \operatorname{SG}(y_j)\oplus \operatorname{SG}(z_k)=0\) 的合法 \(i,j,k\) 进行计数即可。

可以发现，每张图的 SG 函数最大不超过 \(\sqrt m\)，直接暴力枚举前两个的 SG 函数的值，得出第三个的 SG 函数的值即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
const int MOD=998244353;
int n,m;
long long ksm(long long a,long long b)
{
	a%=MOD,b%=(MOD-1);
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
vector<int>G[N];
int sg[N];
int dfs(int u)
{
	if(sg[u]!=-1) return sg[u];
	static int vis[N];
	for(int v:G[u])
	{
		dfs(v);
		vis[sg[v]]=true;
	}
	for(int i=0;;i++)
		if(!vis[i])
		{
			sg[u]=i;
			break;
		}
	for(int v:G[u])
		vis[sg[v]]=false;
	return sg[u];
}
vector<long long> getsg()
{
	for(int i=1;i<=n;i++)
		G[i].clear();
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		G[x].push_back(y);
	}
	memset(sg,-1,sizeof(sg));
	for(int i=n;i>=1;i--)
		dfs(i);
	int Max=*max_element(sg+1,sg+n+1);
	vector<long long>res;
	res.resize(Max+1);
	for(int i=1;i<=n;i++)
		res[sg[i]]=(res[sg[i]]+ksm(1e18,i))%MOD;
	return res;
}
int main()
{
	scanf("%d",&n);
	vector<long long>x=getsg(),y=getsg(),z=getsg();
	long long ans=0;
	for(int i=0;i<x.size();i++)
		for(int j=0;j<y.size();j++)
		{
			int k=i^j;
			if(k>=z.size()) continue;
			ans=(ans+x[i]*y[j]%MOD*z[k]%MOD)%MOD;
		}
	printf("%lld",ans);
	return 0;
}

D - Merge Triplets

考虑将一个块 \(A_i\)，如果 \(A_{i,j}\ge A_{i,j+1}\) 的话，我们就可以将这两个合并成一个块，三个数也可以合并。将这几个数分成一个组，可以发现，排列 \(P\) 就是若干个组按照组内的最大值排序的结果。

考虑合法的 \(P\) 需要满足的条件：

每个组的大小不超过 \(3\)；
每个组拼起来可以组成 \(n\) 个三元组（即为将大小为 \(1,2,3\) 的组的值分别设为 \(1,-1,0\)，那么要求权值和大于等于 \(0\) 且为 \(3\) 的倍数）。

然后就可以 DP 了，令 \(f_{i,j,k}\) 表示当前插入第 \(i\) 个数，当前组的大小为 \(j\)，权值和为 \(k\) 的方案数。当前数有两种方案，插入当前组或者新开一组，转移即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2005,M=6000;
int n,P;
int f[N*3][3][N*6];
int main()
{
	scanf("%d%d",&n,&P);
	n*=3;
	f[1][0][0+M]=1;
	for(int i=1;i<n;i++)
		for(int j=0;j<=2;j++)
			for(int k=-i;k<=i;k++)
			{
				if(j<=1) f[i+1][j+1][k+M]=(f[i+1][j+1][k+M]+1LL*f[i][j][k+M]*i%P)%P;
				if(j==0) f[i+1][0][k+1+M]=(f[i+1][0][k+1+M]+f[i][j][k+M])%P;
				else if(j==1) f[i+1][0][k-1+M]=(f[i+1][0][k-1+M]+f[i][j][k+M])%P;
				else if(j==2) f[i+1][0][k+M]=(f[i+1][0][k+M]+f[i][j][k+M])%P;
			}
	int ans=0;
	for(int k=0;k<=n;k+=3)
		ans=(ans+((long long)f[n][0][k-1+M]+f[n][1][k+1+M]+f[n][2][k+M])%P)%P;
	printf("%d",ans);
	return 0;
}

E - Topology

考虑一条绳子向一个方向前进，如果经过一个点的下面记录一个 \(d_i\)，经过一个点的上面记录一个 \(u_i\)。最后会得到一个序列，不断地在序列中删去相邻的相同元素，如果原序列能被删完，则该点集合法，否则非法。

可以发现，一个合法点集的所有子集都应该合法，且空集必须合法，可以判掉这些情况。

接下来就可以构造了。对于一个非法集合 \(S\)，且它的所有真子集均为合法的，考虑对于每种这种情况构造。

考虑一种构造方法：

如果当前点到了最右边，只需要绕一圈就好了。
如果当前点右边得出了一个操作序列 \(S\)，为了能使删除这个点以后合法，先从上面穿过去，记录一个 \(u_i\)，加上一个 \(S\)，然后在从上面穿回来记录一个 \(u_i\)；再从上面穿过去，记录一个 \(d_i\)，记录一个 \(S\) 的逆序操作序列，然后在从上面穿回来记录一个 \(u_i\)。

这样显然是合法的，且任意删除一个点得出的序列都是可以被删完也就是合法的。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1<<10;
int n;
char s[N];
int p[N];
vector<pair<int,int> > solve(int S,int now)
{
	vector<pair<int,int> >res;
	for(int i=now+1;i<n;i++)
		if(S&(1<<i))
		{
			vector<pair<int,int> > t=solve(S,i);
			for(int j=now;j<=i-1;j++)
				res.push_back(make_pair(j,1));
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int j=i;j>=now;j--)
				res.push_back(make_pair(j,1));
			res.push_back(make_pair(now,0));
			res.push_back(make_pair(now+1,0));
			for(int j=now+1;j<=i;j++)
				res.push_back(make_pair(j,1));
			reverse(t.begin(),t.end());
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int j=i-1;j>=now+1;j--)
				res.push_back(make_pair(j,1));
			res.push_back(make_pair(now+1,0));
			res.push_back(make_pair(now,0));
			return res;
		}
	res.push_back(make_pair(now,1));
	res.push_back(make_pair(now+1,1)); 
	res.push_back(make_pair(now+1,0));
	res.push_back(make_pair(now,0));
	return res;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<(1<<n);i++)
		p[i]=s[i]-'0';
	if(p[0]==0)
	{
		printf("Impossible");
		return 0;
	}
	for(int s=0;s<(1<<n);s++)
		if(p[s]==1)
			for(int i=s;i;i=(i-1)&s)
				if(p[i]==0)
				{
					printf("Impossible");
					return 0;
				}
	vector<pair<int,int> >ans;
	ans.push_back(make_pair(0,0));
	for(int s=1;s<(1<<n);s++)
		if(p[s]==0)
		{
			bool flag=true;
			for(int i=(s-1)&s;i;i=(i-1)&s)
				if(p[i]==0)
				{
					flag=false;
					break;
				}
			if(!flag) continue;
			vector<pair<int,int> >res;
			vector<pair<int,int> >t;
			int u=0;
			for(u=0;u<n;u++)
				if(s&(1<<u))
				{
					t=solve(s,u);
					break;
				}
			if(ans.back()!=make_pair(0,0)) res.push_back(make_pair(0,0));
			for(int i=0;i<=u-1;i++)
				res.push_back(make_pair(i,1));
			for(auto [x,y]:t)
				res.push_back(make_pair(x,y));
			for(int i=u;i>=0;i--)
				res.push_back(make_pair(i,1));
			res.push_back(make_pair(0,0));
			for(auto [x,y]:res)
				ans.push_back(make_pair(x,y));
		}
	printf("Possible\n");
	int len=ans.size()-1;
	printf("%d\n",len);
	for(auto [x,y]:ans)
		printf("%d %d\n",x,y);
	return 0;
}

F - Jewelry Box

挖坑待填。

atcoder contest grand 043

authentic atcoder contest grand

negative atcoder contest grand

atcoder contest radius grand

atcoder contest grand 022

atcoder contest grand 001

histogram atcoder contest grand

atcoder contest grand 019

atcoder contest grand 017

atcoder contest grand 039