題意：有n支隊伍（n是2的整數冪，2<=n<=4），打淘汰賽，勝者進入下一輪，其中1號隊伍能打敗至少一半的隊伍，對于它不能打敗的隊伍l，一定存在一支它能夠打敗的隊伍w，使得w能直接打敗l，求一種方案保證1號隊伍必勝。

隊伍分類：不能直接打敗的隊伍是黑色隊伍，能直接打敗且能打敗黑色隊伍的是灰色隊伍。

這里直接給出算法描述了：

階段1：貪心，每個不能直接打敗的隊伍，選一個沒有匹配的能打敗它的灰色隊伍。

階段2：對于剩下的黑色隊伍，任意匹配，可能會剩下一個。

階段3：找一個能直接打敗的隊伍和1號匹配

階段4：剩下的其他隊伍任意匹配。

對于進階的隊伍，仍然會滿足之前的條件。直到1號隊伍勝利為止。

正確性請參考紫書。手寫了個vec，感覺效率不比stl快多少，可能數據比較少吧。。。下標還寫錯了一發，尷尬。

#include<bits/stdc++.h> using namespace std; const int maxn = 1025;char G[maxn][maxn]; int vec[5][maxn];int main() {// freopen("in.txt","r",stdin);int n, *phase = vec[4];while(~scanf("%d",&n)){for(int i = 0; i < n; i++) scanf("%s",G[i]);int *win = vec[0],*lose = vec[2],sz1= 0,sz2 = 0;for(int i = 1; i < n; i++){if(G[0][i] == '1') win[sz1++] = i;else lose[sz2++] = i;}int N = n, s = 0;while(N > 1){s ^= 1;int *win2 = vec[s+0], *lose2 = vec[s+2], sz3 = 0,sz4 = 0;int sz5 = 0;for(int i = 0; i < sz2; i++){int tlose = lose[i];int j = 0;for(; j < sz1; j++){int &twin = win[j];if(twin > 0 && G[twin][tlose] == '1') {printf("%d %d\n",twin+1,tlose+1);win2[sz3++] = twin;twin = 0;break;}}if(j == sz1) phase[sz5++] = tlose;}while(sz5>1){int &a = phase[sz5-1], &b = phase[sz5-2];printf("%d %d\n",a+1,b+1);if(G[a][b] == '1') lose2[sz4++] = a;else lose2[sz4++] = b;sz5 -= 2;}bool flag = sz5 == 1;int i = 0;for(; i < sz1; i++) if(win[i]>0) { printf("1 %d\n",win[i++]+1); break; }for(; i < sz1; i++) if(win[i]>0) { phase[sz5++] = win[i]; }i = 0;if(flag) {int &a = phase[i], &b = phase[i+1];if(G[a][b] == '1') {lose2[sz4++] = a;}else {win2[sz3++] = b;}printf("%d %d\n",a+1,b+1);i += 2;}for(; i < sz5; i += 2){int &a = phase[i], &b = phase[i+1];if(G[a][b] == '1') {win2[sz3++] = a;}else {win2[sz3++] = b;}printf("%d %d\n",a+1,b+1);}sz1 = sz3; sz2 = sz4;win = win2; lose = lose2;N >>= 1;}}return 0; }

?

轉載于:https://www.cnblogs.com/jerryRey/p/4694691.html

總結

以上是生活随笔為你收集整理的UVA 1609 Foul Play 不公平竞赛 （构(luan)造(gao)+递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

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