sam com 发现 ++ cnblogs 分享 logs ios .com
2
6
1 6 9 4 2 0
7 -6 19 2 -6 6
4
1 2 3 4
4 2 1 3
YES
NO
第一组数据中,可以依次取 i=2,4,5,每次得到的新数列如下:
第一次, i=2,得到 7,-6,15,4,2,0,
第二次, i=4,得到 7,-6,19,-4,6,0,
第三次, i=5,得到 7,-6,19,2,-6,6,所以可以得到 b 数列。
第二组数据中,不可能做到这一点。
将(Ai-1,Ai,Ai+1)变为(Ai-1 + Ai,-Ai,Ai+1 + Ai)
做前缀和转化为
(Ai-1,Ai-1+Ai,Ai-1+Ai+Ai+1)变为(Ai-1+Ai,Ai-1,Ai-1+Ai+Ai+1)
发现一次操作相当于交换前缀和的两位
所以将前缀和排序,判断相同就行了
zyys
- #include < iostream > #include < cstdio > #include < cstring > #include < algorithm > using namespace std;
- int n;
- long long a[100001],
- b[100001];
- int main() {
- int T,
- i,
- flag;
- cin >> T;
- while (T--) {
- scanf("%d", &n);
- for (i = 1; i <= n; i++) scanf("%lld", &a[i]),
- a[i] += a[i - 1];
- for (i = 1; i <= n; i++) scanf("%lld", &b[i]),
- b[i] += b[i - 1];
- sort(a + 1, a + n + 1);
- sort(b + 1, b + n + 1);
- flag = 0;
- for (i = 1; i <= n; i++) if (a[i] != b[i]) {
- flag = 1;
- break;
- }
- if (flag == 0) printf("YES\n");
- else printf("NO\n");
- }
- }
[BZOJ 5071]小A的数字
来源: http://www.bubuko.com/infodetail-2381527.html