题解 P5614 【[MtOI2019]膜Siyuan】

> 你强归你强，$\color{red}{\mathsf{S}}\color{black}\mathsf{iyuan}$ 比你强！ 大家好，我是本题的验题人。 ~~其实这题本来应该放 A 题的位置的，但因为不够签到就成了 B 题。~~ 接下来进入正题。 ## 算法一 当 $M \leq 200$ 时，我们可以直接枚举 $x,y,z$ 的值，判断其是否满足所有等式即可。 时间复杂度：$O(n^3)$，期望得分 $60$。 ## 算法二 假如这个方程只有一个未知数（像 $|a-x|=b$ 这样的形式，其中 $a,b$ 为常数），显然我们可以直接求出该方程的解，而不用枚举 $x$ 的值。 因此我们可以只枚举两个未知数，将两个未知数代入其中一个等式，推算出第三个未知数的值，将这组解代入其余等式，判断是否成立即可。 时间复杂度：$O(n^2)$，期望得分 $100$。 几个注意事项： 1. 记得判断第三个未知数是否在 $[1,M]$ 的范围内； 1. 绝对值方程可能会出现两个相同解的情况（像 $|x-6|=0$ 这样的方程的解为 $x_1=x_2=6$），需要处理这种情况。 ```cpp #include <cstdio> #include <algorithm> using namespace std; struct node { int a,b,c; }p[15]; int main() { int n,m,ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) { int tmp=abs(i-p[1].a)^abs(j-p[1].b)^9; int res1=p[1].c+tmp,res2=p[1].c-tmp; int flag1=(res1>0&&res1<=m),flag2=(res2>0&&res2<=m); for(int k=2;k<=n;k++) { if((abs(i-p[k].a)^abs(j-p[k].b)^abs(res1-p[k].c))!=9)flag1=false; if((abs(i-p[k].a)^abs(j-p[k].b)^abs(res2-p[k].c))!=9)flag2=false; } //if(flag1)printf("%d %d %d\n",i,j,res1); //if(flag2)printf("%d %d %d\n",i,j,res2); if(res1==res2)flag2=false;//排除两个相同解的情况 ans+=flag1+flag2; } printf("%d\n",ans); return 0; } ``` ## 题外话 Orz $\color{red}{\mathsf{S}}\color{black}\mathsf{iyuan}$！