CF1110E Magic Stones

CF1110E Magic Stones

题目描述

一次操作选择1<i<n，使  $ c_i $  变为  $ c_i = c_{i-1} + c_{i+1}  - c_i $ 

是否能做若干次操作，使每个 $ c_i $ 和 $ t_i $ 相等？

数据范围：1e5

题解：

看到这个形式很容易想到差分

我们把这个移项

c[i]'-c[i-1]=c[i+1]-c[i]

这就是差分后的序列

所以每次操作对于差分数列的值没有发生改变 改变的只有位置 也就是交换一下位置

只比较差分序列即可

注意特判第一位

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define rg register
#define I inline
#define MAXN 100010

I ll read()
{
    ll f = 1, x = 0;
    char  ch;
    do
    {
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch < '0' || ch > '9');
    do
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }while(ch >='0' && ch <='9');
    return f*x;
}

int n;
int a[MAXN],t[MAXN];
int ca[MAXN],ct[MAXN];

int main()
{
    n = read();
    for(int i=1;i<=n;i++)
    {
        a[i] = read(); 
        ca[i] = a[i] - a[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        t[i] = read();
        ct[i] = t[i] - t[i-1];
    }
    if(a[1]!=t[1]||a[n]!=t[n]) 
    {
        cout << "No" << endl;
        return 0;
    }
    sort(ca+1,ca+n+1);
    sort(ct+1,ct+n+1);
    for(int i=1;i<=n;i++)
    {
        if(ca[i]!=ct[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}