CF1110E Magic Stones

Posted by

https://www.luogu.org/problemnew/show/CF1110E 思路:很考思维的一道题。当时考场上没想出来。 显然如果第一个位置的元素或最后一个位置的元素互不相等,则不能。 我们假设有3个数为x,y,z,属于c数组。 设:

    \[ d[1]=x-y; \]

    \[ d[2]=y-z; \]

经过一次操作后:

    \[ y=x+z-y; \]

那么:

    \[ d[1]=x-y=x-(x+z-y)=y-z; \]

    \[ d[2]=y-z=(x+z-y)-z=x-y; \]

其实本质上是相邻的两个差分数组的交换。 那么只需要判断差分数组是否对应相等即可解决问题。 代码:
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=100050;
using namespace std;
int n,a[MAXN],b[MAXN],c[MAXN],d[MAXN];
inline int read(){
    int x=0,sign=0;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    if(a[1]!=b[1]||a[n]!=b[n]) return 0&printf("No\n");
    for(int i=2;i<=n;i++){
        c[i]=a[i]-a[i-1];
        d[i]=b[i]-b[i-1];
    }
    sort(c+2,c+n+1);
    sort(d+2,d+n+1);
    for(int i=2;i<=n;i++){
        if(c[i]!=d[i]) return 0&printf("No\n");
    }
    printf("Yes\n");
    return 0;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注