企业官网建设流程全解析

题目描述

SpaceRecon\texttt{SpaceRecon}SpaceRecon是一款201120112011年流行的实时策略游戏，支持三种种族。游戏内置了Actionweb\texttt{Actionweb}Actionweb平台用于举办2M2^{M}2M名玩家参加的锦标赛。锦标赛采用单败淘汰制，共MMM轮。前RRR轮（RRR未公开）为三局两胜制（需赢222局晋级），剩余M−RM - RM−R轮为五局三胜制（需赢333局晋级）。每轮比赛胜者晋级，败者淘汰，不会进行不必要的对局。

赛后，平台公布每位玩家的昵称以及他们在整个锦标赛中赢得的单局总场次（即所有轮次中赢得的对局数之和）。给定这些数据，你需要推断每位玩家实际晋级到了第几轮（即赢了多少轮），并按照晋级轮数降序输出玩家昵称；若晋级轮数相同，则按昵称字典序升序输出。

输入格式

第一行一个整数NNN（1≤N≤1001 \le N \le 1001≤N≤100），表示测试用例数。
每个测试用例以一行整数MMM（1≤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，其中k=Mk=Mk=M表示冠军）。由于前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)

局比赛。若k<Mk < Mk<M，说明他在第k+1k+1k+1轮被淘汰，而他在被淘汰的那一轮中还可以赢得一些局（但未达到晋级所需局数）。被淘汰的那一轮如果是BO3\texttt{BO3}BO3，他最多还能赢111局；如果是BO5\texttt{BO5}BO5，最多还能赢222局。因此，对于k<Mk < Mk<M，他的总胜场www必须满足：

minWins(k)≤w≤minWins(k)+extra(k+1) \text{minWins}(k) \le w \le \text{minWins}(k) + \text{extra}(k+1)minWins(k)≤w≤minWins(k)+extra(k+1)

其中extra(r)=1\text{extra}(r) = 1extra(r)=1（若r≤Rr \le Rr≤R）或222（若r>Rr > Rr>R）。注意r=k+1r = k+1r=k+1是他被淘汰的轮次号。
对于冠军（k=Mk=Mk=M），则总胜场恰好等于minWins(M)\text{minWins}(M)minWins(M)，不存在额外胜场。

由于上述区间互不重叠（可以证明），因此对于一个给定的RRR，每个玩家的总胜场www唯一对应一个kkk。我们可以枚举所有可能的RRR（0≤R≤M0 \le R \le M0≤R≤M），对每个RRR计算出每个玩家的kkk，然后检查这些kkk的频数是否符合单败淘汰赛的客观规律：在2M2^{M}2M名玩家的锦标赛中，晋级kkk轮（0≤k<M0 \le k < M0≤k<M）的玩家数必须为2M−1−k2^{M-1-k}2M−1−k，而冠军（k=Mk=Mk=M）的人数必须为111。如果某个RRR满足上述所有条件，则这个RRR就是合法的，对应的kkk就是每位玩家的实际晋级轮数。

解题思路

1. 预处理区间：对于给定的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)（对k<Mk<Mk<M为minWins(k)+extra(k+1)\text{minWins}(k)+\text{extra}(k+1)minWins(k)+extra(k+1)，对k=Mk=Mk=M就是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。

2. 枚举合法RRR：
   外层循环R=0…MR = 0 \dots MR=0…M，内层对所有玩家调用getRound\texttt{getRound}getRound，如果任何玩家返回−1-1−1，则RRR无效。否则统计频数数组cnt[k]\textit{cnt}[k]cnt[k]。检查对于所有0≤k<M0 \le k < M0≤k<M，是否有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并跳出枚举。

3. 排序输出：将每个玩家的晋级轮数kkk作为排序关键字，按kkk降序排列；若kkk相同，按昵称字典序升序排列。依次输出昵称。

4. 复杂度分析：每个测试用例中，枚举RRR的次数为O(M)O(M)O(M)（最多111111次），每次对2M2^{M}2M个玩家（最多102410241024个）计算kkk，每次计算需遍历M+1M+1M+1个可能值，因此总体时间复杂度为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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structPlayer{string handle;intwins;introundSurvived;// 晋级轮数 k};// 计算给定胜场 wins 在总轮数 M、前 R 轮为 BO3 的情况下，玩家晋级的轮数 kintgetRound(intwins,intM,intR){for(intk=0;k<=M;++k){intminW=2*min(k,R)+3*max(0,k-R);// 晋级 k 轮至少需要的胜场intmaxW;if(k==M){maxW=minW;// 冠军没有淘汰轮，胜场固定}else{intnextRound=k+1;// 被淘汰的轮次intmaxExtra=(nextRound<=R)?1:2;// BO3 最多赢 1 局，BO5 最多赢 2 局maxW=minW+maxExtra;}if(wins>=minW&&wins<=maxW)returnk;}return-1;// 无法匹配}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cin>>N;while(N--){intM;cin>>M;inttotal=1<<M;vector<Player>players(total);for(inti=0;i<total;++i){cin>>players[i].handle>>players[i].wins;}intvalidR=-1;vector<int>rounds(total);// 枚举 Rfor(intR=0;R<=M;++R){vector<int>cnt(M+1,0);boolok=true;vector<int>curRounds(total);for(inti=0;i<total;++i){intk=getRound(players[i].wins,M,R);if(k==-1){ok=false;break;}curRounds[i]=k;cnt[k]++;}if(!ok)continue;// 检查频数是否符合淘汰赛结构for(intk=0;k<M;++k){if(cnt[k]!=(1<<(M-1-k))){ok=false;break;}}if(ok&&cnt[M]==1){validR=R;rounds=curRounds;break;}}// 将计算结果赋给玩家for(inti=0;i<total;++i)players[i].roundSurvived=rounds[i];// 排序：先按晋级轮数降序，再按昵称字典序升序sort(players.begin(),players.end(),[](constPlayer&a,constPlayer&b){if(a.roundSurvived!=b.roundSurvived)returna.roundSurvived>b.roundSurvived;returna.handle<b.handle;});// 输出for(constauto&p:players)cout<<p.handle<<'\n';}return0;}

总结

本题的核心是逆向推断锦标赛轮次。由于RRR未知，但每位玩家的总胜场提供了足够信息，我们可以枚举RRR并利用晋级轮数与胜场数的单调区间映射，再通过单败淘汰赛的固有频数分布来验证合法性。这种方法避免了复杂的树结构重建，直接利用数量关系，实现了简洁高效的判定。
技巧上，注意区间不重叠的性质是枚举可行的前提；同时，由于MMM很小（≤10\le 10≤10），枚举所有可能RRR是完全可行的。该题思路同样适用于其他存在未知规则参数的类似问题。