2022 China Collegiate Programming Contest Mianyang (CGMHA)
2022 CCPC Mianyang qwq
https://zhuanlan.zhihu.com/p/658698687
C Catch You Catch Me
算出根节点的所有子节点的高度,求和即可。
G Let Them Eat Cake
使用双向链表,根据题意模拟即可。可知每次大约删一半。
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++)
{
pre[i] = i - 1;
nxt[i] = i + 1;
cin >> a[i];
}
sz = n;
int idx = 1;int tail = n;
int res = 0;
while(sz > 1)
{
vector<int> tmp;
for(int i = idx; ; i = nxt[i])
{
if(i == idx)
{
if(a[nxt[i]] > a[i]) tmp.push_back(i);
}
else if(i == tail)
{
if(a[pre[i]] > a[i]) tmp.push_back(i);
}
else{
if(a[pre[i]] > a[i] || a[nxt[i]] > a[i]) tmp.push_back(i);
}
if(i == tail) break;
}
res ++;
sz -= tmp.size();
for(int x :tmp)
{
if(x == idx) idx = nxt[x];
else if(x == tail) tail = pre[x];
else{
pre[nxt[x]] = pre[x];
nxt[pre[x]] = nxt[x];
}
}
}
cout << res << endl;
}
M Rock-Paper-Scissors Pyramid
手玩一下,你可以发现在图中 /
结构类似于一种保护, ‘\‘ 结构类似于破坏或者进攻。
/
结构的产生是,这个元素比上一个元素来的小。’\‘ 的产生是因为这个元素比上一个元素来的大,并且如果遇到的 /
结构,并且比/
结构的颜色大,便会一直进攻。
所以我们发现,我们只需要维护一个单调递减的栈。栈上的元素比栈下的元素来的小,是用来保护栈下的元素的。
最后的答案便是栈底的元素。
大概就是这么个思想。感觉能理解,但是怪怪的。
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
#include<stack>
#define int long long
using namespace std;
string s;
bool cmp(char x,char y)
{
if(x == 'S' && y == 'P') return true;
if(x == 'P' && y == 'R') return true;
if(x == 'R' && y == 'S') return true;
return false;
}
void solve()
{
cin >> s;
stack<char> stk;
stk.push(s[0]);
for(int i = 0;i < s.size();i ++)
{
while(cmp(s[i],stk.top())){
stk.pop();
if(stk.size() == 0) break;
}
stk.push(s[i]);
}
while(stk.size() > 1) stk.pop();
cout << stk.top() << endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// freopen("in.txt","r",stdin);
int _; cin >> _; while(_ --)
solve();
}
H Life is Hard and Undecidable, but…
非常抽象的一题。你只需要构造一个生命周期大于 $300$ 的图像。然后要多少就给多少就行。非常抽象。
所以一条斜线即可。
void solve()
{
int n; cin >> n;
n *= 2;
cout << n << endl;
for(int i = 1;i <= n;i ++)
cout << i << ' ' << i << endl;
}
A - Ban or Pick, What’s the Trick
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
#include<stack>
#include<vector>
#include<bitset>
#define int long long
using namespace std;
int n;
int k;
const int IINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 100;
int a[N],b[N];
int dp[N * 2][12][12];
int dfs(int round,int cnta,int cntb) // 总轮数 a已经选的英雄数 b已经选的英雄数
{
if(round == 2 * n) return 0ll;
if(dp[round][cnta][cntb] != IINF + 1) return dp[round][cnta][cntb];
int rounda = (round + 1) >> 1;
int roundb = round >> 1;
int banb = rounda - cnta; // b被ban了多少场
int bana = roundb - cntb;
int nowb = banb + cntb;
int nowa = bana + cnta;
if((round & 1) == 0)
{
int tmp = - IINF;
if(cnta < k && nowa < n) tmp = max(tmp,dfs(round + 1,cnta + 1,cntb) + a[nowa + 1]);
tmp = max(tmp, dfs(round + 1, cnta ,cntb));
return dp[round][cnta][cntb] = tmp;
}
else
{
int tmp = IINF;
if(cntb < k && nowb < n) tmp = min(tmp, dfs(round + 1,cnta, cntb + 1) - b[nowb + 1]);
tmp = min(tmp, dfs(round + 1, cnta, cntb));
return dp[round][cnta][cntb] = tmp;
}
}
void solve()
{
cin >> n >> k;
for(int i = 0;i <= n * 2 + 1;i ++)
for(int j = 0;j <= k + 1;j ++)
for(int t = 0;t <= k + 1;t ++) dp[i][j][t] = IINF + 1;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= n;i ++) cin >> b[i];
sort(a + 1,a + 1 + n, [](int x,int y){return x > y;});
sort(b + 1,b + 1 + n, [](int x,int y){return x > y;});
cout << dfs(0,0,0) << endl;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//int _; cin >> _; while(_ --)
solve();
}