题解 P3940 【分组】
（考试的时候勤勤恳恳【一边摸鱼一边】骗分。首先是对于直接输出1的那一个点不加赘述，然后考虑k=1并且答案唯一的点好像扫一下就能得到答案。对于k=1或k=2，并且ai<=2的情况好像记录一下2的个数也能骗到分。
于是码了一下，最后骗到24分。）
题解：
基本上是std的思路，细节处理稍微有点不一样，然后再详细说一下正解。
正解分成k=1和k=2来分别考虑。显然对于这两种情况，所用的做法是不一样的。
对于k=1，分组所要满足的条件是任意一组中元素之间没有互相冲突，即相加为平方数的。那么每一次分组，我们可以考虑当前元素和上一个分组点之后的所有元素是否产生冲突，如果冲突就考虑进行分组。那么显然扫一遍之前的元素就能判断是否冲突。
但是n有1e5+的级别…最坏的可能性这一扫就要爆炸。那么有什么快速判断当前元素是否合法的方式吗？发现如果我们只用考虑当前元素是否合法，那么前面的元素完全可以只记录值而不记录位置。判断两个数相加是否为一个平方数，可以循环每个数，当然也可以只记录值而循环平方数。
ai的上限其实是一个提示。131072*2=262144=512²。我们只需要枚举1-512，判断枚举到的数的平方减去当前元素，所得到的值是否出现过，就可以判断是否合法。
但是上面这几句都建立在我们只用考虑当前元素是否合法这一前提下。实际上，还有一个重要的限制——字典序。如果从前往后枚举，我们需要记录与当前元素冲突的值的位置，因为把这个位置作为分组点显然比把当前元素的前一位作为分组点要优。举个栗子，对于序列1,2,3，在1和2之间分组显然比在2和3之间分组要优，但是这两种分组都合法。
那么我们能不能让判断产生了冲突的位置成为答案呢——把序列倒过来枚举就可以了。
官方题解也给出了说法，倒过来枚举的冲突点，也就是正序中可能的最靠前的分界点位置，一定更优。因为分界点如果靠后，不仅对于这个分组操作来说不优，并且对于上一个组，它的段长变大，段内产生冲突的可能性变大，分组变多的可能性也随之上升。
于是最后k=1的做法就是，倒过来枚举序列并判断当前元素是否与之前产生冲突，记录冲突点。注意一个一个清空记录存在过的值的vis数组，如果直接memset会增加不必要的复杂度。
对于k=2的情况，思路就要更为复杂一点。首先继承k=1的思路中总体上的倒叙枚举以及枚举平方数的思路。
很显然的是，对于每个分组中的元素，如果根据冲突关系把它们黑白染色，那么只要分组中的元素能组成一张二分图，这个分组就是合法的。根据这一点，枚举序列的时候每次暴力判断二分图其实就是一种高分做法，并且似乎是可以通过全部数据的…
而正常去考虑，每次都跑一次二分图的复杂度显然过高。我们依旧需要能快速判断当前元素是否合法的方法。发现对于交错复杂的敌对关系，即冲突，我们似乎在哪里见到过。
P1525关押罪犯。这道题里我们用并查集的扩展域或者带权并查集维护了交织的敌对关系，并最后判断哪一组不得不产生冲突。这与这道题现在考虑到的这一部分很相似。
其实没有做过这道题也能考虑到并查集，毕竟我们要维护一堆冲突关系，并且判断什么时候不能再把冲突的两个数字分别放在两组中，而是无论怎么放都会产生冲突。
想到这里，尝试用并查集来处理这道题。和关押罪犯一样开一个扩展域，并查集中1-maxx【最大数值】为1-maxx本身的集合，而maxx+1-maxx*2是1-maxx的敌人集合。扫到一个元素，并判断之前有冲突的数值出现的时候，就查看两者并查集维护的信息。如果两个数值本身不在一个集合里，那么它们就能被分别放在两组中。然后维护敌对关系，让两者的敌人域分别和对方的本域合并在一起。
但是还有需要特殊考虑的情况！我们并查集维护的是每一个数值的信息，而序列中如果出现了同样的数值，不可能再把一个并查集分裂出去也没法维护信息。仔细想想，两个相等的数值只要不会相加产生一个平方数，那么它们就可以分在同一组中，毫无影响。于是对于有相同元素出现的时候，判断它的二倍是不是平方数，如果是的话，再考虑能不能分在同一组。两个这样的相同元素能分在同一组的条件是，它们出现且仅出现两次，没有其它敌对元素。如果有其它敌对元素，那么这三个元素一定不能安定地分成两组。于是对相同元素进行特判处理。
最后清空等操作和k=1时是差不多的。
#include<iostream>
#include<cstdio>
using namespace std;
int n,k,maxx;
int a[150010],vis[150010],flag,lst,tag[300010],fa[300010];
int ans[150010],sum;
int get(int x){
if(fa[x]==x)return x;
else return fa[x]=get(fa[x]);
}
void solve1(){
for(int i=n;i>=1;i--){
flag=0;
for(int j=1;j<=512;j++){
if(j*j<=a[i])continue;
if(j*j-a[i]>maxx)break;
if(vis[j*j-a[i]]){
flag=1;
break;
}
}
if(flag){
ans[++sum]=i;
for(int j=i+1;j<=lst;j++){
vis[a[j]]=0;
}
lst=i;
}
vis[a[i]]=1;
}
}
void solve2(){
for(int i=1;i<=maxx;i++)fa[i]=i,fa[i+maxx]=i+maxx;
for(int i=1;i*i<=maxx*2;i++)tag[i*i]=1;
for(int i=n;i>=1;i--){
flag=0;
if(vis[a[i]]){
if(tag[a[i]*2]){//同样的数字出现了两次，并且它的二倍是平方数
for(int j=1;j<=512;j++){
if(vis[a[i]]==2||fa[a[i]+maxx]!=a[i]+maxx){flag=1;break;}
//这里可以用判断敌人域的代表元素是不是它本身的方法来得知有没有敌对元素，是因为我每次并查集合并都是让敌人域合向本域
if(j*j<a[i])continue;
if(j*j-a[i]>maxx)break;
if(vis[j*j-a[i]]&&j*j-a[i]!=a[i]){flag=1;break;}
}
if(flag){
ans[++sum]=i;
for(int j=i;j<=lst;j++){
fa[a[j]]=a[j],fa[a[j]+maxx]=a[j]+maxx;
vis[a[j]]=0;
}
lst=i;
}
}
}
else{
for(int j=1;j<=512;j++){
if(j*j<a[i])continue;
if(j*j-a[i]>maxx)break;
if(vis[j*j-a[i]]){
if(tag[2*(j*j-a[i])]&&vis[j*j-a[i]]==2){
flag=1;
break;
}
int x1=get(a[i]),x2=get(a[i]+maxx),y1=get(j*j-a[i]),y2=get(j*j-a[i]+maxx);
if(x1==y1){
flag=1;
break;
}
else{
fa[y2]=x1;
fa[x2]=y1;
}
}
}
if(flag){
ans[++sum]=i;
for(int j=i;j<=lst;j++){
fa[a[j]]=a[j],fa[a[j]+maxx]=a[j]+maxx;
vis[a[j]]=0;
}
lst=i;
}
}
vis[a[i]]++;
}
}
int main()
{
scanf("%d%d",&n,&k);
lst=n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxx=max(maxx,a[i]);
if(k==1)solve1();
else solve2();
printf("%d\n",sum+1);
for(int i=sum;i>=1;i--){
printf("%d ",ans[i]);
}
return 0;
}要注意的判断细节有点多，在各种细节上WA了好几次，包括因为清空不正确，自信地认为拿到了前四十分，其实只拿到一半…
思路不是很好想，这题一上来给的东西很多，对于我这种思路混乱的容易搞成一团乱麻。应该条理地观察总结性质，逐一思考获取最后的思路。
最后安利一下自己的博客，这场考试的三道题【斐波那契，数颜色，分组】都可以在同一篇找到：https://www.cnblogs.com/chloris/