题解

cookiebus 2023-09-21 9:25:57 11 返回题目

暴力1

如果你啥都不知道,你可以列方程组,然后高斯消元,可以拿80分(特别良心)。

暴力2

如果你连高斯消元都不会写,那么前10分你可以手玩一下,接下来的20分,你可以枚举每个位置的结果,然后check一下。

正解

考虑如果你知道结果了,怎么正着推出结果,本质上是一个高维前缀和。

for (int i=0;i<=n-1;i++) //一共n位
	for (int sta=0;sta<tot;sta++)
	if (a[sta][i]==0) //这一位上是0的拎出来单独处理 
	{
		for (int j=0;j<k;j++) f[j]=sum[sta+j*pw[i]];
		for (int j=0;j<k;j++)
		{
			g[j]=f[j];
			if (j-1>=0) g[j]+=f[j-1];
			if (j+1<k) g[j]+=f[j+1];
		}
		for (int j=0;j<k;j++) sum[sta+j*pw[i]]=g[j];
	} 

那么既然能正着过去,我们就可以倒着恢复回来。

每次就是解方程罢了,的时候解不唯一,所以造数据的时候跳过了。

void antiTO()
{
	int f[10],g[10];
	memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
	for (int i=0;i<tot;i++) cin>>sum[i];
	
	for (int i=n-1;i>=0;i--) //注意这里是倒着恢复的
	for (int sta=0;sta<tot;sta++)
	if (a[sta][i]==0) 
	{
		for (int j=0;j<k;j++) f[j]=sum[sta+j*pw[i]];
		if (k==4)
		{
			g[2]=f[1]-f[0];
			g[1]=f[2]-f[3];
			g[0]=f[0]-g[1];
			g[3]=f[3]-g[2];
		}
		if (k==6)
		{
			g[2]=f[1]-f[0];
			g[3]=f[4]-f[5];
			g[1]=f[2]-g[2]-g[3];
			g[4]=f[3]-g[2]-g[3];
			g[0]=f[0]-g[1];
			g[5]=f[5]-g[4];
		}
		if (k==7)
		{
			g[2]=f[1]-f[0];
			g[4]=f[5]-f[6];
			g[3]=f[3]-g[2]-g[4];
			g[1]=f[2]-g[2]-g[3];
			g[5]=f[4]-g[3]-g[4];
			g[0]=f[0]-g[1];
			g[6]=f[6]-g[5];
		}
		for (int j=0;j<k;j++) sum[sta+j*pw[i]]=g[j];
	} 
	for (int sta=0;sta<tot;sta++) cout<<sum[sta]<<" ";
	cout<<endl;
}
{{ vote && vote.total.up }}