题目大意
给你两个长度为N的数列A和B, 你可以进行一个操作:
选取i,将[latex]A_{i-1}, A_{i}, A_{i+1}[/latex]变换为[latex]A_{i-1}+A_{i}, -A_{i}, A_{i+1}+A_{i}[/latex]。
特别的, 当i=1时不存在这种操作, i=N时只对A
i
和A
i-1
进行操作。
问A能否通过若干操作变换到B。
解题报告
第一眼好神啊!完全不会!
观察性质发现这个加加减减好像和前缀和有关, 对A和B分别前缀和后发现这个操作就是交换相邻两个数字。
然后这就是傻逼题了…
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 100010; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } int A[MAXN], B[MAXN]; LL s1[MAXN], s2[MAXN]; int main () { int T = getInt(); while(T --) { int N = getInt(); for(int i = 1; i<=N; i++) A[i] = getInt(), s1[i] = A[i]+s1[i-1]; for(int i = 1; i<=N; i++) B[i] = getInt(), s2[i] = B[i]+s2[i-1]; sort(s1+1, s1+N+1), sort(s2+1, s2+N+1); bool flg = true; for(int i = 1; i<=N; i++) if(s1[i] != s2[i]) {flg = false; break;} if(flg) puts("YES"); else puts("NO"); } }
Join the discussion