2025ccpc南昌补题笔记(前六题)

目录

写在前面：

L.羽球比赛

题面：

​编辑思路：

代码：

G.玻璃碎晶

题面：

思路：

代码:

A.扭蛋

题面：

思路：

代码：

K.不许偷吃

题面:

思路:

代码:

H.珍珠链

题面：

思路：

代码：

C.虫洞

题面：

思路：

代码：

写在前面：

作者根据自己的能力补题，写了自己的一些思路在此记录方便以后查阅。

L.羽球比赛

题面：

思路：

签到题，简单if语句判断一下即可。

代码：

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; void solve() { ll a,b; cin>>a>>b; if(a>=21&&a-b>=2){ cout<<"Alice"<<endl; return ; } if(a>=30){ cout<<"Alice"<<endl; return ; } swap(a,b); if(a>=21&&a-b>=2){ cout<<"Bob"<<endl; return ; } if(a>=30){ cout<<"Bob"<<endl; return ; } cout<<"Underway"<<endl; } int main(){ ll _=1; // cin>>_; while(_--){ solve(); } return 0; }

G.玻璃碎晶

题面：

样例输出：

-1 1 1 1 2 3

思路：

这也是签到题，用贪心

特判n=1,2,4的时候不存在所有碎晶都是美丽的，随后分n%3等于0，1，2的情况。

当n%3==0只需要每一块碎晶都为3即可

n%3==1的时候，例如13=3+3+3+3+1,可以将3+3+1化为7

n%3==2的时候，将剩下的2加到一个3得到一块大小为5的碎晶也是美丽的。

代码:

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; void solve() { ll n; cin>>n; if(n<3||n==4){ cout<<-1<<endl; return ; } if(n%3==0){ ll ans=n/3; cout<<ans<<endl; } else if(n%3==1){ ll ans=n/3-1; cout<<ans<<endl; } else if(n%3==2){ ll ans=n/3; cout<<ans<<endl; } } int main(){ ll _=1; cin>>_; while(_--){ solve(); } return 0; }

A.扭蛋

题面：

思路：

贪心题，理解题意后模拟

至少需要多少扭蛋币才能保证集齐n种扭蛋，就是在最糟糕的情况下做出的最优解。

最糟糕的情况就是每次都只能按扭蛋数量从大到小的取出一种扭蛋直到这种扭蛋被取完，最优解就是攒到的指定币不要用，在用完能够直接补齐剩下的种类数的时候再用。

将扭蛋种类按扭蛋数量排序过后从大到小开始遍历，每次判断这种扭蛋直接取完是否满足能集齐n种扭蛋，不能就直接遍历下一个，能的话再判断这种扭蛋最少取多少个就够了。

代码：

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; void solve() { ll n,k; cin>>n>>k; ll sum=0; vector<ll>a(n+1); for(ll i=0;i<n;i++) { cin>>a[i]; } sort(a.begin(),a.end(),greater<ll>()); ll bi=0; ll ans=0; for(ll i=0;i<n;i++) { //temp_sum用来存此次的sum,temp_bi用来存此次的bi，因为在if语句中需要用到之前的bi和sum ll temp_sum=sum+a[i]-1;//能用来兑换的扭蛋 ll temp_bi=bi+temp_sum/k; temp_sum=temp_sum%k; if(temp_bi>=(n-i-1))//指定币能补齐剩下没有的种类 { ll res=n-i-1-bi;//差多少个指定币 res=res*k-sum;//需要多少个扭蛋 if(res<=0){ res=1;//不差扭蛋，只需要当前保留一个就行 } else{ res+=1;//还要另外留一个当前扭蛋 } ans+=res; cout<<ans<<endl; return ; } ans+=a[i]; sum=temp_sum; bi=temp_bi; } } int main(){ ll _=1; cin>>_; while(_--){ solve(); } return 0; }

K.不许偷吃

题面:

思路:

贪心题

每一次上菜点心数分四种情况,分别是对4取模得0,1,2,3

其中对%4=0的情况对结果无影响，可以把顺序调在最前面

%4=2的情况在只剩下这种情况下也可以一直上，不会得到剩一个点心，因为结果是4的倍数，所以在只剩下这种情况下的点心一定是2或4的倍数。在只剩下3或1的时候，2也可以和他们组合不得到剩一个点心的情况

所以应该先将%4=1和%4=3的情况应该优先于%4==2处理

一个3可以抵消一个1，要么是3311要么是3131，333的时候就会只剩一个点心，所以我先将3和1轮着抵消，剩下的和2抵消，再剩下的2一直上就行

代码:

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; void solve() { ll n; cin>>n; vector<ll>a(4); vector<vector<ll>>b(4); ll temp=0; for(ll i=0;i<n;i++) { cin>>temp; if(temp%4==0) { a[0]++; b[0].push_back(i+1); } else if(temp%4==1) { a[1]++; b[1].push_back(i+1); } else if(temp%4==2) { a[2]++; b[2].push_back(i+1); } else if(temp%4==3) { a[3]++; b[3].push_back(i+1); } } vector<ll>ans; ll b2_i=0; ll b1_i=0; ll b3_i=0; for(ll i=0;i<b[0].size();i++) { ans.push_back(b[0][i]); } if(a[1]>a[3]) { for(ll i=0;i<b[3].size();i++) { ans.push_back(b[3][i]); ans.push_back(b[1][i]); b1_i++; b3_i++; } a[1]-=a[3]; while(a[1]>0) { if(a[2]<=0){ cout<<-1<<endl; return; } ans.push_back(b[2][b2_i]); b2_i++; a[2]--; ans.push_back(b[1][b1_i]); b1_i++; a[1]--; if(a[1]==0) { cout<<-1<<endl; return; } ans.push_back(b[1][b1_i]); b1_i++; a[1]--; } if(a[2]%2==1){ cout<<-1<<endl; return; } else{ while(a[2]>0) { a[2]--; ans.push_back(b[2][b2_i]); b2_i++; } } } else{ for(ll i=0;i<b[1].size();i++) { ans.push_back(b[3][i]); ans.push_back(b[1][i]); b1_i++; b3_i++; } a[3]-=a[1]; while(a[3]>0) { if(a[2]<=0){ cout<<-1<<endl; return; } ans.push_back(b[3][b3_i]); b3_i++; a[3]--; if(a[3]==0) { cout<<-1<<endl; return; } ans.push_back(b[3][b3_i]); b3_i++; a[3]--; ans.push_back(b[2][b2_i]); b2_i++; a[2]--; } if(a[2]%2==1){ cout<<-1<<endl; return; } else{ while(a[2]>0) { a[2]--; ans.push_back(b[2][b2_i]); b2_i++; } } } for(ll i=0;i<ans.size();i++) { cout<<ans[i]<<" "; } cout<<endl; } int main(){ ll _=1; cin>>_; while(_--){ solve(); } return 0; }

H.珍珠链

题面：

样例输出

6 13 -1

思路：

珍珠串a的总光彩值固定，珍珠串b一共只能进行n次插入操作，而插入操作越靠后光彩值越大，所以要操作次数最少，插入操作越靠后越好，这个时候就有了第一个约束条件，当将要插入第j个珍珠的时候，优先将其前面未提升到指定光彩值的珍珠进行第二种操作来提升。

但当当前i超过一定值的时候，哪怕后面一直只做第一种操作，a串的值也会大于b串，这个时候就失败了，所以第二个约束条件就是不能超过这个值。这个值我用后缀来计算的。

代码：

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; void solve() { ll n; cin>>n; vector<ll>a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } ll nowv=1; vector<ll>b(n); vector<ll>maxv(n);//遍历到此珠子时i的上限 maxv[n-1]=a[n-1]; for(ll i=n-2;i>=0;i--) { ll temp=a[i]; maxv[i]=min(maxv[i+1]-1,temp); } ll b_i=0; for(ll i=0;i<n;i++) { // cout<<i+1<<" "<<nowv<<endl; if(nowv>maxv[i]){ cout<<-1<<endl; return ; } if(b_i>=i) { b[i]=nowv; nowv++; continue; } bool flag=0; while(nowv+a[b_i]-b[b_i]<=maxv[i])//当前光彩值使得b串提升满当前会使得光彩超过下一个该添加的珍珠 { // cout<<i<<" "<<nowv<<" "<<b_i<<" "<<b[b_i]<<endl; nowv+=(a[b_i]-b[b_i]); b[b_i]=a[b_i]; b_i++; if(b_i>=i){ // cout<<"a:"<<i<<" "<<nowv<<endl; b[i]=nowv; nowv++; flag =1; break; } } if(flag){ continue; } if(nowv>maxv[i]){ cout<<-1<<endl; return ; } if(nowv+a[b_i]-b[b_i]>maxv[i]){ b[b_i]+=(maxv[i]-nowv); b[i]=maxv[i]; nowv=b[i]+1; } } nowv--;//因为当前nowv为下一次插入的珍珠值，故当前只执行了操作nowv-1次 //将之前没有达到目标值的珍珠提升到目标值 for(ll i=0;i<n;i++){ if(b[i]<a[i]){ nowv+=(a[i]-b[i]); } } cout<<nowv<<endl; } int main(){ ll _=1; cin>>_; while(_--){ solve(); } return 0; }

C.虫洞

题面：

思路：

1、简化条件

要找到连续的子序列使得这些虫洞被分为不超过k组，每组里面的虫洞都互不相交，就是对于子序列的每一个点，每一组对于这些点最多都只能有一个虫洞包含

比如一共有10个点，有k个虫洞包含了第一个点，将这k个虫洞分为k组，接下来第二个点也被k个虫洞包含，所以他们一定能找到一个组是只有他包含第二个点的，同时这个虫洞因为他并没有包含第一个点，所以这k组中的每一组的前两个点都只有一个虫洞包含，以此类推最终能得到这k组每一组对于这10个点都最多只有一个虫洞包含，即得到结论只要每个点最多被k个虫洞包含即可成立。

2、找出最长子序列

用滑动窗口的方法，每次窗口向右扩展，满足条件就和ans比较作记录，直到有点被超过k个虫洞包含条件不满足，这个时候左边界向右压缩直到下一次满足条件。这样的时间花费是2n，因为数据给的n为2e5，时间复杂度不能超过O(nlogn),判断满足条件的时间只剩下logn，于是用线段树的方法去优化判断的过程。

线段树判断的时候，如果上次满足了条件， 这次不满足条件的点一定出现在新添加的虫洞，只需要查新添加虫洞包含的点就行。

代码：

#include<bits/stdc++.h> using namespace std; using ll=long long; ll Mod=998244353; struct node { ll l,r,maxv,lz; }; void build(ll i,ll l,ll r,vector<pair<ll,ll>>&a,vector<node>&tree) { tree[i].lz=0;//初始化的时候肯定都是0 tree[i].l=l; tree[i].r=r; tree[i].maxv=0; if(l>=r) { return ; } ll mid=(l+r)/2; build(i*2,l,mid,a,tree); build(i*2+1,mid+1,r,a,tree); return ; } inline void push_down(ll i,vector<node>&tree) { if(tree[i].lz!=0) { tree[i*2].lz+=tree[i].lz; tree[i*2+1].lz+=tree[i].lz; tree[i*2].maxv+=tree[i].lz; tree[i*2+1].maxv+=tree[i].lz; tree[i].lz=0; } return ; } inline void add(ll i,ll l,ll r,ll k,vector<node>&tree) { if(tree[i].l>=l&&tree[i].r<=r) { tree[i].maxv+=k; tree[i].lz+=k; return ; } push_down(i,tree); if(tree[i*2].r>=l) add(i*2,l,r,k,tree); if(tree[i*2+1].l<=r) add(i*2+1,l,r,k,tree); tree[i].maxv=max(tree[i*2].maxv,tree[i*2+1].maxv); return ; } inline ll searchs(ll i,ll l, ll r,vector<node>&tree) { if(tree[i].l>=l&&tree[i].r<=r){ return tree[i].maxv; } push_down(i,tree); ll numl=0; ll numr=0; if(tree[i*2].r>=l) numl=max(numl,searchs(i*2,l,r,tree)); if(tree[i*2+1].l<=r) numr=max(numr,searchs(i*2+1,l,r,tree)); ll num=max(numl,numr); return num; } void solve() { ll ans=0; ll n,k; cin>>n>>k; vector<pair<ll,ll>>a(n+1); for(ll i=1;i<=n;i++){ cin>>a[i].first>>a[i].second; } vector<node>tree(4*(n+1)); build(1,1,n,a,tree); ll l=1,r=0; while(r<n){ r++; add(1,a[r].first,a[r].second,1,tree); while(l<r&&searchs(1,a[r].first,a[r].second,tree)>k){//不满足条件，滑动窗口向右压缩 add(1,a[l].first,a[l].second,-1,tree); l++; } ans=max(ans,r-l+1); } cout<<ans<<endl; } int main(){ ll _=1; cin>>_; while(_--){ solve(); } return 0; }