算法
(模拟、排序) $O(MN_2\log N_2)$
题意:
有 $2n$ 个人进行 $m$ 轮猜拳,每轮猜拳中 $n$ 对排名相邻的人两两进行比赛,每轮比赛结束更新排名,规则如下:
- 赢更多场的人排在前,如果两个人赢的场是一样多,那么编号更小的靠前
给出 $2n$ 个人将会在每轮中所出的手势,输出 $m$ 轮猜拳后这 $2n$ 个人的排名。
分析:
每一回合比赛结束后,我们可以对每个玩家按 $(-$获胜次数, $id)$ 从小到大排序
G C P
0 1 2
a 0 1 2
b 1 2 0
b - a ≡ 1 (mod 3) 等价于 a - b ≡ 2 (mod 3)
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using P = std::pair<int, int>;
bool win(char a, char b) {
if (a == 'G' and b == 'C') return true;
if (a == 'C' and b == 'P') return true;
if (a == 'P' and b == 'G') return true;
return false;
}
int main() {
int n, m;
cin >> n >> m;
int n2 = n * 2;
vector<string> a(n2);
rep(i, n2) cin >> a[i];
vector<P> d(n2);
rep(i, n2) d[i] = P(0, i);
rep(mi, m) {
rep(ni, n) {
int i = ni * 2, j = ni * 2 + 1;
int ai = d[i].second, aj = d[j].second;
if (win(a[ai][mi], a[aj][mi])) d[i].first--;
if (win(a[aj][mi], a[ai][mi])) d[j].first--;
}
sort(d.begin(), d.end());
}
rep(i, n2) cout << d[i].second + 1 << '\n';
return 0;
}