HZOJ 分组

打了好多个代码。

对于测试点1，11：手动模拟。

 1 void QJ1_11()
 2 {
 3     if(n==2)
 4     {
 5         int tk;
 6         if(pd(a[1]+a[2]))tk=2;
 7         else tk=1;
 8         if(tk<=k)    
 9         {
10             puts("1");
11             puts("");
12         }
13         else
14         {
15             puts("2");
16             printf("%d
",1);
17         }
18         exit(0);
19     }
20 }

View Code

对于测试点2～6：

可以用贪心的方法，从后往前扫，每遇到一个数，判断是否可以加入当前段，不行则断开。复杂度$n^2$.

 1 void QJ2_6()
 2 {
 3     if(k==1)
 4     {
 5         if(n==4||n==16||n==256||n==1024)
 6         {
 7             LL l=n,num=0;
 8             for(int i=n;i;i--)
 9             {
10                 for(int j=l;j>i;j--)
11                 if(pd(a[i]+a[j]))
12                 {
13                     num++,ans[++cnt]=i,l=i;break;
14                 }
15             }
16             if(ans[cnt]==0&&cnt!=0){cnt--;}
17             else num++;
18             printf("%lld
",num);
19             for(int i=cnt;i;i--)
20                 printf("%lld ",ans[i]);
21             exit(0);
22         }
23     }
24 }

View Code

对于测试点7～10：

n=131072，那么换一种枚举方法，判断是否存在啊a[j]+a[i]=x^2,开一个桶，只需要枚举x（1～512）即可。复杂度n*√n。

 1 void QJ7_10()
 2 {
 3     if(k==1)
 4     {
 5         if(n==131072)
 6         {
 7             int num=0;
 8             for(int i=n;i;i--)
 9             {
10                 for(int j=512;j&&j*j>a[i];j--)
11                 if(t[j*j-a[i]])
12                 {
13                     num++,ans[++cnt]=i;ma(t);break;
14                 }
15                 t[a[i]]=1;
16             }
17             if(ans[cnt]==0&&cnt!=0){cnt--;}
18             else num++;
19             printf("%d
",num);
20             for(int i=cnt;i;i--)
21                 printf("%lld ",ans[i]);
22             exit(0);
23         }
24     }
25 }

View Code

对于测试点12～25：

同样的贪心方法，将矛盾的两只兔子连边，如果此时是一张二分图，那么一定可以将其分成两个小团体使其不发生矛盾，k=2，否则就断开。理论复杂度$n^2$,实际上因为点比较水（可能出题人觉得这是$n^3$，所以没有卡这个算法），可以A掉，跑的还挺快。

 1 void QJ12_25()
 2 {
 3     if(k==2)
 4 //    if(n==4||n==8||n==16)
 5     {
 6         int num=0,l=n;
 7         for(re int i=n;i;i--)
 8         {
 9             for(re int j=l;j>i;j--)
10             if(pd(a[i]+a[j]))
11                 add(i,j),add(j,i);
12             for(re int j=l;j>=i;j--)co[j]=0;
13             if(!dfs(i,2))
14             {
15                 l=i;num++;ans[++cnt]=i;
16                 for(re int j=l;j>=i;j--)first[j]=0;
17                 num_e=0;
18             }
19         }
20         if(ans[cnt]==0&&cnt!=0){cnt--;}
21         else num++;
22         printf("%d
",num);
23         for(re int i=cnt;i;i--)
24             printf("%lld ",ans[i]);
25         exit(0);
26     }
27 }

View Code

同样对k=2的正解：

这个我还没打，先坑着。