A - Second Half Sum难度入门考察循环结构。题目大意给定一个长度为n nn的序列n nn为偶数输出这个序列的后半段。具体思路模拟即可。代码实现时间复杂度O ( 1 ) O(1)O(1)空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;voidsolve(){intn,sum0;cinn;for(inti1;in;i){inta;cina;if(in/2){suma;}}coutsum\n;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}B - Old Maid难度普及-考察基础数据结构。题目大意给定一个长度为n nn的序列每次你可以选择两相同数字并一起删除求剩下数字的总和。具体思路使用map或者unordered_map存储如果个数为奇数就加上。代码实现时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;unordered_mapint,intmp;voidsolve(){intn;cinn;for(inti1;in;i){intx;cinx;mp[x];}intsum0;for(auto[x,y]:mp){if(y1){sumx;}}coutsum\n;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}C - Change Schools难度普及-考察计数思想。题目大意已知有n nn个学生k kk个班级满足要求的班级满足人数加一后是人数最多的班级之一求有多少个满足要求的班级。具体思路首先统计每个班级有多少人。然后求人数的最大值如果班级人数等于最大值或者最大值减一即可。代码实现时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;constintN2e510;intn,k,cnt[N];voidsolve(){cinnk;for(inti1;in;i){intx;cinx;cnt[x];}intans0;intmax_val-INF;for(inti1;ik;i)max_valmax(max_val,cnt[i]);for(inti1;ik;i){if(cnt[i]max_val||cnt[i]max_val-1)ans;}coutans\n;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}D - Coefficient Stair难度普及考察搜索。题目大意按照字典树输出所有满足∑ i 1 n ( i × a i ) k \sum_{i1}^n (i \times a_i) k∑i1n​(i×ai​)k的序列。具体思路首先我们可以定义函数dfs(pos, rem)表示当前填到了位置p o s pospos还剩r e m remrem的总和暴力搜索后不难想到两个剪枝如果当前是最后一位那么只需要填r e m ÷ n rem \div nrem÷n即可如果有余数直接排除。如果当前r e m 0 rem0rem0那么直接填0 00即可。代码实现时间复杂度未知空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;constintN20;intn,k;inta[N];voiddfs(intpos,intrem){// 位置剩余if(posn1){for(inti1;in;i)couta[i] ;cout\n;return;}if(posn){// 要填最后一位使得i*a[i]remif(rem%pos!0)return;a[pos]rem/pos;dfs(pos1,0);return;}if(!rem){a[pos]0;dfs(pos1,rem);return;}for(inti0;i*posrem;i){a[pos]i;dfs(pos1,rem-i*pos);a[pos]0;}}voidsolve(){cinnk;dfs(1,k);}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}E - K-Divisible Subarrays难度普及/提高-考察取模。题目大意给定一个长度为n nn的序列请你把他划分为若干个子序列使得尽可能多的子序列的数字总和可以被k kk整除。具体思路首先不难想到我们可以将序列前缀和取模k kk不妨令这个序列为s i s_isi​。然后我们可以得到如果s l s r s_l s_rsl​sr​那么( l , r ) (l,r)(l,r)一定是合法的。于是我们可以维护一个set表示之前出现过的数字记得先插入0 00。如果你当前数字在set里面就可以形成一个合法序列清空set答案加一即可。然后插入当前数字。代码实现时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;constintN2e510;intn,k,a[N],s[N];voidsolve(){cinnk;for(inti1;in;i){cina[i];s[i](s[i-1]a[i])%k;}intans0;setintvis;vis.insert(0);for(inti1;in;i){if(vis.count(s[i])){ans;vis.clear();}vis.insert(s[i]);}coutans\n;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}F - A/AB Insertion难度提高考察颜子惟线段树。题目大意给定你一个由A和B组成的字符串请你满足以下两种操作修改操作把指定位置的字符改掉。查询操作查询[ l , r ] [l,r][l,r]能否在以下条件下形成一开始是一个空串。可以在任意位置插入A或者AB。具体思路首先应该不难想到可以用线段树做。聚焦操作2。首先可以观察到A的个数应不小于B的个数于是可以用经典的加权前缀和A为1 11B为− 1 -1−1区间和不小于0 00即可。但是我们可以举出反例BBAA发现前缀串B和BB均无法完成也就是任意一个B都要有前面的一个A对应。所以我们可以观察到字符串的任意前缀的和都应不小于0 00。然后考虑数据结构实现。我们得出 “字符串的任意前缀的和都应不小于0 00” 那么我们可以记录区间内的最小前缀和这个值不小于0 00即可。于是我们可以使用线段树的子节点合并来实现。每个节点存储两个值sum区间和mnv区间最小前缀和。考虑节点合并对于两个节点l和r如何合并对于sum直接相加即可。对于mnv可以是l部分的最小前缀和也可以是r部分的最小前缀和加上l部分的和。于是就实现完成了其余见代码。代码实现时间复杂度O ( q log ⁡ n ) O(q \log n)O(qlogn)空间复杂度O ( n ) O(n)O(n)。#includebits/stdc.h#definelllonglong#defineintlonglong#definei128__int128#defineINF1e18usingnamespacestd;// 查询操作判断任意前缀A的数量是否不小于B的数量// 加权前缀和A为1B为-1那么任意前缀和0// 也就是可以对前缀和取最小值这个最小值0// 线段树可以快速的做单点修改和区间求和// 维护前缀和最小值自定义节点合并即可// 对于一个线段树节点[l,mid]和[mid,r]如何合并// 区间前缀和相加即可// 区间前缀最小值就是右边的前缀最小值加上左边的和constintN5e510;intn;string s;structnode{intsum;intmnv;}tr[N2];nodemerge(node l,node r){node res;res.suml.sumr.sum;res.mnvmin(l.mnv,l.sumr.mnv);returnres;}voidpush_up(intx){tr[x]merge(tr[x1],tr[x1|1]);}voidbuild(intx,intl,intr){if(lr){intval(s[l]A?1:-1);tr[x]{val,val};return;}intmid(lr)1;build(x1,l,mid);build(x1|1,mid1,r);push_up(x);}voidupdate(intx,intl,intr,intpos,charch){if(lr){intval(chA?1:-1);tr[x]{val,val};return;}intmid(lr)1;if(posmid)update(x1,l,mid,pos,ch);elseupdate(x1|1,mid1,r,pos,ch);push_up(x);}nodequery(intx,intl,intr,intql,intqr){if(qllrqr)returntr[x];intmid(lr)1;if(qrmid)returnquery(x1,l,mid,ql,qr);if(midql)returnquery(x1|1,mid1,r,ql,qr);returnmerge(query(x1,l,mid,ql,qr),query(x1|1,mid1,r,ql,qr));}voidsolve(){cinns;s s;build(1,1,n);intq;cinq;while(q--){intop;cinop;if(op1){intpos;charch;cinposch;update(1,1,n,pos,ch);}else{intl,r;cinlr;if(query(1,1,n,l,r).mnv0){coutYes\n;}else{coutNo\n;}}}}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;// cin T;T1;while(T--)solve();return0;}