A - 123233
模拟即可。
点击查看代码
void solve() {
int cnt[10]{};
int n;
std::cin >> n;
while (n) {
++ cnt[n % 10];
n /= 10;
}
for (int i = 1; i <= 3; ++ i) {
if (cnt[i] != i) {
std::cout << "No\n";
return;
}
}
std::cout << "Yes\n";
}
B - Hurdle Parsing
题意：给你一个字符串，用'|'，分割了一些'-'，问每一段'-'的个数是多少。
模拟。
点击查看代码
void solve() {
std::string s;
std::cin >> s;
for (int i = 0; i + 1< s.size(); ++ i) {
int j = i + 1;
while (j < s.size() && s[j] == '-') {
++ j;
}
std::cout << j - i - 1 << " ";
i = j - 1;
}
std::cout << "\n";
}
C - Move Segment
题意：给你一个\(01\)串，把第\(k\)个\(1\)的连通块移到前面\(1\)的后面。
模拟。
点击查看代码
void solve() {
int n, k;
std::cin >> n >> k;
std::string s;
std::cin >> s;
int cnt = s[0] == '1', last = -1;
for (int i = 0; i < n; ++ i) {
if (s[i] == '0' && s[i + 1] == '1') {
++ cnt;
if (cnt == k) {
int j = i + 1;
++ last;
while (j < n && s[j] == '1') {
std::swap(s[j], s[last]);
++ j, ++ last;
}
break;
}
}
if (s[i] == '1') {
last = i;
}
}
std::cout << s << "\n";
}
D - Strange Mirroring
题意：对于一个字符串，每次把它大小写改变然后接到后面，重复\(10^{100}\)次，\(q\)次询问，每次问第\(k\)个字符。
模拟单个字符发现，每次长度是成倍数增长，第\(n + 2^in\)个地方一定是取反的，因为这个地方就是第一个字符变过来的，这提示我们找到\(k\)在的块，然后就变成了一个子问题，看要找多少次记录取反次数就行。
点击查看代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
int q;
std::cin >> q;
while (q -- ) {
i64 x;
std::cin >> x;
int cnt = 0;
while (x > n) {
i64 k = 1;
while ((__int128)k * n < x) {
k *= 2;
}
x -= (__int128)k * n / 2;
++ cnt;
}
char c = s[x - 1];
if (cnt & 1) {
c = c >= 'a' ? c - 32 : c + 32;
}
std::cout << c << " \n"[!q];
}
}
E - 1D Bucket Tool
题意：\(n\)个格子每个格子的颜色为\(i\)，有两种操作：
- 让\(x\)和所有与他相邻并且颜色相同的格子颜色都变成\(y\)。
- 询问颜色为\(x\)的有多少个格子。
容易想到用并查集维护颜色相同的块，那么当改变一个格子颜色时，判断是不是要和这个块最左边位置减一的位置是不是同一个颜色，和这个块最右边位置加一的位置是不是同一个颜色。那么我们需要用并查集记录一个集合的颜色，个数，最左边位置和最右边位置。
点击查看代码
struct DSU {
std::vector<int> fa, cnt;
DSU(int _n) {
fa.assign(_n + 1, 0);
cnt.assign(_n + 1, 1);
std::iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) {
return;
}
fa[y] = x;
cnt[x] += cnt[y];
cnt[y] = 0;
}
int same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return cnt[find(x)];
}
};
void solve() {
int n, q;
std::cin >> n >> q;
DSU ds(n);
std::vector<int> id(n + 1), min(n + 1), max(n + 1), cnt(n + 1, 1);
std::iota(id.begin(), id.end(), 0);
std::iota(min.begin(), min.end(), 0);
std::iota(max.begin(), max.end(), 0);
while (q -- ) {
int op;
std::cin >> op;
if (op == 1) {
int x, y;
std::cin >> x >> y;
if (id[ds.find(x)] != y) {
cnt[y] += ds.size(x);
cnt[id[ds.find(x)]] -= ds.size(x);
id[ds.find(x)] = y;
int l = min[ds.find(x)] - 1, r = max[ds.find(x)] + 1;
if (l && id[ds.find(l)] == y) {
min[ds.find(x)] = min[ds.find(l)];
ds.merge(x, l);
}
if (r <= n && id[ds.find(r)] == y) {
max[ds.find(x)] = max[ds.find(r)];
ds.merge(x, r);
}
}
} else {
int x;
std::cin >> x;
std::cout << cnt[x] << "\n";
}
}
}
F - Exchange Game
题意：有两个人，第一个人有\(n\)张牌，第二个人有\(m\)张牌，桌子上还有\(k\)张牌。两个人轮流出牌，如果桌子上有一张牌小于当前这个人出的牌，那么当前这个人可以拿走这张牌。问第一个人能不能赢。
注意到\(n+m+k<=12\)，想到爆搜，定义\(dfs(u, x, y), (u \in \{0, 1\})\)为出牌人为\(u\)第一个拥有牌的状态为\(x\)，第二个为\(y\)，这里的\(x,y\)都是二进制数，利用状压表示有没有某一张牌。那么每次枚举当前这个人出哪张牌和是否拿走某张牌。和\(sg\)函数一样，不能走为必败态，如果当前状态能走到一个必败态则是必胜态，否则时必败态。
点击查看代码
const int N = 1 << 12;
int f[2][N][N];
int a[12];
int n, m, k;
int dfs(int u, int x, int y) {
if (f[u][x][y] != -1) {
return f[u][x][y];
}
int c = ~(x | y);
int res = 0;
if (u == 0) {
for (int i = 0; i < n + m + k; ++ i) {
if (x >> i & 1) {
res |= !dfs(u ^ 1, x - (1 << i), y);
for (int j = 0; j < n + m + k; ++ j) {
if ((c >> j & 1) && a[j] < a[i]) {
res |= !dfs(u ^ 1, x - (1 << i) + (1 << j), y);
}
}
}
}
} else {
for (int i = 0; i < n + m + k; ++ i) {
if (y >> i & 1) {
res |= !dfs(u ^ 1, x, y - (1 << i));
for (int j = 0; j < n + m + k; ++ j) {
if ((c >> j & 1) && a[j] < a[i]) {
res |= !dfs(u ^ 1, x, y - (1 << i) + (1 << j));
}
}
}
}
}
f[u][x][y] = res;
return res;
}