P14011 [POCamp 2023] 珿求 / bootfall
神人题目。
令 \(A\) 为当前选择 \(a\) 的和，\(D\) 同理。我们要尽量让 \(\max(0, A - D') > \max(0, A' - D)\)。
分类讨论，发现当 \(A - D' \leq 0\) 且 \(A' - D \leq 0\) 的时候一定平局，然后是两种特殊情况，若 \(A - D' < 0 \wedge A' = D\) 或 \(A = D' \wedge A' - D < 0\) 时也都是平局。令 \(f_1(i, j)\) 表示前 \(i\) 个人 \(D = j\) 时 \(A\) 的最小值，\(f_2(i, j)\) 与 \(F_1\) 正好相反，\(f_3(i, j)\) 表示前 \(i\) 个人 \(A + D\) 能否为 \(j\)。
当然这是平局情况，我们要尽可能赢下比赛。当 \(A - D' > A' - D\) 时除去前面平局时讨论的情况，一定会赢。并且我们只要保证 \(A - D' > 0\)，不需要管 \(A' - D\) 与 \(0\) 的关系。令 \(g(i)\) 为 \(A \in [i, \sum a_i]\) 时最终 \(A + D\) 的最大值。我们只需要判断 \(g(D' + 1)\) 是否大于 \(A' + D'\) 即可。
如果既不能赢也不能平就会输。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }return x * f;
}
// mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<LL> u0(0, 1ll << 60);const int N = 410, M = 160010;
int n, q, a[N], d[N], f1[2][M], f2[2][M];
int g[M];
bool f3[2][M << 1];
// f1 sumd 为 j，最小化 suma
// f2 suma 为 j，最大化 sumd
// f3 能否 suma + sumd = jint main() {ios::sync_with_stdio(false); cin.tie(0);cin >> n;int sumd = 0, suma = 0;for (int i = 1; i <= n; i ++) {cin >> a[i] >> d[i];sumd += d[i], suma += a[i];}memset(f1, 0x3f, sizeof f2); f1[0][0] = 0, f3[0][0] = true;memset(f2, -1, sizeof f2); f2[0][0] = 0;for (int i = 1; i <= n; i ++) {for (int j = 0; j <= suma + sumd; j ++) {if (j <= sumd) {if (f1[i - 1 & 1][j] != INF) f1[i & 1][j] = f1[i - 1 & 1][j] + a[i];if (j >= d[i]) f1[i & 1][j] = min(f1[i & 1][j], f1[i - 1 & 1][j - d[i]]);}if (j <= suma) {if (f2[i - 1 & 1][j] != -1) f2[i & 1][j] = f2[i - 1 & 1][j] + d[i]; if (j >= a[i]) f2[i & 1][j] = max(f2[i & 1][j], f2[i - 1 & 1][j - a[i]]);}if (j >= a[i]) f3[i & 1][j] |= f3[i - 1 & 1][j - a[i]];if (j >= d[i]) f3[i & 1][j] |= f3[i - 1 & 1][j - d[i]]; // if (j <= suma) cout << f2[i & 1][j] << ' ';}}for (int i = suma; i >= 0; i --) g[i] = max(g[i + 1], i + f2[n & 1][i]); int cnt1 = 0, cnt2 = 0, cnt3 = 0;cin >> q;while (q --) {int A, D; cin >> A >> D;if (g[D + 1] > A + D) cnt1 ++;else {if (sumd >= A) cnt2 ++;else if (f3[n & 1][A + D]) cnt2 ++;else if (f1[n & 1][A] < D) cnt2 ++;else if (f2[n & 1][D] > A) cnt2 ++;else cnt3 ++;}}cout << cnt1 << ' ' << cnt2 << ' ' << cnt3 << endl;return 0;
}
P14012 [POCamp 2023] 枫树 / Maple Tree
好牛的题。
先发现一个点到其它所有点的路径中的最短路径一定是一条边。拓展一下不难发现我们可以通过求一遍 \(1\) 到其它点路径长度的顺序得到一个拓扑序。
然后考虑按照拓扑序考虑每个点，对于一个点，如果找儿子的话比较困难，但是父亲只有一个，所以找父亲。
找父亲的过程考虑在拓扑序小于 \(i\) 的所有点中找。因为操作限制必须支持 \(\log\) 次交互，而且又是二叉树，可以想到边分治或者点分治之类的东西。这个题显然边分治更好做，躯体来说对于一条边 \((x, y)\) 如果 \(d(x, i) < d(y, i)\)，则 \(i\) 一定在 \(x\) 这一侧。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }return x * f;
}const int N = 1010;
int n, p[N], vis[N], sz[N], fa[N];
vector<int> G[N];bool ask(int a, int b, int c) {cout << "? " << a << ' ' << b << ' ' << c << endl;string s; cin >> s;return s == "A";
}void dfs(int u) {sz[u] = 1;for (auto v : G[u]) if (vis[v] && fa[u] != v) fa[v] = u, dfs(v), sz[u] += sz[v];
}vector<int> nxt;void find(int u, int fa) {nxt.push_back(u);for (auto v : G[u]) if (vis[v] && fa != v) find(v, u);
}void calc(vector<int> v, int u) {if (v.size() == 1) {G[v[0]].push_back(u); G[u].push_back(v[0]);return;}for (auto x : v) vis[x] = 1;dfs(v[0]); int p = 0, maxp = INF;for (auto x : v) if (fa[x] && max(sz[x], (int)v.size() - sz[x]) < maxp)maxp = max(sz[x], (int)v.size() - sz[x]), p = x;bool f = ask(p, fa[p], u); if (f) vis[fa[p]] = 0, find(p, 0);else vis[p] = 0, find(fa[p], 0); for (auto x : v) fa[x] = sz[x] = vis[x] = 0;v.swap(nxt); nxt.clear();calc(v, u);
}void output(int u) {vis[u] = 1; for (auto v : G[u]) if (!vis[v]) {cout << u << ' ' << v << endl;output(v);}
}int main() {cin >> n;for (int i = 1; i <= n; i ++) p[i] = i;stable_sort(p + 1, p + 1 + n, [&](int x, int y) {return ask(x, y, 1);}); for (int i = 2; i <= n; i ++) {vector<int> v;for (int j = 1; j < i; j ++) v.push_back(p[j]);calc(v, p[i]); }memset(vis, 0, sizeof vis);cout << "!" << endl;output(1); return 0;
}
P14013 [POCamp 2023] 送钱 / The Generous Traveler
题目相当于在一个路径上一直取模，由于取模不满足结合律所以不好直接倍增预处理。
这时候有一个很经典的结论：一个 \(v\) 通过取模得到的不同的值是 \(\log v\) 级别的。原因是 \(v\) 模一个 \(< v\) 的数的余数不超过 \(\lceil \frac{v}{2} \rceil\)。
所以考虑每次跳路径上的一个小于 \(v\) 的点，这可以用树链剖分加线段树实现。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }return x * f;
}const int N = 500010;
int n, q, a[N];
vector<int> G[N];int top[N], sz[N], dfn[N], id[N], son[N], fa[N], dep[N], tn;void dfs(int u, int f) {fa[u] = f; sz[u] = 1; dep[u] = dep[f] + 1;for (auto v : G[u]) if (v != f) {dfs(v, u); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; }
}void dfs2(int u, int tp) {top[u] = tp, dfn[u] = ++ tn, id[tn] = u; if (son[u]) dfs2(son[u], tp); for (auto v : G[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}struct SNode { int l, r, v; };
struct Segment_Tree {SNode tr[N << 2];void pushup(int u) { tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v); }void build(int u, int l, int r) {tr[u] = {l, r, INF};if (l == r) return tr[u].v = a[id[l]], void();int mid = l + r >> 1;build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);pushup(u);}int query1(int u, int l, int r, int x) {if (tr[u].v > x || l > r || tr[u].r < l || tr[u].l > r) return INF;if (tr[u].l == tr[u].r) return tr[u].l;int mid = tr[u].l + tr[u].r >> 1, res;res = query1(u << 1 | 1, l, r, x); if (res != INF) return res;return query1(u << 1, l, r, x);}int query2(int u, int l, int r, int x) {if (tr[u].v > x || l > r || tr[u].r < l || tr[u].l > r) return INF;if (tr[u].l == tr[u].r) return tr[u].l;int mid = tr[u].l + tr[u].r >> 1, res;res = query2(u << 1, l, r, x); if (res != INF) return res;return query2(u << 1 | 1, l, r, x);}
} sgt;int lca(int x, int y) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]]; }return dep[x] < dep[y] ? x : y;
}void work1(int l, int r, int &k) {for (int i = r; ; ) {int q = sgt.query1(1, l, i, k); if (q == INF) break;k %= a[id[q]]; i = q - 1; }
}void work2(int l, int r, int &k) {for (int i = l; ; ) {int q = sgt.query2(1, i, r, k); if (q == INF) break;k %= a[id[q]]; i = q + 1;}
}void calc(int x, int y, int k) {int d = lca(x, y);vector<PII> l, r;while (top[x] != top[d]) {l.push_back({dfn[top[x]], dfn[x]}); x = fa[top[x]]; } l.push_back({dfn[d], dfn[x]}); while (top[y] != top[d]) {r.push_back({dfn[top[y]], dfn[y]});y = fa[top[y]]; }if (dfn[d] + 1 <= dfn[y]) r.push_back({dfn[d] + 1, dfn[y]}); reverse(r.begin(), r.end()); for (auto [L, R] : l) work1(L, R, k); for (auto [L, R] : r) work2(L, R, k);printf("%d\n", k);
}int main() {// freopen("P14013_21.in", "r", stdin);n = read(), q = read();for (int i = 1; i < n; i ++) {int a = read(), b = read();G[a].push_back(b); G[b].push_back(a);}for (int i = 1; i <= n; i ++) a[i] = read();dfs(1, 0); dfs2(1, 1); sgt.build(1, 1, n); while (q --) {int x = read(), y = read(), k = read();calc(x, y, k); }return 0;
}