[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");
}

[CF1110E] Magic Stones - 思维

原文：https://www.cnblogs.com/mollnn/p/13649706.html