526互联

AtCoder Grand Contest 030

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

A - Poisonous Cookies

解毒的饼干肯定所有都吃，剩下的算一下最多能吃多少毒饼干就好了。

#include<iostream>
#include<cstdio>
using namespace std;
int A,B,C;
int main()
{
	scanf("%d%d%d",&A,&B,&C);
	printf("%d",min(A+B+1,C)+B);
	return 0;
}

B - Tree Burning

可以发现最后的策略一定是先向一个方向走到某个位置，然后在反复横跳，枚举到了那里取个最小值即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int L,n;
long long a[N];
long long sp[N];
long long sn[N];
long long calc1(int k)
{
	if((n-k+1)%2==0) return a[k]+(sn[k+(n-k+1)/2]*2-(L-a[k+(n-k+1)/2]))+(sp[k+(n-k+1)/2-1]-sp[k]-a[k]*(k+(n-k+1)/2-1-k))*2+a[k]*(n-k);
	else return a[k]+(sn[k+(n-k+1+1)/2]*2)+((sp[k+(n-k+1+1)/2-1]-sp[k]-a[k]*(k+(n-k+1+1)/2-1-k))*2-(a[k+(n-k+1+1)/2-1]-a[k]))+a[k]*(n-k);
}
long long calc2(int k)
{
	if(k%2==0) return (L-a[k])+(sp[k/2]*2-a[k/2])+(sn[k/2+1]-sn[k]-(L-a[k])*(k-(k/2+1)))*2+(L-a[k])*(k-1);
	else return (L-a[k])+(sp[k/2]*2)+((sn[k/2+1]-sn[k]-(L-a[k])*(k-(k/2+1)))*2-(a[k]-a[k/2+1]))+(L-a[k])*(k-1);
}
int main()
{
	scanf("%d%d",&L,&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		sp[i]=sp[i-1]+a[i];
	for(int i=n;i>=1;i--)
		sn[i]=sn[i+1]+(L-a[i]);
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,calc1(i));
	for(int i=1;i<=n;i++)
		ans=max(ans,calc2(i));
	printf("%lld",ans);
	return 0;
}

C - Coloring Torus

首先有一个想法，就是对于斜着的填同一个颜色，即在 \((i,j)\) 填 \((i+j)\bmod k+1\)，但是这样 \(n\) 还是与 \(k\) 同级。可以对于同一斜线上的奇数行加上 \(n\)，这样就可以将 \(n\) 缩小一倍。

#include<iostream>
#include<cstdio>
using namespace std;
int k;
int n;
int main()
{
	scanf("%d",&k);
	if(k==1)
	{
		printf("1\n");
		printf("1");
		return 0;
	}
	n=(k+3)/4*2;
	printf("%d\n",n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int v=(i+j)%n+1;
			if(i&1) v+=n;
			if(v>k) v-=n;
			printf("%d ",v);
		}
		printf("\n");
	}
	return 0;
}

D - Inversion Sum

首先有一个非常简单的 DP，令 \(f_{i,j,k}\) 表示考虑前 \(i\) 个操作的 \(2^i\) 种情况，\(a_j> a_k\) 的个数。转移非常简单，时间复杂度 \(O(qn^2)\)，无法通过。

可以发现，每次只有跟 \(x_i,y_i\) 有关的状态会被转移，其他都是乘二的形式。可以把状态中的个数改成概率，最后再乘上 \(O(2^Q)\)。这样转移就是 \(O(n)\) 的了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=3005;
const int MOD=1000000007;
int n,Q;
int a[N];
int x[N],y[N];
long long f[N][N];
long long g[N][N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long Pw[N];
void init(int n=3000)
{
	Pw[0]=1;
	for(int i=1;i<=n;i++)
		Pw[i]=Pw[i-1]*2%MOD;
	return;
}
int main()
{
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=Q;i++)
		scanf("%d%d",&x[i],&y[i]);
	init();
	long long inv2=ksm(2,MOD-2);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i]>a[j]) f[i][j]=1;
	for(int i=1;i<=Q;i++)
	{
		for(int j=1;j<=n;j++)
			g[x[i]][j]=f[x[i]][j],g[j][x[i]]=f[j][x[i]],g[y[i]][j]=f[y[i]][j],g[j][y[i]]=f[j][y[i]];
		for(int j=1;j<=n;j++)
			if(j!=x[i]&&j!=y[i])
			{
				f[x[i]][j]=(f[x[i]][j]*inv2%MOD+g[y[i]][j]*inv2%MOD)%MOD;
				f[j][x[i]]=(f[j][x[i]]*inv2%MOD+g[j][y[i]]*inv2%MOD)%MOD;
				f[y[i]][j]=(f[y[i]][j]*inv2%MOD+g[x[i]][j]*inv2%MOD)%MOD;
				f[j][y[i]]=(f[j][y[i]]*inv2%MOD+g[j][x[i]]*inv2%MOD)%MOD;
			}
		f[x[i]][y[i]]=(f[x[i]][y[i]]*inv2%MOD+g[y[i]][x[i]]*inv2%MOD)%MOD;
		f[y[i]][x[i]]=(f[y[i]][x[i]]*inv2%MOD+g[x[i]][y[i]]*inv2%MOD)%MOD;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			ans=(ans+Pw[Q]*f[i][j]%MOD)%MOD;
	printf("%lld",ans);
	return 0;
}

E - Less than 3

有一个神仙转化，在 \(01\) 划一道红线，\(10\) 之间划一道蓝线，起点和重点可以发现每次操作就是移动某条线一格，且移动时不能跨过线，红蓝线之间的距离要 \(\le 2\)。序列相同当且仅当两者的红蓝线位置相同。

可以证明，两种红蓝线位置序列之间的最少操作次数即为两者各个位置之差的绝对值之和。

那么就可以枚举 \(s\) 前面选的线的个数计算一下，枚举 \(t\) 前面选的个数计算一下就好了取个最小值。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
const int INF=1061109567;
int n;
char s[N],t[N];
int a[N],b[N];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	scanf("%s",t+1);
	int tota=0,totb=0;
	for(int i=1;i<n;i++)
		if(s[i]!=s[i+1]) a[++tota]=i;
	for(int i=1;i<n;i++)
		if(t[i]!=t[i+1]) b[++totb]=i;
	int ans=INF;
	for(int i=-tota-1;i<=totb+1;i++)
		if((i&1)^(s[1]==t[1]))
		{
			int res=0;
			for(int j=min(1,1-i);j<=max(tota,totb-i);j++)
				res+=abs(((j<0)?0:((j>tota)?n:a[j]))-((j+i<0)?0:((j+i>totb)?n:b[j+i])));
			ans=min(ans,res);
		}
	printf("%d",ans);
	return 0;
}

F - Permutation and Minimum

从大到小填入每个数，每对的权值即为后填入的那个数的权值。

对于两个数都确定的对，我们可以直接跳过。剩下的就是 \((-1,x)\) 和 \((-1,-1)\) 的对。

那么就可以 DP 了，令 \(f_{i,j,k}\) 表示考虑前 \(i\) 对，有 \(j\) 个数还需要数与它配对，\(k\) 对还有一个数没填的 \((-1,x)\) 对。

考虑转移。

如果当前数为 \((-1,x)\) 中的 \(x\)，要么拉一个填了一个数的 \((-1,-1)\) 的对与它配对，要么到后面去配对。

如果当前数在原序列中为 \(-1\)，要么与前面的数配对到 \((-1,-1)\) 的对，要么填入前面的 \((-1,x)\) 的对，要么到后面配对。

直接转移就是 \(O(n^3)\) 的。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
const int MOD=1000000007;
int n;
int a[N+N];
bool vis[N+N],book[N+N];
int b[N+N],m;
long long f[N+N][N+N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n+n;i++)
		scanf("%d",&a[i]);
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++)
		if(a[2*i-1]==-1&&a[2*i]==-1) cnt1++;
		else if(a[2*i-1]==-1&&a[2*i]!=-1) cnt2++,book[a[2*i]]=true;
		else if(a[2*i-1]!=-1&&a[2*i]==-1) cnt2++,book[a[2*i-1]]=true;
		else if(a[2*i-1]!=-1&&a[2*i]!=-1) vis[a[2*i-1]]=vis[a[2*i]]=true;
	for(int i=n+n;i>=1;i--)
		if(!vis[i]) b[++m]=i;
	f[0][0][0]=1;
	for(int i=1;i<=m;i++)
		for(int j=0;j<=cnt1+cnt2;j++)
			for(int k=0;k<=cnt2;k++)
				if(f[i-1][j][k])
				{
					if(book[b[i]])
					{
						f[i][j][k+1]=(f[i][j][k+1]+f[i-1][j][k])%MOD;
						if(j-1>=0) f[i][j-1][k]=(f[i][j-1][k]+f[i-1][j][k])%MOD;
					}
					else
					{
						f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k])%MOD;
						if(j-1>=0) f[i][j-1][k]=(f[i][j-1][k]+f[i-1][j][k])%MOD;
						if(k-1>=0) f[i][j][k-1]=(f[i][j][k-1]+f[i-1][j][k]*k%MOD)%MOD;
					}
				}
	long long ans=f[m][0][0];
	for(int i=1;i<=cnt1;i++)
		ans=ans*i%MOD;
	printf("%lld",ans);
	return 0;
}