POCamp 2023
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 = j
int 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;
}
浙公网安备 33010602011771号