526互联

AtCoder Grand Contest 039

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - Connection and Disconnection

对于连续的一段连续的长度为 \(L\) 的段，至少需要 \(\frac{L}{2}\) 次操作。判下头尾相等的情况，实现时注意细节即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=205;
int n,k;
char s[N];
vector<int>len;
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%d",&k);
	for(int i=1,j=1;i<=n;i=j)
	{
		j=i;
		while(j<=n&&s[i]==s[j]) j++;
		len.push_back(j-i);
	}
	if(k==1)
	{
		int res=0;
		for(int L:len)
			res+=L/2;
		printf("%d",res);
		return 0;
	}
	if(s[1]==s[n])
	{
		int l=len.front(),r=len.back();
		if(len.size()==1)
		{
			long long ans=1LL*n*k/2;
			printf("%lld",ans);
			return 0;
		}
		len.erase(len.begin());
		len.pop_back();
		len.push_back(l+r);
		int res=0;
		for(int L:len)
			res+=L/2;
		long long ans=0;
		if(k>=2) ans+=1LL*res*(k-2);
		len.pop_back();
		len.insert(len.begin(),l);
		for(int L:len)
			ans+=L/2;
		len.erase(len.begin());
		len.push_back(l+r);
		len.push_back(r);
		for(int L:len)
			ans+=L/2;
		printf("%lld",ans);
		return 0;
	}
	int res=0;
	for(int L:len)
		res+=L/2;
	long long ans=1LL*res*k;
	printf("%lld",ans);
	return 0;
}

B - Graph Partition

如果原图不是二分图显然不合法，合法的情况的最大值即为图上两点最短路的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=205;
int n;
int a[N][N];
int col[N];
void dfs(int u,int color)
{
	if(col[u]!=-1)
	{
		if(col[u]!=color)
		{
			printf("-1");
			exit(0);
		}
		return;
	}
	col[u]=color;
	for(int v=1;v<=n;v++)
		if(a[u][v]) dfs(v,color^1);
	return;
}
int f[N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%1d",&a[i][j]);
	memset(col,-1,sizeof(col));
	dfs(1,0);
	memset(f,63,sizeof(f));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]) f[i][j]=a[i][j];
	for(int i=1;i<=n;i++)
		f[i][i]=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ans=max(ans,f[i][j]+1);
	printf("%d",ans);
	return 0;
}

C - Division by Two with Something

考虑操作等价于将最低位取反然后再放到最高位，考虑一个二进制数 \(a\) 是否合法。考虑将 \(a\) 取反后在 \(a\) 后面再放一份，令这个数为 \(b\)。

则问题转化成了每次将 \(b\) 的最低位放到最高位，问 \(b\) 的最小循环节是多少。令其为 \(T\)，显然 \(T\mid 2n\)。可以发现，\(T\mid n\) 的时候，\(b\) 的前 \(n\) 位和后 \(n\) 位为相等的情况，这与 \(b\) 的构造条件相矛盾，故不合法。可以证明，当 \(T\mid 2n\) 且 \(T\nmid 2n\) 时显然可以构造出方案。

考虑 \([0,X]\) 的限制，可以发现，对于前 \(T\) 位，令 \(X\) 的前 \(T\) 位位 \(x\)，我们最多有 \(x+1\) 种方案，我们只要确定了前 \(T\) 位的方案，剩余的位置也就确定了。只有当 \(b\) 的前 \(T\) 位与 \(x\) 相等的情况可能会不合法，将此时的 \(b\) 构造出来，判一下是否合法，如果不合法减掉这种方案即可。

还有要注意的是，对于 \(a|b\)，我们在算 \(T=b\) 的方案时同时也会将 \(T=a\) 的方案算上，容斥一下即可。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=200005;
const int MOD=998244353;
int n;
int a[N];
long long solve(int T)
{
	static int p[N],q[N];
	for(int i=1;i<=T/2;i++)
		p[i]=a[i],q[i]=a[i]^1;
	static int b[N];
	for(int i=1;i<=n*2;)
	{
		for(int j=1;j<=T/2;j++)
			b[i+j-1]=p[j];
		i+=T/2;
		for(int j=1;j<=T/2;j++)
			b[i+j-1]=q[j];
		i+=T/2;
	}
	long long ans=0;
	for(int i=1;i<=T/2;i++)
		ans=(ans*2+a[i])%MOD;
	ans=(ans+1)%MOD;
	for(int i=1;i<=n;i++)
		if(b[i]<a[i]) break;
		else if(b[i]>a[i])
		{
			ans=(ans-1+MOD)%MOD;
			break;
		}
	return ans;
}
long long f[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%1d",&a[i]);
	for(int i=1;i<=n*2;i++)
		if(n*2%i==0&&n%i!=0) f[i]=solve(i);
	for(int i=1;i<=n*2;i++)
		if(n*2%i==0&&n%i!=0)
			for(int j=i+i;j<=n*2;j+=i)
				if(n*2%j==0&&n%j!=0) f[j]=(f[j]-f[i]+MOD)%MOD;
	long long ans=0;
	for(int i=1;i<=n*2;i++)
		if(n*2%i==0&&n%i!=0) ans=(ans+f[i]*i%MOD)%MOD;
	printf("%lld",ans);
	return 0;
}

D - Incenters

这是什么屑题？？？

可以发现，对于 \(\triangle ABC\)，它的内接圆圆心坐标即为三段弧中点的坐标之和，然后瞎 jb 算即可。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=3005;
const double PI=acos(-1);
int n,L;
double t[N];
int main()
{
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++)
		scanf("%lf",&t[i]);
	double ansx=0,ansy=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
	    {
			int cnt=j-i-1;
			ansx+=cos((t[i]+t[j])/L*PI)*(n-2*cnt-2),ansy+=sin((t[i]+t[j])/L*PI)*(n-2*cnt-2);
		}
	ansx/=1LL*n*(n-1)*(n-2)/6,ansy/=1LL*n*(n-1)*(n-2)/6;
	printf("%.15lf %.15lf",ansx,ansy);
	return 0;
}

E - Pairing Points

枚举与 \(1\) 相连的点 \(i\)，环断成了 \(2\sim i-1\) 和 \(i+1\sim 2n\) 两部分。

枚举最上面跨过 \(i\) 的边 \((x,y)\)，且 \(x,y\) 上面不能有跨过 \(i\) 的边，再枚举 \(p,q\) 表示当前的 \([l,p]\) 是只有一条 \((x,y)\) 是连向外面的，\(q\) 同理。那么就转化成了三个子问题，令 \(f_{l,i,r}\) 表示 \([l,r]\) \(i\) 向外面连边，剩余的点只有在区间内连边，转移枚举 \(x,y,p,q\) 转移即可。

直接转移是 \(O(n^7)\) 的，可以用一些神必技巧做到 \(O(n^5)\)。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=45;
int n;
int a[N][N];
long long dp[N][N][N];
long long dfs(int l,int i,int r)
{
	if(dp[l][i][r]!=-1) return dp[l][i][r];
	if(l==r) return 1;
	if(l==i||i==r) return 0;
	long long res=0;
	for(int j=l;j<i;j++)
		for(int k=i+1;k<=r;k++)
			if(a[j][k])
				for(int p=j;p<i;p++)
					for(int q=i+1;q<=k;q++)
						res+=dfs(l,j,p)*dfs(p+1,i,q-1)*dfs(q,k,r);
	return dp[l][i][r]=res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n*2;i++)
		for(int j=1;j<=n*2;j++)
			scanf("%1d",&a[i][j]);
	memset(dp,-1,sizeof(dp));
	long long ans=0;
	for(int i=2;i<=n*2;i++)
		if(a[1][i]) ans+=dfs(2,i,2*n);
	printf("%lld",ans);
	return 0;
}

F - Min Product Sum

考虑如果每行每列的最小值确定了，令 \(x_i=\min\limits_{j=1}^m\{a_{i,j}\}\)，\(y_j=\min\limits_{i=1}^n\{a_{i,j}\}\)，则答案为 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m \min(x_i,y_j)\)。

考虑快速计算这个。将 \(x_i,y_j\) 从大到小排序，按照大小顺序依次加入 \(x_i,y_j\)。不妨令当前加入了 \(i\) 行 \(j\) 列，当前加入的数为 \(k\)，则当前加入一行的贡献为 \(k^j\)，加入一列的贡献为 \(k^i\)。注意这里的 \(x,y\) 是有序的，为了能够使用组合数计算方案数，我们需要每次将相等的一起加入。

考虑枚举 \(x,y\)，从小到大 DP，计算方案数。但是我们会发现，这个东西算出的方案所对应的 \(x',y'\) 可能比 \(x,y\) 要大，这不满足我们的条件。

考虑去计算 \(a\) 的 \(x',y'\) 大于等于 \(x, y\) 的方案数，也就是对于 \(A_{i,j}\)，它的取值范围为 \(\max(x_i,y_j)\sim K\) 的方案数。

考虑容斥，我们称某些行选表示强制这行大于 \(x\)，称某些列选表示强制这列大于 \(y\)。如果我们选了 \(c\) 行 \(d\) 列，算就是至少有 \(c\) 行 \(d\) 列不合法的方案数，容斥系数为 \((-1)^{c+d}\)。

令 \(f_{k,i,j}\) 表示当前加入了 \(1\sim k\) 的数，填了 \(i\) 行 \(j\) 列的方案数。

转移时分成四种情况：

  • 加入 \(a\) 行不被选的：

\[f_{k,i,j} \cdot C_{n - i}^a \cdot k^{a\cdot (m - j)} \cdot {(K - k + 1)}^{a\cdot j} \to {f_{k,i + a,j}} \]

  • 加入 \(b\) 行不被选的：

\[f_{k,i,j} \cdot C_{m - j}^b \cdot k^{b\cdot (n - i)} \cdot {(K - k + 1)}^{b\cdot i} \to {f_{k,i,j+b}} \]

  • 加入 \(c\) 行被选的：

\[(-1)^c \cdot f_{k,i,j} \cdot C_{n - i}^c \cdot k^{c\cdot (m - j)} \cdot {(K - k)}^{c\cdot j} \to {f_{k,i + c,j}} \]

  • 加入 \(d\) 行被选的：

\[(-1)^d \cdot f_{k,i,j} \cdot C_{m - j}^d \cdot k^{d\cdot (n - i)} \cdot {(K - k)}^{d\cdot i} \to {f_{k,i,j+d}} \]

直接实现可能会被卡常，需要一些神必卡常技巧。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int n,m,K;
int P;
int C[N][N];
int Pw[N][N*N];
int add(const int &x,const int &y)
{
	int t=x+y;
	if(t>=P) t-=P;
	return t;
}
int sub(const int &x,const int &y)
{
	int t=x-y;
	if(t<=0) t+=P;
	return t;
}
void init(int n=100)
{
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=add(C[i-1][j],C[i-1][j-1]);
	}
	for(int i=0;i<=n;i++)
	{
		Pw[i][0]=1;
		for(int j=1;j<=n*n;j++)
			Pw[i][j]=1LL*Pw[i][j-1]*i%P;
	}
	return;
}
int f[2][N][N];
int cur;
int main()
{
	scanf("%d%d%d",&n,&m,&K);
	scanf("%d",&P);
	init();
	int cur=0;
	f[0][0][0]=1;
	for(int k=1;k<=K;k++)
	{
		cur^=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(f[cur^1][i][j])
				{
					int pw=1LL*Pw[k][m-j]*Pw[K-k+1][j]%P,fac=f[cur^1][i][j];
					for(int a=0;i+a<=n;a++)
					{
						int res=1LL*C[n-i][a]*fac%P;
						f[cur][i+a][j]=add(f[cur][i+a][j],res);
						fac=1LL*fac*pw%P;
					}
				}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				f[cur^1][i][j]=0;
		cur^=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(f[cur^1][i][j])
				{
					int pw=1LL*Pw[k][n-i]*Pw[K-k+1][i]%P,fac=f[cur^1][i][j];
					for(int b=0;j+b<=m;b++)
					{
						int res=1LL*C[m-j][b]*fac%P;
						f[cur][i][j+b]=add(f[cur][i][j+b],res);
						fac=1LL*fac*pw%P;
					}
				}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				f[cur^1][i][j]=0;
		cur^=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(f[cur^1][i][j])
				{
					int pw=1LL*Pw[k][m-j]*Pw[K-k][j]%P,fac=f[cur^1][i][j];
					for(int c=0;i+c<=n;c++)
					{
						int res=1LL*C[n-i][c]*fac%P;
						if(c&1) f[cur][i+c][j]=sub(f[cur][i+c][j],res);
						else f[cur][i+c][j]=add(f[cur][i+c][j],res);
						fac=1LL*fac*pw%P;
					}
				}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				f[cur^1][i][j]=0;
		cur^=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				if(f[cur^1][i][j])
				{
					int pw=1LL*Pw[k][n-i]*Pw[K-k][i]%P,fac=f[cur^1][i][j];
					for(int d=0;j+d<=m;d++)
					{
						int res=1LL*C[m-j][d]*fac%P;
						if(d&1) f[cur][i][j+d]=sub(f[cur][i][j+d],res);
						else f[cur][i][j+d]=add(f[cur][i][j+d],res);
						fac=1LL*fac*pw%P;
					}
				}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++)
				f[cur^1][i][j]=0;
	}
	printf("%d",f[cur][n][m]);
	return 0;
}