Gym102994
总览
| 题号 | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 完成情况 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
A. Everyone Loves Playing Games
A 有 \(N\) 对数， B 有 \(M\) 对数，A 从 \(N\) 对数中分别选一个数得到异或和 \(X\)，然后 B 从 \(N\) 对数得到一个异或和 \(Y\)，\(A\) 希望 \(X \oplus Y\) 最大，\(B\) 希望 \(X \oplus Y\) 最小，求最后的结果。
\(N, M \leq 10000, 0 \leq x \leq 10^{18}\)。
设每对数为 \((x_i, y_i)\)，先都选上 \(x_i\)，然后变成选或不选 \(x_i \oplus y_i\) 的问题。
A 和 B 分别建出线性基，然后从高位向低位考虑。
只需要考虑某一位 A 和 B 都有影响的情况，这位如果为 1 那么 A B 只会选一个，如果为 0 则要么都选，要么都不选，不管哪种情况两种状态都可以通过异或 \(A_i \oplus B_i\) 来相互转换，所以这种情况将 \(A_i \oplus B_i\) 插入 \(A\) 的线性基来提供“反悔”的机会。
#include <bits/stdc++.h>
#include <string.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
struct LinearBasis {
LL p[61];
LinearBasis() {
memset(p, 0, sizeof p);
}
void ins(LL x) {
for (int i = 60; i >= 0; i--) {
if (x >> i & 1 ^ 1) continue;
if (!p[i]) {
p[i] = x;
break;
}
x ^= p[i];
}
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int n, m;
std::cin >> n >> m;
LinearBasis p, q;
LL ans = 0;
for (int i = 0; i < n; i++) {
LL x, y;
std::cin >> x >> y;
ans ^= x;
p.ins(x ^ y);
}
for (int i = 0; i < m; i++) {
LL x, y;
std::cin >> x >> y;
ans ^= x;
q.ins(x ^ y);
}
for (int i = 60; i >= 0; i--) {
auto a = p.p[i], b = q.p[i];
ans = std::max(std::min(ans ^ a, ans ^ a ^ b), std::min(ans, ans ^ b));
if ((a & b) >> i & 1) p.ins(a ^ b);
}
std::cout << ans << "\n";
}
return 0;
}B. Gifted Composer
有一个空字符串，每次操作在开头或结尾加一个字符，然后求当前字符串的循环节个数。
\(n \leq 10^6\)。
长度为 \(x\) 的循环节一定在第 \(x\) 次操作后出现，然后在某一时间消失，后面不会再出现。
枚举 \(x\) 然后二分这个消失的时间，判断循环节可以通过判断是否存在长度 \(n - x\) 的 Border 来实现。
复杂度 \(O(n \log n)\)。
#include <bits/stdc++.h>
constexpr uint32_t P(1e9 + 7);
using Hash = std::pair<uint64_t, uint64_t>;
inline Hash operator+(Hash a, Hash b) {
return {a.first + b.first, (a.second + b.second) % P};
}
inline Hash operator-(Hash a, Hash b) {
return {a.first - b.first, (a.second + P - b.second) % P};
}
inline Hash operator*(Hash a, Hash b) {
return {a.first * b.first, a.second * b.second % P};
}
constexpr Hash Base(131, 31);
constexpr int N(1e6 + 5);
Hash pw[N];
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n;
std::cin >> n;
int l = 0;
std::deque<char> s;
std::string opt;
for (int i = 0; i < n; i++) {
std::string a, b;
std::cin >> a >> b;
opt += a;
if (a[0] == 'p') {
l++, s.push_front(b[0] + (b[1] == 'i'));
} else {
s.push_back(b[0] + (b[1] == 'i'));
}
}
pw[0] = {1, 1};
for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * Base;
std::vector<Hash> h(n); h[0] = {s[0], s[0]};
for (int i = 1; i < n; i++) h[i] = h[i - 1] * Base + Hash(s[i], s[i]);
std::vector<std::pair<int, int>> interval;
interval.reserve(n);
int r = l - 1;
for (char c : opt) {
if (c == 'p') {
l--;
} else {
r++;
}
interval.emplace_back(l, r);
}
assert(interval.size() == n);
std::vector<int> ans(n + 1);
auto get = [&](int l, int r) {
return l <= r ? h[r] - (l ? h[l - 1] * pw[r - l + 1] : Hash()) : Hash();
};
for (int i = 0; i < n; i++) {
l = i, r = n;
while (l < r) {
int m = l + r >> 1;
auto [x, y] = interval[m];
if (get(x, y - i - 1) == get(x + i + 1, y)) {
l = m + 1;
} else {
r = m;
}
}
ans[i]++, ans[l]--;
}
for (int i = 1; i <= n; i++) ans[i] += ans[i - 1], std::cout << ans[i - 1] << "\n";
return 0;
}C. An Unsure Catch
D. String Theory
给定一个字符串 \(S\)，和整数 \(k\)，求形如 \(AAA\dots A\) （\(k\) 个 \(A\)）的子串的个数，其中 \(A\) 是任意非空字符串。
\(n \leq 3 \times 10^5, 1 \leq k \leq 20\)。
枚举循环节长度 \(i\)，枚举左端点 \(l\)，右端点 \(r\) 可以二分得出，然后这个贡献是 \(r - l + 1 - ki + 1\)，发现下一个左端点一定在区间 \([r - k + 1, r + 1]\)，总枚举次数是调和级数。
复杂度 \(O(n \log^2 n)\)。
\(k \leq 20\) 的条件实际上是没用的。
#include <bits/stdc++.h>
constexpr uint32_t P(1e9 + 7);
using Hash = std::pair<uint64_t, uint64_t>;
inline Hash operator+(Hash a, Hash b) {
return {a.first + b.first, (a.second + b.second) % P};
}
inline Hash operator-(Hash a, Hash b) {
return {a.first - b.first, (a.second + P - b.second) % P};
}
inline Hash operator*(Hash a, Hash b) {
return {a.first * b.first, a.second * b.second % P};
}
constexpr Hash Base(131, 31);
constexpr int N(3e5 + 5);
Hash pw[N];
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t, k = 3e5;
pw[0] = {1, 1};
for (int i = 1; i <= k; i++) pw[i] = pw[i - 1] * Base;
std::cin >> t;
while (t--) {
std::string s;
std::cin >> k >> s;
int n = s.length();
if (k == 1) {
std::cout << 1LL * n * (n + 1) / 2 << "\n";
continue;
}
std::vector<Hash> h(n);
h[0] = {s[0], s[0]};
for (int i = 1; i < n; i++) h[i] = h[i - 1] * Base + Hash(s[i], s[i]);
auto get = [&](int l, int r) {
return l <= r ? h[r] - (l ? h[l - 1] * pw[r - l + 1] : Hash()) : Hash();
};
auto check = [&](int l, int r, int x) {
return get(l, r - x) == get(l + x, r);
};
long long ans = 0;
for (int i = 1, l, r; i <= n; i++) {
for (int j = 0; j <= n - i; j = r + 1) {
l = std::max(0, j - i + 1), r = j;
while (l < r) {
int m = l + r >> 1;
if (check(m, j + i - 1, i)) {
r = m;
} else {
l = m + 1;
}
}
r = j;
if (n - 1 > r) {
for (int k = 1 << std::__lg(n - 1 - r); k; k >>= 1) {
if (r + k < n && check(l, r + k, i)) r += k;
}
}
assert(r >= j + i - 1);
ans += std::max(0, r - l + 1 - k * i + 1);
}
}
std::cout << ans << "\n";
}
return 0;
}E. Road Construction
F. Girlfriend
给定一个无向图，q 次询问 \(s\) 到 \(t\) 的次大边权的最小值。
\(n, q \leq 10^5, m \leq 2 \times 10^5\)。
二分答案 \(ans\)，问题转化为判断是否存在一条边连接两个联通块（\(s\) 和 \(t\) 只走小于等于 \(ans\) 的边形成的联通块）。
建出 kruskal 重构树倍增即可求出这两个联通块。
然后判断是否存在连接两个子树的边，转换成 dfs 序后用一个二维偏序的数据结构解决即可。
复杂度 \(O(n \log^2 n)\)。
#include <bits/stdc++.h>
constexpr int N(2e5 + 5);
int up[20][N], fa[N], in[N], out[N], cnt, val[N];
int find(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
};
std::vector<int> g[N];
void dfs(int x) {
in[x] = ++cnt;
for (int y : g[x]) {
// assert(!in[y]);
dfs(y);
}
out[x] = cnt;
}
struct Node {
int ls, rs, w;
} t[N * 50];
int pt;
void ins(int &o, int l, int r, int x) {
t[++pt] = t[o], o = pt, t[o].w++;
if (l == r) return;
int m = l + r >> 1;
x <= m ? ins(t[o].ls, l, m, x) : ins(t[o].rs, m + 1, r, x);
}
int ask(int u, int v, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[v].w - t[u].w;
int m = l + r >> 1, ans = 0;
if (x <= m) ans += ask(t[u].ls, t[v].ls, l, m, x, y);
if (y > m) ans += ask(t[u].rs, t[v].rs, m + 1, r, x, y);
return ans;
}
int root[N];
bool check(int x, int y, int z) {
for (int i = 18; i >= 0; i--) {
if (up[i][x] && val[up[i][x]] <= z) x = up[i][x];
}
for (int i = 18; i >= 0; i--) {
if (up[i][y] && val[up[i][y]] <= z) y = up[i][y];
}
return ask(root[in[x] - 1], root[out[x]], 1, cnt, in[y], out[y]) > 0;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) {
int n, m, q;
cnt = pt = 0;
std::cin >> n >> m >> q;
std::iota(fa + 1, fa + 1 + 2 * n, 1);
for (int i = 1; i <= n + n; i++) g[i].clear();
std::vector<std::array<int, 3>> e(m);
for (auto &[z, x, y] : e) std::cin >> x >> y >> z;
std::sort(e.begin(), e.end());
int id = n;
for (auto [z, x, y] : e) {
x = find(x), y = find(y);
if (x == y) continue;
fa[x] = fa[y] = ++id;
g[id].push_back(x);
g[id].push_back(y);
up[0][x] = up[0][y] = id;
val[id] = z;
up[0][id] = 0;
}
for (int i = 1; i <= 18; i++)
for (int j = 1; j <= id; j++) {
up[i][j] = up[i - 1][up[i - 1][j]];
}
for (int i = n + 1; i <= id; i++) {
if (!up[0][i]) dfs(i);
}
std::vector<std::vector<int>> h(id + 1);
for (auto [z, x, y] : e) {
h[in[x]].push_back(in[y]);
h[in[y]].push_back(in[x]);
}
for (int i = 1; i <= cnt; i++) {
root[i] = root[i - 1];
for (auto j : h[i]) ins(root[i], 1, cnt, j);
}
while (q--) {
int x, y;
std::cin >> x >> y;
if (find(x) != find(y)) {
std::cout << "-1\n";
continue;
}
int l = 0, r = 1e9;
while (l < r) {
int m = l + r >> 1;
if (check(x, y, m)) {
r = m;
} else {
l = m + 1;
}
}
std::cout << l << "\n";
}
}
return 0;
}G. Blackjack
有 \(n\) 个物品，权值为 \(v_i\)，每轮随机拿走一个，然后你可以选择是否进行下一轮，求最优策略下，最后拿走物品的权值和在 \((a, b]\) 区间内的概率。 \(n, v_i, a, b \leq 500\)。
最优策略显然就是一直拿直到落到 \((a, b]\) 上，或者超过了 \(b\) 游戏结束。
问题转化成随机拿若干个物品，最后落在 \((a, b]\)，且倒数第二步没有落在 \((a, b]\) 的概率。
这是个背包问题，先求出整个背包，然后枚举最后一个拿的物品退背包即可。
复杂度 \(O(n^2b)\)。
#include <bits/stdc++.h>
#define perr(a...) fprintf(stderr, a)
#define dbg(a...) perr("\033[32;1m"), perr(a), perr("\033[0m")
template <class T, class U>
inline bool smin(T &x, const U &y) {
return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
return x < y ? x = y, 1 : 0;
}
using LL = long long;
using PII = std::pair<int, int>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, a, b;
std::cin >> n >> a >> b;
std::vector<std::vector<double>> f(1, std::vector<double>(b + 1)), g;
f[0][0] = 1;
std::vector<int> v(n);
for (auto &x : v) {
std::cin >> x;
f.emplace_back(b + 1);
for (int i = f.size() - 1; i; i--) {
for (int j = b; j >= x; j--) {
f[i][j] += f[i - 1][j - x] / (n - i + 1) * i;
}
}
}
double ans = 0;
for (auto x : v) {
g = f;
for (int i = 1; i <= n; i++)
for (int j = x; j <= b; j++) {
g[i][j] -= g[i - 1][j - x] / (n - i + 1) * i;
}
for (int i = 0; i < n; i++) {
for (int j = std::max(a + 1, x); j - x <= a && j <= b; j++) {
ans += g[i][j - x] / (n - i);
}
}
}
printf("%.10f\n", ans);
return 0;
}H. Yet Another Geometry Problem
I. A Math Problem
J. Gaokao
签到题。
K. Data Structure
给定一棵树，\(q\) 次操作，第一种操作为 \(a, x, y, z\) 表示 \(a\) 的子树中距离 \(a\) 模 \(x\) 余 \(y\) 的点权值加 \(z\)，第二种操作为询问 \(a\) 的权值。
\(n, q \leq 3\times 10^5\)。
如果暴力修改的话一种思路是按深度将点分类，直接 \(\frac n x\) 次区间修改，然后单点查询。
另一种思路是每个模数用dfs序维护子树，每次区间修改 \([in_a, out_a]\)，查询时枚举模数单点查询。
按 \(x\) 分类，大于 \(X\) 的用第一种，小于 \(X\) 的用第二种。
设两种单次修改时间分别为 \(C_1(n), C_2(n)\)，单次查询时间分别为 \(Q_1(n), Q_2(n)\)，则总复杂度为
\[ O\left(q\left[\frac{n}{X} C_1(n) + C_2(n) + Q_1(n) + XQ_2(n)\right]\right) \]
取 \(X = \sqrt\frac{nC_1(n)}{Q_2(n)}\)，最优复杂度为 \[ O\left(q\left[\sqrt{nC_1(n)Q_2(n)} + C_2(n) + Q_1(n)\right]\right) \]
如果 \(C_1(n) = Q_2(n) = O(1), C_2(n) = Q_1(n) = O(\sqrt n)\)，可以做到 \(O(q \sqrt n)\)。
这题我现场写了树状数组和线段树，\(O(q \sqrt n \log n)\)，也跑过了。
#include <bits/stdc++.h>
constexpr int N(3e5 + 5), T(233);
std::vector<int> g[N], h[N];
int in[N], out[N], dep[N], id[N], max_dep;
void dfs(int x) {
max_dep = std::max(max_dep, dep[x]);
in[x] = ++in[0];
id[x] = h[dep[x]].size();
h[dep[x]].push_back(in[x]);
for (int y : g[x]) {
dep[y] = dep[x] + 1;
dfs(y);
}
out[x] = in[0];
}
struct FenwickTree {
std::vector<int> c;
FenwickTree(int n = -1) : c(n + 1) {}
void add(int p, int x) {
for (p++; p < c.size(); p += p & -p) c[p] += x;
}
int ask(int p) {
int r = 0;
for (p++; p; p -= p & -p) r += c[p];
return r;
}
} bit[N];
struct Node {
int ls, rs, w;
} t[N * 100];
int cnt;
void ins(int &o, int l, int r, int x, int y, int z) {
if (!o) t[o = ++cnt] = {0, 0, 0};
if (x <= l && r <= y) {
t[o].w += z;
return;
}
int m = l + r >> 1;
if (x <= m) ins(t[o].ls, l, m, x, y, z);
if (y > m) ins(t[o].rs, m + 1, r, x, y, z);
}
int ask(int o, int l, int r, int x) {
if (!o) return 0;
if (l == r) return t[o].w;
int m = l + r >> 1;
return t[o].w + (x <= m ? ask(t[o].ls, l, m, x) : ask(t[o].rs, m + 1, r, x));
}
int n, root[T][T];
int ask(int a) {
int ans = bit[dep[a]].ask(id[a]);
for (int i = 1; i < T; i++) {
ans += ask(root[i][dep[a] % i], 1, n, in[a]);
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) {
int m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++) g[i].clear(), h[i].clear();
for (int i = 2, x; i <= n; i++) {
std::cin >> x;
g[x].push_back(i);
}
in[0] = 0;
max_dep = 0;
dfs(1);
for (int i = 0; i <= max_dep; i++) bit[i] = FenwickTree(h[i].size());
cnt = 0;
for (int i = 0; i < T; i++)
for (int j = 0; j < i; j++) root[i][j] = 0;
while (m--) {
int opt, a;
std::cin >> opt >> a;
if (opt == 1) {
int x, y, z;
std::cin >> x >> y >> z;
if (x >= T) {
for (int i = dep[a] + y; i <= max_dep; i += x) {
int l = std::lower_bound(h[i].begin(), h[i].end(), in[a]) -
h[i].begin();
int r = std::upper_bound(h[i].begin(), h[i].end(), out[a]) -
h[i].begin();
bit[i].add(l, z), bit[i].add(r, -z);
}
} else {
ins(root[x][(y + dep[a]) % x], 1, n, in[a], out[a], z);
}
} else {
std::cout << ask(a) << "\n";
}
}
}
return 0;
}L. Landlord
签到题。
M. Travel Dream
最后修改于 2021-08-19