巅峰赛T4-T6题解
2025-03-30 22:03:00
发布于：广东
546阅读
0回复
0点赞
T4
个人难度：绿 下位
一眼并查集。
题目问题是如果某些人离开群后有多少人得不到消息，我们可以假设这些人在一开始时就离开，
然后再将查询反转，把问题转换成第 个人加入第 个群后会有多少人收不到消息。这样就转换成简单的并查集问题了，只需要查询班长所在的集合有多少人即可。
注意特判（如样例二）的情况，就是班长没有加入任何一个群，这时得不到消息的人数为 而不是 ，因为班长是知道这个消息的。
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <memory.h>
using namespace std;
//反正内存用的是ACGO的，我不花钱想用就用（
struct Union{
vector <int> father;
vector <int> size;
int n;
int find(int n){
return (father[n] == n ? n : father[n] = find(father[n]));
}
void merge(int x, int y){
int n = find(x), m = find(y);
if(n == m){//如果已经在一个集合
size[n]--;//说明有重复元素，集合元素--
return;
}
father[max(n, m)] = min(n, m);//合并
size[min(n, m)] += size[max(n, m)] - 1;
}
void resize(int n){
this -> n = n;
father.resize(n);
size.resize(n);
for(int i = 1; i < n; i++) father[i] = i, size[i] = 1;
}
}u;
int cur;
struct Query{//记录查询，需要重复使用
int x, y;
}query[200005];
set <int> a[200005];//使用set可以O(logN)删除，方便处理一开始的退群
set <int> monitor;//记录班长所在的群
int ans[200005];//记录答案
int last[1000005];//记录这个人加入的编号最小的班群
int n, m, q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
u.resize(m + 5);
for(int i = 1; i <= m; i++){
int len;
cin >> len;
for(int j = 1; j <= len; j++){
int val;
cin >> val;
a[i].insert(val);
}
}
for(int i = 1; i <= q; i++){
cin >> query[i].x >> query[i].y;
a[query[i].y].erase(query[i].x);//提前退群
}
for(int i = 1; i <= m; i++){
u.size[i] = a[i].size();
for(int j:a[i]){
if(j == 1) monitor.insert(i);//如果是班长记得加入monitor
if(!last[j]) last[j] = i;
else u.merge(i, last[j]);//和带 j 的最小的集合合并
}
}
ans[q + 1] = (monitor.empty() ? n - 1 : n - u.size[u.find(*monitor.begin())]);//注意要计算此时的集合大小，对应最后一次查询
for(int i = q; i; i--){//反转，转换成加群问题
if(query[i].x == 1) monitor.insert(query[i].y);//如果是班长记得加入monitor
if(!last[query[i].x]) last[query[i].x] = query[i].y;
else u.merge(query[i].y, last[query[i].x]);//合并
u.size[u.find(query[i].y)]++;//注意这个人加群了，所以size++
ans[i] = (monitor.empty() ? n - 1 : n - u.size[u.find(*monitor.begin())]);//计算集合大小
}
for(int i = 2; i <= q + 1; i++){
cout << ans[i] << '\n';
}
return 0;
}
时间复杂度：（我也不知道啊，我乱写的）
T5
个人难度：黄 中位
首先打个正常的 DP，令 为到达第 行第 列时宝藏价值最大值，则有
如果暴力硬算，时间复杂度 。
注意到这个 max 可以分成左右两部分，即
我们可以使用线段树来求出区间和。
注意使用滚动数组，否则会 MLE；还要特判 的情况。
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
struct Segtree{//线段树板子
int n;
vector <int> tree, left, right;
Segtree(){}
Segtree(int n){
this -> n = n;
tree.resize(n * 4 + 5, 0);
left.resize(n * 4 + 5, 0);
right.resize(n * 4 + 5, 0);
build(1, 1, n);
}
void clear(){
tree.resize(n * 4 + 5, 0);
}
void build(int u, int l, int r){
left[u] = l, right[u] = r;
if(l == r) return;
int mid = l + r >> 1;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
};
void update(int u, int idx, int val){
if(left[u] >= idx && right[u] <= idx){
tree[u] = max(tree[u], val);
return;
}
int mid = left[u] + right[u] >> 1;
if(idx <= mid) update(u * 2, idx, val);
else update(u * 2 + 1, idx, val);
tree[u] = max(tree[u * 2], tree[u * 2 + 1]);
}
int query(int u, int l, int r){
if(l > r) return 0;
if(left[u] >= l && right[u] <= r) return tree[u];
int mid = left[u] + right[u] >> 1, ans = 0;
if(l <= mid) ans = max(ans, query(u * 2, l, r));
if(r > mid) ans = max(ans, query(u * 2 + 1, l, r));
return ans;
}
};
vector <vector <int>> a;
Segtree dp1, dp2;
int n, m;
int mx;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
a.resize(n + 5, vector <int> (m + 5));
dp1 = Segtree(m + 5);
dp2 = Segtree(m + 5);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
if(m == 1){//阴
cout << a[1][1];
return 0;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int val = max(dp1.query(1, 1, j - 1), dp1.query(1, j + 1, m)) + a[i][j];//求出区间和
dp2.update(1, j, val);//单点修改
mx = max(mx, val);
}
dp1 = dp2;//滚动数组
dp2.clear();
}
cout << mx;
return 0;
}
时间复杂度：。
什么？你说直接记录前缀最大值和后缀最大值也能过？没错，赛时我唐了。
T6
个人难度：绿 上位
本题是道大模拟题，我将使用分类讨论的思路讲解。为方便表示时间复杂度，我们令 为数字个数，即 。
注意到题目只需要我们凑出 的倍数，所以除法是个诈骗，可以不用管。
于是我们可以把构造结果分成 种情况，分别判断。
-
。
模拟难度：红 中位
显然，只有一种情况，直接判断、输出即可。注意乘法取模。
namespace multiply{ bool solve(){ if(a[1] % 24 * a[2] % 24 * a[3] % 24 * a[4] % 24 == 0){ cout << a[1] << '*' << a[2] << '*' << a[3] << '*' << a[4] << '\n'; return 1; } return 0; } }时间复杂度：。
-
。
模拟难度：红 上位
我们可以选择一个数作为 ，剩下三个数就作为 。
namespace triple{ bool check(){ if((a[1] + a[2] * a[3] * a[4]) % 24 == 0){//判断是否合法 cout << a[1] << '+' << a[2] << '*' << a[3] << '*' << a[4] << '\n'; return 1; } if((a[1] - a[2] * a[3] * a[4]) % 24 == 0){ cout << a[1] << '-' << a[2] << '*' << a[3] << '*' << a[4] << '\n'; return 1; } return 0; } bool solve(){ for(int i = 1; i <= 4; i++){ swap(a[1], a[i]);//交换 a_i if(check()){ swap(a[1], a[i]); return 1; } swap(a[1], a[i]); } return 0; } }时间复杂度：。
-
。
模拟难度：橙 上位
都有两种选择情况：正，负。
所以我们可以爆搜一波，如果有可能的结果，就对应输出。
注意，第一个数不能为负，所以如果 ，需要找一个大于 的数代替 。
namespace without_brackets{ bool state[1005];//记录状态 void print(){ if(state[1]){//如果 a_i 为负 int idx = -1; for(int i = 2; i <= 5; i++){ if(!state[i]){//找到第一个不为负的元素 idx = i; break; } } cout << a[idx];//交换这两个数的输出顺序 for(int i = 1; i <= 4; i++){ if(i == idx) cout << '-' << a[1]; else cout << (state[i] ? '-' : '+') << a[i]; } }else{ cout << a[1];//按顺序输出 for(int i = 2; i <= 4; i++){ cout << (state[i] ? '-' : '+') << a[i]; } } cout << '\n'; } bool dfs(int idx, int ct){//爆搜 if(idx > 4){ if(ct == 0){//如果该情况合法就输出 print(); return 1; } return 0; } if(dfs(idx + 1, (ct + a[idx]) % 24)) return 1;//选择加 a_i state[idx] = 1; if(dfs(idx + 1, ((ct - a[idx]) % 24 + 24) % 24)){//选择减 a_i state[idx] = 0; return 1; } state[idx] = 0; return 0; } bool solve(){ return dfs(1, 0); } }时间复杂度：。
-
。
模拟难度：橙 上位
我们先选好配对的两个数，再和第三种情况一样，爆搜四个数的状态，最后输出即可。
namespace with_2_brackets{ int state[1005]; void print(){ cout << '('; if(state[1] == -1){//如果第一个数为负就先输出第二个数 cout << a[2] << '-' << a[1]; }else{ cout << a[1] << (state[2] == 1 ? '+' : '-') << a[2]; } cout << ")*("; if(state[3] == -1){//同理 cout << a[4] << '-' << a[3]; }else{ cout << a[3] << (state[4] == 1 ? '+' : '-') << a[4]; } cout << ")\n"; } bool dfs(int idx){ if(idx > 4){ if((a[1] * state[1] + a[2] * state[2]) * (a[3] * state[3] + a[4] * state[4]) % 24 == 0){//合法就输出 print(); return 1; } return 0; } state[idx] = 1;//选择正 if(dfs(idx + 1)){ state[idx] = 0; return 1; } state[idx] = -1;//选择负 if(dfs(idx + 1)){ state[idx] = 0; return 1; } state[idx] = 0; return 0; } bool solve(){ for(int i = 2; i <= 4; i++){ swap(a[2], a[i]);//挑选两两配对的数 if(dfs(1)){ swap(a[2], a[i]); return 1; } swap(a[2], a[i]); } return 0; } }时间复杂度：。
-
。
模拟难度：黄 中位
这里的右括号可以加在任何地方，如 。
我们先挑选 ，即乘数，然后搜索每个数的 个状态。假设现在要枚举状态的数为 ，则 种状态的结果如下：
- ，这是 在括号外面，并且符号为正的结果。
- ，这是 在括号外面，并且符号为负的结果。
- ，这是 在括号里面，并且符号为正的结果。
- ，这是 在括号里面，并且符号为负的结果。
接着，我们把所有在括号内和在括号外的数分别进行组合、输出。
namespace with_1_bracket{//Warning:特大24点来袭！！！ int state[1005]; string add(vector <int> v){//返回表达式，这个相当于情况 4 输出的升级版 string s; if(v.empty()) return s;//如果是空的直接返回 if(state[v.front()] & 1){//如果首位为负 int idx = -1; for(int i:v){ if(~state[i] & 1){//找到第一个不为负的 idx = i; break; } } if(idx == -1){ for(int i:v){ s += '-';//实在没办法了就加个符号标注一下，后面再处理 s += to_string(a[i]); } return s; } for(int i:v){ if(i == v.front()){//交换输出 s += to_string(a[idx]); }else if(i == idx){ s += '-'; s += to_string(a[v.front()]); }else{ s += ((state[i] & 1) ? '-' : '+'); s += to_string(a[i]); } } }else{ for(int i:v){ if(i != v.front()) s += ((state[i] & 1) ? '-' : '+');//否则正常输出 s += to_string(a[i]); } } return s; } bool print(){ vector <int> in_bkt, out_bkt; for(int i = 2; i <= 4; i++){ if(state[i] > 1) in_bkt.push_back(i);//判断是在括号内还是在括号外 else out_bkt.push_back(i); } if(in_bkt.empty()) return 0;//如果没有一个是在括号内的就说明不合法 string s1 = add(in_bkt), s2 = add(out_bkt);//分别进行组合 if(!s1.empty() && s1.front() == '-'){//如果 s1 开头是负号就要先输出 s2 cout << s2 << '-' << a[1] << "*("; for(int i = 1; i < s1.size(); i++){ if(s1[i] == '-') cout << '+';//s1 所有的负号转正号 else cout << s1[i]; } cout << ")\n"; return 1; } cout << a[1] << "*(" << s1 << ')';//正常输出 if(!s2.empty()){ if(s2.front() != '-') cout << '+';//如果 s2 开头不为 - 就得添上 + 连接 cout << s2; } cout << '\n'; return 1; } bool dfs(int idx, int ct){//爆搜 if(idx > 4){ if(ct == 0){ return print(); } return 0; } if(dfs(idx + 1, (ct + a[idx]) % 24)) return 1;//+k state[idx] = 1; if(dfs(idx + 1, ((ct - a[idx]) % 24 + 24) % 24)){//-k state[idx] = 0; return 1; } state[idx] = 2; if(dfs(idx + 1, (ct + a[1] * a[idx]) % 24)){//+ak state[idx] = 0; return 1; } state[idx] = 3; if(dfs(idx + 1, ((ct - a[1] * a[idx]) % 24 + 24) % 24)){//-ak state[idx] = 0; return 1; } state[idx] = 0; return 0; } bool solve(){ for(int i = 1; i <= 4; i++){ swap(a[1], a[i]);//挑选乘数 if(dfs(2, 0)){ swap(a[1], a[i]); return 1; } swap(a[1], a[i]); } return 0; } }时间复杂度：。
卧槽类似我了 谁抄我题解我 [数据删除]
全部评论 13
T4 30pts求调
#include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f; } void write(int x) { if(x<0){x=-x;putchar('-');} if(x/10) write(x/10); putchar(x%10+48); } int n=read(),m=read(),q=read(); set<int>st[200005],qn[200005]; pair<int,int>pr[200005]; bool ci[200005]; bool vis[200005]; set<int>cs; void dfs(int id) { cs.insert(id); for(auto it:qn[id]) { if(ci[it])continue; ci[it]=1; for(auto iit:st[it]) if(!cs.count(iit)) { cs.insert(iit); dfs(iit); } } return ; } signed main() { for(int i=1;i<=m;i++) { int k=read(); for(int j=1;j<=k;j++) { int p=read(); st[i].insert(p); qn[p].insert(i); } } for(int i=1;i<=q;i++) { int p=read(),c=read(); st[c].erase(p); qn[p].erase(c); pr[i]={p,c}; } dfs(1); stack<int>stk; for(int i=q;i>=1;i--) { stk.push(n-cs.size()); int p=pr[i].first,c=pr[i].second; //cout<<ci[c]<<"-\n"; if(ci[c]==1) { cs.insert(p); //cout<<1<<endl; continue; } if(cs.count(p)) { for(auto it:st[c])cs.insert(it); ci[c]=1; //cout<<2<<endl; continue; } st[c].insert(p); qn[p].insert(c); //cout<<3<<endl; } while(!stk.empty()) { write(stk.top()); cout<<'\n'; stk.pop(); } return 0; }2025-03-30 来自 江苏
1大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬大佬
2025-04-17 来自 浙江
0
有帮助，赞一个