[CF1110E] Magic Stones

Description

给定两个数列 (c,t)，每次操作可以选择一个 (i)，令 (c_i leftarrow c_{i+1}+c_{i-1}-c_i)，问进行若干次操作后，是否能使得数列 (c) 和 (t) 相等。

Solution

分析差分序列，将 (c_{i-1},c_i,c_{i+1}) 变为 (c_{i-1},c_{i-1}+c_{i+1}-c_i,c_{i+1}) 后，差分序列从 (c_i-c_{i-1},c_{i+1}-c_i) 变为 (c_{i+1}-c_i,c_{i}-c_{i-1})，即差分序列的相邻两项交换了。

因此每次操作的实质就是交换差分序列的相邻两项。

于是，若原序列满足 (c_1=t_1,c_n=t_n)，我们只需要比较差分序列的元素多重集是否相等即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n,c[N],t[N],a[N],b[N];

int solve()
{
    if(c[1]==t[1] && c[n]==t[n])
    {
        for(int i=1;i<=n;i++)
        {
            a[i]=c[i]-c[i-1];
            b[i]=t[i]-t[i-1];
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=b[i])
            {
                return false;
            }
        }
        return true;
    }
    else
    {
        return false;
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>t[i];

    cout<<(solve()?"Yes":"No");
}