題意：
? ? ? 有n個學生進教室，先后順序不同，每個人進去后會和當前在教室里的人握手,并且記錄人數，而且當教室里有超過三個人的時候 他們有可能組隊去參加比賽,后來的人看不到他們。


思路：

? ? ?這個題目還行挺有意思的，我們可以一個人一個人來模擬，就是枚舉握手次數，然后在相應的里面找到一個，如果一個都找不到就-3，到最后就行了，比如一開始我們枚舉0，就是握手次數是0的，如果找到有0，那么這個人就是第一個人，如果0的不唯一的話隨便挑一個就行，找到后就+1，找握手次數為1的，找到后就是第二個進來的，然后+1，找2的...如果當前握手次數找不到的話就-3，找到就繼續(xù)，還找不到就還-3，這樣如果那次當前枚舉次數小于0了，那么就說明失敗了，就是無解，還有就是找到的時候不能暴力去找，可以用個二維容器什么的，我用的是前向星配合類似DINIC里面那個優(yōu)化（職業(yè)病啊），比如當前i這個人的握手次數是3，那么就連邊3->i,這樣當我們想在3里面刪除的時候隨便找一個就行，刪除之后記得這樣處理 list[s] = E[k].next,就是下次直接從下一個開始就行，這個地方怎么處理都行，順手就行，用容器還有鏈表啥的都行，不多說了，關鍵是想到枚舉握手次數的那個地方就好辦了。

#include<stdio.h> #include<string.h>#define N_node 200005 #define N_edge 250005typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mkc[N_node]; int Ans[N_node] ,AT;void add(int a ,int b) {//printf("%d %d**\n" ,a ,b);E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int main () {int n ,i ,a ,b;while(~scanf("%d" ,&n)){memset(list ,0 ,sizeof(list)) ,tot = 1;memset(mkc ,0 ,sizeof(mkc));for(i = 1 ;i <= n ;i ++){b = i;scanf("%d" ,&a);add(a ,b);mkc[a] ++;}int nowc = 0;AT = 0;while(nowc >= 0 && AT != n){if(!mkc[nowc]) nowc -= 3;elsefor(int k = list[nowc] ;k ;k = E[k].next){Ans[++AT] = E[k].to;mkc[nowc]--;list[nowc] = E[k].next;nowc ++;break;}//printf("%d\n" ,nowc);}if(AT == n){printf("Possible\n");for(i = 1 ;i <= n ;i ++)if(i == n) printf("%d\n" ,Ans[i]);else printf("%d " ,Ans[i]);}else printf("Impossible\n");}return 0;}

總結

以上是生活随笔為你收集整理的cf534D 枚举握手次数的全部內容，希望文章能夠幫你解決所遇到的問題。

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