巅峰赛T4-T6题解
2025-03-30 22:03:00
发布于：广东
116阅读
42回复
2点赞
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; } }时间复杂度：。
卧槽类似我了 谁抄我题解我 [数据删除]
全部评论 6
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; }6天前 来自 江苏
1
有帮助，赞一个