2023 China Collegiate Programming Contest (CCPC) Guilin (VP桂林 & 补题)
2023CCPC桂林的概况是：3题快铜、5题银、7题金9题捧杯、11题冠亚军已更新GMKIH，待更新BC签到题提供py，其余c++（很多卡时间有点死，py直接g）签到题未提供思路，其余提供解题思路。
2023 China Collegiate Programming Contest (CCPC) Guilin (VP桂林 & 补题)
文章目录
写在前面
2023CCPC桂林的概况是：
3题快铜、5题银、7题金
9题捧杯、11题冠亚军
已更新GMKIH，待更新BC
签到题提供py，其余c++（很多卡时间有点死，py直接g）
签到题未提供思路，其余提供解题思路
G. Hard Brackets Problem (签到题)
按题意模拟，或后缀和判无解。
ac代码参考：
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
out = sys.stdout.write
def S():
return input()
def I():
return int(input())
def print1(x):
return out(str(x) + "\n")
# ----------------------------- # ----------------------------- #
def solve():
s = list(S())
st, n = 0, len(s)
i = 0
while i < n and s[i] == ')': i += 1
ans = s[:i]
end,st = 0,0
while i < n:
if s[i] == '(':
st += 1
end += 1
ans.append('(')
else:
if end:
end -= 1
st -= 1
ans.append(')')
else: ns.append(')')
i += 1
print1(''.join(ans) if st == 0 else "impossible")
for _ in range(I()):
solve()
M. Flipping Cards (第二个签到题)
ac代码参考
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,tot;
int a[N],b[N];
int c[2*N];
int dp[N][2];
bool check(int mid)
{
int cnt=0;
for(int i=1;i<=n;++i){
if(a[i]>=mid)
cnt++;
}
dp[0][0]=dp[0][1]=cnt;
int maxx=cnt;
for(int i=1;i<=n;++i){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]); // 不选 i
// 选 i
if(b[i]>=mid&&a[i]<mid)
dp[i][1]=max(dp[0][0]+1,dp[i-1][1]+1);
else if(b[i]>=mid&&a[i]>=mid)
dp[i][1]=max(dp[0][0],dp[i-1][1]);
else if(b[i]<mid&&a[i]<mid)
dp[i][1]=max(dp[0][0],dp[i-1][1]);
else if(b[i]<mid&&a[i]>=mid)
dp[i][1]=max(dp[0][0]-1,dp[i-1][1]-1);
maxx=max({maxx,dp[i][0],dp[i][1]});
}
return maxx>=(n+1)/2;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i];
c[++tot]=a[i];
c[++tot]=b[i];
}
sort(c+1,c+1+tot);
tot=unique(c+1,c+1+tot)-c-1;
int l=1,r=tot;
int ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(c[mid])){
ans=c[mid];
l=mid+1;
}
else
r=mid-1;
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
while(T--)
solve();
return 0;
}
K. Randias Permutation Task (半个铜牌题)
注意到答案不超过 min { 2 m , n ! } ≤ 362880 \min\{2^m, n!\} ≤ 362880 min{2m,n!}≤362880 (m个选或不选，)，所以任何复杂度是 O ( a n s ) O(ans) O(ans) 级 别的爆搜都是正确的。具体来说，令 f i f_i fi 表示前 i i i 个排列能复合出的排列的集合，每次枚举下一 个排列选不选即可。
时间复杂度 Θ ( n m ⋅ min ( 2 m , n ! ) ⋅ log min ( 2 m , n ! ) ) Θ(nm · \min(2^m, n!) · \log \min(2^m, n!)) Θ(nm⋅min(2m,n!)⋅logmin(2m,n!))。
ac代码参考
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 185;
int n, m, ans;
map<vector<int>, int>mp;
void solve(){
cin >> n >> m;
vector<vector<int>>a(m+1, vector<int>(n+1));
for (int i = 1; i <= m; i++) { // m 个排列
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
vector<int> res(n + 1);
for (int i = 1; i <= m; i++) {
map<vector<int>, int> tmp;
tmp = mp;
tmp[a[i]] = 1;
for (auto w : mp) {
vector<int>p = w.first;
for (int j = 1; j <= n; j++) {
res[j] = p[a[i][j]];
}
tmp[res]=1;
}
mp = tmp;
}
cout << mp.size() << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
I. Barkley II (铜牌题)
- 给一个序列，选择一个区间使得区间颜色数 − 区间 m e x mex mex 最大，那么考虑是不是需要留一个比较小的不选，来使得答案最大？
- 一个显然的暴力做法是枚举每一个算法种类，以此当间隔，再 O ( n ) O(n) O(n) 的计算该情况的答案，取 max \max max。总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 考虑怎么优化使其时间复杂度可以接受，使用树状数组扫描线统计颜色数即可（静态区间数颜色问题）。
- 树状数组的知识点可以看这题学会：SDOI2009 HH的项链，总的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
ac代码参考
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 5e5+5;
int a[N], su[N], vis[N];
int n, m;
vector<vector<int>> dic(N);
struct Que{
int l, r, mex;
Que(int x, int y, int z) : l(x), r(y), mex(z){}
};
vector<Que> ask;
void add(int pos, int x){
while (pos <= n){
su[pos] += x;
pos += (-pos) & pos;
}
}
int query(int pos){
int res = 0;
while (pos){
res += su[pos];
pos -= (-pos) & pos;
}
return res;
}
void solve(){
ask.clear();
cin >> n >> m;
a[0] = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] <= n) dic[a[i]].push_back(i);
}
for (int i = 1; i <= n+1; i++){
if (dic[i].size()){
int pre = 1;
for (auto r : dic[i]){
if (r - 1 >= pre)
ask.push_back(Que(pre, r - 1, i));
pre = r + 1;
}
if (pre <= n)
ask.push_back(Que(pre, n, i));
} else {
ask.push_back(Que(1, n, i));
break;
}
}
auto cmp = [&](Que x, Que y){
return x.r < y.r;
};
sort(ask.begin(), ask.end(), cmp);
for (int i = 1; i <= n; i++) vis[a[i]] = 0;
for(int i = 1; i <= n; i++)
dic[a[i]].clear();
for (int i = 0; i <= n; i++) su[i] = 0;
int nxt = 1, ans = -1e9;
for(auto que : ask){
for(int j = nxt; j <= que.r; j++){
if (vis[a[j]]) add(vis[a[j]], -1);
add(j, 1);
vis[a[j]] = j;
}
nxt = que.r + 1;
ans = max(ans, query(que.r) - query(que.l - 1) - que.mex);
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
B. The Game (半个银牌题)
C. Master of Both IV (银牌题)
H. Sweet Sugar (金牌题)
题面可被翻译为：给定一棵无根树，每个点的点权为 0 0 0、 1 1 1 或 2 2 2，从树上找到尽量多的不重叠的连通块，使得每个连通块的点权和都为 k k k。
任选点权和为 k k k 的连通块，其中 k > 2 k > 2 k>2，那么该连通块至少包含两个点权非零的叶子，否则可以在不改变 k k k 的前提下迭代删去点权为 0 0 0 的叶子。
- 如果至少有一个叶子的点权为 2 2 2，那么删去该叶子即可得到点权和 为 k − 2 k − 2 k−2 的连通块。
- 否则所有叶子的点权都为 1 1 1，那么同时删去两个叶子即可得到点权 和为 k − 2 k − 2 k−2 的连通块。
因此可以通过树形 DP 求出总和为奇数 / / /偶数的点权和最大的连通块来 O ( 1 ) O(1) O(1) 判断是否存在点权和为 k k k 的连通块。
任选一点为根，自底向上贪心。 假设当前考虑完了 x x x 的所有儿子，如果 x x x 子树目前与 x x x 相连的部分存在 一个点权和为 k k k 的连通块，那么切掉 x x x 与 x x x 父亲之间的边不会使得答案变差，对答案的贡献为 1 1 1。 时间复杂度 O ( n ) O(n) O(n)。
ac代码参考
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, N = 1e6+5;
int head[N], ver[N+N], nxt[N+N];
int c[N];
int n, k, tot;
array<int, 3> dfs(int x, int p) {
array<int, 3> res = {c[x], 0, INF};
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (y == p) continue;
auto [su, ans, caneat] = dfs(y, x);
res[0] += su; // 子树总点权
res[1] += ans; // 树形DP整合子树答案
res[2] = min(res[2], caneat);
}
if (res[0] & 1)
res[2] = min(res[2], res[0]);
if (res[0] >= k)
// 判断是否存在点权和为 k 的连通块，res[0] - res[2] 用于改变子树点权的奇偶
if ((res[0] & 1) == (k & 1) || res[0] - res[2] >= k) {
return {0, res[1] + 1, INF};
}
return res;
}
void solve() {
tot = 0;
auto add = [](int x,int y){
ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
};
cin >> n >> k;
for(int i = 0; i <= n; i++) head[i] = 0;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
add(x,y);
add(y,x);
}
auto [_, ans, __] = dfs(1, 1); // x, parent
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
26
0- 0
已为社区贡献5条内容
所有评论(0)