題目描述
小 C 在了解了她所需要的資訊之後，讓兔子們調整到了恰當的位置。小 C 準備給兔子 們分成若幹個小組來喂恰當的胡蘿蔔給兔子們吃。
此時， nnn 隻兔子按一定順序排成一排，第 iii 隻兔子的顔色是 aia_iai 。由于順序已經是被 調整好了的，是以每個小組都應當是序列上連續的一段。
在分組前，小 C 發現了一個規律：有些兔子會兩兩發生沖突。并且，兩隻兔子會發生矛 盾，當且僅當代表他們的顔色的數值之和為一個正整數的平方。比如，1 色兔子和 2 色兔子 不會發生沖突，因為 3 不是任何一個正整數的平方；而 1 色兔子卻會和 3 色兔子發生沖突， 因為 4=224 = 2^24=22。
小 C 認為，隻要一個小組内的沖突不要過大就行。是以，小 C 定義了一個小組的沖突 值 kkk ，表示在這個小組裡，至少需要将這個組再一次分成 kkk 個小團體；每個小團體并不需 要是序列上連續的一段，但是需要使得每個小團體内任意兩隻兔子之間都不會發生沖突。
小 C 要求，沖突值最大的小組的沖突值 kkk 不超過 KKK 就可以了。當然，這樣的分組方 法可能會有很多個；為了使得分組變得更加和諧，小 C 想知道，在保證分組數量最少的情況 下，字典序最小的方案是什麼。你能幫幫她嗎？
字典序最小的方案是指，按順序排列分組的間隔位置，即所有存在兔子 iii 和 i+1i + 1i+1 在 不同組的位置 iii，和其它所有相同分組組數相同的可行方案相比總有第一個不同的位置比其 它方案小的方案。
輸入輸出格式
輸入格式：
從标準輸入中讀入資料。
輸入第 1 行兩個正整數 n,Kn,Kn,K。
輸入第 2 行 nnn 個正整數，第 iii 個數表示第 iii 隻兔子的顔色 aia_iai。
輸出格式：
輸出到标準輸出中。
輸出第 1 行一個正整數 mmm，為你至少需要将兔子分為多少個小組。
輸出第 2 行m−1m-1m−1個從小到大的排列的正整數，第 iii 個數 sis_isi 表示 sis_isi 和 si+1s_i + 1si+1 在 你的方案裡被分到了兩個小組。如果 m=1m = 1m=1，那麼請輸出一個空行。
輸入輸出樣例
輸入樣例#1：
複制
5 2
1 3 15 10 6 輸出樣例#1： 複制
2
1 說明
【樣例 1 解釋】
如果将五隻兔子全部分到同一個小組的話，那麼 (1, 3) (3, 6) (6, 10) (10, 15) (1, 15) 均 不能分到同一個小團體；因為最多分成兩個小團體，是以為了滿足前 4 對限制，隻能分為 {{1, 6, 15}, {3, 10}}，但此時不滿足 (1, 15) ，是以不存在一種組數為 1 的方案滿足全部限制。
如果将五隻兔子分為兩個小組的話，一種字典序最小的可行的分組方案是 {1}, {3, 15, 10, 6}，此時第二組内的小團體數量不超過 2 的一種分法是 {{3, 10}, {15, 6}}。
【資料範圍】
子任務會給出部分測試資料的特點。如果你在解決題目中遇到了困難，可以嘗試隻解 決一部分測試資料。
每個測試點的資料規模及特點如下表：
特殊性質 1：保證最優分組方案唯一。
特殊性質 2：保證不會有兩隻相同顔色的兔子。
從後向前選，能多選就多選，
理由：數字越少肯定越優，同時間隔盡量向前推，字典序盡量小
當k=1時很簡單，直接走一邊，每次枚舉1～512判斷，看是否存在x^2-a[i]的值
當k=2時，每一組可以分兩組，那麼要出現i無法配置設定的情況
那隻能是a[i]+a[j]=x^2,a[i]+a[k]=y^2 a[j]+a[k]=z^2
即j和k不能分一起，i也不能放在j或k在的一組
于是用鏡像并查集
如果滿足條件，那麼i和j不能放一起，于是可以了解為i+n和j不可以放一起，i和j+n不可以放一起
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6 using namespace std;
7 int set[400001],p[1001],a[400001],vis[400001],cnt,n,k;
8 vector<int>map[400001];
9 vector<int>v;
10 vector<int>ans;
11 int find(int x)
12 {
13 if (set[x]!=x) set[x]=find(set[x]);
14 return set[x];
15 }
16 bool pd(int x,int y)
17 {
18 if (find(x)==find(y)) return 1;
19 return 0;
20 }
21 void add(int x,int y)
22 {
23 int p=find(x),q=find(y);
24 if (p!=q)
25 set[p]=q;
26 }
27 bool check1(int x)
28 {int i;
29 for (i=512;i>=1;i--)
30 if (p[i]<=a[x]) return 1;
31 else
32 {
33 if (vis[p[i]-a[x]]&&vis[p[i]-a[x]]==cnt)
34 return 0;
35 }
36 return 1;
37 }
38 bool check2(int x)
39 {int i,j;
40 for (i=512;i>=1;i--)
41 if (p[i]<=a[x]) return 1;
42 else
43 {
44 if (vis[p[i]-a[x]]&&vis[p[i]-a[x]]==cnt)
45 {
46 for (j=0;j<map[p[i]-a[x]].size();j++)
47 {
48 if (pd(x,map[p[i]-a[x]][j]))
49 return 0;
50 add(x,map[p[i]-a[x]][j]+n);
51 add(x+n,map[p[i]-a[x]][j]);
52 }
53 }
54 }
55 return 1;
56 }
57 void solve1()
58 {int i;
59 cnt=1;
60 for (i=1;i<=512;i++)
61 p[i]=i*i;
62 for (i=1;i<=n;i++)
63 scanf("%d",&a[i]);
64 for (i=n;i>=1;i--)
65 if (check1(i))
66 {
67 vis[a[i]]=cnt;
68 }
69 else
70 {
71 cnt++;
72 vis[a[i]]=cnt;
73 v.push_back(i);
74 }
75 cout<<cnt<<endl;
76 for (i=v.size()-1;i>=0;i--)
77 printf("%d ",v[i]);
78 }
79 void solve2()
80 {int i;
81 cnt=1;
82 for (i=1;i<=512;i++)
83 p[i]=i*i;
84 for (i=1;i<=n;i++)
85 scanf("%d",&a[i]);
86 for (i=1;i<=2*n;i++)
87 set[i]=i;
88 for (i=n;i>=1;i--)
89 if (check2(i))
90 {
91 if (vis[a[i]]!=cnt)
92 vis[a[i]]=cnt,map[a[i]].clear();
93 map[a[i]].push_back(i);
94 }
95 else
96 {
97 cnt++;
98 vis[a[i]]=cnt;
99 map[a[i]].clear();
100 map[a[i]].push_back(i);
101 ans.push_back(i);
102 }
103 cout<<cnt<<endl;
104 for (i=ans.size()-1;i>=0;i--)
105 printf("%d ",ans[i]);
106 }
107 int main()
108 {
109 cin>>n>>k;
110 if (k==1)
111 solve1();
112 else solve2();
113 }