打了好多個代碼。

對于測試點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\n",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\n",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\n",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\n",num); 23 for(re int i=cnt;i;i--) 24 printf("%lld ",ans[i]); 25 exit(0); 26 } 27 } View Code

同樣對k=2的正解：

這個我還沒打，先坑著。

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11296096.html

總結

以上是生活随笔為你收集整理的HZOJ 分组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。