\(solved: A B C D E F G\)
A – Past ABCs
用sacnf直接读入后三个数字即可, 然后判断数字是否在 \(\left[1, 349\right]\), 注意还有个条件是不能为 \(316\).
void solve() {
int a;
if (scanf("ABC%d", &a) && a <= 349 && a >= 1 && a != 316)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}B – Dentist Aoki
一开始全为 \(1\), 然后我们对于每个操作做模 \(2\) 加法, 最后计算 \(1\) 的个数.
void solve() {
int n, q;
cin >> n >> q;
vector<int> arr(n + 1, 1);
arr[0] = 0;
for (int i = 0; i < q; i++){
int t;
cin >> t;
arr[t] ^=1;
}
cout << accumulate(arr.begin(),arr.end(),0LL) << '\n';
}C – Sort
要用最多 \(n – 1\) 次 \(swap\) 操作完成对一个排列的排序.
显然只要贪心的让每一位复位即可.
void solve() {
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<int> d(n + 1);
for (int i = 1; i <= n; i++) d[arr[i]] = i;
vector<pair<int, int>> ans;
for (int i = 1; i <= n; i++) {
if (d[i] == i)
continue;
else {
auto &x = arr[i];
auto &y = arr[d[i]];
ans.push_back({i,d[i]});
d[arr[i]] = d[i];
swap(x,y);
}
}
cout << ans.size() << '\n';
for (auto [x,y]:ans) {
cout << x << ' ' << y << '\n';
}
}D – New Friends
就是朋友的性质可以传递, 那显然一个大小为 \(n\) 的联通块最多有 \(\frac{n \times (n – 1)}{2}\) 对朋友关系, 直接对于每个连通块用最大值减去原本有的朋友关系对数即可.
class DSU {
public:
std::vector<int> d, siz, cnt;
DSU(std::size_t size) : d(size + 1), siz(size + 1, 1), cnt(size + 1) {
std::iota(d.begin(), d.end(), 0);
}
int root(int u) {
return d[u] == u ? u : d[u] = root(d[u]);
}
void bind(int u, int v) {
u = root(u), v = root(v);
if (u != v) {
cnt[v] += cnt[u] + 1;
siz[v] += siz[u];
d[root(u)] = root(v);
} else
cnt[u]++;
}
};
void solve() {
int n, m;
cin >> n >> m;
LL ans = 0;
DSU dsu(n);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
dsu.bind(a, b);
}
for (int i = 1; i <= n; i++) {
if (dsu.root(i) == i) {
ans += 1LL * dsu.siz[i] * (dsu.siz[i] - 1) / 2 - dsu.cnt[i];
deb(dsu.siz[i], dsu.cnt[i]);
}
}
cout << ans << '\n';
}E – Toward 0
已知 \(N, X, Y, A\), 要求将 \(N\) 变为 \(0\) 的期望花费.
两种操作:
- 花费 \(X\), 让 \(N\) 变为 \(\left\lfloor \frac{N}{A} \right\rfloor\).
- 花费 \(Y\), 让 \(N\) 变为 \(\left\lfloor \frac{N}{b} \right\rfloor\), 其中 \(b\) 等可能的为 \(\left[1, 6\right]\).
显然的, 当第二种操作的 \(b\) 随机到 \(1\) 的时候是完全没用的, 我们将这种情况的花费的期望合并到 \(b\) 为 \(\left[2, 6\right]\) 中.
设 \(f(x)\) 为 \(x\) 变到 \(0\) 的期望花费, 则有:
\(f(N) = Y + \frac{1}{6}\times f(\left\lfloor \frac{N}{1} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{3} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{4} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{5} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{6} \right\rfloor)\).
即:
\(f(N) = Y + \frac{1}{6}\times f(N) + \frac{1}{6}\times f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{3} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{4} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{5} \right\rfloor) + \frac{1}{6}\times f(\left\lfloor \frac{N}{6} \right\rfloor)\).
转化下得到:
\(f(N) = \frac{6}{5} \times Y + \frac{1}{5}\times f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{5}\times f(\left\lfloor \frac{N}{3} \right\rfloor) + \frac{1}{5}\times f(\left\lfloor \frac{N}{4} \right\rfloor) + \frac{1}{5}\times f(\left\lfloor \frac{N}{5} \right\rfloor) + \frac{1}{5}\times f(\left\lfloor \frac{N}{6} \right\rfloor)\).
直接记忆化搜索, 发现我们除的都是 \(2, 3, 5\) 的倍数, 所以最多有 \(log(N)^3\) 种 \(f(x)\), 大胆搜即可.
void solve() {
LL n, a;
double x, y;
cin >> n >> a >> x >> y;
map<LL, double> cache;
cache[0] = 0;
auto get = [&](auto self, LL n) -> double {
if (cache.count(n))
return cache[n];
return cache[n] = min(self(self, n / a) + x,
(self(self, n / 2) + self(self, n / 3) + self(self, n / 4) + self(self, n / 5) + self(self, n / 6)) / 5 + y * 6 / 5);
};
cout << fixed << setprecision(15) << get(get, n) << '\n';
}F – Transpose
字符串转化.
先用栈进行括号匹配, 记录下标为 \(i\) 括号对应的是 \(nex[i]\) 的括号.
然后就可以直接 \(dfs\), 记当前位置为 \(i\), \(dfs\) 开始位置为 \(begin\), 然后到 \(end\) 停止, 走的方向为 \(d\), 是否要大小写交换为 \(change\).
void dfs(int begin, int d, int end, int change, const string &s, const vector<int> &nex);
开始时直接 \(dfs(0, 1, len, 0, s, nex)\)
遇到 '(' 和 ')' 的时候进入下一层 \(dfs\), 这里起点就应该为 \(nex[i] – d\), 方向 \(-d\), 终点 \(i\), 是否交换 \(change \oplus 1\). \(dfs\) 完了记得将 \(i\) 置为 \(nex[i]\), 然后继续走, 直到 \(end\).
void dfs(int begin, int d, int end, int change, const string &s, const vector<int> &nex) {
for (int i = begin; i != end; i += d) {
if (s[i] == '(' || s[i] == ')')
dfs(nex[i] - d, -d, i, change ^ 1, s, nex), i = nex[i];
else {
if (change) {
cout << char(islower(s[i]) ? s[i] - 'a' + 'A' : s[i] - 'A' + 'a');
} else {
cout << s[i];
}
}
}
}
void solve() {
string s;
cin >> s;
vector<int> nex(s.size());
stack<int> sta;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(')
sta.push(i);
else if (s[i] == ')')
nex[i] = sta.top(), nex[sta.top()] = i, sta.pop();
}
dfs(0, 1, s.size(), 0, s, nex);
cout << '\n';
}G – Mediator
强制在线, 逐渐将一些点连成森林, 同时询问两点 \(x, y\) 是否同时与一个点相邻.
当询问的两个点在不同联通块时, 显然是无的. 在同一个联通块时, 选一个点作为树根, 那么查询的点一定是 \(x, y\) 的共同父亲, 或者是其中一个点的儿子, 另一个点的父亲.
那么考虑怎么在合并的时候维护父子关系.
一共 \(n\) 个点, 一开始都是独立的点, 直接启发式合并, 每次将小的树连到大的上, 这样每个点最多只要计算 \(log(n)\) 次父亲, 总复杂度为 \(nlog(n)\).
class DSU {
public:
std::vector<int> d, siz;
DSU(std::size_t size) : d(size + 1), siz(size + 1, 1) {
std::iota(d.begin(), d.end(), 0);
}
int root(int u) {
return d[u] == u ? u : d[u] = root(d[u]);
}
void bind(int u, int v) {
u = root(u), v = root(v);
siz[v] += siz[u];
d[u] = v;
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<vector<int>> gra(n + 1);
vector<int> fa(n + 1);
int lastans = 0;
DSU dsu(n);
auto dfs = [&](auto self, int u, int pre) -> void {
fa[u] = pre;
for (auto v : gra[u]) {
if (v != pre)
self(self, v, u);
}
};
for (int i = 0; i < q; i++) {
int a, b, c;
cin >> a >> b >> c;
a = 1 + (((a * (1LL + lastans)) % Mod) % 2);
b = 1 + (((b * (1LL + lastans)) % Mod) % n);
c = 1 + (((c * (1LL + lastans)) % Mod) % n);
deb(a, b, c);
if (a == 1) {
gra[c].push_back(b);
gra[b].push_back(c);
if (dsu.siz[dsu.root(c)] < dsu.siz[dsu.root(b)]) {
swap(c, b);
}
dfs(dfs, b, c);
dsu.bind(b, c);
} else {
if (fa[b] == fa[c] && fa[b] != 0) {
lastans = fa[b];
} else if (fa[fa[b]] == c) {
lastans = fa[b];
} else if (fa[fa[c]] == b) {
lastans = fa[c];
} else
lastans = 0;
cout << lastans << '\n';
}
}
}