【B题】Codeforces Round #631 (Div. 2)

Codeforces Round #631 (Div. 2)"/>

【B题】Codeforces Round #631 (Div. 2)

题意：
每次给你个序列a（1 ≤ ai ≤ n−1)，问你这个序列a能否由两个序列组成；
这两个序列要满足的条件：
p1是a的前缀，p2是a的后缀，p1+p2=a；
p1和p2的长度至少大于等于1；
p1，p2的长度就代表着它的序列里有哪些数字，比如长度是3，那么其中的数字就是，1，2，3。顺序没关系。序列中每个数字都只出现一次。

比赛思路：
比赛的时候以为自己一下子就想出来了，结果写了个假算法，
我自以为聪明用了前缀和做，因为每个数字都只出现一次，所以每次判断一下，比如长度是3，那么这个区间的和是6，那就对了。其实肯定wa…但是比赛总是当局者迷。因为可以只是和恰好是这个数字，又不能说明每个数字都只出现了一次，2 2 2 的和也是6啊。

题解思路：
实际上题解的思路也很好想，只能说被自己的操作迷惑了。

每个序列a都会有一个最大值，如果a要是能被p1，p2分的话，p1，p2其中必定有一个要长度要等于最大值，不然肯定a肯定不能被分成两个部分；
然后判断【长度max，长度n-max】和【长度n-max，长度max】这两种情况，遍历一下看看有没有满足的。同时还要考虑到一个细节，如果长度max=n-max，那么就会算两遍，解决方法就是第二次的判断的时候加上2*max！=n就好了。

附上题解：

#include<cstdio>
const int SIZE = 200000;
int p[SIZE];
int ans[SIZE][2];
int ans_cnt;
bool judge(int a[], int n){static int used[SIZE+1];for(int i = 1; i <= n; i++) used[i] = 0;for(int i = 0; i < n; i++) used[a[i]] = 1;for(int i = 1; i <= n; i++) {if(!used[i]) return 0;}return 1;
}
bool judge(int len1, int n){return judge(p, len1) && judge(p + len1, n - len1);
}
int main() {int t = 0;scanf("%d", &t);while(t--) {ans_cnt = 0;int n;scanf("%d", &n);int ma=0;for(int i = 0; i < n; i++) {scanf("%d", &p[i]);if(ma < p[i]) ma = p[i];}if(judge(n - ma,n)) {ans[ans_cnt][0] = n - ma;ans[ans_cnt++][1] = ma;}if(ma * 2 != n && judge(ma,n)) {ans[ans_cnt][0] = ma;ans[ans_cnt++][1] = n - ma;}printf("%d\n", ans_cnt);for(int i = 0; i < ans_cnt; i++) {printf("%d %d\n", ans[i][0], ans[i][1]);}}return 0;
}