【杭电多校比赛记录】2025“钉耙编程”中国大学生算法设计春季联赛（7）
比赛链接本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18836346
开题 + 补题情况
这场就非常的难了，感觉有打区域赛的感觉了，开了两题，一个签到一个树形 DP，1004 写了个二分 + 线段树，不出意料地 TLE 了，实际上是一个线段树二分的板子题，这波是科技点没点够了。
1008 - 木柜子组乐队
考虑用键盘手和不用键盘手，分别计算，很简单的组合数学。
答案为 \(a \times b \times c \times d \times e + a \times b \times c \times C(d, 2)\)。
点击查看代码void solve()
{
i64 a, b, c, d, e;std::cin >> a >> b >> c >> d >> e;
i64 ans = 0;
ans += a * b * c * d * e;
ans += a * b * c * d * (d - 1) / 2;
std::cout << ans << '\n';
}1004 - 最早连续串（补题）
赛时思路对了的，但是科技点没点够，写了个二分 + 线段树查询最值，由于有两个 log，喜提 TLE。
这实际上是一个线段树二分的板子题。
不难发现，对于每一个连续的 \(0\) 或连续的 \(1\)，一定是选取最左边的那一个，因此，我们可以把这一段连续段的长度归属给最左边这个点。
然后在查询时，由于我们要查找的是第一个长度 \(\geq k\) 的 \(op\) 串，因此，我们可以在线段树上进行二分。
对于每一个结点，若它的左节点最大值 \(\geq k\)，则往左节点走，若它的右节点最大值 \(\geq k\)，则往右节点走，若左右节点都不满足，则无解，一直这样走下去，直到走到区间长度为 \(1\) 的结点，此时的位置就是第一个长度 \(\geq k\) 的 \(op\) 串的起始位置。
由于只在线段树上进行了递归，所以这个的复杂度很明显是 \(O(q \log n)\) 的，足以通过此题。
至于每次修改后对线段树的更新，我们可以用一个 \(set\) 来存储所有的连续段的左右端点以及颜色，模拟修改区间颜色以及合并相同颜色的区间，对于旧区间的信息，在线段树上清除掉，对于新区间的信息，在线段树上进行更新，这个操作的复杂度依然是 \(O(q \log n)\)。
因此，总复杂度为 \(O(q \log n)\)，足以通过此题。
点击查看代码#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1
#define int long long
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int N = 2e5 + 9;
struct Node {
int v;
i64 w;
};
struct point {
int v;
i64 p, q;
};
void solve()
{
int n;std::cin >> n;
std::vector<std::vector<point>> e(n + 1);
for(int i = 1;i < n;i ++) {
int u, v, p, q;std::cin >> u >> v >> p >> q;
e.push_back({v, p, q});
e.push_back({u, q, p});
}
std::vector<std::vector<Node>> g(n + 1);
std::vector<point> fa(n + 1);
std::vector<i64> dep(n + 1);
int s, t;std::cin >> s >> t;
auto dfs = [&](auto &&self, int st, int pre, i64 w) -> void {
dep = dep + 1;
for(auto &i : e) {
if(i.v == pre)continue;
g.push_back({i.v, i.p});
fa = {st, i.p, i.q};
self(self, i.v, st, i.q);
}
};
dfs(dfs, s, 0, 0);
std::vector<i64> dp(n + 1);
auto dfs1 = [&](auto &&self, int st) -> void {
dp = 0;
for(auto & : g) {
self(self, v);
dp = std::max(dp, dp + dp + fa.p + fa.q);
}
};
dfs1(dfs1, s);
auto lca = [&](int x, int y) -> int {
while(x != y) {
if(dep < dep) {
std::swap(x, y);
}
x = fa.v;
}
return x;
};
int lc = lca(s, t);
i64 ans = 0;
int pre = 0;
while(s != lc) {
ans += dp;
if(pre != 0) {
if(dp + fa.p + fa.q > 0) {
ans -= dp + fa.p + fa.q;
}
}
ans += fa.q;
pre = s;
s = fa.v;
}
int pres = pre;
pre = 0;
while(t != lc) {
ans += dp;
if(pre != 0) {
if(dp + fa.p + fa.q > 0) {
ans -= dp + fa.p + fa.q;
}
}
ans += fa.p;
pre = t;
t = fa.v;
}
int pret = pre;
int hi = fa.v;
if(hi != 0) {
i64 oh = dp;
if(dp + fa.p + fa.q > 0) {
oh -= dp + fa.p + fa.q;
}
ans = std::max(ans, ans + oh + fa.p + fa.q);
}
i64 tmp = dp;
if(pres != 0) {
if(dp + fa.p + fa.q > 0) {
tmp -= dp + fa.p + fa.q;
}
}
if(pret != 0) {
if(dp + fa.p + fa.q > 0) {
tmp -= dp + fa.p + fa.q;
}
}
ans = std::max(ans, ans + tmp);
std::cout << ans << '\n';
}
signed main()
{
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int t = 1;std::cin >> t;
while(t --)solve();
return 0;
}1009 - 未来城市（补题）
看了题解后真的觉得太巧妙了。
对于每个能源核心，可以看作一个结点，而每个项目就是一个连接了两个能源核心的边。
然后仔细一看，这不就可以用类似最大生成树的方式来选择边吗？
但这个和最大生成树又不太一样，因为它最终形成的并不是一棵树，而是允许有一个环，也就是说，形成 \(n\) 个点 \(n\) 条边，一条边刚好对应一个结点。
于是我初步尝试了一个想法，找这个图上的最大生成树，然后对于树外的边，逐一枚举加进来的情况，取答案最大值。
然后，喜提 WA 了，为什么呢？因为选边后形成的不一定是一个连通块，而是很多个连通块，对于每一个连通块，都满足边数 \(\leq\) 点数。
因此，就有一个新的思路了，依然是对边按边权从大到小排序，逐一加边，如果加上当前这条边后，所在的连通块不满足边数 \(\leq\) 点数，那就不加进来，最后得到的就会是最大的答案。
点击查看代码#include <bits/stdc++.h>
#define inf32 1e9
#define inf64 2e18
#define ls o << 1
#define rs o << 1 | 1
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
const int N = 2e5 + 9;
struct segtree {
std::vector<int> t;
int n;
segtree(int _n, std::vector<int> &a) {
n = _n;
t.resize((n + 1) << 2);
build(1, n, 1, a);
}
segtree() {}
void build(int s, int e, int o, std::vector<int> &a) {
if(s == e) {
t = a;
return;
}
int mid = s + e >> 1;
build(s, mid, ls, a);
build(mid + 1, e, rs, a);
pushup(o);
}
void change(int ix, int x, int s, int e, int o) {
if(s == e && s == ix) {
t = x;
return;
}
int mid = s + e >> 1;
if(ix <= mid)change(ix, x, s, mid, ls);
else change(ix, x, mid + 1, e, rs);
pushup(o);
}
int query(int x, int s, int e, int o) {
// std::cout << s << ' ' << e << '\n';
if(s == e)return s;
int mid = s + e >> 1;
if(t >= x)return query(x, s, mid, ls);
if(t >= x)return query(x, mid + 1, e, rs);
return -1;
}
void pushup(int o) {
t = std::max(t, t);
}
};
struct Node {
int l, r, c;
bool operator < (const Node &v) const {
if(l != v.l)return l < v.l;
else return r < v.r;
}
};
void solve()
{
std::string s;std::cin >> s;
int n = s.size();
s = ' ' + s;
std::set<Node> st;
for(int i = 1, j = 1;i <= n;i = j + 1, j = i) {
while(j + 1 <= n && s == s)j ++;
st.insert({i, j, s - '0'});
}
std::array<std::vector<int>, 2> a;
for(int i = 0;i < 2;i ++) {
a.resize(n + 1);
}
for(auto & : st) {
a = r - l + 1;
}
std::array<segtree, 2> sgt;
for(int i = 0;i < 2;i ++) {
sgt = segtree(n, a);
}
int q;std::cin >> q;
while(q --) {
int op, k;std::cin >> op >> k;
int ix = sgt.query(k, 1, n, 1);
std::cout << ix << '\n';
if(ix == -1)continue;
auto ite = st.lower_bound({ix, -1, 1});
int s = ite -> l, e = ite -> r, c = ite -> c;
if(e - s + 1 == k) {
auto pre = ite;
auto suf = ite;
pre --;
suf ++;
sgt.change(s, 0, 1, n, 1);
if(ite != st.begin()) {
sgt.change(pre -> l, 0, 1, n, 1);
}
if(suf != st.end()) {
sgt.change(suf -> l, 0, 1, n, 1);
}
if(ite != st.begin()) {
s = pre -> l;
}
if(suf != st.end()) {
e = suf -> r;
}
if(suf != st.end()) {
st.erase(suf);
}
if(ite != st.begin()) {
st.erase(ite);
st.erase(pre);
} else {
st.erase(ite);
}
st.insert({s, e, c ^ 1});
sgt.change(s, e - s + 1, 1, n, 1);
} else {
auto pre = ite;
pre --;
sgt.change(s, 0, 1, n, 1);
if(ite != st.begin()) {
sgt.change(pre -> l, 0, 1, n, 1);
}
int l = s + k;
if(ite != st.begin()) {
s = pre -> l;
}
if(ite != st.begin()) {
st.erase(ite);
st.erase(pre);
} else {
st.erase(ite);
}
st.insert({s, l - 1, c ^ 1});
st.insert({l, e, c});
sgt.change(s, l - 1 - s + 1, 1, n, 1);
sgt.change(l, e - l + 1, 1, n, 1);
}
}
}
int main()
{
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int t = 1;std::cin >> t;
while(t --)solve();
return 0;
}1005 - 随机游走（补题）
对于此题，首先手画一下可以发现，对于所有的边双连通分量，以及这些分量之间的路径，都是可以随意行走的（因为始终可以通过另一条路径绕过来）。
因此，我们可以把这些点全部缩成一个点，但这题实际上是不需要使用缩点算法找边双的，因为可以发现，我们要找的这些可以随意行走的点，实际上就是把周围的枝条抠出掉的点，那么，拓扑排序就可以完成这件事。
（以下说的“边双”都是指图中所有的边双以及边双之间的路径构成的点集）
把那些点缩成一个点后，这个图就变成一棵树了，此时就很明显了，答案就是找树的直径。
如果对于没有边双的图，找树的直径确实是正确的，但是对于有边双的图，我们可以先往边双上走，这样是可以走回来的，此时的答案应该是：不包含边双的树的直径加上往边双走获得的价值。
那么此时又有问题了，如果直径包含边双怎么办呢？
也很简单，用类似 1007 的处理方法，我们把边双作为这棵树的根，这样的话，对于每一棵子树找到的直径，不可能经过边双，那么也就不会重复计算走边双的价值。
赛时想到了拓扑的，但实实在在是没想到是树的直径。
点击查看代码#include #define inf32 1e9#define inf64 2e18#define ls on >> m; std::vector a(n + 1), in(n + 1); for(int i = 1;i > a; } std::vector g(n + 1); for(int i = 1;i > u >> v; g.push_back(v); g.push_back(u); in ++; in ++; } std::vector vis(n + 1); std::queue q; for(int i = 1;i
页:
[1]