UVa 12450 SpaceRecon Tournament

题目描述SpaceRecon\texttt{SpaceRecon}SpaceRecon是一款201120112011年流行的实时策略游戏支持三种种族。游戏内置了Actionweb\texttt{Actionweb}Actionweb平台用于举办2M2^{M}2M名玩家参加的锦标赛。锦标赛采用单败淘汰制共MMM轮。前RRR轮RRR未公开为三局两胜制需赢222局晋级剩余M−RM - RM−R轮为五局三胜制需赢333局晋级。每轮比赛胜者晋级败者淘汰不会进行不必要的对局。赛后平台公布每位玩家的昵称以及他们在整个锦标赛中赢得的单局总场次即所有轮次中赢得的对局数之和。给定这些数据你需要推断每位玩家实际晋级到了第几轮即赢了多少轮并按照晋级轮数降序输出玩家昵称若晋级轮数相同则按昵称字典序升序输出。输入格式第一行一个整数NNN1≤N≤1001 \le N \le 1001≤N≤100表示测试用例数。每个测试用例以一行整数MMM1≤M≤101 \le M \le 101≤M≤10开始接下来有2M2^{M}2M行每行包含一个玩家昵称由字母数字组成长度111到161616和一个整数www表示该玩家的总胜场数。输入保证数据来自一个合法的锦标赛。输出格式对于每个测试用例输出2M2^{M}2M行每行一个玩家昵称按照题目要求排序。样例输入1 2 John 1 Jake 5 Joe 4 Jane 0输出Jake Joe Jane John题目分析本题的关键在于虽然RRR未知但每位玩家的总胜场www与他的晋级轮数kkk之间存在严格的数量关系。设某玩家晋级了kkk轮0≤k≤M0 \le k \le M0≤k≤M其中kMkMkM表示冠军。由于前RRR轮是BO3\texttt{BO3}BO3三局两胜后M−RM - RM−R轮是BO5\texttt{BO5}BO5五局三胜因此该玩家要至少赢得minWins(k)2⋅min⁡(k,R)3⋅max⁡(0,k−R) \text{minWins}(k) 2 \cdot \min(k, R) 3 \cdot \max(0, k - R)minWins(k)2⋅min(k,R)3⋅max(0,k−R)局比赛。若kMk MkM说明他在第k1k1k1轮被淘汰而他在被淘汰的那一轮中还可以赢得一些局但未达到晋级所需局数。被淘汰的那一轮如果是BO3\texttt{BO3}BO3他最多还能赢111局如果是BO5\texttt{BO5}BO5最多还能赢222局。因此对于kMk MkM他的总胜场www必须满足minWins(k)≤w≤minWins(k)extra(k1) \text{minWins}(k) \le w \le \text{minWins}(k) \text{extra}(k1)minWins(k)≤w≤minWins(k)extra(k1)其中extra(r)1\text{extra}(r) 1extra(r)1若r≤Rr \le Rr≤R或222若rRr RrR。注意rk1r k1rk1是他被淘汰的轮次号。对于冠军kMkMkM则总胜场恰好等于minWins(M)\text{minWins}(M)minWins(M)不存在额外胜场。由于上述区间互不重叠可以证明因此对于一个给定的RRR每个玩家的总胜场www唯一对应一个kkk。我们可以枚举所有可能的RRR0≤R≤M0 \le R \le M0≤R≤M对每个RRR计算出每个玩家的kkk然后检查这些kkk的频数是否符合单败淘汰赛的客观规律在2M2^{M}2M名玩家的锦标赛中晋级kkk轮0≤kM0 \le k M0≤kM的玩家数必须为2M−1−k2^{M-1-k}2M−1−k而冠军kMkMkM的人数必须为111。如果某个RRR满足上述所有条件则这个RRR就是合法的对应的kkk就是每位玩家的实际晋级轮数。解题思路预处理区间对于给定的MMM和枚举的RRR定义函数getRound(w,M,R)\texttt{getRound}(w, M, R)getRound(w,M,R)它遍历kkk从000到MMM计算出minWins(k)\text{minWins}(k)minWins(k)和上界maxWins(k)\text{maxWins}(k)maxWins(k)对kMkMkM为minWins(k)extra(k1)\text{minWins}(k)\text{extra}(k1)minWins(k)extra(k1)对kMkMkM就是minWins(M)\text{minWins}(M)minWins(M)若www落在[minWins(k),maxWins(k)][\text{minWins}(k), \text{maxWins}(k)][minWins(k),maxWins(k)]内则返回kkk否则返回−1-1−1。枚举合法RRR外层循环R0…MR 0 \dots MR0…M内层对所有玩家调用getRound\texttt{getRound}getRound如果任何玩家返回−1-1−1则RRR无效。否则统计频数数组cnt[k]\textit{cnt}[k]cnt[k]。检查对于所有0≤kM0 \le k M0≤kM是否有cnt[k]2M−1−k\textit{cnt}[k] 2^{M-1-k}cnt[k]2M−1−k并且cnt[M]1\textit{cnt}[M] 1cnt[M]1。若成立则当前RRR是合法的记录每个玩家的kkk并跳出枚举。排序输出将每个玩家的晋级轮数kkk作为排序关键字按kkk降序排列若kkk相同按昵称字典序升序排列。依次输出昵称。复杂度分析每个测试用例中枚举RRR的次数为O(M)O(M)O(M)最多111111次每次对2M2^{M}2M个玩家最多102410241024个计算kkk每次计算需遍历M1M1M1个可能值因此总体时间复杂度为O(N⋅M⋅2M⋅M)≈O(100×10×1024×10)≈107O(N \cdot M \cdot 2^{M} \cdot M) \approx O(100 \times 10 \times 1024 \times 10) \approx 10^7O(N⋅M⋅2M⋅M)≈O(100×10×1024×10)≈107完全可以接受。空间复杂度O(2M)O(2^{M})O(2M)。代码实现// SpaceRecon Tournament// UVa ID: 12450// Verdict: Accepted// Submission Date: 2026-06-22// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structPlayer{string handle;intwins;introundSurvived;// 晋级轮数 k};// 计算给定胜场 wins 在总轮数 M、前 R 轮为 BO3 的情况下玩家晋级的轮数 kintgetRound(intwins,intM,intR){for(intk0;kM;k){intminW2*min(k,R)3*max(0,k-R);// 晋级 k 轮至少需要的胜场intmaxW;if(kM){maxWminW;// 冠军没有淘汰轮胜场固定}else{intnextRoundk1;// 被淘汰的轮次intmaxExtra(nextRoundR)?1:2;// BO3 最多赢 1 局BO5 最多赢 2 局maxWminWmaxExtra;}if(winsminWwinsmaxW)returnk;}return-1;// 无法匹配}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cinN;while(N--){intM;cinM;inttotal1M;vectorPlayerplayers(total);for(inti0;itotal;i){cinplayers[i].handleplayers[i].wins;}intvalidR-1;vectorintrounds(total);// 枚举 Rfor(intR0;RM;R){vectorintcnt(M1,0);booloktrue;vectorintcurRounds(total);for(inti0;itotal;i){intkgetRound(players[i].wins,M,R);if(k-1){okfalse;break;}curRounds[i]k;cnt[k];}if(!ok)continue;// 检查频数是否符合淘汰赛结构for(intk0;kM;k){if(cnt[k]!(1(M-1-k))){okfalse;break;}}if(okcnt[M]1){validRR;roundscurRounds;break;}}// 将计算结果赋给玩家for(inti0;itotal;i)players[i].roundSurvivedrounds[i];// 排序先按晋级轮数降序再按昵称字典序升序sort(players.begin(),players.end(),[](constPlayera,constPlayerb){if(a.roundSurvived!b.roundSurvived)returna.roundSurvivedb.roundSurvived;returna.handleb.handle;});// 输出for(constautop:players)coutp.handle\n;}return0;}总结本题的核心是逆向推断锦标赛轮次。由于RRR未知但每位玩家的总胜场提供了足够信息我们可以枚举RRR并利用晋级轮数与胜场数的单调区间映射再通过单败淘汰赛的固有频数分布来验证合法性。这种方法避免了复杂的树结构重建直接利用数量关系实现了简洁高效的判定。技巧上注意区间不重叠的性质是枚举可行的前提同时由于MMM很小≤10\le 10≤10枚举所有可能RRR是完全可行的。该题思路同样适用于其他存在未知规则参数的类似问题。