2022 CCPC 广州站
H. GameX
题目描述
Alice 和 Bob 在玩一个游戏。
游戏开始时，有一个整数集合 \(S = {a_1, a_2, a_3,...,a_n}\)。Alice 和 Bob 交替进行 \(k\) 轮如下操作：
每次操作，玩家可以选择一个整数 \(x\)，并将 \(x\) 插入 \(S\) 中。注意，每轮中 Alice 和 Bob 都可以操作，即每轮会插入两个数。
游戏结束后，如果 \(\text{MEX}(S)\) 是偶数，则 Alice 获胜，否则 Bob 获胜。
输入
第一行包含一个正整数 \(T\) ( \(1\le T\le 10^4\) )，表示测试用例的数量。
对于每个测试用例
- 第一行包含两个整数 \(n, k\) ( \(1\le n,k\le 2\times 10^5\) )，分别表示游戏开始前 \(S\) 的大小和回合数。
- 下一行包含 \(n\) 个不同的自然数 \(a_1,a_2,\cdots,a_n\) （ \(0\le a_i\le 10^6\) ）。 \(0\le a_i\le 10^6\) ），表示 \(S\) 。
可以保证 \(\sum n, \sum k\le 2\times 10^5\) 。
输出
对于每个测试用例，如果 Alice 获胜，则输出 Alice，否则输出 Bob。
题解
比较简单的签到题，对于 Alice，她期望最终的 \(\text{MEX}(S)\) 是偶数，那么她的最优策略一定是在每一轮插入当前最小的未出现的奇数；同样，Bob 的最优策略是在每一轮插入当前最小的未出现的偶数。
考虑到数据范围 \(\sum k\le 2\times 10^5\)，可以直接模拟这个过程，最终给出答案即可。
AC 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
void solve() {
int n, k;
cin >> n >> k;
bitset<2 * N> a;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[x] = 1;
}
int alice = 1, bob = 0;
for (int i = 0; i < k; i++) {
while (a[alice]) {
alice += 2;
}
a[alice] = 1;
while (a[bob]) {
bob += 2;
}
a[bob] = 1;
}
for (int i = 0; i < 2 * N; i++) {
if (!a[i]) {
if (i % 2 == 0) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
return;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
L. Station of Fate
题目描述
有 \(n\) 人站在 \(m\) 站，排成 \(m\) 队。
你不知道哪个人在哪个车站，也不知道他们排队的顺序，因此你想计算不同方案的数量。当且仅当有一个车站的队列由不同的人组成或有不同的顺序时，两个方案才被认为是不同的。
计算不同方案的数量，对 \(998, 244, 353\) 取模。
输入
第一行包含一个整数 \(T\) ( \(1\le T\le 100\) )，表示测试用例的数量。然后是 \(T\) 个测试用例。
每个测试用例包含一行，其中包含两个整数 \(n, m\) ( \(1 \le m \le n \le 10^5\) )。
输出
针对每个测试用例，输出不同方案的数量，取模 \(998\, 244\, 353\) 。
题解
一个比较简单的组合数学签到。
首先考虑对 \(n\) 个人进行排列，有 \(n!\) 种方案；然后使用插板法将 \(n\) 个人分成 \(m\) 组，有 \(\binom{n-1}{m-1}\) 种方案。
所以答案是 \(n! \times \binom{n-1}{m-1} \mod 998244353\)。
AC 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
const int mod = 998244353;
int fract[N];
void init() {
fract[0] = 1;
for (int i = 1; i < N; i++) {
fract[i] = (fract[i - 1] * i) % mod;
}
}
int fastpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = (res * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int inv(int x) {
return fastpow(x, mod - 2);
}
void solve() {
int n, m;
cin >> n >> m;
int ans = fract[n] * fract[n - 1] % mod * inv(fract[n - m]) % mod * inv(fract[m - 1]) % mod;
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
E. Elevator
题目描述
在一幢有 \(m\) 层、编号为 \(1\) 至 \(m\) 的大楼中，有 \(n\) 部电梯参加从 \(0\) 时刻开始的速度比赛。
第 \(i\) 电梯将在第 \(x_i\) 秒从 \(1\) 层出发，以每秒 \(1\) 层的速度上升。此外，除了 \(1\) 层和 \(m\) 层之外，每一层都有一个按钮，如果按下按钮，第一部到达该层的电梯会停止 \(1\) 秒。如果有多台电梯同时到达某一楼层，则只有编号最小的电梯才会被视为第一台电梯。现在没有按下按钮，但您可以在比赛开始前按下某些楼层的按钮。请注意，比赛开始后您不能按按钮。
现在你想知道，你是否能够通过按下按钮来操纵比赛，使 \(i\) 个电梯第一个到达 \(m\) 层，如果可以，你至少要按下多少个按钮。如果有多台电梯同时到达 \(m\) 层，则只有编号最小的电梯才会被视为第一台电梯。
输入
第一行包含两个正整数 \(n,m\) ( \(1\le n\le 5 \cdot 10^5,2\le m\le 10^9\) )，分别表示电梯和楼层的数量。
第二行包含 \(n\) 个正整数 \(x_1,\ldots,x_n\) ( \(1 \le x_i \le 10^9\) )，表示电梯的启动时间。
输出
输出 \(n\) 行。 第 \(i\) 行应包含要使第 \(i\) 个电梯第一个到达 \(m\) 层所需按下的最少按钮数。如果不可能，输出 \(-1\) 。
题解
首先考虑将所有电梯按照出发时间排序，如果出发时间相同，按照编号从小到大的顺序排序。
此时，排名第一的电梯无需按下任何按钮，就可以获得第一名。
对于排名第二的电梯，我们需要阻碍排名第一的电梯。如果这个电梯编号更小，那么我们要在抵达 \(m\) 层之间的路上按下足够多的按钮，使得排名第二的电梯可以反超排名第一，如果这个电梯编号更大，那么我们只需要使得两者并列向前即可。
对于排名第三的电梯，我们则需要阻碍前面两个电梯...这个过程可以以此类推下去。
设排序后的出发时间序列是 \(t_1, t_2, t_3, ..., t_n\)，那么排名第 \(i\) 的电梯需要按下的按钮个数是
其中，\(presum_i\) 表示前 \(i\) 个电梯出发时间的前缀和，\(inv_i\) 表示前 \(i - 1\) 个电梯中，电梯序号大于第 \(i\) 个电梯序号的电梯个数，即电梯序号数组上以第 \(i\) 个元素结尾的逆序对个数。
显然，该问题无解当且仅当 \(1\) 层至 \(m\) 层的层数不足以布置 \(ans\) 多个按钮。
电梯总数 \(n\) 满足 \(1\le n\le 5 \cdot 10^5\)，可以使用树状数组 \(n \log{n}\) 维护逆序对，总体复杂度 \(O(n \log{n})\)， 可以通过该题。
AC 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int tree[N];
int lowbit(int x) { return x & -x; }
void update(int x, int v) {
for (int i = x; i < N; i += lowbit(i)) {
tree[i] += v;
}
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
ans += tree[i];
}
return ans;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
vector<int> idx(n);
vector<int> ans(n);
vector<int> presum(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
idx[i] = i;
}
sort(idx.begin(), idx.end(), [&](int i, int j) {
if (a[i] == a[j]) {
return i < j;
}
return a[i] < a[j];
});
sort(a.begin(), a.end());
presum[0] = 0;
for (int i = 0; i < n; i++) {
presum[i + 1] = presum[i] + a[i];
}
for (int i = 0; i < n; i++) {
update(idx[i] + 1, 1);
int inv = i + 1 - query(idx[i] + 1);
int pref = presum[i];
int res = i * a[i] + i - pref - inv;
ans[idx[i]] = (res <= m - 2 ? res : -1);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}