联考总结
估：100 + 10 + 100 + 56
实：100 + 10 + 100 + 56 rk5
饭堂了没有做出来 t2 的唐题。
T1
给定 DAG 问有没有长度为 \(n\) 的链。
直接拓扑排序即可。
T2
原：P6940 [ICPC 2017 WF] Visual Python++
没有做出来，怎么会使呢。
考虑先从右往左扫描线，每次将右下角加入 set，左上角配对直接找高度大于等于他且最小的显然不劣，lower_bound 即可，找不到无解。然后再来判别的无解条件，不难发现无解时一定存在边框相交，考虑扫描线，线段树维护一个点上有多少个边框，存在值 \(\ge 2\) 无解。做完了，注意要离散化。
#include
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair
#define pll pair
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));// freopen("rectangle_sample5.in", "r", stdin);// freopen(".out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 2 * 1e5 + 18;int n, sx, sy, ans[maxn];
struct node {int x, y;
} s[maxn], t[maxn];
set p;
vector tx, ty, upd[maxn], ask[maxn];
struct mdf {int l, r, x;
} ;
vector dif[maxn];class xds {struct tree {int l, r, t, v;} t[maxn << 2];void push_up(int i) { t[i].v = max(t[i << 1].v, t[i << 1 | 1].v); }void push_down(int i) {t[i << 1].t += t[i].t;t[i << 1].v += t[i].t;t[i << 1 | 1].t += t[i].t;t[i << 1 | 1].v += t[i].t;t[i].t = 0;}
public:void build(int i, int l, int r) {t[i].l = l, t[i].r = r, t[i].v = t[i].t = 0;if(l == r) AC;int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);}void updata(int i, int l, int r, int x) {if(t[i].l >= l && t[i].r <= r) {t[i].t += x, t[i].v += x;AC;}push_down(i);int mid = t[i].l + t[i].r >> 1;if(l <= mid) updata(i << 1, l, r, x);if(r > mid) updata(i << 1 | 1, l, r, x);push_up(i);}il bool chk() { return t[1].v <= 1; }
} ds;void ACehomoxue() {n = rd();for(int i = 1; i <= n; i++) s[i] = {rd(), rd()};for(int i = 1; i <= n; i++) t[i] = {rd(), rd()};tx.push_back(0), ty.push_back(0);for(int i = 1; i <= n; i++) tx.push_back(s[i].x), tx.push_back(t[i].x), ty.push_back(s[i].y), ty.push_back(t[i].y);sort(tx.begin(), tx.end()), sort(ty.begin(), ty.end());tx.erase(unique(tx.begin(), tx.end()), tx.end());ty.erase(unique(ty.begin(), ty.end()), ty.end());for(int i = 1; i <= n; i++) {s[i].x = lower_bound(tx.begin(), tx.end(), s[i].x) - tx.begin();s[i].y = lower_bound(ty.begin(), ty.end(), s[i].y) - ty.begin();t[i].x = lower_bound(tx.begin(), tx.end(), t[i].x) - tx.begin();t[i].y = lower_bound(ty.begin(), ty.end(), t[i].y) - ty.begin();upd[t[i].x].push_back(i);ask[s[i].x].push_back(i);}sx = tx.size() - 1, sy = ty.size() - 1;for(int x = sx; x; x--) {for(int i : upd[x]) {int y = t[i].y;p.insert({y, i});}for(int i : ask[x]) {int y = s[i].y;auto it = p.lower_bound(make_pair(y, 0));if(it == p.end()) { cout << "syntax error"; el; AC; }ans[i] = it -> second;p.erase(it);}} for(int i = 1; i <= n; i++) {int a = s[i].x, b = s[i].y, c = t[ans[i]].x, d = t[ans[i]].y;if(a == c) {dif[a].push_back({b, d, 1});dif[c + 1].push_back({b, d, -1});continue;} dif[a].push_back({b, d, 1});dif[a + 1].push_back({b + 1, d - 1, -1});dif[c].push_back({b + 1, d - 1, 1});dif[c + 1].push_back({b, d, -1});}ds.build(1, 1, sy);for(int i = 1; i <= sx; i++) {for(auto [l, r, x] : dif[i]) if(l <= r) ds.updata(1, l, r, x);if(!ds.chk()) { cout << "syntax error"; el; AC; }}for(int i = 1; i <= n; i++) cout << ans[i], el;
}T3
原：P13552 鱼类考古学
注意到先与后加不劣，应为一次与为 \(x + y - x | y\)，相当于 \(x | y\) 为代价，且不难发现约加代价越大。考虑将数字分成 \(k\) 组与起来然后加起来。考虑按位贪心，对于枚举到第 \(d\) 位有 \(c0\) 个为 \(0\) 有 \(c1\) 个为 \(1\)，我们尽量让为 \(1\) 的全都单独一组，所以 \(k > c1\) 时直接让为 \(1\) 的单独一组对为 \(0\) 的算下一位即可。否则为 \(0\) 的一定要全部在一组里面不劣，将其全部与起来当成一个数，且这一位显然对答案有贡献 \((k - 1) \times 2 ^ d\)，递归下一位即可。做完了，设 \(V\) 表示值域，有时间复杂度 \(O(n \log V)\)。
code#include
using namespace std;
#define int ll
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair
#define pll pair
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));int t = 1;t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 1e6 + 18;int n, k, a[maxn], ans;const int maxs = maxn * 30;
vector p, p0, p1;void ACehomoxue() {p.clear(), p0.clear(), p1.clear();n = rd(), k = rd(), ans = 0;for(int i = 1; i <= n; i++) {a[i] = rd();p.push_back(a[i]);}for(int d = 30; d + 1; d--) {if(p.empty()) break;p0.clear(), p1.clear();if(k == (ll) p.size()) { for(int i : p) ans += i; break; }if(k == 1) {int v = p[0];for(int i : p) v &= i;ans += v;break;}for(int i : p) {if((i >> d) & 1) p1.push_back(i);else p0.push_back(i);}if(p1.empty()) { p = p0; continue; }if(p0.empty()) {ans += k * (1 << d);for(int &i : p1) i ^= 1 << d;p = p1;continue;}if(k > (ll) p1.size()) {for(int i : p1) ans += i;k -= p1.size();p = p0;} else {int v = p0[0];for(int i : p0) v &= i;ans += (k - 1) * (1 << d);for(int &i : p1) i ^= 1 << d;p = p1;p.push_back(v);}}cout << ans;el;
}
T4
原：P14211 [ROI 2016 Day2] 快递服务
给你一棵树和一堆路径，求两条路径最大相交长度和两者编号。
set 简单应用。
贡献分两种。将一条路径 \((u, v)\) 划为两条，分别是 \((u, w)\) 和 \((v, w)\) 其中 \(w\) 表示 \(\operatorname{lca}(u, v)\)。按照路径 \(w\) 是否相同分类，\(w\) 不同只需算每个 \((w, v)\) 和 \((w, u)\) 公共长度即可。
对于每个节点 \(x\)，我们开个 set 维护 \((u, w)\) 和 \((v, w)\) 且 \(u\) 和 \(v\) 都在子树内 \(w\) 为 \(x\) 祖先。启发式合并，当两个集合于 \(x\) 合并，显然里面所有 \(u\) 啊 \(v\) 啊的 lca 都应在 \(x\)，不难发现答案为 \(dep_{\max w} - dep_{x}\)。由于答案尽量大所以我们其实不需 set，只需开两个数组存储 \(w\) 深度最小的即可，可以做到 \(O(n)\)。
对于 \(w\) 在同一节点，类似的开 set 启发式合并，对于 \((u, v)\) 要合并进入集合 \(t\) 在点 \(x\)，不难发现其贡献为 \(dep_x + dep_{\max_{v ^ \prime \in t} \operatorname{lca}(v, v ^ \prime)} - 2 dep_w\)，即要找到集合中 \(v ^ \prime\) 和 \(v\) 的 lca 深度最大的，有结论其应和 \(v\) 的 dfs 序尽量接近，那么这部分的 set 就按 dfs 序排序即可，查询时简单 lower_bound，时间复杂度 \(O(n \log ^ 2 n)\)。
做完了。
code#include
using namespace std;
#define int int
#define ll long long
#define usd unsigned
#define el putchar('\n')
#define lowbit(x) (x & (-x))
#define AC return
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define void inline void
#define il inline
#define Mod(x) (((x) % mod + mod) % mod)
#define pii pair
#define pll pair
il char gc() { char c; while((c = getchar()) <= ' ') ; return c; }
il int rd() {char c; int x, f = 1;while(!isdigit(c = getchar())) if(c == '-') f *= -1;x = c ^ 48;while(isdigit(c = getchar())) x = (x << 3) + (x << 1) + (c ^ 48);return x * f;
}
void ACehomoxue();
signed main() {srand(time(0));// freopen(".in", "r", stdin);// freopen(".out", "w", stdout);int t = 1;// t = rd();while(t--) ACehomoxue();AK;
}
const int mod = 998244353, maxn = 2 * 1e5 + 18, maxk = 19;
int n, m, nxt[maxn][maxk], dep[maxn], fa[maxn], lg[maxn];
int ans, x1 = 1, x2 = 2, in[maxn], dfn, rfl[maxn], stk[maxn];
vector vec[maxn], pt[maxn];
pii e[maxn], mn[maxn];
set > s[maxn];
il int mindep(int u, int v) {return dep[u] < dep[v] ? u : v;
}
void g1() {int top = 0;stk[++top] = 1, dep[1] = 1;while(top) {int x = stk[top--];in[x] = ++dfn, rfl[dfn] = x;for(int i = (int)vec[x].size() - 1; i + 1; i--) {int to = vec[x][i];dep[to] = dep[x] + 1;stk[++top] = to;}}for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;for(int i = 1; i <= n; i++) nxt[i][0] = fa[rfl[i]];for(int j = 1; j < maxk; j++)for(int i = 1; i + (1 << j) - 1 <= n; i++)nxt[i][j] = mindep(nxt[i][j - 1], nxt[i + (1 << (j - 1))][j - 1]);
}
il int lca(int u, int v) {if(u == v) return u;int l = in[u], r = in[v];if(l > r) swap(l, r);l++;int k = lg[r - l + 1];return mindep(nxt[l][k], nxt[r - (1 << k) + 1][k]);
}
void upd(int x, int d, int i) {if(d >= dep[x]) AC;if(mn[x].second) {int val = dep[x] - max(d, mn[x].first);if(val > ans) ans = val, x1 = i, x2 = mn[x].second;}if(!mn[x].second || d < mn[x].first) mn[x] = {d, i};
}
void g2() {for(int i = n; i > 1; i--) {int x = rfl[i];if(mn[x].second) upd(fa[x], mn[x].first, mn[x].second);}
}
il bool cmp(const int &i, const int &j) {return in[i] < in[j];
}
class vt {vector vec[maxn], p;bool vis[maxn];int depp;void dfs(int x) {if(s[x].size() > 1) {auto it = s[x].begin(), pre = it++;for(; it != s[x].end(); pre = it++) {int val = dep[x] - 2 * depp+ dep[lca(rfl[pre -> first], rfl[it -> first])];if(val > ans) ans = val, x1 = pre -> second, x2 = it -> second;}}for(int to : vec[x]) {if(s[to].size() > s[x].size()) swap(s[x], s[to]);for(pii pr : s[to]) {int nx = pr.first, i = pr.second;auto it = s[x].lower_bound({nx, 0});if(it != s[x].end()) {int val = dep[x] - 2 * depp+ dep[lca(rfl[nx], rfl[it -> first])];if(val > ans) ans = val, x1 = i, x2 = it -> second;}if(it != s[x].begin()) {it--;int val = dep[x] - 2 * depp+ dep[lca(rfl[nx], rfl[it -> first])];if(val > ans) ans = val, x1 = i, x2 = it -> second;}}s[x].merge(s[to]);}}
public:void sol(int w) {for(int i : p) vis[i] = false, vec[i].clear(), s[i].clear();p.clear(), p.push_back(w);vis[w] = true;for(int i : pt[w]) {auto [u, v] = e[i];if(!vis[u]) vis[u] = true, p.push_back(u);if(!vis[v]) vis[v] = true, p.push_back(v);}sort(p.begin(), p.end(), cmp);for(int i = 1, sz = p.size(); i < sz; i++) {int x = lca(p[i - 1], p[i]);if(!vis[x]) vis[x] = true, p.push_back(x);}sort(p.begin(), p.end(), cmp);for(int i = 1, sz = p.size(); i < sz; i++)vec[lca(p[i - 1], p[i])].push_back(p[i]);depp = dep[w];for(int i : pt[w]) {auto [u, v] = e[i];s[u].insert({in[v], i});s[v].insert({in[u], i});}for(int i = (int)p.size() - 1; i; i--) dfs(p[i]);}
} ss;
void ACehomoxue() {n = rd(), m = rd();for(int i = 2; i <= n; i++) {fa[i] = rd();vec[fa[i]].push_back(i);}g1();for(int i = 1; i <= m; i++) {int u = rd(), v = rd(), w = lca(u, v);e[i] = {u, v};upd(u, dep[w], i), upd(v, dep[w], i);pt[w].push_back(i);}g2();for(int i = 1; i <= n; i++)if(pt[i].size() > 1) ss.sol(i);cout << ans;el;cout << x1 << ' ' << x2;el;
}