2025山東CCPC補題

感覺這場比賽的題目挺不錯的；沒有說那些為了算法而算法或者為了思維而思維的題，都是混合在一起相互搭配的題目；

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;
}

---