codeforces Div1 941 AB
A. Everything Nim
爱丽丝和鲍勃正在玩一个关于 $n$ 堆石头的游戏。轮到每个棋手时,他们都会选择一个正整数 $k$ ,这个正整数最多等于最小的非空堆的大小,然后从每个非空堆中一次性取出 $k$ 个石子。第一个无法下棋的棋手(因为所有棋子都是空的)输。
既然爱丽丝先下,如果双方都以最佳方式下棋,谁会赢得比赛?
对于每个测试用例,打印一行,写上获胜者的名字(假设双方都发挥出最佳水平)。如果 Alice 获胜,则打印 “Alice”,否则打印 “Bob”(不带引号)。
code
我们先跑一下 去重
因为 相同大小的堆 是重复的, 不起作用
如果 每一个堆的大小都比 之前的堆 大小 大1
那么 比赛的过程就是确定的 比赛的结果也是确定是
如果一个堆的大小比 之前的堆大小 大不止1
那么有两种选择 , 将这个堆减的只剩1
将这个堆剪完
这两种选择必定有一种是 必胜态,有一种是必败态
所以第一个进入该局面的人是 必胜态
那么就解决了这道题
code
https://codeforces.com/contest/1965/submission/258568135
// Codeforces - Codeforces Round 941 (Div. 1) A. Everything Nim
// https://codeforces.com/contest/1965/problem/A 2024-04-28 21:15:16
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
set<int> S;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
S.emplace(x);
}
vector<int> a;
a.emplace_back(0);
for (auto it : S) {
a.emplace_back(it);
}
n = a.size() - 1;
vector<int> d(n + 1);
for (int i = 1; i <= n; i++) {
d[i] = a[i] - a[i - 1];
}
bool falg = false;
for (int i = 1; i <= n; i++) {
if (d[i] > 1) {
falg = true;
break;
}
}
if (!falg) { // 无改变的机会
if (n & 1)
cout << "Alice\n"; // 奇数次运动结束战斗
else
cout << "Bob\n";
} else {
int idx = 0;
for (int i = 1; i <= n; i++) {
if (d[i] > 1) {
idx = i;
break;
}
}
if (idx & 1)
cout << "Alice\n";
else
cout << "Bob\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
B. Missing Subsequence Sum
给你两个整数 $n$ 和 $k$ 。求一个大小最多为 $25$ 的非负整数序列 $a$ ,使得下列条件成立。
- 没有和为 $k$ 的 $a$ 的子序列。
- 对于 $v \ne k$ 所在的所有 $1 \le v \le n$ ,存在一个和为 $v$ 的 $a$ 的子序列。
如果 $a$ 可以通过删除几个(可能是零个或全部)元素而得到 $b$ ,且不改变其余元素的顺序,那么序列 $b$ 就是 $a$ 的子序列。例如, $[5, 2, 3]$ 是 $[1, 5, 7, 8, 2, 4, 3]$ 的子序列。
可以证明,在给定的约束条件下,解总是存在的。
think
我们可以手玩一下
+1
[1,1]
+1
[1,2]
+2
[1,4]
+4
[1,8]
+8
[1,16]
我们可以通过这个策略来 充填 [1,n]
等到要铺到 k 的时候我们 特判一下
不去铺 k
而用 一次操作 铺满 [1,k-1]
再用一次操作 铺满 [k+1,$2^x$]
然后就可以继续重复上面的操作了
便可以解决这道题
code
https://codeforces.com/contest/1965/submission/258570982
// Codeforces - Codeforces Round 941 (Div. 1) B. Missing Subsequence Sum
// https://codeforces.com/contest/1965/problem/B 2024-04-28 21:27:49
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, k;
int high_dig(int x) {
int res = 0;
while (x) {
x /= 2;
res++;
}
return res;
}
void solve() {
cin >> n >> k;
vector<int> ans;
ans.emplace_back((1LL << high_dig(k)) + k);
int idx = 0;
while ((1LL << (idx + 1LL)) - 1 < k) {
ans.emplace_back(1LL << idx++);
}
// for (auto it : ans) cout << it << " ";
// cout << "\n";
if (k - 1 != ((1LL << idx) - 1))
ans.emplace_back(k - 1 - ((1LL << (idx)) - 1LL));
ans.emplace_back(k + 1);
idx++;
for (int i = idx; i <= 23 and ans.size() < 25; i++) {
ans.emplace_back(1LL << i);
}
cout << ans.size() << "\n";
for (auto it : ans) cout << it << " ";
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}