自动搬运

查看原文

来自洛谷，原作者为

	hwx12233 这个人废了，什么都没留下

搬运于2025-08-24 22:12:35，当前版本为作者最后更新于2019-11-03 21:31:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先

我想哭一会。。。

我交了27遍才过。。。我的27遍提交啊！！？？

然后进入正题

先是一般暴力：

枚举X，Y，Z，再把所有a、b、c检验一遍，判断A^B^C是否成立

显然这种做法是m三方n的；期望得分60

m=2000？？？ 炸了呀！咋办？

优化：

很容易 被大佬指点 得出只要枚举X和Y，再去判断Z是否成立就行啦

因为只要X和Y确定，那么Z一定也可以确定，不用枚举了，只要和暴力一样去判断就好了

时间复杂度m方，可以满分

做法：

当枚举第一组三元组时 先求出Z

由异或交换律得A^B^C=9 <=> C=A^B^9

设一个L= (abs(a[w]-i)^abs(b[w]-j)^9) =C

再解一个绝对值方程 |ci-Z|=L

可得

Z=ci-L（ci>Z）

Z=ci+L（ci<Z）

就得出（此处temp，temp2为两个解）

temp=ci-L（当temp<m&&temp>0&&ci>temp）

temp2=ci+L（当temp2<m&&temp2>0&&ci<temp2）

（p.s.没有temp=0的情况，因为Z是正整数，这个改了我十多遍,也没有temp2=m的情况，因为ci也<=m）

如果不符合解的条件 那就把解赋为-1，自动跳过

判断不符合的方

之后就枚举每一个a,b,c判断是否符合

代码中a，b，c数组分别对应x，y，z

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,x[6],y[6],z[6],ans=0,temp,temp1,temp2;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>z[i];
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++)
	for(int w=1;w<=n;w++)
	{
		if(w==1)//第一组数时解出两个解 
		{
			int l=(abs(x[w]-i)^abs(y[w]-j)^9);
			temp=z[w]-l;//算出两个解 
			temp2=z[w]+l;
			if(temp<=0||temp>m||z[w]<temp) temp=-1;//如果解不符合范围，赋值-1
			//题目中说XYZ是正整数所以要<=0   和   <=z[w] 
			if(temp2>m||temp2<=z[w]||temp2<0) temp2=-1;//判断范围为原范围的补集 
		}
		if((abs(x[w]-i)^abs(y[w]-j)^abs(z[w]-temp))==9&&temp!=-1){//每一个解进行判断 
			if(w==n&&temp!=-1){
				ans++; cout<<temp<<" temp1"<<endl;
			}
			//如果符合，ans++ 
		}
		else temp=-1;//有一个不符合就停止 
		if((abs(x[w]-i)^abs(y[w]-j)^abs(z[w]-temp2))==9&&temp2!=-1)//同上 
		{
			if(w==n&&temp2!=-1){
				ans++;cout<<temp2<<" temp2"<<endl;
			}
		}
		else temp2=-1;
	}
	cout<<ans<<endl;
}

谢谢观看