（update:目前更新至ABCDHIJ）
CSDN上同步更新了，可食用 -> 传送门直达\
总结：考场多次犯蠢，没睡醒导致的
A——回文子串
题目链接：https://ac.nowcoder.com/acm/contest/98502/A
前缀知识：思维
容易发现，只有当相同的字母聚在一起时，能够产生的贡献是最大的（例如aaaa 放在一起会有aa aaa aaaa之类的贡献一并加入），题目说了可以重排该串，故累计所有出现字母的数量
千万别想复杂了还去遍历啥的 ...\
void solve(){
string s;cin>>s;
//可以直接累计字母个数不用像我一样写这么麻烦qwq
sort(s.begin(),s.end());
//算下范围应该不用开long long
ll ans=0;
for(int i=0;i<s.length();i++){
int pt=i+1,now=0;
while(s[pt]==s[i]&&pt<s.length()){
now++;
pt++;
}
ans+=1ll*(pt-i-1)*(pt-i)/2;
i=pt-1;
}
cout<<ans+s.length()<<'\n';
}
B——心中的义父
题目链接：https://ac.nowcoder.com/acm/contest/98502/B
开局wa一发，AB换着犯蠢到50min才想起来...战犯级表现
签到题，输出min(2n-1,(m+1)/2×2)就行了(大多数人wa都是因为没判断m吧...)\
C——资源分配
题目链接：https://ac.nowcoder.com/acm/contest/98502/C
很多人想着根据题目推公式了，但因为涉及到下取整啥的不太可行，我们选择直接选出z来遍历
但是选z的话不可能直接从1开始遍历（很显然会超时）
前缀知识：二分
注意到如果选z满足，那么选z+1必然满足（即答案具有单调性），考虑二分答案
代码如下
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define N 100010
#define inf 0x7ffffffffffff
ll n,x;
void solve(){
cin>>n>>x;
auto check=[&](ll mid)->bool{
ll now=n,get=0;
while(true){
ll tmp=now;
now-=mid;
//注意要是不足mid则全拿掉
if(now<=0){
get+=tmp;
break;
}else{
get+=mid;
now-=now*x/100;
}
}
return get>=1.0*n/2;
};
ll l=1,r=1e14,ans=inf;
while(l<=r){
ll mid=l+r>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
cout<<ans<<'\n';
}
H——东方红红蓝
题目链接：https://ac.nowcoder.com/acm/contest/98502/H
（首先注意别读错题了，只有RRB BBG GGR才有贡献！）
看到这道题，让我想到了类似的一道题，可以练一练这种简单计数题 -> 传送门（里面的E题）
前缀知识：前缀和/后缀和，计数，思维
其实思路很简单，我们枚举2 - n-1每一个点为中间点，看它能对答案产生多少贡献
例如 当前为B 那只有前面的B的个数和后面G的个数能对其产生贡献，其它同理
但是题目又加上了“ * ”这个万能牌
故对B来说(其他同理)，答案贡献为:
前面“ * ”的个数×后面G的个数 + 前面B的个数×后面“ * ”的个数 + 前面B的个数×后面G的个数 + 前面“ * ”的个数×后面“ * ”的个数
（update：已修改代码，感谢指正qwq）
因为是枚举每个点为中间点所作出的贡献，因此不需要单独判断,不用担心***会算重，当然单独拎出来也可以
代码如下：（看起来很吓人但是不难想）
//pre为前面的，suf为后面的，第二维代表RBG*
ll n,pre[N][4],suf[N][4];
void solve(){
cin>>n;
string s;cin>>s;
s=" "+s;
//记得初始化！（多次wa的源头）
for(int i=0;i<=s.length();i++){
pre[i][0]=pre[i][1]=pre[i][2]=pre[i][3]=0;
suf[i][0]=suf[i][1]=suf[i][2]=suf[i][3]=0;
}
for(int i=1;i<s.length();i++){
for(int j=0;j<4;j++) pre[i][j]=pre[i-1][j];
pre[i][0]=pre[i-1][0]+(s[i]=='R');
pre[i][1]=pre[i-1][1]+(s[i]=='B');
pre[i][2]=pre[i-1][2]+(s[i]=='G');
pre[i][3]=pre[i-1][3]+(s[i]=='*');
}
for(int i=s.length()-1;i>=1;i--){
for(int j=0;j<4;j++) suf[i][j]=suf[i+1][j];
suf[i][0]=suf[i+1][0]+(s[i]=='R');
suf[i][1]=suf[i+1][1]+(s[i]=='B');
suf[i][2]=suf[i+1][2]+(s[i]=='G');
suf[i][3]=suf[i+1][3]+(s[i]=='*');
}
ll ans=0;
for(int i=2;i<s.length()-1;i++){
if(s[i]=='R'){
ans+=pre[i-1][0]*suf[i+1][1]+pre[i-1][0]*suf[i+1][3]+pre[i-1][3]*suf[i+1][1]+pre[i-1][3]*suf[i+1][3];
}else if(s[i]=='B'){
ans+=pre[i-1][1]*suf[i+1][2]+pre[i-1][1]*suf[i+1][3]+pre[i-1][3]*suf[i+1][2]+pre[i-1][3]*suf[i+1][3];
}else if(s[i]=='G'){
ans+=pre[i-1][2]*suf[i+1][0]+pre[i-1][2]*suf[i+1][3]+pre[i-1][3]*suf[i+1][0]+pre[i-1][3]*suf[i+1][3];
}else{
//这里要注意也可以直接加上pre[i-1][3]*suf[i+1][3],即***的情况，不会算重（脑子昏了qwq）
ans+=pre[i-1][0]*suf[i+1][1]+pre[i-1][1]*suf[i+1][2]+pre[i-1][2]*suf[i+1][0]+pre[i-1][3]*(suf[i+1][0]+suf[i+1][1]+suf[i+1][2])+(pre[i-1][0]+pre[i-1][1]+pre[i-1][2])*suf[i+1][3]+pre[i-1][3]*suf[i+1][3];
}
}
cout<<ans<<'\n';
}
J——木桶效应
题目链接：https://ac.nowcoder.com/acm/contest/98502/J
" 这题比赛时犯大错，结束前3min突然想出正解但没时间改了qwq "
前缀知识：后缀和，思维
赛后仔细想了想，发现不用将op为1和op为2的两种情况分别放进两个数组（太麻烦了容易错）
这里有组样例供大家测（过了这个基本就过了）
输入：
6
1 2 3 7 5 100
13
1 3
2 2 2
1 2
2 2 3
2 2 4
2 5 1
1 3
1 2
2 2 1
1 2
2 3 1
2 4 2
1 2
输出：
3 2 2 2 3 100
思路如下：
先考虑所有没被修改的点，最后变成的肯定是max(自己，op为1修改里面最大的值val);
再看修改的点，我们发现如果修改同一位置，那么后面的点会把前面的点修改的值给覆盖掉（op为1和2都一样），对于每个最后修改的点，能改变它的只有它后面的当op=1的时候,故预处理一个后缀max记录所有op=1的里的val的最大值，从后往前遍历，每次到要修改的点时就比较更新max（suf[i+1],当前修改的pos位置的值）,最后输出即可。复杂度：O（n+q）
代码如下：（比较丑陋）
//vis记录当前点是否是操作2单点修改pos,mp记录当前位置是否是最后一次修改
int n,suf[N],vis[N],mp[N];
//记录值，索引位置
struct point{
int val,pos;
}a[N],p[N];
void solve(){
cin>>n;
int minn=inf;
for(int i=1;i<=n;i++){
cin>>a[i].val;
minn=min(a[i].val,minn);
}
int q;cin>>q;
for(int i=1;i<=q;i++){
int op;cin>>op;
if(op==1){
int val;cin>>val;
minn=max(minn,val);
p[i].pos=0;
p[i].val=val;
}else if(op==2){
//这里的mp也可以拿个数组lst直接覆盖
int pos,val;cin>>pos>>val;
p[i].pos=pos;
vis[pos]=1;
mp[pos]=1;
p[i].val=val;
a[pos].val=val;
}
}
for(int i=q;i>=1;i--){
suf[i]=suf[i+1];
if(!p[i].pos){
suf[i]=max(suf[i+1],p[i].val);
}
}
for(int i=q;i>=1;i--){
//确保该点是对应pos最后一个修改的点
if(p[i].pos&&mp[p[i].pos]){
a[p[i].pos].val=max(a[p[i].pos].val,suf[i+1]);
mp[p[i].pos]=0;
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
a[i].val=max(a[i].val,minn);
}
cout<<a[i].val<<" \n"[i==n];
}
}
似乎有人写线段树也能过，下次试试()
D——决斗
题目链接：https://ac.nowcoder.com/acm/contest/98502/D
这题思路其实出的很快，但比赛时因为不记得卡特兰数通项推了半天qwq
前缀知识：逆元，乘法原理，卡特兰数，思维
思路如下：
考虑一共n场比赛，2n个角色，易得每个W和Z其实是一样的（我赢代表对方输，对方赢代表我输），但是不一样就在于每个连续的W和连续的Z要分开处理，详细解释一下样例（见下）
前面的WW其实就是：(_代表W出战的角色，O代表Z出战的角色，从左到右实力递增)
OO__
O_O_
同样Z就是：
_O
样例二中的WWW就是：
OOO___
OO__O_
O_OO__
OO_O__
O_O_O_
因此我们可以发现这种形式很像汽车进库出库的方案数（其实也就是卡特兰数）
要保证右边的每个_不能大于左边的O的个数
如果是Z的话同理，只需要把O变成_,_变成O就行
最后就对每个连续区间得出的答案相乘就行（乘法原理），注意卡特兰数通项分母要转成逆元，不然会wa
代码如下：
#define ll long long
#define N 100010
#define inf 0x7fffffff
const ll mod=998244353;
ll ksm(ll x,ll b){
ll ans=1;
while(b){
if(b&1) ans=(ans*x)%mod;
b>>=1;
x=(x*x)%mod;
}
return ans%mod;;
}
ll f[N],res[N];
ll C(ll n,ll m){
return (f[m]*ksm(f[n],mod-2)%mod*ksm(f[m-n],mod-2)%mod)%mod;
}
void solve(){
ll n;cin>>n;
//预处理阶乘
f[0]=1ll;
for(int i=1;i<=2*n;i++){
f[i]=(f[i-1]*1ll*i)%mod;
}
string s;cin>>s;
vector<int> v;
//处理每个连续的区间
for(int i=0;i<s.length();i++){
int pt=i+1;
while(s[pt]==s[i]&&pt<s.length()){
pt++;
}
v.push_back(pt-i);
i=pt-1;
}
ll ans=1;
//计算卡特兰数（注意逆元）,以及我这边稍微化简了一项，通项为C(2n,n)/(n+1);
res[0]=1,res[1]=1,res[2]=2;
for(int i=3;i<=n;i++){
res[i]=(C(i-1,2*i)%mod*ksm(i,mod-2)%mod)%mod;
}
for(auto x:v){
ans*=res[x];
ans%=mod;
}
cout<<ans<<'\n';
}
I——跳格子
题目链接: https://ac.nowcoder.com/acm/contest/98502/I
wc诈骗题，赛场上真就被题目搞混了，如果静下心来把前面六题a了就可以冷静思考了（qwq）
前置知识：思维，并查集（其实也不用）
思路如下：
玩一玩样例很容易得到:获胜的条件和这个数组里面环的个数奇偶性有关，一个人选的话肯定会走完这个环里面所有位置。因此，我们预处理出最开始数组里面成环的个数（当然一个数也算）。
接着发现：每次交换的操作无论如何都只会有两种状态：两个小环变成一个大环，一个大环变成两个小环
（ps:题目已经排除自己和自己交换这种无效操作了，但其实如果不排除也可以写，就是前缀和记录一下自己和自己交换出现的次数即可，最后一共（pre[r]-pre[l-1]）没有奇变偶/偶变奇的过程，减掉最后算贡献即可）。
因此，对于每次询问具体交换哪些数我们无需考虑，只需要考虑交换的次数就可以了，最后计算贡献看奇偶性就行了。
复杂度：O（n+m+q）
代码如下：
#define N 200010
#define ll long long
int n,m,q,a[N],vis[N],tot;
//两小环变一大环/一大环变两小环
void solve(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(!vis[i]){
tot++;
int now=i;
while(!vis[now]){
vis[now]=1;
now=a[now];
}
}
}
//如果l和r可能相等的话，则记录一下前缀和（pre[i]=pre[i-1]+(l==r)）但题目已经说了，故这里不需要
for(int i=1;i<=m;i++){
int l,r;cin>>l>>r;
}
//每次询问判断奇偶性就行了
for(int i=1;i<=q;i++){
int l,r;cin>>l>>r;
cout<<((r-l+1+tot)&1?"z":"w")<<'\n';
}
}
后续再看看哪些题可以补补qwq
下次接着努力吧...
京公网安备 11010502036488号