最终得对抗自己

[BZOJ 5071] 小A的数字

题目大意

给你两个长度为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

Your email address will not be published. Required fields are marked *