当前位置：首页 > news >正文

Solutions - 板刷 UOJ 小记

news 2026/4/18 6:49:00

开始板刷 UOJ!

UOJ #1. A + B Problem

AC Time：2026-04-16 16:23:16

全 UOJ 最难题！（

#include <bits/stdc++.h>
using namespace std;int main(){int a, b;cin >> a >> b;cout << a+b;return 0;
}

UOJ #2. 【NOI2014】起床困难综合症

AC Time：2026-04-16 17:25:07

比较基础的题了。

发现每一位是独立的，我们先预处理出每一位选 \(0\) 或 \(1\)，运算以后最后的值。然后就可以用一种类似数位 DP 的方式搞了。

然后做完了。

复杂度：\(\mathrm O(n \log V)\)，\(V\) 为值域。

UOJ #3. 【NOI2014】魔法森林

AC Time：2026-03-23 17:53:34

这题在我板刷 UOJ 之前就 A 了，为了完整性放在这里。

枚举 A 的最大值，维护在 A 的最大值取某个值的情况下 B 的 MST，发现是一个动态加边 MST，用 LCT 维护。

然后做完了。\(\mathrm O(n \log n)\)。实现的时候为了方便维护可以把边转换成点。

#include <bits/stdc++.h>
#define llong long long
#define N 200005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, m, ans = 1e9+7;
struct Edge{int u, v, w1, w2;
};
Edge G[N];typedef pair<int, int> Node;
int son[N][4], fa[N], id[N], tag[N];
Node val[N];
int tmp[N], top;#define get(x) (son[fa[x]][0] == x ? 0 : (son[fa[x]][1] == x ? 1 : 2))inline void pushup(int x){val[x] = max({val[son[x][0]], val[son[x][1]], make_pair(G[id[x]].w2, id[x])});return;
}
inline void addtag(int x){swap(son[x][0], son[x][1]);tag[x] ^= 1;return;
}
inline void pushdown(int x){if(!tag[x]) return;addtag(son[x][0]), addtag(son[x][1]);tag[x] = 0;return;
}
inline void rotate(int y){int x = fa[y], k = get(y);son[fa[x]][get(x)] = y, fa[y] = fa[x];son[x][k] = son[y][k^1], fa[son[y][k^1]] = x;son[y][k^1] = x, fa[x] = y;pushup(x), pushup(y);return;
}
inline void splay(int x){int now = x;tmp[top = 1] = now;while(get(now) != 2) tmp[++top] = now = fa[now];while(top) pushdown(tmp[top--]);while(get(x) != 2){if(get(fa[x]) != 2)rotate(get(x) == get(fa[x]) ? fa[x] : x);rotate(x);}return;
}inline void access(int x){for(int y = 0; x; x = fa[y = x])splay(x), son[x][1] = y, pushup(x);return;
}
inline void makeroot(int x){access(x);splay(x);addtag(x);return;
}
inline int find(int x){access(x);splay(x);pushdown(x);while(son[x][0]) pushdown(x = son[x][0]);splay(x);return x;
}
inline void split(int x, int y){makeroot(x);access(y);splay(y);
}
inline void link(int x, int y){access(x);makeroot(x);splay(x);fa[x] = y;return;
}
inline void cut(int x, int y){makeroot(x);access(y);splay(y);son[y][0] = fa[x] = 0;pushup(y);return;
}int main(){read(n, m);for(int i = 1; i <= m; ++i)read(G[i].u, G[i].v, G[i].w1, G[i].w2);sort(G+1, G+m+1, [&](Edge o1, Edge o2){return o1.w1 < o2.w1;});for(int i = 1; i <= m; ++i)id[i+n] = i, val[i+n] = make_pair(G[i].w2, i);for(int i = 1; i <= m; ++i){int u = G[i].u, v = G[i].v;if(find(u) != find(v)){link(u, i+n);link(v, i+n);}else{split(u, v);splay(u);if(val[u].first > G[i].w2){int j = val[u].second;cut(G[j].u, j+n);cut(G[j].v, j+n);link(u, i+n);link(v, i+n);}}if(find(1) == find(n)){split(1, n);splay(1);ans = min(ans, G[i].w1+val[1].first);}}if(ans > 1e9) puts("-1");else printf("%d", ans);return 0;
}