題目鏈接

---

聽dalao說很nb，做做看（然而不小心知道題解了）。

\(Description\)

給定長為\(n\)的序列\(A_i\)和\(B_i\)。你可以進行任意多次操作，每次操作任選一個\(i\in[2,n-1]\)，把\(A_i\)變成\(A_{i-1}+A_{i+1}-A_i\)。
求能否將序列\(A_i\)變成\(B_i\)。
\(n\leq10^5\)。

\(Solution\)

\(A_i\to A_{i-1}+A_{i+1}-A_i\)這個形式很有趣，求出\(A_i\)的差分序列\(d_i\)試試看。
令\(d_{i-1}=A_i-A_{i-1},\ d_i=A_{i+1}-A_i\)。
如果變換\(A_i\)，那么\(d_{i-1}\)會變成\(A_{i+1}-A_i=d_i\)，\(d_i\)會變成\(A_i-A_{i-1}=d_{i-1}\)。
也就是我們可以任意交換\(A_i\)的差分序列\(d_i\)。
所以再求出\(B_i\)的差分序列\(d_i'\)，判斷\(d_i\)能否變成\(d_i'\)，再判一下\(A_1\)是否等于\(B_1\)即可。

---

//46ms 900KB #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() typedef long long LL; const int N=1e5+5;int d1[N],d2[N];inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-48,c=gc());return now; } inline bool Check(const int n) {for(int i=1; i<n; ++i) if(d1[i]!=d2[i]) return 0;return 1; }int main() {const int n=read();int A1=read();for(int i=1,pre=A1,now; i<n; ++i) d1[i]=(now=read())-pre, pre=now;int B1=read();for(int i=1,pre=B1,now; i<n; ++i) d2[i]=(now=read())-pre, pre=now;std::sort(d1+1,d1+n), std::sort(d2+1,d2+n);puts(A1==B1&&Check(n)?"Yes":"No");return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/10364291.html

總結

以上是生活随笔為你收集整理的Codeforces.1110E.Magic Stones(思路 差分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。