AtCoder Beginner Contest 380(A-F)

比赛链接：AtCoder Beginner Contest 380(A-F)

A - 123233

题意

给出一个数字 $N$，问这个数字中是否 $1$ 恰好出现了 $1$ 次，$2$ 恰好出现了 $2$ 次，$3$ 恰好出现了 $3$ 次。

数据范围

$100000\le N\le 999999$

思路

把 $N$ 当字符串处理，然后直接遍历字符串，统计每种数字的数量，判断是否符合条件即可

复杂度

时间复杂度 $O(|N|)$，空间复杂度 $O(|N|)$

代码实现

// Problem: A - 123233
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;void solve()
{string s;cin >> s;int cnt[10] = { 0 };for (char c : s) {cnt[c - '0']++;}if (cnt[1] == 1 && cnt[2] == 2 && cnt[3] == 3)cout << "Yes";elsecout << "No";
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}

B - Hurdle Parsing

题意

有一个长度为 $n$ 的序列 $A$，通过序列 $A$ 以如下方式构造出字符串 $S$。

• $S$ 以 ${}^{\prime }{|}^{\prime }$ 开头。 然后进行 $n$ 次操作：
• 在第 $i$ 次操作时，添加 $A_i$ 个 ${}^{\prime }{-}^{\prime }$ 到 $S$
  结尾，然后添加 ${}^{\prime }{|}^{\prime }$ 到 $S$ 结尾。

现在给出字符串 $S$，求出序列 $A$。

数据范围

$3\le |S|\le 100，n\ge 1$

思路

$A_i$ 为 $S$ 中第 $i$ 个字符 ${}^{\prime }{-}^{\prime }$ 的连续段的长度，因此可以从左到右遍历 $S$，每遇到一个字符 ${}^{\prime }{-}^{\prime }$，就以该字符为开头，向右遍历完其所在的连续段，从而得到该连续段的长度。
在遍历完一个连续段后，就直接跳到连续段之后的下一个位置遍历，这样就可以遍历到所有的连续段并得到对应长度。

复杂度

时间复杂度 $O(|S|)$，空间复杂度 $O(|S|)$

代码实现

// Problem: B - Hurdle Parsing
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;void solve()
{string s;cin >> s;int n = s.size();for (int i = 0; i < n; i++) {if (s[i] == '-') {int j = i;while (j < n && s[j] == '-')j++;cout << j - i << ' ';i = j - 1;}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}

C - Move Segment

题意

给出一个长度为 $n$ 的 $01$ 串 $S$。

定义 ${}^{\prime }1-bloc{k}^{\prime }$ 为只含 $1$ 的子串，且该子串前后都不存在 $1$，换句话说，若子串对应的区间为 $[l,r]$，则 $l=1$ 或 $S_{l-1}=0$，且 $r=n$ 或 $S_{r+1}=0$。

$01$ 串中保证至少有 $k$ 个 ${}^{\prime }1-bloc{k}^{\prime }$，现在要求把第 $k$ 个 ${}^{\prime }1-bloc{k}^{\prime }$ 移动到 第 $k-1$ 个 ${}^{\prime }1-bloc{k}^{\prime }$ 的后面，然后输出修改后的 $S$。

数据范围

$1\le n\le 5\ast 10^5,2\le k$

思路

模拟题，从左到右遍历字符串，然后记录上一个 ${}^{\prime }1-bloc{k}^{\prime }$ 的末尾下标 $pre$，当遍历到第 $k$ 个 ${}^{\prime }1-bloc{k}^{\prime }$ 时，将其移动到 $pre$ 接下去的位置即可。

复杂度

时间复杂度 $O(n)$，空间复杂度 $O(n)$

代码实现

// Problem: C - Move Segment
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;int n, k;
string s;void solve()
{cin >> n >> k >> s;int pre = -1, cnt = 0;for (int i = 0; i < n; i++) {if (s[i] == '1') {cnt++;int j = i;while (j < n && s[j] == '1') {j++;}if (cnt == k) {int len = j - i;for (int i1 = 1; i1 <= len; i1++) {s[i + i1 - 1] = '0';}for (int i1 = 1; i1 <= len; i1++) {s[pre + i1] = '1';}break;}pre = i = j - 1;}}cout << s;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}

D - Strange Mirroring

题意

给出一个字符串 $S$，对 $S$ 进行 $10^{100}$ 次如下操作：

• 新建一个字符串 $T$，通过转换 $S$ 每个位置的字母的大小写得到。

• 把 $S$ 变成 $S+T$。

现在进行 $q$ 次查询，第 $i$ 次查询给出一个数字 $k_i$，问字符串 $S$ 第 $k_i$ 个字母是什么？

数据范围

$1\le |S|,q\le 2\ast 10^5,1\le k_i\le 10^{18}$

思路

令 $n$ 为初始时 $S$ 的长度。

不考虑大小写的话，第 $k_i$ 个字母即为 $S_{k_i\%n+1}$。

现在要考虑第 $k_i$ 个字母的大小写形式。

因为不考虑大小写的情况下，每次操作都是把 $S$ 变成 $S+S$，所以第 $i$ 次操作后，$S$ 会翻倍 $i$ 次， $S$ 的长度为 $2^i\ast n$。

令 $f(w,id)$ 为第 $id$ 个位置的字母的大小写，是否与初始时 $S$ 对应位置的字母的大小写相同，$0$ 表示相同，$1$ 表示不同。
同时，第 $w$ 次操作后，恰好包含了第 $id$ 个位置，换句话说，$w$ 为满足 $2^w\ast n\ge id$ 的最小值。

在 $S$ 中前一半和后一半对应位置的大小写相反，具体的说，当 $S$ 的长度为 $2^w\ast n$ 时，第 $i$ 个位置$(1\le i\le 2^{w-1}\ast n)$ 与 第 $i+2^{w-1}\ast n$ 的位置的字母相同，大小写相反。

因此，若 $id\le 2^{w-1}\ast n$，那么 $f(w,id)=f(w-1,id)$，否则 $f(w,id)=f(w-1,id-2^{w-1}\ast n)\oplus 1$。

特别的，当 $w=0$ 时，表示未操作时的初始串，$f(0,id)=0$。

因为上一个状态的长度都是当前状态长度的一半，所以求解 $f(w,id)$ 的复杂度为 $O({\log }_{2}id)$

复杂度

时间复杂度 $O(q\ast {\log }_2{k}_i)$，空间复杂度 $O(|S|)$

代码实现

// Problem: D - Strange Mirroring
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;int n, q;
string s;// 代码实现和思路有些不同，w传的是倍数，思路中传的是指数
int f(int w, int id)
{if (w == 1) {return 0;}int len = w * n;if (id <= len / 2) {return f(w / 2, id);} else {return f(w / 2, id - w / 2 * n) ^ 1;}
}void solve()
{cin >> s >> q;n = s.size();s = ' ' + s;while (q--) {int id;cin >> id;int p = (id - 1) % n + 1;char c = s[p];for (int i = 0; i <= 63; i++) {int w = 1ll << i;if (w * n >= id) {int op = f(w, id);if (op) {if (islower(c))c = toupper(c);elsec = tolower(c);}break;}}cout << c << ' ';}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}

E - 1D Bucket Tool

题意

有 $n$ 个单元格，初始时第 $i$ 个单元格的颜色为 $i$，第 $i$ 个单元格与第 $i+1$ 个单元格相邻。

进行 $q$ 次查询，查询有两种情况：

1. 修改第 $x$ 个单元格所在的同色连通块的颜色为 $c$。
2. 输出颜色为 $c$ 的单元格有多少个。

数据范围

$1\le n\le 5\ast 10^5,1\le q\le 2\ast 10^5$

思路

考虑用并查集维护同色连通块，并查集上需要维护连通块的单元格数，左边界和右边界。

对于操作 $1$，首先第 $x$ 个单元格的颜色的单元格数会减少所在连通块的单元格数，然后把颜色 $c$ 的单元格数增加所在连通块的单元格数。

如果修改颜色后，和左边连通块或者右边连通块颜色相同，则合并在一起。

对于操作 $2$，则直接输出记录的对应颜色单元格数即可。

复杂度

时间复杂度 $O(n+q)$，空间复杂度 $O(n)$

代码实现

// Problem: E - 1D Bucket Tool
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;int n, q;
int p[N], lx[N], rx[N], sz[N], col[N], cnt[N];int find(int x)
{return x == p[x] ? x : p[x] = find(p[x]);
}void merge(int x, int y)
{x = find(x), y = find(y);if (x != y) {p[x] = y;lx[y] = min(lx[y], lx[x]);rx[y] = max(rx[y], rx[x]);sz[y] += sz[x];}
}void solve()
{cin >> n >> q;for (int i = 1; i <= n; i++) {cnt[i] = sz[i] = 1;p[i] = lx[i] = rx[i] = col[i] = i;}while (q--) {int op;cin >> op;if (op == 1) {int x, c;cin >> x >> c;x = find(x);cnt[col[x]] -= sz[x];col[x] = c;cnt[c] += sz[x];if (lx[x] != 1) {int fl = find(lx[x] - 1);if (col[fl] == c) {merge(x, fl);}}if (rx[x] != n) {int fr = find(rx[x] + 1);if (col[fr] == c) {merge(x, fr);}}} else {int c;cin >> c;cout << cnt[c] << '\n';}}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}

F - Exchange Game

题意

$Takahashi$ 有 $n$ 张卡片，$Aoki$ 有 $m$ 张卡片，初始时桌子上有 $L$ 张卡片，每张卡片上都有数字。

$Takahashi$ 和 $Aoki$ 先后出牌，$Takahashi$ 先手出牌，当前轮到某人出牌时，如果无牌可出则输，否则，可以出一张牌，如果当前桌子上有一张比刚出的牌更小的牌，则当前的出牌人可以拿起这张牌。

问哪个人必赢？

数据范围

$n+m+L\le 12$，牌上的数字为正数，不超过 $10^9$

思路

注意到总牌数很少，对应的情况数必然不超过 $3^{n+m+L}$，最大为 $531,441$，因此可以记忆化搜索所有的博弈状态，从而确定哪个人必赢。

其中可以加个小剪枝，就是如果要在出牌后，在桌子上拿牌的话，取小于刚出的牌的最大的牌是最优的，因为取得的牌越大，后面再打出就可能可以再次在桌上取牌，从而保持有牌的状态避免失败。

复杂度

时间复杂度 $O(3^{n+m+L})$，空间复杂度 $O(3^{n+m+L})$

代码实现

// Problem: F - Exchange Game
// Contest: AtCoder - AtCoder Beginner Contest 380
// URL: https://atcoder.jp/contests/abc380/tasks/abc380_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;#define int long longconst int N = 1e6 + 5;int n, m, k;map<array<multiset<int>, 3>, int> f[2];int dfs(array<multiset<int>, 3> st, int op)
{if (f[op].count(st))return f[op][st];if (!st[op].size())return f[op][st] = 0;for (int x : st[op]) {auto it = st[2].lower_bound(x);int y = -1;if (st[2].size() && it != st[2].begin()) {y = *(--it);}array<multiset<int>, 3> ne = st;ne[op].erase(ne[op].lower_bound(x));if (y != -1) {ne[2].erase(ne[2].lower_bound(y));ne[op].insert(y);}ne[2].insert(x);if (!dfs(ne, op ^ 1))return f[op][st] = 1;}return f[op][st] = 0;
}void solve()
{cin >> n >> m >> k;array<multiset<int>, 3> st;for (int i = 0; i < n; i++) {int x;cin >> x;st[0].insert(x);}for (int i = 0; i < m; i++) {int x;cin >> x;st[1].insert(x);}for (int i = 0; i < k; i++) {int x;cin >> x;st[2].insert(x);}int flag = dfs(st, 0);cout << (flag ? "Takahashi" : "Aoki") << '\n';
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T--) {solve();}
}