CF1110E Magic Stones（构造题）

这场CF怎么这么多构造题……

题目大意：给定两个长度为 $n$ 的序列 $c$ 和 $t$。每次我们可以对 $c_i(2\le i<n)$ 进行一次操作，也就是把 $c_i$ 变成 $c_i'=c_{i-1}+c_{i+1}-c_i$。问 $c$ 能否在若干次操作后变成 $t$。

$1\le n\le 10^5,1\le c_i,t_i\le 2\times 10^9$。

很容易考虑差分。我们设 $d_i=c_i-c_{i-1},s_i=t_i-t_{i-1}(2\le i\le n)$。

那么对 $c_i$ 进行一次操作后，

$d_i$ 会变成 $d_i'=c_i'-c_{i-1}=c_{i-1}+c_{i+1}-c_i-c_{i+1}=c_{i+1}-c_i=d_{i+1}$，

$d_{i+1}$ 会变成 $d_{i+1}'=c_{i+1}-c_i'=c_{i+1}-(c_{i-1}+c_{i+1}-c_i)=c_i-c_{i-1}=d_i$。

实际上就是把 $d_i$ 和 $d_{i+1}$ 换了个位置。

很明显，仅仅通过交换相邻元素，就可以把原序列变成任意一种原元素的排列。

而两个序列完全相同，当且仅当它们的第一个元素相同且差分序列完全相同。

所以只需判断 $c_1=t_1$ 且 $d$ 和 $s$ 能通过重排变得完全一样即可。

后半部分如何判断？排个序后看看是否完全一样即可。

时间复杂度 $O(n\log n)$。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

    char ch=getchar();int x=,f=;

    while(ch<'' || ch>'') f|=ch=='-',ch=getchar();

    while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();

    return f?-x:x;

}

int n,c[maxn],t[maxn],d1[maxn],d2[maxn];

int main(){

    n=read();

    FOR(i,,n) c[i]=read();

    FOR(i,,n) t[i]=read();

    if(c[]!=t[]) return puts("No"),;    //先判首项相等

    bool flag=true;

    FOR(i,,n) d1[i]=c[i]-c[i-],d2[i]=t[i]-t[i-];    //两个差分序列

    sort(d1+,d1+n+);sort(d2+,d2+n+);    //排序

    FOR(i,,n) if(d1[i]!=d2[i]){flag=false;break;}    //比较

    puts(flag?"Yes":"No");

}

巴特西

CF1110E Magic Stones（构造题）

最新文章

热门文章