姑且把它歸類為一道博弈吧，畢竟這也是在找必勝方案。

十分有意思的一道題目，設(shè)計(jì)一種方案讓你支持的1隊(duì)獲勝。

題目給出了兩個(gè)很重要的條件：

• 1隊(duì)能打敗至少一半的隊(duì)伍
• 對于1隊(duì)不能打敗的黑隊(duì)，一定存在一個(gè)1隊(duì)能打敗的灰隊(duì)，使得這支灰隊(duì)能夠打敗黑隊(duì)。也就是說1隊(duì)可以通過灰隊(duì)間接打敗黑隊(duì)

一共有2ⁿ支隊(duì)伍，每輪比賽會(huì)刷掉一半的隊(duì)伍，紫書上巧妙的做法就是每輪比賽后讓題目給的兩個(gè)性質(zhì)依然成立，這樣1隊(duì)最終一定能勝出。

方案如下，大致分為3個(gè)階段：

物盡其用。依次考慮每個(gè)黑隊(duì)，如果有能夠打敗他的灰隊(duì)的話，便讓這兩只隊(duì)伍進(jìn)行比賽。當(dāng)然，灰隊(duì)會(huì)晉級(jí)下一輪。如果沒有能夠打敗當(dāng)前黑隊(duì)而且還沒有進(jìn)行比賽的灰隊(duì)，那么這支黑隊(duì)進(jìn)入后面的混戰(zhàn)。

讓1隊(duì)勝出。在1隊(duì)能夠打敗的隊(duì)伍中找到一支還未進(jìn)行比賽的隊(duì)伍。對于其他未匹配的隊(duì)伍，也進(jìn)入下一步的混戰(zhàn)。

自由混戰(zhàn)。黑隊(duì)和黑隊(duì)混戰(zhàn)，這樣能保證至少消滅一半的黑隊(duì)，頂多有一個(gè)黑隊(duì)剩下。然后剩下的隊(duì)伍繼續(xù)混戰(zhàn)。

至于為什么這樣一定會(huì)成功，還請參考紫書。

1 #include <cstdio> 2 #include <vector> 3 using namespace std; 4 5 const int maxn = 1030; 6 7 char table[maxn][maxn]; 8 9 int main() 10 { 11 //freopen("in.txt", "r", stdin); 12 13 int n; 14 while(scanf("%d", &n) == 1 && n) 15 { 16 for(int i = 1; i <= n; i++) scanf("%s", table[i] + 1); 17 vector<int> win, lose; 18 for(int i = 2; i <= n; i++) 19 { 20 if(table[1][i] == '1') win.push_back(i); 21 else lose.push_back(i); 22 } 23 24 int T = n; 25 while(T >>= 1) 26 { 27 vector<int> win2, lose2, final;//進(jìn)入下一輪1能打敗和被打敗，以及這一輪混戰(zhàn)的隊(duì)伍 28 bool match; 29 //階段1:盡可能多的用灰隊(duì)消滅黑隊(duì) 30 for(int i = 0; i < lose.size(); i++) 31 { 32 int black = lose[i]; 33 match = false; 34 for(int j = 0; j < win.size(); j++) 35 { 36 int& gray = win[j]; 37 if(gray > 0 && table[gray][black] == '1') 38 { 39 printf("%d %d\n", black, gray); 40 match = true; 41 win2.push_back(gray);//灰隊(duì)進(jìn)入下一輪 42 gray = 0; 43 break; 44 } 45 } 46 if(!match) final.push_back(black);//進(jìn)入后面的混戰(zhàn) 47 } 48 //階段2:給1隊(duì)找個(gè)對手 49 match = false; 50 for(int i = 0; i < win.size(); i++) 51 { 52 int team = win[i]; 53 if(team > 0) 54 { 55 if(!match) { printf("1 %d\n", team); match = true; } 56 else final.push_back(team);//1已經(jīng)匹配到對手，該隊(duì)進(jìn)入混戰(zhàn) 57 } 58 } 59 //階段3:自由混戰(zhàn)，注意到黑隊(duì)在final中都是挨在一起的 60 for(int i = 0; i < final.size(); i += 2) 61 { 62 printf("%d %d\n", final[i], final[i + 1]); 63 int survive = final[i]; 64 if(table[final[i + 1]][final[i]] == '1') survive = final[i + 1]; 65 if(table[1][survive] == '1') win2.push_back(survive); 66 else lose2.push_back(survive); 67 } 68 win = win2; 69 lose = lose2; 70 /*for(int i = 0; i < win.size(); i++) printf("%d ", win[i]); 71 puts(""); 72 for(int i = 0; i < lose.size(); i++) printf("%d ", lose[i]);*/ 73 } 74 } 75 76 return 0; 77 } 代碼君

?

轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4443947.html

總結(jié)

以上是生活随笔為你收集整理的UVa 1609 (博弈) Foul Play的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。