2023北京集训 做题笔记
动态规划
钦定 \(1\) 为根，发现如果 \(u,v\) 不为祖先后代关系，则选择根能把它们全部消掉
剩下的 \(u,v\) 均为祖先后代，假设 \(u\) 为祖先
如果在一条链上，问题转化为选择尽量少的点覆盖所有线段，与端点重合不算
常规做法是按右端点排序，每次尽量选择靠右的
放到树上，按深度从大到小选，每次尽量选深度更浅的点，路径上不是 \(u\) 且深度最浅的 \(x\) 是这条路径最后一个能选的点
于是这样就能把路径按 \(x\) 深度从大到小排序后贪心，每次取出一条路径，看它有没有被消除，如果没有则选 \(x\) 并标记
而且这样选的点一定是合法方案中深度最浅的，刚好能尽可能消去覆盖根的路径
支持单点加，子树查询，复杂度为 \(O(n\log n)\)
但是有 \(O(n)\) 的 DP 做法
我们把路径挂在 \(x\) 处，\(f_x\) 表示已经消去 \(x\) 子树内所有路径的最小代价
如果不选 \(x\)，累加子树的 DP 值，子树之间不影响
但这样可能会导致标记点为 \(x\) 的路径不一定被消除
分类讨论下去发现不可做
如果这条路径不能被消除，说明点一定都在路径下端 \(y\) 的子树中
因此将 \(f_x\) 与 \(f_y+1\) 取 \(\max\)，表示此时选上 \(x\)，这样不会影响答案，因为万一其它部分有点则 \(\max\) 无用
最后考虑覆盖根的路径，同理，如果它没被覆盖，需要选根，此时点都在端点 \(x,y\) 的子树内，\(ans\) 初始为 \(f_1\)，与 \(f_x+f_y+1\) 取 \(\max\)，同理不会影响答案
最小化的 DP 最后是通过取 \(\max\) 转移的，很有意思
void dfs(int x)
{
dfn[x] = ++cnt, anc[0][x] = fa[x], dep[x] = dep[fa[x]] + 1;
for(int y : edge[x]) dfs(y);
}
int query(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int i = 18; i >= 0; --i)
if(anc[i][x] && dep[anc[i][x]] >= dep[y]) x = anc[i][x];
if(x == y) return x;
for(int i = 18; i >= 0; --i)
if(anc[i][x] && anc[i][y] && anc[i][x] != anc[i][y]) x = anc[i][x], y = anc[i][y];
return anc[0][x];
}
int jump(int x, int y)
{
for(int i = 18; i >= 0; --i)
if(anc[i][x] && dep[anc[i][x]] > dep[y]) x = anc[i][x];
return x;
}
void Dfs(int x)
{
for(int y : edge[x])
{
Dfs(y);
f[x] += f[y];
}
for(int y : lin[x]) f[x] = max(f[x], f[y] + 1);
}
int main()
{
read(n, m);
for(int i = 2; i <= n; ++i) read(fa[i]), edge[fa[i]].pb(i);
dfs(1);
for(int j = 1; j <= 18; ++j)
for(int i = 1; i <= n; ++i) anc[j][i] = anc[j - 1][anc[j - 1][i]];
for(int i = 1; i <= m; ++i)
{
read(u[i], v[i]);
if(dfn[u[i]] > dfn[v[i]]) swap(u[i], v[i]);
int lca = query(u[i], v[i]);
if(fa[v[i]] == u[i]) {cout << -1; return 0;}
if(lca == u[i]) lin[jump(v[i], u[i])].pb(v[i]);
else book[i] = 1;
}
Dfs(1), ans = f[1];
for(int i = 1; i <= m; ++i)
if(book[i]) ans = max(ans, f[u[i]] + f[v[i]] + 1);
cout << ans;
return 0;
}
首先考虑选出的点的形态，发现选出的权值非 \(0\) 点一定形成一个团
如果 \(u,v\) 直接没有边，则贡献独立，把点权都给那个度数更大的点更优
然后在一个团内点权肯定均匀分配，设 \(m\) 为团的大小，最终答案为 \(\frac {m(m-1)}2\times (\frac K m)^2=\frac{K^2(m-1)}{2m}\)
发现团的大小越大，答案越大，问题变为求最大团
注意到数据范围为 \(n\le 40\)，可能是折半搜索，状压之类的东西
可以先对前 \(\frac n 2\) 个点状压求出当选出点为 \(s\) 子集时的最大团，转移时分类讨论 \(\operatorname{lowbit}\) 是否在团中
然后枚举后 \(\frac n 2\) 个点的集合 \(t\)，如果它们两两有连边就钦定它们在团中，找出与它们每个点都有连边的点集 \(s\)，答案为 \(\operatorname{popcount(t)}+f_s\)
复杂度为 \(O(2^{\frac n 2})\)
当然如果直接记忆化用前 \(\frac n 2\) 个点的方式状压 DP，发现能直接过
本质相同，前 \(\frac n 2\) 个点时每个点处只有两种决策，枚举量不超过 \(2^{\frac n 2}\)，处理后 \(\frac n 2\) 个点时状态不含前面 \(\frac n 2\) 个点，总状态数只有 \(2^{\frac n 2}\)
int main()
{
read(n), read(k);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) read(g[i][j]), e[i] |= ((ll)g[i][j] << (j - 1));
m = (n + 1) / 2;
for(int i = 1; i <= m; ++i) f[1ll << (i - 1)] = 1;
for(int i = 1; i < (1 << m); ++i)
{
int nw = __builtin_ctz(i & (-i)) + 1;
ll tmp = e[nw] & ((1 << m) - 1);
f[i] = max({f[i], f[i ^ (1 << (nw - 1))], f[i & tmp] + 1});
}
for(ll i = 0; i < (1 << (n - m)); ++i)
{
ll s = i << m, tmp = 0;
int flag = 1, cnt = 0;
for(int j = 1; j <= n - m; ++j)
if((i >> (j - 1)) & 1)
{
++cnt;
if(((e[j + m] | (1ll << (j + m - 1))) & s) != s) {flag = 0; break;}
}
if(!flag) continue;
for(int j = 1; j <= m; ++j)
if((e[j] & s) == s) tmp |= 1 << (j - 1);
ans = max(ans, f[tmp] + cnt);
}
cout << fixed << setprecision(12) << (double)k * k * (ans - 1) / (double)(2.0 * ans);
return 0;
}
疯狂推性质
判定条件太奇怪了，想要找到最难符合条件的序列，如果它都满足那么整个区间都满足
性质 1：序列是完美的等价于序列中元素从小到大排序后，每个前缀是好的
子序列的条件能让我们随便选数，如果固定了最小值与最大值，肯定元素越多越不优，因此排序后选出的一定是子区间
而扩展至前缀会让最小值变小，总和变大，因此子区间其实就是看前缀
下面 \(a_1\sim a_n\) 为排好序的数组
性质 2：\(a_1\times a_n\ge \sum_{i=1}^n a_i\ge na_1\)，因此如果 \(a_n=n\)，则 \(a_{1\sim n}=n\)，否则 \(a_{n}=n+1\)
此时固定了最大值，只用考虑最小值与和
此时如果枚举 \(a_1\) 的值，已经可以初步 DP 了，设 \(f_{i,s,j}\) 表示填到第 \(i\) 个，和为 \(s\)，上一个填的数为 \(j\) 且 \(1\sim i\) 前缀是好的方案数
但是复杂度为状态 \(O(n^4)\)，转移枚举第 \(i+1\) 个数填的数，转移 \(O(n)\)，加上枚举 \(a_1\) 复杂度为 \(O(n^6)\)，不可接受
性质 3：设 \(b_i=a_i-a_1\ge 0\)，则 \(a_1\times(n+1)\ge \sum_{i=1}^n a_1+b_i=na_1+\sum_{i=1}^nb_i\)，因此 \(a_1\ge \sum_{i=1}^n b_i\)
现在我们枚举 \(a_1\) 后可以 DP \(b\) 数组，总和为 \(O(n)\)，从枚举位置填什么改为枚举数 \(j\) 填的个数，复杂度变为调和级数 \(O(n\ln n)\)
此时复杂度为 \(O(n^4\ln n)\)
DP 部分没什么好优化的了，考虑优化枚举 \(a_1\)
感性理解都知道 \(a_1\) 不会很小，但下界是多少呢？
性质 4：\(\forall i\in[1,n],a_i \ge i\)，则 \(a_1\ge \frac{(n+1-a_1)(n-a_1)}2\)，\(a_1\ge n-2\sqrt {n}\)
由性质 2 得 \(a_1\times a_i\ge\sum_{j=1}^i a_i\ge ia_1\)，即 \(a_i\ge i\)，此时 \(b_i\) 最小为 \(1\sim a_1\) 取 \(a_1\)，\(a_1+1\sim n\) 取 \(1\sim n-a_1\)
那么复杂度变为 \(O(n^3\ln n\sqrt n)\)，记忆化搜索可过，实现上可调大上界
int dfs(int i, int s, int j) // have placed b_{1~i} sum_{k=1}^i b_i = s now try to place b_{i+1~x} = j
{
if(book[i][s][j]) return f[i][s][j];
if(j > n + 2 - lim) return f[i][s][j] = 0;
if(i >= n) return f[i][s][j] = fact[n];
book[i][s][j] = 1;
int &res = f[i][s][j]; res = 0;
for(int x = j ? 0 : 1; s + j * x <= lim && i + x <= n; ++x)
if(s + j * x + lim * (i + x) <= lim * (lim + j))
res = add(res, 1ll * dfs(i + x, s + j * x, j + 1) * invf[x] % mod);
return res;
}
int main()
{
cin >> n >> mod;
fact[0] = invf[0] = 1;
for(int i = 1; i <= n; ++i) fact[i] = 1ll * fact[i - 1] * i % mod;
invf[n] = qmi(fact[n], mod - 2);
for(int i = n - 1; i > 0; --i) invf[i] = 1ll * invf[i + 1] * (i + 1) % mod;
for(lim = max(1, n - 25); lim <= n + 1; ++lim)
{
memset(book, 0, sizeof(book));
ans = add(ans, dfs(0, 0, 0));
}
cout << ans;
return 0;
}
图论
机器人每次的行走过程可以看作是从充电站到下一个充电站组成的几段，要求最长的段最短
想法是求出以充电站之间距离为边权的完全图的最小生成树，后来发现不太可做
求出每个点距离自己最近的充电站比较有技巧性：建超级源点 \(S\)，与每个充电站连边权为 \(0\) 的边，则距离为 \(dis_x\)
设机器人满电电量为 \(c\)，它通过边权为 \(w\) 的边 \((x,y)\)，机器人到达 \(x\) 时电量最多为 \(c-dis_x\)
则 \(c-dis_x\ge w,c-w-dis_x\ge dis_y\)
则 \(c\ge dis_x+dis_y+w\)
这样限制被下放到了每一条边上，建出新边权的原图的最小生成树
void dij(int st)
{
priority_queue<pll, vector<pll>, greater<pll> > heap;
memset(dis, 0x3f, sizeof(dis));
heap.push({0, st}), dis[st] = 0;
while(!heap.empty())
{
ll x = heap.top().se; heap.pop();
if(book[x]) continue;
book[x] = 1;
for(pll y : edge[x])
if(dis[y.fi] > dis[x] + y.se)
{
dis[y.fi] = dis[x] + y.se;
heap.push({dis[y.fi], y.fi});
}
}
}
int find(int x) {return x != fa[x] ? fa[x] = find(fa[x]) : x;}
void kruskal()
{
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= m; ++i) edg[i].w += dis[edg[i].u] + dis[edg[i].v];
sort(edg + 1, edg + m + 1, [](const edges x, const edges y){return x.w < y.w;});
for(int i = 1; i <= m; ++i)
{
int x = find(edg[i].u), y = find(edg[i].v);
if(x == y) continue;
fa[x] = y, tree[edg[i].u].pb({edg[i].v, edg[i].w}), tree[edg[i].v].pb({edg[i].u, edg[i].w});
}
}
void Dfs(int x, int fath)
{
f[0][x] = fath, dep[x] = dep[fath] + 1;
for(pll y : tree[x])
if(y.fi != fath) mn[0][y.fi] = y.se, Dfs(y.fi, x);
}
ll query(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
if(x == y) return 0;
ll res = 0;
for(int i = 17; i >= 0; --i)
if(f[i][x] && dep[f[i][x]] >= dep[y]) res = max(res, mn[i][x]), x = f[i][x];
if(x == y) return res;
for(int i = 17; i >= 0; --i)
if(f[i][x] && f[i][y] && f[i][x] != f[i][y])
res = max({res, mn[i][x], mn[i][y]}), x = f[i][x], y = f[i][y];
return max({res, mn[0][x], mn[0][y]});
}
int main()
{
read(n, m, k, q);
for(int i = 1; i <= m; ++i)
{
read(edg[i].u, edg[i].v, edg[i].w);
edge[edg[i].u].pb({edg[i].v, edg[i].w}), edge[edg[i].v].pb({edg[i].u, edg[i].w});
}
for(int i = 1; i <= k; ++i) edge[n + 1].pb({i, 0}), edge[i].pb({n + 1, 0});
dij(n + 1);
kruskal(), Dfs(1, 0);
for(int j = 1; j <= 17; ++j)
for(int i = 1; i <= n; ++i)
{
f[j][i] = f[j - 1][f[j - 1][i]];
mn[j][i] = max(mn[j - 1][i], mn[j - 1][f[j - 1][i]]);
}
for(int i = 1; i <= q; ++i)
{
read(a, b);
print(query(a, b)), putchar('\n');
}
return 0;
}
支配对好题
涉及路径的题考虑点分治，当前分治中心为 \(x\)
处理出每个点到分治中心的距离 \(dis_i\)
如果对于 \(i\le j\le k\)，\((i,k)\) 为有效对，说明 \(dis_i+dis_k\le dis_j+dis_k,dis_i+dis_j\)，即 \(dis_i,dis_k\le dis_j\)
发现条件为 \(dis_i,dis_k\le \min_{j=i+1}^{k-1}dis_j\)
此时枚举每个数作为 \(\min\) 时带来的支配对，把距离扔到 set 里，找前面比它小的第一个数和后面比它小的第一个数，这两个组成支配对
总共只有 \(O(n\log n)\) 组支配对，问题变为求 \(l\le x< y\le r\) 中 \(w(x,y)\) 的最小值，离线后扫描线即可
为了卡常，扫描线可以用树状数组支持单点修改，查后缀 \(\min\)，用单调栈做两遍实现找支配对的过程
struct BIT
{
ll sum[N];
void init() {fill(sum, sum + n + 1, inf);}
void upd(int x, ll val) {for(; x; x -= x & (-x)) sum[x] = min(sum[x], val);}
ll query(int x)
{
ll res = inf;
for(; x <= n; x += x & (-x)) res = min(res, sum[x]);
return res;
}
}bit;
void dfsxin(int x, int fa)
{
siz[x] = 1; int res = 0;
for(pii y : edge[x])
if(!vis[y.fi] && y.fi != fa)
dfsxin(y.fi, x), siz[x] += siz[y.fi], res = max(res, siz[y.fi]);
res = max(res, tot - siz[x]);
if(res < mn) mn = res, root = x;
}
int getroot(int x) {dfsxin(x, 0), tot = mn = siz[x], dfsxin(x, 0); return root;}
void dfs(int x, int fa)
{
lin[++cnt] = x;
for(pii y : edge[x])
if(!vis[y.fi] && y.fi != fa) dis[y.fi] = dis[x] + y.se, dfs(y.fi, x);
}
void solve(int x)
{
vis[x] = 1, dis[x] = cnt = 0;
dfs(x, 0);
sort(lin + 1, lin + cnt + 1);
top = 0;
for(int i = 1; i <= cnt; ++i)
{
while(top && dis[stk[top]] > dis[lin[i]]) nxt[stk[top]] = lin[i], --top;
stk[++top] = lin[i];
}
while(top) nxt[stk[top--]] = n + 1;
for(int i = cnt; i > 0; --i)
{
while(top && dis[stk[top]] > dis[lin[i]]) pre[stk[top]] = lin[i], --top;
stk[++top] = lin[i];
}
while(top) pre[stk[top--]] = 0;
for(int i = 1; i <= cnt; ++i)
{
if(pre[lin[i]]) upd[lin[i]].pb({pre[lin[i]], dis[pre[lin[i]]] + dis[lin[i]]});
if(nxt[lin[i]] <= n) upd[nxt[lin[i]]].pb({lin[i], dis[lin[i]] + dis[nxt[lin[i]]]});
}
for(pii y : edge[x])
if(!vis[y.fi]) solve(getroot(y.fi));
}
int main()
{
read(n);
for(int i = 1; i < n; ++i)
{
read(u, v, w);
edge[u].pb({v, w}), edge[v].pb({u, w});
}
read(q);
for(int i = 1; i <= q; ++i)
{
read(u, v);
ask[v].pb({u, i});
}
solve(getroot(1));
bit.init();
for(int i = 1; i <= n; ++i)
{
for(pii x : upd[i]) bit.upd(x.fi, x.se);
for(pii x : ask[i]) ans[x.se] = bit.query(x.fi);
}
for(int i = 1; i <= q; ++i) print(ans[i] < inf ? ans[i] : -1), putchar('\n');
return 0;
}
可以狂暴树剖上线段树优化建图，然后缩点找出度为 \(0\) 的强连通分量大小最小值，但不优美
考虑点分治，每次以分治中心为首都
中间遇到要变的颜色就不断扩展，直到包含中心颜色的所有点
但需要扩展的点跨过了分治中心怎么办？
此时发现答案一定不如取上一层的分治中心，直接跳过
复杂度为 \(O(n\log n)\)
void dfsxin(int x, int fa)
{
siz[x] = 1;
int res = 0;
for(int y : edge[x])
if(!vis[y] && y != fa) dfsxin(y, x), siz[x] += siz[y], res = max(res, siz[y]);
res = max(res, tot - siz[x]);
if(res < mn) root = x, mn = res;
}
void getroot(int x)
{
dfsxin(x, 0), tot = siz[x], mn = n, dfsxin(x, 0);
}
void dfs(int x, int fath)
{
book[x] = 2, fa[x] = fath;
for(int y : edge[x])
if(y != fath && !vis[y]) dfs(y, x);
}
int insert(int color)
{
if(has[color]) return 0;
for(int x : col[color])
{
if(!book[x]) return 1;
if(book[x] == 2) q.push(x), book[x] = 1;
}
has[color] = 1, ++sum; return 0;
}
void merge(int capital)
{
while(!q.empty()) q.pop();
if(insert(c[capital])) return;
while(!q.empty())
{
int x = q.front(); q.pop();
if(!fa[x] || vis[fa[x]] || book[fa[x]] == 1) continue;
if(insert(c[fa[x]])) return;
}
ans = min(ans, sum - 1);
}
void clear(int x, int fath)
{
book[x] = has[c[x]] = fa[x] = 0;
for(int y : edge[x])
if(y != fath && !vis[y]) clear(y, x);
}
void solve(int x)
{
vis[x] = 1;
dfs(x, 0);
sum = 0, merge(x);
clear(x, 0);
for(int y : edge[x])
if(!vis[y]) getroot(y), solve(root);
}
int main()
{
read(n, k), ans = k;
for(int i = 1; i < n; ++i)
{
read(u, v);
edge[u].pb(v), edge[v].pb(u);
}
for(int i = 1; i <= n; ++i) read(c[i]), col[c[i]].pb(i);
getroot(1);
solve(root);
printf("%d", ans);
return 0;
}
杂项
CF1446D2 Frequency Problem (Hard Version)
区间出现最多的数，想到众数，发现这两个数之一一定是众数
反证法，如果不是，那么还可以扩展区间，使它包含这么多个众数，因为是众数所以一定能扩展
把所有众数提出来，枚举剩下的数是哪个即可通过 easy version
注意如果区间不合法，即还有数出现次数更多没关系，因为这一定对应一个更优区间
如果众数个数为 \(m\)，朴素做法的复杂度是 \(O(nm+\sum cnt_{a})\)，考虑优化 \(O(nm)\)
把众数出现看作 \(1\)，当前指定的数为 \(-1\)，则找到尽量远的前缀和相同的位置
画出折线图发现当前数前后 \(O(1)\) 个众数是有用的
把每个指定的数对应前后第一个众数，删除它，继续操作，这样得到新的序列，总长度为 \(O(n)\)
然后统计答案，注意预处理每个位置前后真正对应的答案区间端点
精细实现能做到 \(O(n)\)，但用 \(O(n\log n)\) 也可以
set<int> tot; vector<int> tmp;
typedef set<int>::iterator iter;
int findnxt(int x, int i)
{
int p = lower_bound(num[i].begin(), num[i].end(), x) - num[i].begin();
return num[i][p + 1];
}
int main()
{
read(n);
for(int i = 1; i <= n; ++i) read(a[i]), ++sum[a[i]], num[a[i]].pb(i);
for(int i = 1; i <= n; ++i)
if(sum[i] > sum[zs]) zs = i;
for(int i : num[zs]) tot.insert(i);
for(int i = 1; i <= n; ++i) num[i].pb(n + 1);
for(int i = 1; i <= n; ++i)
if(a[i] != zs) id[i] = cnt;
else id[i] = ++cnt;
for(int i = 0; i <= n + n; ++i) pos[i] = -1;
cerr << zs << " " << cnt << "\n";
for(int i = 1; i <= n; ++i)
{
if(!sum[i] || i == zs) continue;
tmp.clear();
for(int j : num[i])
{
if(j > n) break;
tmp.pb(j);
iter pre = tot.lower_bound(j);
if(!tot.empty() && pre != tot.begin()) tmp.pb(*prev(pre)), tot.erase(*prev(pre));
iter nxt = tot.upper_bound(j);
if(nxt != tot.end()) tmp.pb(*nxt), tot.erase(*nxt);
}
sort(tmp.begin(), tmp.end());
int st1 = n, st2 = n; ++T;
for(int j = 0; j < tmp.size(); ++j)
{
nxt[tmp[j]] = findnxt(tmp[j], a[tmp[j]]) - 1;
if(a[tmp[j]] == zs) st1 = min(st1, tmp[j]);
else st2 = min(st2, tmp[j]);
if(j + 1 < tmp.size()) nxt[tmp[j]] = min(nxt[tmp[j]], tmp[j + 1] - 1);
}
int lsh = lower_bound(num[i].begin(), num[i].end(), st2) - num[i].begin();
lsh ? st2 = num[i][lsh - 1] + 1 : st2 = 1;
lsh = lower_bound(num[zs].begin(), num[zs].end(), st1) - num[zs].begin();
lsh ? st1 = num[zs][lsh - 1] + 1 : st1 = 1;
st1 = max(st1, st2), tim[id[st1 - 1] + n] = T, pos[id[st1 - 1] + n] = st1 - 1;
for(int j = 0, sum = 0, nw = 0; j < tmp.size(); ++j)
{
if(a[tmp[j]] == i) ++nw;
sum = id[tmp[j]] - nw;
if(tim[sum + n] != T) tim[sum + n] = T, pos[sum + n] = tmp[j];
else ans = max(ans, nxt[tmp[j]] - pos[sum + n]);
}
for(int i : tmp) if(a[i] == zs) tot.insert(i);
}
cout << ans;
return 0;
}