分析：暴力分挺多，也挺好想的，个人感觉两个特殊性质没什么卵用.
对于K=1，n ≤ 1024的情况，从后往前贪心地分，如果能和上一组分在一起就分在一起，否则就再开一组，这样可以保证字典序最小.ai ≤ 2就看前面有没有2.有就不能分在一组.n ≤ 131072就不能再这样二重循环枚举了，因为两个数的和顶多只有262114 = 512^2,从1枚举到512，看看它的平方有没有被占用就可以了，就把问题从序列上转化到了值域上.
对于K=2,其实做法和K=1没什么两样，只是每一组可以分成两个对立的小组，非常像noip2010关押罪犯，加一个并查集就好了.用一个vector存每个值的兔子的位置，判断一下有没有冲突就好了.
暴力+正解：
#include <cmath> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 131072; vector <int>E[maxn * 2 + 10]; int n, k, a[150000], ans[150000], cnt, fa[300010], vis[300010], T; bool flag = true; bool check2(int x) { for (int i = 2; i <= 512; i++) { if (i * i - x >= 0 && vis[i * i - x]) return false; } return true; } int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } bool check(int x, int y) { int t = x + y; int p = sqrt(t); if (p * p == t) return false; return true; } void solve1() { if (n <= 1024) { int cur = n; for (int i = n; i >= 1; i--) { for (int j = i + 1; j <= cur; j++) { if (!check(a[i], a[j])) { ans[++cnt] = i; cur = i; } } } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } else if (flag) { int cur = n; bool flag2 = false; for (int i = n; i >= 1; i--) { if (flag2 && a[i] == 2) { ans[++cnt] = i; cur = i; } if (a[i] == 2) flag2 = 1; } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } else { int cur = n; for (int i = n; i >= 1; i--) { if (!check2(a[i])) { for (int j = i + 1; j <= cur; j++) vis[a[j]] = 0; ans[++cnt] = i; cur = i; } vis[a[i]] = 1; } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } } void hebing(int x, int y) { x = find(x), y = find(y); fa[x] = y; } bool check3(int x) { for (int i = 1; i <= 512; i++) { if (i * i - a[x] >= 0 && vis[i * i - a[x]] == T) { int now = i * i - a[x]; for (int j = 0; j < E[now].size(); j++) { if (find(x) == find(E[now][j])) return false; hebing(x + n, E[now][j]); hebing(x, E[now][j] + n); } } } return true; } void solve2() { if (flag) { int flag2 = 0; for (int i = n; i >= 1; i--) { if (flag2 == 2 && a[i] == 2) { ans[++cnt] = i; flag2 = 0; } if (a[i] == 2) flag2++; } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } else if (n <= 1024) { for (int i = 1; i <= n * 2; i++) fa[i] = i; int cur = n; for (int i = n; i >= 1; i--) { for (int j = i + 1; j <= cur; j++) { if (!check(a[i], a[j])) { if (find(i) == find(j)) { ans[++cnt] = i; cur = i; } else { int xx = find(i + n), yy = find(j + n); fa[i] = yy; fa[j] = xx; } } } } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } else { T = 0; for (int i = 1; i <= n * 2; i++) fa[i] = i; for (int i = n; i >= 1; i--) { if (!check3(i)) { T++; ans[++cnt] = i; } if (vis[a[i]] != T) { vis[a[i]] = T; E[a[i]].clear(); } E[a[i]].push_back(i); } printf("%d\n", cnt + 1); for (int i = cnt; i >= 1; i--) printf("%d ", ans[i]); printf("\n"); } } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (a[i] > 2) flag = false; } if (k == 1) solve1(); if (k == 2) solve2(); return 0; }
原文：http://www.cnblogs.com/zbtrs/p/7789999.html