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

目录写在前面L.羽球比赛题面​编辑思路代码G.玻璃碎晶题面思路代码:A.扭蛋题面思路代码K.不许偷吃题面:思路:代码:H.珍珠链题面思路代码C.虫洞题面思路代码写在前面作者根据自己的能力补题写了自己的一些思路在此记录方便以后查阅。L.羽球比赛题面思路签到题简单if语句判断一下即可。代码#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; void solve() { ll a,b; cinab; if(a21a-b2){ coutAliceendl; return ; } if(a30){ coutAliceendl; return ; } swap(a,b); if(a21a-b2){ coutBobendl; return ; } if(a30){ coutBobendl; return ; } coutUnderwayendl; } int main(){ ll _1; // cin_; while(_--){ solve(); } return 0; }G.玻璃碎晶题面样例输出-1 1 1 1 2 3思路这也是签到题用贪心特判n1,2,4的时候不存在所有碎晶都是美丽的随后分n%3等于012的情况。当n%30只需要每一块碎晶都为3即可n%31的时候例如1333331,可以将331化为7n%32的时候将剩下的2加到一个3得到一块大小为5的碎晶也是美丽的。代码:#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; void solve() { ll n; cinn; if(n3||n4){ cout-1endl; return ; } if(n%30){ ll ansn/3; coutansendl; } else if(n%31){ ll ansn/3-1; coutansendl; } else if(n%32){ ll ansn/3; coutansendl; } } int main(){ ll _1; cin_; while(_--){ solve(); } return 0; }A.扭蛋题面思路贪心题理解题意后模拟至少需要多少扭蛋币才能保证集齐n种扭蛋就是在最糟糕的情况下做出的最优解。最糟糕的情况就是每次都只能按扭蛋数量从大到小的取出一种扭蛋直到这种扭蛋被取完最优解就是攒到的指定币不要用在用完能够直接补齐剩下的种类数的时候再用。将扭蛋种类按扭蛋数量排序过后从大到小开始遍历每次判断这种扭蛋直接取完是否满足能集齐n种扭蛋不能就直接遍历下一个能的话再判断这种扭蛋最少取多少个就够了。代码#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; void solve() { ll n,k; cinnk; ll sum0; vectorlla(n1); for(ll i0;in;i) { cina[i]; } sort(a.begin(),a.end(),greaterll()); ll bi0; ll ans0; for(ll i0;in;i) { //temp_sum用来存此次的sum,temp_bi用来存此次的bi因为在if语句中需要用到之前的bi和sum ll temp_sumsuma[i]-1;//能用来兑换的扭蛋 ll temp_bibitemp_sum/k; temp_sumtemp_sum%k; if(temp_bi(n-i-1))//指定币能补齐剩下没有的种类 { ll resn-i-1-bi;//差多少个指定币 resres*k-sum;//需要多少个扭蛋 if(res0){ res1;//不差扭蛋只需要当前保留一个就行 } else{ res1;//还要另外留一个当前扭蛋 } ansres; coutansendl; return ; } ansa[i]; sumtemp_sum; bitemp_bi; } } int main(){ ll _1; cin_; while(_--){ solve(); } return 0; }K.不许偷吃题面:思路:贪心题每一次上菜点心数分四种情况,分别是对4取模得0,1,2,3其中对%40的情况对结果无影响可以把顺序调在最前面%42的情况在只剩下这种情况下也可以一直上不会得到剩一个点心因为结果是4的倍数所以在只剩下这种情况下的点心一定是2或4的倍数。在只剩下3或1的时候2也可以和他们组合不得到剩一个点心的情况所以应该先将%41和%43的情况应该优先于%42处理一个3可以抵消一个1要么是3311要么是3131333的时候就会只剩一个点心所以我先将3和1轮着抵消剩下的和2抵消再剩下的2一直上就行代码:#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; void solve() { ll n; cinn; vectorlla(4); vectorvectorllb(4); ll temp0; for(ll i0;in;i) { cintemp; if(temp%40) { a[0]; b[0].push_back(i1); } else if(temp%41) { a[1]; b[1].push_back(i1); } else if(temp%42) { a[2]; b[2].push_back(i1); } else if(temp%43) { a[3]; b[3].push_back(i1); } } vectorllans; ll b2_i0; ll b1_i0; ll b3_i0; for(ll i0;ib[0].size();i) { ans.push_back(b[0][i]); } if(a[1]a[3]) { for(ll i0;ib[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-1endl; 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-1endl; return; } ans.push_back(b[1][b1_i]); b1_i; a[1]--; } if(a[2]%21){ cout-1endl; return; } else{ while(a[2]0) { a[2]--; ans.push_back(b[2][b2_i]); b2_i; } } } else{ for(ll i0;ib[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-1endl; return; } ans.push_back(b[3][b3_i]); b3_i; a[3]--; if(a[3]0) { cout-1endl; 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]%21){ cout-1endl; return; } else{ while(a[2]0) { a[2]--; ans.push_back(b[2][b2_i]); b2_i; } } } for(ll i0;ians.size();i) { coutans[i] ; } coutendl; } int main(){ ll _1; cin_; while(_--){ solve(); } return 0; }H.珍珠链题面样例输出6 13 -1思路珍珠串a的总光彩值固定珍珠串b一共只能进行n次插入操作而插入操作越靠后光彩值越大所以要操作次数最少插入操作越靠后越好这个时候就有了第一个约束条件当将要插入第j个珍珠的时候优先将其前面未提升到指定光彩值的珍珠进行第二种操作来提升。但当当前i超过一定值的时候哪怕后面一直只做第一种操作a串的值也会大于b串这个时候就失败了所以第二个约束条件就是不能超过这个值。这个值我用后缀来计算的。代码#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; void solve() { ll n; cinn; vectorlla(n); for(ll i0;in;i){ cina[i]; } ll nowv1; vectorllb(n); vectorllmaxv(n);//遍历到此珠子时i的上限 maxv[n-1]a[n-1]; for(ll in-2;i0;i--) { ll tempa[i]; maxv[i]min(maxv[i1]-1,temp); } ll b_i0; for(ll i0;in;i) { // couti1 nowvendl; if(nowvmaxv[i]){ cout-1endl; return ; } if(b_ii) { b[i]nowv; nowv; continue; } bool flag0; while(nowva[b_i]-b[b_i]maxv[i])//当前光彩值使得b串提升满当前会使得光彩超过下一个该添加的珍珠 { // couti nowv b_i b[b_i]endl; nowv(a[b_i]-b[b_i]); b[b_i]a[b_i]; b_i; if(b_ii){ // couta:i nowvendl; b[i]nowv; nowv; flag 1; break; } } if(flag){ continue; } if(nowvmaxv[i]){ cout-1endl; return ; } if(nowva[b_i]-b[b_i]maxv[i]){ b[b_i](maxv[i]-nowv); b[i]maxv[i]; nowvb[i]1; } } nowv--;//因为当前nowv为下一次插入的珍珠值故当前只执行了操作nowv-1次 //将之前没有达到目标值的珍珠提升到目标值 for(ll i0;in;i){ if(b[i]a[i]){ nowv(a[i]-b[i]); } } coutnowvendl; } 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于是用线段树的方法去优化判断的过程。线段树判断的时候如果上次满足了条件 这次不满足条件的点一定出现在新添加的虫洞只需要查新添加虫洞包含的点就行。代码#includebits/stdc.h using namespace std; using lllong long; ll Mod998244353; struct node { ll l,r,maxv,lz; }; void build(ll i,ll l,ll r,vectorpairll,lla,vectornodetree) { tree[i].lz0;//初始化的时候肯定都是0 tree[i].ll; tree[i].rr; tree[i].maxv0; if(lr) { return ; } ll mid(lr)/2; build(i*2,l,mid,a,tree); build(i*21,mid1,r,a,tree); return ; } inline void push_down(ll i,vectornodetree) { if(tree[i].lz!0) { tree[i*2].lztree[i].lz; tree[i*21].lztree[i].lz; tree[i*2].maxvtree[i].lz; tree[i*21].maxvtree[i].lz; tree[i].lz0; } return ; } inline void add(ll i,ll l,ll r,ll k,vectornodetree) { if(tree[i].lltree[i].rr) { tree[i].maxvk; tree[i].lzk; return ; } push_down(i,tree); if(tree[i*2].rl) add(i*2,l,r,k,tree); if(tree[i*21].lr) add(i*21,l,r,k,tree); tree[i].maxvmax(tree[i*2].maxv,tree[i*21].maxv); return ; } inline ll searchs(ll i,ll l, ll r,vectornodetree) { if(tree[i].lltree[i].rr){ return tree[i].maxv; } push_down(i,tree); ll numl0; ll numr0; if(tree[i*2].rl) numlmax(numl,searchs(i*2,l,r,tree)); if(tree[i*21].lr) numrmax(numr,searchs(i*21,l,r,tree)); ll nummax(numl,numr); return num; } void solve() { ll ans0; ll n,k; cinnk; vectorpairll,lla(n1); for(ll i1;in;i){ cina[i].firsta[i].second; } vectornodetree(4*(n1)); build(1,1,n,a,tree); ll l1,r0; while(rn){ r; add(1,a[r].first,a[r].second,1,tree); while(lrsearchs(1,a[r].first,a[r].second,tree)k){//不满足条件滑动窗口向右压缩 add(1,a[l].first,a[l].second,-1,tree); l; } ansmax(ans,r-l1); } coutansendl; } int main(){ ll _1; cin_; while(_--){ solve(); } return 0; }