巅峰赛 #31 题解
2026-03-02 22:15:00
发布于：广东
86阅读
0回复
0点赞
目前来看，这大概是我最后一次打巅峰赛了。
A
Difficulty：3- / Easy
Tag：-
糖丸了。删边看成删点然后写了神秘拓扑。如此视力，如何省选？
注意到树上割任意一条边一定会分成两个子树。所以答案只能是 。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <int> a(m + 5);
std::vector <std::vector <int>> v(n + 5);
std::vector <int> in(n + 5);
for(int i = 1; i <= m; i++){
std::cin >> a[i];
}
for(int i = 1; i < n; i++){
int x, y;
std::cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
std::cout << std::max(0, m - 1) << '\n';
}
}
时间复杂度：。
B
不到啊，没调出来。
C
Difficulty：3- / Easy
显然这个就是让我们求最长合法括号子序列。贪心选就行了。
namespace cjdst{
void solve(){
int n;
std::string a;
std::cin >> n >> a;
int cur = 0, ans = 0;
for(char c:a){
if(c == '(') cur++;
else{
cur--;
if(cur < 0) ans++, cur = 0;
}
}
std::cout << ans + cur << '\n';
}
}
时间复杂度：。
D
Difficulty：3.8 / Easy+
Tag：双堆
好题。
先离散化一下。
注意到题目可以转化成 次区间 ，可以删除不超过 个区间，求序列 最小值。
遇到最小化最大值的，显然二分答案，转化成让序列 不超过 的最小删除区间数量。
然后有个显然的贪心，枚举当前时刻，如果当前的所在区间超过 个，则按区间结束位置从大到小删除。感性理解证明不难。
现在我们需要一个数据结构支持单点增删求最大 / 最小值。显然可以 set。
但是 2log 还是太考验常数了，set 估计卡不过去。所以：
我们可以用双堆维护这个操作。具体实现看代码。
namespace cjdst{
class QQ{
std::priority_queue <int> q1, q2;
public:
void insert(int val){
q1.push(val);
}
void erase(int val){
q2.push(val);
while(!q1.empty() && !q2.empty() && q1.top() == q2.top()){
q1.pop(), q2.pop();
}
}
int top(){
return q1.top();
}
int size(){
return q1.size() - q2.size();
}
};
bool check(int mid, int n, int m, std::vector <pii> &a){
QQ q, qq;
int l = 1, ans = 0;
for(int i = 1; i <= n * 2; i++){
while(l <= n && a[l].first == i){
q.insert(a[l].second);
qq.insert(-a[l].second);
l++;
}
while(qq.size() && qq.top() > -i){
q.erase(-qq.top());
qq.erase(qq.top());
}
while(q.size() > mid){
ans++;
qq.erase(-q.top());
q.erase(q.top());
}
}
return (ans <= m);
}
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <pii> a(n + 5);
std::vector <int> c(n * 2 + 5);
int ct = 0;
for(int i = 1; i <= n; i++){
std::cin >> a[i].first >> a[i].second;
c[++ct] = a[i].first;
c[++ct] = a[i].second;
}
std::sort(c.begin() + 1, c.begin() + ct + 1);
for(int i = 1; i <= n; i++){
a[i].first = std::lower_bound(c.begin() + 1, c.begin() + ct + 1, a[i].first) - c.begin();
a[i].second = std::lower_bound(c.begin() + 1, c.begin() + ct + 1, a[i].second) - c.begin();
}
std::sort(a.begin() + 1, a.begin() + n + 1);
int l = 0, r = n;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid, n, m, a)) r = mid - 1;
else l = mid + 1;
}
std::cout << l << '\n';
}
}
时间复杂度：。
E
Difficulty：3- / Easy
Tag：-
贪心，显然修改前面的最优。
namespace cjdst{
void solve(){
ll n, m, k, b;
std::string s;
std::cin >> n >> m >> k >> b >> s;
s = " " + s + " ";
std::vector <std::string> a(m + 5);
std::vector <int> p(n + 5);
for(int i = 1; i <= m; i++){
std::cin >> a[i];
}
for(int i = 1; i <= n; i++){
std::cin >> p[i];
}
for(int i = 1; i <= n; i++){
if(s[i] == 'a') continue;
if(!k) break;
bool flag = 0;
while(s[i] != 'a' && b >= p[i]){
flag = 1;
s[i]--;
b -= p[i];
}
k -= flag;
}
s = s.substr(1, n);
int ans = 1;
for(int i = 1; i <= m; i++){
if(a[i] <= s) ans++;
}
std::cout << ans << '\n' << s << '\n';
}
}
时间复杂度：。
F
Difficulty：4.6 / Easy
Tag：MST
考虑按时间建图。我们发现如果 已经连通，那再连 的边是无意义的，可以直接删除。
删完以后发现会连成一个森林。考虑在这个森林中查询。
既然是树，我们会发现只有 路径上所有边都连上 才能连通。所以答案就是路径上所有边的时间的最大值。边转点树剖套 ST 表即可。
namespace cjdst{
template <typename T>
class Sparse_Table{
std::vector <std::vector <T>> st;
int n;
public:
Sparse_Table(int n, std::vector <T> a){
this -> n = n;
st.resize(a.size() + 5, std::vector <T>(std::__lg(n) + 5));
for(int i = 1; i <= n; i++){
st[i][0] = a[i];
}
for(int i = 1; i <= std::__lg(n); i++){
for(int j = 1; j <= n; j++){
if(j + (1 << i) - 1 > n) break;
st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
}
}
T query(int l, int r){
int idx = std::__lg(r - l + 1);
return std::max(st[l][idx], st[r - (1 << idx) + 1][idx]);
}
};
class Tree_Spliter{
std::vector <std::vector <pii>> edges;
std::vector <int> dfn, dep, father, head, rank, son, siz;
void dfs(int cur, int fa, std::vector <int> &b){
father[cur] = fa;
siz[cur] = 1;
dep[cur] = dep[fa] + 1;
for(auto i:edges[cur]){
if(i.first == fa) continue;
b[i.first] = i.second;
dfs(i.first, cur, b);
siz[cur] += siz[i.first];
if(siz[son[cur]] < siz[i.first]) son[cur] = i.first;
}
}
void dfs2(int cur, int top, int &curdfn){
head[cur] = top;
curdfn++;
dfn[cur] = curdfn;
rank[curdfn] = cur;
if(!son[cur]) return;
dfs2(son[cur], top, curdfn);
for(auto i:edges[cur]){
if(i.first != son[cur] && i.first != father[cur]) dfs2(i.first, i.first, curdfn);
}
}
public:
Tree_Spliter(){}
Tree_Spliter(int n, int root, std::vector <std::vector <pii>> a, std::vector <int> &b){
dfn.resize(n + 5), dep.resize(n + 5), father.resize(n + 5);
head.resize(n + 5), rank.resize(n + 5);
son.resize(n + 5), siz.resize(n + 5);
edges = a;
dfs(root, 0, b);
std::vector <int> c(n + 5);
int curdfn = 0;
dfs2(root, root, curdfn);
for(int i = 1; i <= n; i++){
c[dfn[i]] = b[i];
}
b = c;
}
int get_lca(int x, int y){
int hx = head[x], hy = head[y];
while(hx != hy){
if(dep[hx] < dep[hy]) y = father[hy], hy = head[y];
else x = father[hx], hx = head[x];
}
return (dep[x] < dep[y] ? x : y);
}
std::vector <pii> get_path(int x, int y){
std::vector <pii> ans;
int hx = head[x], hy = head[y];
while(hx != hy){
if(dep[hx] < dep[hy]){
ans.push_back({dfn[hy], dfn[y]});
y = father[hy], hy = head[y];
}
else{
ans.push_back({dfn[hx], dfn[x]});
x = father[hx], hx = head[x];
}
}
if(dfn[x] > dfn[y]) std::swap(x, y);
if(dfn[x] + 1 <= dfn[y]) ans.push_back({dfn[x] + 1, dfn[y]});
return ans;
}
pii get_subtree(int idx){
return {dfn[idx], dfn[idx] + siz[idx] - 1};
}
int node_to_dfn(int idx){
return dfn[idx];
}
int dfn_to_node(int idx){
return rank[idx];
}
};
class dsu{
std::vector <int> father, siz;
public:
int n, unions;
dsu(){
n = 0;
}
dsu(int n){
this -> n = n;
unions = n;
father.resize(n + 5, 0);
siz.resize(n + 5, 1);
for(int i = 1; i <= n; i++){
father[i] = i;
}
}
int find(int n){
return (father[n] == n ? n : father[n] = find(father[n]));
}
bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return 0;
if(siz[x] < siz[y]) std::swap(x, y);
siz[x] += siz[y];
father[y] = x;
unions--;
return 1;
}
};
void solve(){
int n, m, q;
std::cin >> n >> m >> q;
std::vector <std::vector <pii>> mst(n + 5);
dsu u(n);
for(int i = 1; i <= m; i++){
int x, y;
std::cin >> x >> y;
if(u.merge(x, y)){
mst[x].push_back({y, i});
mst[y].push_back({x, i});
}
}
for(int i = 2; i <= n; i++){
if(u.merge(1, i)){
mst[1].push_back({i, m + 1});
mst[i].push_back({1, m + 1});
}
}
std::vector <int> b(n + 5);
Tree_Spliter tr(n, 1, mst, b);
Sparse_Table <int> st(n, b);
while(q--){
int x, y;
std::cin >> x >> y;
if(x == y){
std::cout << "0\n";
continue;
}
auto cur = tr.get_path(x, y);
int ans = 0;
for(auto i:cur){
ans = std::max(ans, st.query(i.first, i.second));
}
if(ans == m + 1) std::cout << "-1\n";
else std::cout << ans << '\n';
}
}
}
时间复杂度：。
F
Difficulty：6.3 / Easy+
Tag：整体二分，并查集
注意到这个查询是可二分的。显然吧。
所以每次二分我们只需要看 的边是否能让它们连通。
显然可以整体二分。
我们可以改一下递归顺序，逐层处理。显然每一层只会加 条边。
搭配并查集即可 ，常数小。
code：你觉得我会写吗？
目前来看，这大概是我最后一次打巅峰赛了。
这句话的意思是：我在 3/1 22:00 之前打的最后一场巅峰赛大概是这一场，用“大概”是因为题解是在 3/1 12:29 写的所以不能确定 3/1 12:29 - 22:00 这段时间是否还打过其它巅峰赛，体现了这篇题解的严谨性，没有别的意思。/bangbangt
全部评论 13
目前来看，这大概是我最后一次打巅峰赛了。
这句话的意思是：我在 3/1 22:00 之前打的最后一场巅峰赛大概是这一场，用“大概”是因为题解是在 3/1 12:29 写的所以不能确定 3/1 12:29 - 22:00 这段时间是否还打过其它巅峰赛，体现了这篇题解的严谨性，没有别的意思。/bangbangt
2026-03-03 来自 重庆
0用“大概”是因为题解是在 3/1 12:29 写的所以不能确定 3/1 12:29 - 22:00 这段时间是否还打过其它巅峰赛
我的天呐时空穿越大人
2026-03-01 来自 广东
0
有帮助，赞一个