Studying Father's luogu blog

Studying Father's luogu blog

从零至灵,由壹达意

题解 P5614 【[MtOI2019]膜Siyuan】

posted on 2019-11-03 19:35:51 | under 题解 |

你强归你强, $\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]$ 的范围内;
  2. 绝对值方程可能会出现两个相同解的情况(像 $|x-6|=0$ 这样的方程的解为 $x_1=x_2=6$ ),需要处理这种情况。
#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}$ !