题解 P5614 【[MtOI2019]膜Siyuan】

· · 题解

首先

我想哭一会。。。

我交了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;
}

谢谢观看