2025山东CCPC补题
2025山东CCPC补题
目录
- 2025山东CCPC补题
- K - UNO！ （双端队列的简单应用）
- M - 第九届河北省大学生程序设计竞赛 （二进制枚举模拟）
- J - Generate 01 String
感觉这场比赛的题目挺不错的；没有说那些为了算法而算法或者为了思维而思维的题，都是混合在一起相互搭配的题目；
K - UNO！ （双端队列的简单应用）
题目原文
Attachments - The 9th Hebei Collegiate Programming Contest - Codeforces
解题思路
一道简单的模拟题；赛时想着去用数组去模拟会超时；后面想着如果没有手牌就删掉，但是删除函数的时间复杂度是O(n)依然会超时；想到了用队列去做但是里面有反转的操作导致不好调换顺序；后面想到用双端队列但是之前没有用过，所以不太熟悉（其实定义都没定义出来）
思路不难分析；根据题意模拟即可；如果手牌降为0就直接将这个人弹出；写的时候注意细节（比如使用+2牌时也会让下个人停止行动一次）；题目数据保证最后一定会剩至少两个手牌不为空，所以直接模拟就可以；
用到的基本的操作函数在这篇博客中有介绍，比较基础；
代码实现
看着比较长，其实里面上下是一样的就是换了个方向；
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
int a[N];
void slove(){int n,m;cin>>n>>m;deque<pii> q;for(int i=1;i<=n;i++){int x;cin>>x;q.push_back({x,i}); // 将数据和下标一起存入}int ff=1; // 用来记录方向while(m--){char op;cin>>op;if(ff==1){ // 顺时针方向pii f=q.front(); // 从队头取元素q.pop_front();f.fi--;if(op=='S'){ // 停止牌if(f.fi!=0)q.push_back(f); q.push_back(q.front()); // 将下一个也存入队尾q.pop_front();}if(op=='R'){ // 反转牌ff=-1;if(f.fi!=0) // 改变了方向，下一次就该从队尾取了，所以这个再存回队头q.push_front(f);}if(op=='D'){ // +2牌if(f.fi!=0)q.push_back(f);pii f=q.front();q.pop_front();q.push_back({f.fi+2,f.se}); // +2后也会被停止，所以直接存到后面}if(op=='C'){if(f.fi!=0)q.push_back(f);}}else{ // 逆时针的方向，思路和上面一模一样，只是取得时候从队尾取数据了pii f=q.back();q.pop_back();f.fi--;if(op=='S'){if(f.fi!=0)q.push_front(f);q.push_front(q.back());q.pop_back();}if(op=='R'){ff=1;if(f.fi!=0)q.push_back(f);}if(op=='D'){if(f.fi!=0)q.push_front(f);pii f=q.back();q.pop_back();q.push_front({f.fi+2,f.se});}if(op=='C'){if(f.fi!=0)q.push_front(f);}}}while(q.size()){ // 将队列中剩余的手牌数量同步到数组中，便于输出pii f=q.front();q.pop_front();a[f.se]=f.fi;}for(int i=1;i<=n;i++) // 按序输出即可cout<<a[i]<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}
M - 第九届河北省大学生程序设计竞赛 （二进制枚举模拟）
题目原文
Attachments - The 9th Hebei Collegiate Programming Contest - Codeforces
解题思路
题目中的每道题都只有选择或不选择两种状态，里面的数据范围也只有18，所以不难想到利用二进制取模拟；题目又规定了所选取的题目数量只能是10~13道题目，范围很小，所以可以考虑直接去枚举判断；
输入原有的题目数量，和队伍的数量；然后在输入每个队伍能做出题目的情况；然后再告诉我们三种牌的最低名次和对应需要的过题数；
最后的判断能否满足条件就是看对应名次的选手过题数是否和要求的题数相等；
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
const int N=2e5+10;
string a[205]; // 存每个组的作答情况 void slove(){int n, m; cin >> n >> m;for(int i=1; i<=m; ++i)cin >> a[i]; int jp, yp, tp, ja, ya, ta;cin >> jp >> yp >> tp >> ja >> ya >> ta;// 遍历所有可能的子集（二进制枚举）for(int i=0; i<=(1<<n)-1; i++){ // i的每一位表示是否选择对应的位int c = 0, x = i;while(x){ // 计算当前的i选择题目的个数（即二进制中1的个数）if(x & 1) c++;x >>= 1;}if(c > 13 || c < ja || c < 10) // 剪枝：如果选中的位数不在10~13之间，或小于ja跳过continue;vector<int> an(m+1, 0); // an表示每个组在当前的选题情况下能做对的题数 an[0] = 0x3f3f3f; // 初始化为一个大数，用于占位（方便后面排序对齐） // 遍历每一位，每个题目是否被选中 for(int j=0; j<n; j++){if((i >> j) & 1){ // 如果第j位被选中for(int k=1; k<=m; k++){ // 遍历每一组的作答情况 if(a[k][j] == '1') // 如果这题该组会做就+1 an[k]++;}}}sort(an.begin(), an.end(), greater<int>()); // 将an数组从大到小排序if(an[jp] == ja && an[yp] == ya && an[tp] == ta){ // 判断三种获奖条件是否满足 cout << c << endl; // 输出选取的题数 for(int j=0; j<n; j++){if((i >> j) & 1)cout << j+1 << ' '; // 输出选取的题号 }return;}}cout << -1;
} signed main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);int _=1;//cin >> _;while(_--)slove();return 0;
}
J - Generate 01 String
题目原文
Attachments - The 9th Hebei Collegiate Programming Contest - Codeforces
解题思路
比赛时光想着每次去找最优的配队方式去输出，但是我们根本不需要考虑具体的对应关系，在满足01数量相等时结果是一定可行的；所以我们只需遍历统计01的出现情况去判断是否需要在这里操作增加新的还是是可以和前面配对的即可；
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=2e5+10;
int a[N];
void slove(){string s;cin>>s;if(count(s.begin(),s.end(),'0')!=count(s.begin(),s.end(),'1')){cout<<-1<<endl; // 01数量不同不可操作return ;}int c0=0,c1=0; // 统计可用01的个数int t=1; // 记录所处S的位置cout<<s.size()/2<<endl; // 每次多两个数，所以操作次数一定是长度除2for(int i=0;i<s.size();i++){if(s[i]=='0'){if(c0==0){ // 如果没有可用0，说明需要新增一个，输出cout<<t<<' '<<1<<endl;c1++; // 可用1增加}else{ // 有可用的0就和前面的1配对c0--; t++; // 位置移动，前面会多一个S}}else{ // 1的情况与0类似if(c1==0){cout<<t<<' '<<2<<endl;c0++;}else{c1--;t++;}}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}