526互联

AtCoder Grand Contest 041

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

A - Table Tennis Training

如果 \(n\) 为偶数，一个 \(+1\) 一个 \(-1\) 即可。

如果 \(n\) 为奇数，那么肯定有一个先到了 \(1\) 或 \(n\)，然后再 \(+1,-1\)，取个较小值即可。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a,b;
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if(a>b) swap(a,b);
	if((b-a)%2==0) return printf("%lld",(b-a)/2),0;
	long long ans=min(a,n-b+1);
	printf("%lld",ans+(b-a-1)/2);
	return 0;
}

B - Voting Judges

可以先将 \(a_i\) 从大到小排序。可以发现，如果位置 \(x\) 为合法的，那么位置 \(1\sim x-1\) 必然也是合法的。

考虑二分，对于一个位置 \(x\)，我们需要判断它能不能出现在前 \(p\) 大的数字中。一个显然的想法是我们肯定每次都将 \(x\) 这个位置 \(+1\)，这样才能尽可能的满足条件。可以分成几种情况来讨论：

  • 当 \(x\leq p\) 时显然合法；
  • 当 \(a_x+m< a_p\) 时也不合法；
  • 剩下的情况如果合法我们只需要保证 \(a_x\) 经过了若干次操作后 \(\ge a_p\) 即可。

考虑需要将 \(m\cdot v\) 次分配到每个位置上。我们的目标是使得除了 \(1\sim p-1\) 的位置上的数，没有数经过操作后会比 \(a_x+m\) 更大，即我们需要尽可能减少 \(p\sim x-1\) 这些位置的操作次数。\(1\sim p-1\) 和 \(x+1\sim n\) 的位置显然可以随便加。剩下的位置保证每个数操作次数不超过 \(\min(m,a_x+m-a_i)\)。如果这样操作后仍有操作次数剩余，则不合法，否则合法。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,v,p;
int a[N];
bool check(int x)
{
	if(x<=p) return true;
	if(a[x]+m<a[p]) return false;
	long long ret=1LL*m*v;
	ret-=m;
	ret-=1LL*(p-1)*m+1LL*(n-(x+1)+1)*m;
	for(int i=p;i<x;i++)
		ret-=min(m,a[x]+m-a[i]);
	return ret<=0;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&v,&p);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1,greater<int>());
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

C - Domino Quality

\(n\leq 3\) 时显然无解。

可以手玩出 \(n=3,4,5,6,7\) 时的情况，可以发现除了 \(3\) 以外都有每行列的出现次数为 \(3\) 的次数，那么可以用 \(n=4\) 拼出若干块以后剩下拼 \(n=5,6,7\) 的块。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
const char s3[4][4]=
{
"aa.",
"..a",
"..a"
};
const char s4[5][5]=
{
"aabc",
"ddbc",
"efgg",
"efhh"
};
const char s5[6][6]=
{
"a.bbc",
"add.c",
"eeffg",
"hi..g",
"hi.jj"
};
const char s6[7][7]=
{
"aabbc.",
"d...ce",
"d.f..e",
"..fghh",
"ii.g.k",
".llnnk"
};
const char s7[8][8]=
{
"aabbc..",
".d..cee",
"fd...gg",
"f.h...i",
"..hjj.i",
"kklm...",
"..lmnn."
};
int n,m;
char col[N][N];
int main()
{
	scanf("%d",&n);
	if(n<=2)
	{
		printf("-1");
		return 0;
	}
	if(n==3)
	{
		for(int x=0;x<3;x++)
		{
			for(int y=0;y<3;y++)
				printf("%c",s3[x][y]);
			printf("\n");
		}
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			col[i][j]='.';
	if(n%4==0)
	{
		for(int i=1;i<=n;i+=4)
			for(int x=0;x<4;x++)
				for(int y=0;y<4;y++)
					col[i+x][i+y]=s4[x][y];
	}
	else if(n%4==1)
	{
		m=n-5;
		int i;
		for(i=1;i<=m;i+=4)
			for(int x=0;x<4;x++)
				for(int y=0;y<4;y++)
					col[i+x][i+y]=s4[x][y];
		for(int x=0;x<5;x++)
			for(int y=0;y<5;y++)
				col[i+x][i+y]=s5[x][y];
	}
	else if(n%4==2)
	{
		m=n-6;
		int i;
		for(i=1;i<=m;i+=4)
			for(int x=0;x<4;x++)
				for(int y=0;y<4;y++)
					col[i+x][i+y]=s4[x][y];
		for(int x=0;x<6;x++)
			for(int y=0;y<6;y++)
				col[i+x][i+y]=s6[x][y];
	}
	else if(n%4==3)
	{
		m=n-7;
		int i;
		for(i=1;i<=m;i+=4)
			for(int x=0;x<4;x++)
				for(int y=0;y<4;y++)
					col[i+x][i+y]=s4[x][y];
		for(int x=0;x<7;x++)
			for(int y=0;y<7;y++)
				col[i+x][i+y]=s7[x][y];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			printf("%c",col[i][j]);
		printf("\n");
	}
	return 0;
}

D - Problem Scores

考虑 \(n\) 为奇数的情况，可以发现，只要 \(k=\lfloor \frac{n-1}{2}\rfloor\) 时满足及条件即可。

因为原序列的 \(A\) 为非降序排列，则只需要使前 \(k+1\) 个数的和大于后 \(k\) 个数。

考虑将原序列差分,不妨令差分序列为 \(x\)，可以发现一个位置对答案的贡献为 \(w_i=\max(k+1-i+1,0)-\min(n-i+1,k)\)。可以发现，其中就是有 \(x_1\) 为正，其余位置均小于等于 \(0\)。

考虑计算 \(a_1\) 的取值范围。

因为 \(1\leq a_n\leq n\)，且 \(a_n=a_1+\sum\limits_{i=2}^n x_i\)，则可以得出：

\[a_1\leq n-\sum_{i=2}^nx_i \]

同理有 \(x_1+ \sum\limits_{i=2}^nw_ix_i \ge 1\)，即：

\[1-\sum\limits_{i=2}^nw_ix_i\leq a_1\leq n-\sum\limits_{i=2}^nx_i \]

可以看出 \(a_1\) 的取值有 \((n-\sum\limits_{i=2}^nx_i)-(1-\sum\limits_{i=2}^nw_ix_i)+1=n-(\sum\limits_{i=2}^nx_i-\sum\limits_{i=2}^nw_ix_i)\) 种方案。

考虑 DP 出 \(\sum\limits_{i=2}^nx_i-\sum\limits_{i=2}^nw_ix_i=\sum\limits_{i=2}^n(1-w_i)x_i\) 的方案数。这个将 \((1-w_i)\) 看做一个物品，\(x_i\) 表示选这个物品的次数，做一个完全背包就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
int n,k,P;
int w[N];
long long dp[N][N];
int main()
{
	scanf("%d%d",&n,&P);
	k=(n-1)/2;
	for(int i=1,j=1;i<=k+1;i++,j--)
		w[i]=j;
	for(int i=n,j=-1,cnt=1;cnt<=k;cnt++,i--,j--)
	{
		w[i]=j;
		if(n%2==0&&cnt==k) w[i-1]=j;
	}
	dp[1][0]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=n;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j-(1-w[i])>=0) dp[i][j]=(dp[i][j]+dp[i][j-(1-w[i])])%P;
		}
	long long ans=0;
	for(int j=0;j<=n;j++)
		ans=(ans+dp[n][j]*(n-j)%P)%P;
	printf("%lld",ans);
	return 0;
}

E - Balancing Network

对于 \(T=1\) 的情况：

考虑对于一个结束的点 \(i\)，我们需要构造一种方案使得最后所有点都到 \(i\)。考虑从右往左确定每条边的方向，用 \(vis_u\) 表示 \(u\) 最后能不能到 \(i\)。对于一条边 \((u,v)\)，如果 \(u\) 和 \(v\) 都能到达或者都不能到达就随便连边。如果一个可以到达一个不能到达就由不能到达的那一个连向可以到达的那一个。直接暴力做的话是 \(O(nm)\) 的。

可以发现，如果有多个 \(i\) 满足条件，我们只需要一个就行了。令 \(f_{i,j,k}\) 表示考虑到 \(i\) 这条边，\(j\) 能不能到达 \(k\)。考虑一条边 \((u,v)\) 的贡献，可以得出转移为：

\[f_{i-1,u,k}=f_{i-1,v,k}=f_{i,u,k}\operatorname{or} f_{i,v,k} \]

这个显然可以用 bitset 优化一波。

对于 \(T=2\) 的情况：

对于 \(n\leq 2\) 的情况显然不合法。

考虑从后往前推，对于一个位置 \(u\)，我们可以处理出它最后能到 \(to_u\)，和每个以 \(i\) 结尾的位置为 \(siz_i\)。

对于一条边 \((u,v)\)，如果 \(siz_{to_u}\ge n-1\)，需要将边定向为 \(u\to v\)；\(siz_{to_v}\ge n-1\) 时同理。

代码：

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N=50005,M=100005;
int n,m,T;
int x[M],y[M];
namespace Subtask1
{
bitset<N>f[N];
bool ans[M];
void print(int u)
{
	static bool book[N];
	book[u]=true;
	for(int i=m;i>=1;i--)
		if(!book[x[i]]) book[x[i]]=book[y[i]],ans[i]=1;
		else book[y[i]]=book[x[i]],ans[i]=0;
	for(int i=1;i<=m;i++)
		if(ans[i]) printf("v");
		else printf("^");
	return;
}
int main()
{
	for(int i=1;i<=n;i++)
		f[i][i]=true;
	for(int i=m;i>=1;i--)
		f[x[i]]=f[y[i]]=f[x[i]]|f[y[i]];
	bitset<N>res;
	for(int i=1;i<=n;i++)
		res[i]=1;
	for(int i=1;i<=n;i++)
		res&=f[i];
	if(res.count()==0) printf("-1");
	else print(res._Find_first());
	return 0;
}
}
namespace Subtask2
{
int siz[N],to[N];
bool ans[M];
int main()
{
	if(n<=2)
	{
		printf("-1");
		return 0;
	}
	for(int i=1;i<=n;i++)
		to[i]=i,siz[i]=1;
	for(int i=m;i>=1;i--)
	{
		if(siz[to[x[i]]]>=n-1)
		{
			ans[i]=1;
			swap(x[i],y[i]);
		}
		siz[to[y[i]]]--;
		to[y[i]]=to[x[i]];
		siz[to[y[i]]]++;
	}
	for(int i=1;i<=m;i++)
		if(ans[i]) printf("v");
		else printf("^");
	return 0;
}
}
int main()
{
	scanf("%d%d%d",&n,&m,&T);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]);
	if(T==1) return Subtask1::main();
	else if(T==2) return Subtask2::main();
	return 0;
}

F - Histogram Rooks

考虑从上层往下层填，可以将点分成若干类：

  • 这一列上面已经放过车了，下面可以选择放或不放；
  • 这一列上面没有放过车，且上面有某一行没有被填过；
  • 这一列上面没有放过车，且上面的每一行都被填过了；

考虑一种朴素的 DP，令 \(f_{(d,l,r),i,j}\) 表示只考虑上面 \(d\) 层，\([l,r]\) 的列，且 \(l,r\) 均不能再往外拓展了，有 \(i\) 个一类列，\(j\) 个二类列，\(r-l+1-i-j\) 个三类列的方案数。转移时需要背包合并 \(d+1\)，然后加入第 \(d\) 行的贡献，复杂度大概是 \(O(n^5)\) 的？

考虑优化 DP，可以发现，我们如果确定了后面的行中有没有一行没有填过，我们就可以将第三类和第二类合并。

令 \(f_{(d,l,r),i}\) 表示只考虑上面 \(d\) 层，\([l,r]\) 的列，且 \(l,r\) 均不能再往外拓展了，且后面的每一行都必须放，有 \(i\) 列第三类的方案数；\(g_{(d,l,r),i}\) 表示只考虑上面 \(d\) 层，\([l,r]\) 的列，且 \(l,r\) 均不能再往外拓展了，且后面的有一行没有放，有 \(i\) 列第一类的方案数。

不妨令 \(s\) 表示上一层的所有位置的长度，\(len=r-l+1,t=len-s\)。

考虑转移 \(f\)，先将 \(d+1\) 层的答案用背包合并起来，然后在考虑第 \(d\) 层的贡献，枚举上面二类列填的个数，再枚举当前层填的二类列个数，然后一三类的和第 \(d\) 层多出的可以随便填，注意要减掉都不选的时候的方案可以得出转移：

\[f_{d,i+t+s}=\sum \begin{cases}C_{s-i}^j\cdot 2^{i+t}\cdot f_{d,i} &(j> 0) \\ C_{s-i}^j\cdot (2^{i+t}-1)\cdot f_{d,i}&(j=0)\end{cases} \]

考虑转移 \(g\)，同样先将 \(d+1\) 层的答案用背包合并起来，然后在考虑第 \(d\) 层的贡献，枚举上面一类列填的个数，再枚举当前层填的一类列个数，可以得出：

\[g_{d,i+j}=\sum C_{len-i}^j\cdot 2^i \cdot g_{d,i} \]

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=405;
const int MOD=998244353;
int n;
int h[N];
long long Pw[N];
long long C[N][N];
void init(int n=400)
{
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=n;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	}
	Pw[0]=1;
	for(int i=1;i<=n;i++)
		Pw[i]=Pw[i-1]*2%MOD;
	return;
}
long long f[N][N],g[N][N];
void dfs(int d,int l,int r)
{
	static long long tmpf[N],tmpg[N];
	for(int i=0;i<=r-l+1;i++)
		f[d][i]=g[d][i]=0;
	f[d][0]=g[d][0]=1;
	int pre=l,s=0;
	for(int i=l;i<=r;i++)
		if(h[i]==d)
		{
			if(pre<=i-1)
			{
				dfs(d+1,pre,i-1);
				int len=i-1-pre+1;
				for(int j=0;j<=s;j++)
					for(int k=0;k<=len;k++)
						tmpf[j+k]=(tmpf[j+k]+f[d][j]*f[d+1][k]%MOD)%MOD;
				for(int j=0;j<=s+len;j++)
					f[d][j]=tmpf[j],tmpf[j]=0;
				for(int j=0;j<=s;j++)
					for(int k=0;k<=len;k++)
						tmpg[j+k]=(tmpg[j+k]+g[d][j]*g[d+1][k]%MOD)%MOD;
				for(int j=0;j<=s+len;j++)
					g[d][j]=tmpg[j],tmpg[j]=0;;
				s+=len;
			}
			pre=i+1;
		}
	if(pre<=r)
	{
		dfs(d+1,pre,r);
		int len=r-pre+1;
		for(int j=0;j<=s;j++)
			for(int k=0;k<=len;k++)
				tmpf[j+k]=(tmpf[j+k]+f[d][j]*f[d+1][k]%MOD)%MOD;
		for(int j=0;j<=s+len;j++)
			f[d][j]=tmpf[j],tmpf[j]=0;
		for(int j=0;j<=s;j++)
			for(int k=0;k<=len;k++)
				tmpg[j+k]=(tmpg[j+k]+g[d][j]*g[d+1][k]%MOD)%MOD;
		for(int j=0;j<=s+len;j++)
			g[d][j]=tmpg[j],tmpg[j]=0;;
		s+=len;
	}
	int len=r-l+1,t=len-s;
	for(int i=0;i<=s;i++)
	{
		for(int j=0;j<=s-i;j++)
			tmpf[i+t+j]=(tmpf[i+t+j]+C[s-i][j]*(j?Pw[i+t]:(Pw[i+t]-1))%MOD*f[d][i]%MOD)%MOD;
		tmpf[i]=(tmpf[i]+g[d][i])%MOD;
		for(int j=0;j<=len-i;j++)
			tmpg[i+j]=(tmpg[i+j]+C[len-i][j]*Pw[i]%MOD*g[d][i]%MOD)%MOD;
	}
	for(int i=0;i<=len;i++)
	{
		f[d][i]=tmpf[i],tmpf[i]=0;
		g[d][i]=tmpg[i],tmpg[i]=0;
	}
	return;
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&h[i]);
	dfs(1,1,n);
	printf("%lld",f[1][n]);
	return 0;
}