2024河南萌新联赛第六场题解

本文主要是介绍2024河南萌新联赛第六场题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这场的出题组是郑州大学acm实验室，验题组是郑州大学和郑州轻工业大学的志愿者同学们。

官方题解大部分内容是我写的，B题思路部分是对应的出题人自己写的，E题思路以及代码都是对应的出题人写的~~因为我不会写这个题~~，题目的题面，数据和std程序等明天问问能不能放。std程序是各自的出题人自己写的，和本篇题解的代码不一样。

碎碎念就扔到题解最后了，想看可以看，不想看也没关系。

难度分布如下：
在这里插入图片描述

A 装备二选一（一）

思路：

这题就是算一下期望，然后比较一下哪件武器的伤害期望更大即可。

手上的武器 $a\%$ 概率暴击造成 $b$ 倍伤害，假设原本伤害是 $x$ ，因此伤害期望就是 $(1-a\%)*x+a\%*bx$ ，同理新获得的武器的伤害期望就是 $(1-c\%)*x+c\%*dx$ 。假设两者中间有一个不等号，对不等式进行化简： $(1-a\%)*x+a\%*bx\ \bigcirc\ (1-c\%)*x+c\%*dx$ $(100-a)+a*b\ \bigcirc\ (100-c)+c*d$ $a*(b-1)\ \bigcirc \ c*(d-1)$

因此只要比较一下最后两个式子的大小，就知道中间的不等号是什么了。如果是小于号，则更换武器，否则就不需要更换。

这题赛时一堆wa的，据说好像是用double会出现精度问题导致的wa。长长记性，以后能不用浮点数就不要用。这题一开始数据弱了，给了一个错误写法结果过了，后面写题解的时候才发现问题，好在及时补救上了。

code：

#include <iostream>
#include <cstdio>
using namespace std;int a,b,c,d;int main(){cin>>a>>b>>c>>d;puts((a*(b-1)<c*(d-1))?"YES":"NO");return 0;
}

至于为什么这个地方只出了（一），出题人说要在后续比赛出（二），敬请期待吧。

B 百变吗喽

思路：

下面是出题人自己写的题解，我引用一下：

我们设在第一个字符串 $s$ 的位置 $i$ 上插入一个字符 $c h$ 之后，使得字符串 $s$ 变为 $s^{'}$ 并和目标字符串 $t$ 完全相同。那么就等价于同时满足下列三个条件：

$s[0\dots i-1] = t[0\dots i-1]$
$s[i\dots n-1] = t[i+1\dots n]$
$c h = t [i]$
由于 $c h$ 可以为任意字符，那么第三个条件一定成立。而前两个条件成立就等价于 $s$ 和 $t$ 在 $i$ 处拆分的前缀和后缀字符串都相等。

于是我们找到s和t的最长公共前缀长度 $p re$ ，以及最长公共后缀长度 $s u f$ 。那么我们可以在 $\in [suf,pre]$ 处插入一个字符 $t [i]$ 来实现 $s^{'}$ 和 $t$ 全等。因此，总的方案数为 $ma x (0, p re - s u f + 1)$ , 每个方案为 $i\ t[i]$ $\in [suf,pre])$

这题数据弱了，导致赛时有些不对的代码也能过。

code：

这是字符串从 $1$ 开始编号的写法，也就是第一个字符编号是 $1$ 。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int n,i1,i2;
string s1,s2;int main(){cin>>s1>>s2;n=s2.length();s1=" "+s1;s2=" "+s2;for(i1=1;i1<=n-1 && s1[i1]==s2[i1];i1++);for(i2=n;i2>=1 && s1[i2-1]==s2[i2];i2--);if(i2<=i1){cout<<i1-i2+1<<endl;for(int i=i2;i<=i1;i++)cout<<i-1<<" "<<s2[i]<<endl;}else cout<<0<<endl;return 0;
}

编号从 $0$ 开始的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int n,i1,i2;
string s1,s2;int main(){cin>>s1>>s2;n=s2.length();for(i1=0;i1<n-1 && s1[i1]==s2[i1];i1++);for(i2=n-1;i2>=0 && s1[i2-1]==s2[i2];i2--);if(i2<=i1){cout<<i1-i2+1<<endl;for(int i=i2;i<=i1;i++)cout<<i<<" "<<s2[i]<<endl;}else cout<<0<<endl;return 0;
}

16进制世界

思路：

如果不看饱食度，实际上就是一个裸的背包问题。算上幸福度其实也难不了多少。

朴素的想法是给幸福度再开一维，但是这样肯定会爆空间。因为我们只需要最后幸福度为 $16$ 的倍数，换句话说就是模 $16$ 同余 $0$ ，不在乎它有多大。如果两个数 $a, b$ 加起来是 $16$ 的倍数，那么就有 $(a+b)\% 16=0$ $(a\%16+b\% 16)\%16=0$

换句话说就是如果两个数 $a, b$ 加起来是 $16$ 的倍数，只需要 $a, b$ 模 $16$ 的余数加起来是 $16$ 的倍数即可，同理可以拓展到多个数相加以及递归地将 $a, b$ 拆成其他几个数的和。这样我们 $d p$ 的第二维就没必要存储幸福度，而只需要存储幸福度模 $16$ 后的余数即可。

那么我们就设 $d p [i] [j]$ 表示饱食度为 $i$ 时，幸福度模 $16$ 同余为 $j$ 时能吃的最多月饼个数。对一个月饼，饱食度和幸福度分别为 $v, w$ ，递推方程为 $dp[i+v][(j+w)\%mod]=max\{dp[i+v][(j+w)\%mod],dp[i][j]+1\}$ 。

因为每个月饼只有一个，所以枚举 $i$ 时应该从大到小枚举，否则在算较大的 $i$ 的 $d p$ 值时用的是已经更新过的较小的 $i$ 的 $d p$ 值，相当于吃了多块这个月饼。还有就是记得除了 $d p [0] [0] = 0$ 其他位置初始化为 $-\infty$ ，因为必须从 $d p [0] [0]$ 向后推，不能从其他位置开始。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int inf=1e9;
const int maxn=1e5+5;
const int mod=16;int n,m;
int dp[maxn][20];//饱食度 幸福度 int main(){cin.tie(0)->sync_with_stdio(false);cin>>n>>m;for(int i=0;i<=m;i++)for(int j=0;j<mod;j++)dp[i][j]=-inf;dp[0][0]=0;for(int _=1,v,w;_<=n;_++){cin>>v>>w;w%=mod;for(int i=m-v;i>=0;i--)for(int j=0;j<16;j++)dp[i+v][(j+w)%mod]=max(dp[i+v][(j+w)%mod],dp[i][j]+1);}int ans=0;for(int i=0;i<=m;i++)ans=max(ans,dp[i][0]);cout<<ans<<endl;return 0;
}

D 四散而逃

思路：

发现如果中间 $n - 2$ 个位置只要存在一个 $\gt1$ 的数，就可以进行至少一次“奔逃”操作，这个位置的一侧可以让逃出来的一个人分配到这边的某个奇数位置上（如果没有就直接放在边上就可以了，就不要放到中间的位置上了，因为这样不仅让中间的某个位置人数变多，需要的“奔逃”次数变多，还让他变成了奇数人数，没有好处），然后就会产生一个偶数，重复这样的操作，就可以把中间所有数都变成偶数，进而都“奔逃”到两边。

反之如果一开始中间 $n - 2$ 个位置全是 $1$ ，那么就无解了。

中间 $n - 2$ 个位置里，一个位置假设有 $x$ 人，如果是奇数，就需要别的地方过来一个人补齐 $x + 1$ ，需要的“奔逃”次数就是 $(x + 1) /2$ ，如果是偶数，直接“奔逃”需要 $x /2$ 次。

这题数据太弱了，我一开始写错了，结果AC了，想都没想就过了（毕竟难度定的才easy，也没多想），后面题解也跟着写错了。赛时估计一些代码也都能过。哎这提示我们出题的时候要自己手搓一些可能的hack数据放上去。

code：

#include <iostream>
#include <cstdio>
using namespace std;int n;int main(){cin>>n;bool flag=false;long long ans=0;for(int i=1,t;i<=n;i++){cin>>t;if(i!=1 && i!=n){if(t>1)flag=true;ans+=(t+1)/2;}}cout<<((flag)?ans:-1)<<endl;return 0;
}

E 铃兰小姐是我们的光

思路：

整体思路替罪羊树维护动态的 dfs 序然后把数颜色转换成序列区间和。在这题是转换成了子树和。插入一个点就是把 $u$ 和 $u + n$ （ $u$ 子树结束的标记，权值为 $0$ ，仅用于查询）插入到 $f$ 后。

为了维护 dfs 序，能够支持插入和比较前后关系，我们为每个点维护一个标记 $tag_i$ ，需要比较两个节点在 dfs 序上的前后关系，只需要比较 $t a g$ 的大小即可。

如何维护这个标记呢？我们让每个点对应一个实数区间 $(l, r)$ ，其中根节点对应实数区间 $(0, 1)$ 。对于每个节点 $i$ 该节点的 $tag_i=\frac{l+r}{2}$ ，左儿子对应的区间为 $l, tag_i)$ ，右儿子对应的区间为 $tag_i, r)$ 。由于我们插入节点的时候都是插入到某个节点后面，只需根据 $t a g$ 找到该节点，然后插入到右儿子的位置即可。替罪羊树树用重构保证了树高是 $O(\log n)$ 的，因此无需担心浮点数精度问题。

每个颜色开一个 set 保存所有该颜色的节点，这个 set 的小于号用替罪羊树的标号比较进行重载，这样就能找到当前插入节点相同颜色前驱和后继。替罪羊树发生重构时虽然会修改 $t a g$ 的值，但是大小关系一直没变，保证了重载比较的正确性。

对于维护颜色，我们对每个节点维护另一个权值 $v a l$ 只需在每种颜色处 $+ 1$ ，同色相邻节点的 $l c a$ （最近公共祖先）处 $- 1$ ，这样计算一个节点的子树内颜色数就变成了求子树权值和。实际操作就是每加入一个节点 $u$ 在本身处 $+ 1$ ； $u$ 和同色前驱的 $l c a$ （最近公共祖先）处 $- 1$ ； $u$ 和同色后继的 $l c a$ 处 $- 1$ ；前驱和后继的 $l c a$ 处 $+ 1$ ，因为前驱和后继不再相邻。这个思想类似树上链并，看成对同颜色的节点到根节点的链求一个并，也是出这题的灵感来源之一。

这样处理之后，问题变成了子树求和。之前用替罪羊树维护了 dfs 序，求和也可以在替罪羊树上完成，因为替罪羊树树高是 $\log n$ 的，类似线段树地求 $tag_u$ 和 $tag_{u+n}$ 之间所有节点地权值和即可。

总复杂度 $\log n)$

code：

#include<bits/stdc++.h>
#define next nxt
using namespace std;
int read(){int c=0,nx,sign=1;while(!isdigit(nx = getchar()))if(nx=='-')sign=-1;while(isdigit(nx))c=c*10+nx-'0',nx=getchar();return sign*c;
}const int N=2e6 + 20,M=N*2;
int head[N],next[M],ver[M];
inline void addEdge(int u,int v){static int now = 0;next[++now]=head[u],head[u]=now,ver[now]=v;next[++now]=head[v],head[v]=now,ver[now]=u;
}const int K = N * 2;
double alpha = 0.7;
int n, m, root;
int sum[K], dat[K];
int ls[K], rs[K], sz[K];
double val[K];
int k;
// bool cmp(int x, int y){
// 	return val[x] < val[y];
// }class cmp {public:bool operator() (const int& lc, const int& rc)const {return val[lc] < val[rc];}
};
set<int, cmp> col[N];int *to_build;
double tol, tor;inline int New(int x){static int now = 0;dat[++now] = x;return now;
}
inline void pushup(int s){sz[s] = sz[ls[s]] + sz[rs[s]] + 1;sum[s] = sum[ls[s]] + sum[rs[s]] + dat[s];
}
inline bool is(int s){// cerr<<"&"<<sz[s] * alpha<<' '<<max(sz[ls[s]], sz[rs[s]])<<endl;return sz[s] * alpha < max(sz[ls[s]], sz[rs[s]]); 
}void add(double p, int u, int x, int &s = root, double l=0, double r=1){// cerr<<"add "<<p<<' '<<u<<' '<<x<<' '<<s<<' '<<l<<' '<<r<<endl;if(!s){s = u;val[s] = (l + r) / 2;// cerr<<"feijo\n";dat[s] = x;sz[s] = 1;return ;}if(p < val[s])add(p, u, x, ls[s], l, val[s]);elseadd(p, u, x, rs[s], val[s], r);pushup(s);if(is(s))to_build = &s, tol = l, tor = r;
}void modify(double p, int x, int s = root){if(p < val[s])modify(p, x, ls[s]);else if(p > val[s])modify(p, x, rs[s]);elsedat[s] += x;pushup(s);
}int query(double ql, double qr, int s = root, double l=0, double r=1){// cerr<<"query "<<ql<<' '<<qr<<' '<<s<<' '<<l<<' '<<r<<endl;if(!s)return 0;if(ql <= l and r <= qr){return sum[s];}int ans = 0;if(ql < val[s])ans = query(ql, qr, ls[s], l, val[s]);if(qr > val[s])ans += query(ql, qr, rs[s], val[s], r);if(ql <= val[s] and qr >= val[s])ans += dat[s];return ans;
}int stk[K], top;
void dfs(int s){// cerr<<"dfs "<<s<<' '<<l<<endl;if(!s)return ;dfs(ls[s]);stk[++top] = s;dfs(rs[s]);
}
void build(int &s, int l=1, int r=top, double vl=tol, double vr=tor){// cerr<<"build "<<s<<' '<<l<<' '<<r<<' '<<vl<<' '<<vr<<endl;if(l > r){s = 0;return ;}int mid = (l + r) >> 1;s = stk[mid];val[s] = (vl + vr) / 2;build(ls[s], l, mid - 1, vl, val[s]);build(rs[s], mid + 1, r, val[s], vr);pushup(s);
}inline void insert(double p, int u, int x){add(p, u, x);if(to_build){// cerr<<"????\n";top = 0;dfs(*to_build);// cerr<<"**top="<<top<<endl;// for(int i=1;i<=top;i++)// 	cerr<<stk[i]<<' ';// cerr<<endl;build(*to_build);to_build = 0;}
}namespace lca_bz{int lg[N];int fa[21][N],d[N];int lca(int u,int v){if(d[u] < d[v])swap(u,v);while(d[u] > d[v])u = fa[lg[d[u] - d[v]]][u];if(u==v)return u;for(int i=lg[d[u]];i>=0;i--)if(fa[i][u] != fa[i][v])u = fa[i][u], v = fa[i][v];return fa[0][u];}
}
using namespace lca_bz;// void print(int s=root){
// 	if(!s)
// 		return ;
// 	print(ls[s]);
// 	cerr<<'*'<<s<<' '<<ls[s]<<' '<<rs[s]<<' '<<val[s]<<' '<<dat[s]<<' '<<sum[s]<<' '<<sz[s]<<endl;
// 	print(rs[s]);
// }int main(){// 强制在线版标程// fclose(stderr);n = read(), m = read();// printf("%d %d\n", n, m);d[0] = -1;int cntt = 0;for(int i=1;i<=n;i++)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);for(int i=0;i<=n;i++)--lg[i];int pre = 0;while(m--){int op = read(), u = read() ^ pre, f, c;if(op == 0){cntt++;f = read() ^ pre, c = read() ^ pre;// printf("%d %d %d %d", op, u ^ pre, f ^ pre, c ^ pre);d[u] = d[f] + 1;fa[0][u] = f;for(int i=1, tt = lg[d[u]];i<=tt;i++)fa[i][u] = fa[i - 1][fa[i - 1][u]];insert(val[f], u, 1);insert(val[u], u + n, 0);// cerr<<"EFJIO\n";auto &cc = col[c];auto lp = cc.lower_bound(u), rp = cc.upper_bound(u);auto lt = lp != cc.begin(), rt = rp != cc.end();if(lt){lp--;f = lca(u, *lp);modify(val[f], -1);}if(rt){f = lca(u, *rp);modify(val[f], -1);}if(lt and rt){f = lca(*lp, *rp);modify(val[f], 1);}cc.insert(u);}else{// printf("%d %d %d %d", op, u ^ pre);printf("%d\n", pre = query(val[u], val[u + n]));pre = query(val[u], val[u + n]);// cout<<'*'<<cntt-u+1<<endl;}// cerr<<query(val[u], val[u + n])<<endl;// print();// cerr<<'*'<<(val[1] <= val[1])<<endl;}// cerr<<"color "<<clock()<<endl;
}

F 追寻光的方向

思路1（前缀和）：

注意一开始是停在第一个路灯下面的，所以第一个路灯的值是无所谓的，直接跳过。

准确来说应该是后缀和，我们用 $s u f [i]$ 表示 $i\sim n$ 中最大的数的位置（如果有多个就记最靠前的那个）。然后从第一个路灯开始模拟一下跳的过程就行了。

因为跑到最后一个路灯的时候直接就到终点了，不需要休息，所以答案要减一。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;int n,a[maxn],suf[maxn];int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];suf[n]=n;for(int i=n-1;i>=1;i--)suf[i]=(a[i]>=a[suf[i+1]])?i:suf[i+1];int ans=0;for(int p=2;p<=n;p=suf[p]+1,ans++);cout<<ans-1<<endl;return 0;
}

思路2（排序+模拟）：

因为亮度最大的灯只要在我们前方，我们就优先考虑跑到它下面，如果在身后就不用考虑了。所以可以对所有路灯的亮度从大到小排个序，然后模拟上面的过程。先跑到最亮的灯下，再跑到次大的灯下……如果看到某个灯编号比我们自己所在的编号要小就丢弃。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
#define pii pair<int,int>int n;
pii a[maxn];int main(){cin>>n;n--;int t;cin>>t;for(int i=1;i<=n;i++){cin>>t;a[i]={t,i};}sort(a+1,a+n+1,[](pii a,pii b)->bool{return (a.first==b.first)?a.second<b.second:a.first>b.first;});int ans=0,p=0;for(int i=1;i<=n;i++){auto [l,id]=a[i];if(id>p)p=id,ans++;}cout<<ans-1<<endl;return 0;
}

思路3（单调栈）：

第一次我们是跑到 $2\sim n$ 中最大的值下的，假如是第 $x$ 个元素，然后我们再跑到 $x+1\sim n$ 中的最大值……

换个思路，第 $x$ 个位置上的数其实相当于把前面的 $2\sim x-1$ 位置上的数都挤掉了，因为有第 $x$ 位置上的最大值，所以前面的数都不需要考虑，这种“比你小还比你强，所以你就没用了”的思想就很单调队列（不过不需要从队首出队，所以直接用单调栈就行了）。

code：

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;int n;
stack<int> sta;int main(){cin>>n;for(int i=1,t;i<=n;i++){cin>>t;if(i==1)continue;while(!sta.empty() && t>sta.top())sta.pop();sta.push(t);}cout<<sta.size()-1;return 0;
}

G 等公交车

思路：

我们在距离为 $d$ 的车站等候，那么第 $i$ 辆公交车到站的时刻就是 $t_i+d$ ，那我们在某个时刻 $t$ ，要等的第一辆车就是第一个大于等于 $t$ 的时刻到的车（这一步可以二分查找）。但是我们不可能给每个公交车的发车时刻都加上一个 $d$ ，这样是 $O(nq\log n)$ 的。

不妨这样来想，我们在距离为 $d$ 的车站在 $t$ 时刻开始等候，其实就相当于我们在距离为 $0$ 的车站在 $t - d$ 时刻开始等候。因为一辆车在某个时间到距离为 $d$ 的车站，那么在 $d$ 分钟前一定到距离为 $0$ 的车站，所以两者的到站顺序是完全一致的。这样就不需要给每个公交车的发车时刻都加上一个 $d$ ，而只需要在二分查找的时候找 $t - d$ 的时刻后第一辆发的车就可以了。时间复杂度 $O(q\log n)$

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;int n,m,q;
int a[maxn],b[maxn];int main(){cin.tie(0)->sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];cin>>q;for(int i=1,tm,id,idx;i<=q;i++){cin>>tm>>id;tm-=a[id];auto it=lower_bound(b+1,b+m+1,tm);if(it-b>m)cout<<"TNT\n";else cout<<*it-tm<<"\n";}return 0;
}

H 24点

思路：

就，暴搜打表，然后查表，就可以了。

先把输入的扑克牌点数转化为对应的数字，用 $ma p$ 就行。

一组数据总共就四个数，不同顺序相同的四个数可以看作是一种情况。我们把 $13$ 种取值看成 $13$ 个盒子，四个数看成是 $4$ 个相同的小球，这样就相当于相同球放入不同盒可以空盒的球盒问题，用隔板法可以计算，这样总共就是 $C^4_{13+4-1}=1820$ 种情况。所以 $T$ 虽然能到 $5 e 5$ ，但大部分都是重复的，所以只需要算这 $1820$ 种情况，打表然后查表即可。

问题在于如何判定一种情况有解，爆搜即可。数的顺序是可变的，确定好数的顺序后，运算的顺序也是可变的，比如我们可以先算第二个数和第三个数，然后它们的结果再和第一个数进行运算（也就是加括号调整运算顺序）。如果只枚举所有排列，不枚举运算顺序的话（也就是只从左向右运算）是有可能出bug的，比如 $10-(2\times 3)=4$ 这个我们是不能通过枚举排列然后从左到右依次结合算出 $4$ 的。所以需要枚举数的顺序和运算的顺序，弄好这两个东西后，再枚举一下运算符就可以了。整个的运算次数大概是 $4!\times 3!\times 4^3\times 1820=16773120$ ，之后查表也花不了太多时间， $2 s$ 时限很稳。

枚举数的顺序好说，直接用 STL 的 bool next_permutation(iterator start,iterator end) 函数就可以了。
运算的顺序的枚举可以枚举运算符的序号，一开始是 $4$ 个数 $3$ 个运算符，用 $0$ 代表第 $0$ 个运算符，两边分别是第 $0$ 个数和第 $1$ 个数，枚举到 $0$ 就将它们结合，同理 $1, 2$ 。运算一次后剩余 $3$ 个数 $2$ 个运算符，同理用 $0, 1$ 来代表这两个运算符以及两边的操作数。最后剩下 $2$ 个数 $1$ 个运算符，直接计算。这样一共是 $3! = 6$ 种情况。
枚举运算符好说，可以写三重 $f or$ 循环，为了方便也可以用 $3$ 位 $4$ 进制数来代表三个运算符。

实际在写的时候你会发现有时候会出现除出分数的情况，而且这无法通过枚举数的顺序和运算顺序规避掉。比如 A 3 4 6 这种情况，运算方法只有 6/(1-(3/4))=24 一种。解决方法也简单，就是直接用浮点数来算，因为就四个数运算，精度损失几乎可以忽略不计。可以设置一个精度值 $eps=10^{-9}$ ，最后和 $24$ 比较一下，如果精度（与 $24$ 的差值的绝对值）在 $e p s$ 以内，就认为结果就是 $24$ ，不过浮点运算太慢，容易超时。或者可以用取模运算，这样除法就被转化为乘法了，除以一个数相当于乘上这个数的逆元。

这题一开始没想到有原题的，结果发现开赛两分钟就被某牛客rk几十的大佬秒了然后榜就开始歪了，大伙都来写这爆搜粪题才发现问题所在。不过好在没原的那么彻底，还是有点不一样的地方的。这题一开始数据量给的 $5 e 5$ ，但是验题的时候发现根本没人做，临时改数据量换成了 $T = 1000$ 。

这题一开始std写出锅了， $1820$ 种情况有 $16$ 种 YES 情况会误判成 NO。后来出题人换了三种写法又上了一个对拍程序才弄好。赛时被某大佬带歪了榜结果半小时 $18$ 人过爆搜粪题，不过也能说明这题至少没再出锅。~~赛时发现有原题，改改std交了直接过了~~

代码：

浮点数运算

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <ctime>
using namespace std;
const double eps=1e-9;int T;
bool ck[15][15][15][15];bool merge(vector<double> &a,int idx,int opt){//是否可以成功合并，可以则合并 if(a.end()-a.begin()<idx+1)return false;if(opt==3 && a[idx+1]==0)return false;//除0了if(opt==0)a[idx]+=a[idx+1];else if(opt==1)a[idx]-=a[idx+1];else if(opt==2)a[idx]*=a[idx+1];else if(opt==3)a[idx]/=a[idx+1];a.erase(a.begin()+idx+1);return true;
}
double compute(vector<int> t,int order,int optr){//od顺序，opt运算符 vector<double> a;for(int i=0;i<4;i++)a.push_back(t[i]);int idx,opt;idx=order%3;order/=3;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;idx=order;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;idx=0;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;return a[0];
}
void check(vector<int> a){auto &flag=ck[a[0]][a[1]][a[2]][a[3]];do{for(int od=0;od<6;od++)//这里枚举运算顺序，用两位3进制数代替，不过最高位只能取得到0,1for(int opt=0;opt<64;opt++)if(abs((compute(a,od,opt)-24))<=eps){flag=true;return;}}while(next_permutation(a.begin(),a.end()));flag=false;return;
}map<string,int> mp;int main(){cin.tie(0)->sync_with_stdio(false);mp["A"]=1;mp["2"]=2;mp["3"]=3;mp["4"]=4;mp["5"]=5;mp["6"]=6;mp["7"]=7;mp["8"]=8;mp["9"]=9;mp["10"]=10;mp["J"]=11;mp["Q"]=12;mp["K"]=13;for(int a=1;a<=13;a++)for(int b=a;b<=13;b++)for(int c=b;c<=13;c++)for(int d=c;d<=13;d++)check(vector<int>{a,b,c,d});cin>>T;int t[4];string tmp;while(T--){for(int i=0;i<4;i++){cin>>tmp;t[i]=mp[tmp];}sort(t,t+4);cout<<((ck[t[0]][t[1]][t[2]][t[3]])?"YES":"NO")<<"\n";}return 0; 
}

取模运算。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <ctime>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;int T;
bool ck[15][15][15][15];ll qpow(ll a,ll b){b%=mod;ll ans=1,base=a%mod;while(b){if(b&1){ans=ans*base%mod;}base=base*base%mod;b>>=1;}return ans;
}
inline ll inv(ll x){return qpow(x,mod-2);
}bool merge(vector<ll> &a,int idx,int opt){//是否可以成功合并，可以则合并 if(a.end()-a.begin()<idx+1)return false;if(opt==3 && a[idx+1]==0)return false;if(opt==0)a[idx]+=a[idx+1];else if(opt==1)a[idx]+=mod-a[idx+1];else if(opt==2)a[idx]*=a[idx+1];else if(opt==3)a[idx]*=inv(a[idx+1]);a.erase(a.begin()+idx+1);a[idx]%=mod;return true;
}
ll compute(vector<ll> a,int order,int optr){//od顺序，opt运算符 int idx,opt;idx=order%3;order/=3;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;idx=order;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;idx=0;opt=optr%4;optr/=4;if(!merge(a,idx,opt))return -1;return a[0];
}
void check(vector<ll> a){auto &flag=ck[a[0]][a[1]][a[2]][a[3]];do{for(int od=0;od<6;od++)for(int opt=0;opt<64;opt++){if(compute(a,od,opt)==24){flag=true;return;}}}while(next_permutation(a.begin(),a.end()));flag=false;return;
}map<string,int> mp;int main(){cin.tie(0)->sync_with_stdio(false);mp["A"]=1;mp["2"]=2;mp["3"]=3;mp["4"]=4;mp["5"]=5;mp["6"]=6;mp["7"]=7;mp["8"]=8;mp["9"]=9;mp["10"]=10;mp["J"]=11;mp["Q"]=12;mp["K"]=13;for(int a=1;a<=13;a++)for(int b=a;b<=13;b++)for(int c=b;c<=13;c++)for(int d=c;d<=13;d++)check(vector<ll>{a,b,c,d});cin>>T;int t[4];string tmp;while(T--){for(int i=0;i<4;i++){cin>>tmp;t[i]=mp[tmp];}sort(t,t+4);cout<<((ck[t[0]][t[1]][t[2]][t[3]])?"YES":"NO")<<"\n";}return 0; 
}

I 正义从不打背身

思路：

这题我觉的挺神秘的，是打表找规律。因为题目给出的操作是比较固定的，所以我们猜测应该会出现什么规律，为了找到规律所以要先暴力打个表，思路其实挺明确的。

我们暴力模拟里面的反转过程，看看进行 $i$ 次后每个位置上的人原本的编号是多少，以及翻转情况

打表程序：

cin>>n>>m;
vector<int> a(n+1);
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<=m;i++){for(int j=1;j<=i/2;j++)swap(a[j],a[i-j+1]);for(int j=1;j<=i;j++)vis[a[j]]^=1;printf("%2d:",i);for(int j=1;j<=i;j++)cout<<a[j]<<" ";cout<<endl;printf("  :");for(int j=1;j<=i;j++)cout<<(vis[a[j]]?"*":"-")<<" ";cout<<endl;
}

给个 $n = m = 15$ 的数据：

 1:1:*2:2 1:* -3:3 1 2:* * -4:4 2 1 3:* * - -5:5 3 1 2 4:* * * - -6:6 4 2 1 3 5:* * * - - -7:7 5 3 1 2 4 6:* * * * - - -8:8 6 4 2 1 3 5 7:* * * * - - - -9:9 7 5 3 1 2 4 6 8:* * * * * - - - -
10:10 8 6 4 2 1 3 5 7 9:* * * * * - - - - -
11:11 9 7 5 3 1 2 4 6 8 10:* * * * * * - - - - -
12:12 10 8 6 4 2 1 3 5 7 9 11:* * * * * * - - - - - -
13:13 11 9 7 5 3 1 2 4 6 8 10 12:* * * * * * * - - - - - -
14:14 12 10 8 6 4 2 1 3 5 7 9 11 13:* * * * * * * - - - - - - -
15:15 13 11 9 7 5 3 1 2 4 6 8 10 12 14:* * * * * * * * - - - - - - -

其实还是比较好看的。后 $m+1\sim n$ 没有参与操作，就维持原本的状态。前 $m$ 个数的前半部分是以 $m$ 开头， $2$ 为公差递减到 $1$ 或者 $2$ 的等差数列，后半部分以 $1, 2$ 中剩余的那个开头，以 $2$ 为公差递增到 $m - 1$ 。状态的反转情况是：前半部分翻转。

前半部分的长度是 $(m + 1) /2$ ，后半部分的长度是 $m /2$ ，整除运算。知道这个之后就几个 $f or$ 循环就搞定了。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=2e6+5;int n,m;
bool vis[maxn];
string s;int main(){cin>>n>>m;cin>>s;s=" "+s;for(int i=1,j=m;j>=1;i++,j-=2)vis[i]=(s[j]=='P');for(int i=(m+1)/2+1,j=(m&1)?2:1;j<=m;i++,j+=2)vis[i]=(s[j]=='P');for(int i=m+1;i<=n;i++)vis[i]=(s[i]=='P');for(int i=1;i<=(m+1)/2;i++)vis[i]^=1;for(int i=1;i<=n;i++)cout<<vis[i]<<" ";return 0;
}

J 临场发挥

思路：

不那么明显的区间 $d p$ 。

首先要看出来一个贪心的小结论。就是就是能力值大的，应该放在两边，反之放中间。因为如果大数 $x_1$ 与内侧的某个数 $x_2$ 交换位置，假如说向这两个数距离为 $d$ 格，那么大数减少了 $x_1*d$ 的贡献，而小数只增加了 $x_2*d$ 的贡献，得不偿失了。

所以我们可以将所有数从小到大排序，然后设 $d p [l] [r]$ 为用前 $r - l + 1$ 个数填满区间 $[l, r]$ 的最大贡献。根据上面的贪心小结论，我们每次拿到的数与前面用到的数相比是最大的，所以一定是放在区间两边的。假设拿到的数的大小为 $a_i$ ，原本的位置为 $i d$ ，所以递推方程就是 $dp[l][r]=max\{dp[l+1][r]+|l-id|*a_i,dp[l][r-1]+|r-id|*a_i\}$ 。

code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
const int maxn=2005;
const ll linf=1e18;int n;
ll dp[maxn][maxn];
pll a[maxn];int main(){cin>>n;for(int i=1,t;i<=n;i++){cin>>t;a[i]=pll(t,i);}sort(a+1,a+n+1);for(int len=1;len<=n;len++){auto [ai,id]=a[len];for(int l=1,r=l+len-1;r<=n;l++,r++){dp[l][r]=max(dp[l+1][r]+abs(l-id)*ai,dp[l][r-1]+abs(r-id)*ai);}}cout<<dp[1][n]<<endl;return 0;
}

其实我一开始没看懂上面说的啥，然后我用另外一种写法硬是写过了……

大体思路和上面是一样的，不过我们排序是从大到小排序，然后先给大的排到两边。设 $d p [l] [r]$ 表示用前 $l + r$ 个最大值，左边放 $l$ 个，右边放 $r$ 个的最大贡献。

状态转移方程应该也挺好想的，不过就没有区间dp的感觉了。 $dp[l][r]=max\{dp[l-1][r]+|l-id|*a_i,dp[l][r-1]+|n-r+1-id|*a_i\}$

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
const int maxn=2005;
const ll linf=1e18;int n;
ll dp[maxn][maxn];//左边有l个，右边有r个 
pll a[maxn];int main(){cin>>n;for(int i=1,t;i<=n;i++){cin>>t;a[i]=pll(t,i);}sort(a+1,a+n+1,greater<pll>());for(int i=1;i<=n;i++){auto [ai,id]=a[i];ll l,r;for(l=0;l<=i;l++){r=i-l;if(l>0)dp[l][r]=max(dp[l][r],dp[l-1][r]+abs(l-id)*ai);if(r>0)dp[l][r]=max(dp[l][r],dp[l][r-1]+abs(n-r+1-id)*ai);}}ll ans=0;for(int l=0;l<=n;l++)ans=max(ans,dp[l][n-l]);cout<<ans<<endl;return 0;
}

K BanG Dream! It’s MyGO!!!

思路：

~~表达了作者的思乡之情~~

这题算是狠狠地扫盲了。

三角形的计数是三元环计数问题。
三芒星简单，统计一下每个点的度数 $d_u$ ，然后用组合数就能算了。总个数是 $\sum C_{d_u}^3$ 。
闪电折线不能直接算出来。但是我们可以枚举中间那条边，然后两个端点的度数-1乘起来就是闪电折线和三角形*3的总个数。因为三角形个数可以算出来，那这个也就可以算了。

所以这题重点在于三元环计数求三角形个数。详情请看 OI wiki，讲的还挺不错。

code：

本来出题人还想出个模数，答案对模数取模，避免溢出，结果发现数据并不会超，就删掉了。这里计数的时候一开始也没写long long就过了，保险起见还是加上了。

#include <iostream> 
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;int n,m;
int deg[maxn];
int u[maxn<<1],v[maxn<<1];int head[maxn],ent;
struct edge{int v,nxt;
}e[maxn<<2];
void add(int u,int v){e[++ent]={v,head[u]};head[u]=ent;
}ll cnt1,cnt2,cnt3;
bool vis[maxn];
void triangle(){for(int u=1;u<=n;u++){for(int i=head[u];i;i=e[i].nxt)vis[e[i].v]=true;for(int i=head[u],v;i;i=e[i].nxt){v=e[i].v;for(int j=head[v],w;j;j=e[j].nxt){w=e[j].v;if(vis[w])cnt1++;}}for(int i=head[u];i;i=e[i].nxt)vis[e[i].v]=false;}
}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>u[i]>>v[i];deg[u[i]]++;deg[v[i]]++;}for(int i=1;i<=m;i++){cnt3+=1ll*(deg[u[i]]-1)*(deg[v[i]]-1);//闪电折线和三角形*3 if(deg[u[i]]>deg[v[i]] || (deg[u[i]]==deg[v[i]] && u[i]>v[i]))swap(u[i],v[i]);add(u[i],v[i]);}for(int i=1;i<=n;i++)cnt2+=1ll*deg[i]*(deg[i]-1)*(deg[i]-2)/6;triangle();cnt3-=3*cnt1;cout<<cnt1+cnt2+cnt3;return 0;
}

L 约瑟夫问题

思路：

这题本来出的是裸约瑟夫问题，不过后来感觉直接能搜到原题不好，所以换成了看程序。不过应该还是比较容易看出是约瑟夫问题吧。

约瑟夫问题可是老朋友了，不熟悉的可以去 OI wiki 长长见识（线性方法的一个证明）。这个题还要输出每一个出局的人，所以暴力模拟删人的过程，用线段树或者树状数组来优化找到下一个要删的人的过程即可。时间复杂度是 $O(n\log n)$ 或者 $O(n\log^2 n)$ 。

code：

不动脑子的暴力线段树二分写法。这题一开始数据比较弱，而且只有 $1 e 5$ ，导致 $v ec t or$ 暴力删数可以直接写过（ $v ec t or$ 是 $O(n^2)$ ，但是常数很小），后来加强了，但是加强之后这个线段树过不去了（线段树是常数比较大的 $n\log ^2 n$ ），后来大家伙一致认为还是放行线段树比较好，所以最后还是调整时限给过了。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3e5+5;int n,k;struct segement_tree{#define ls (p<<1)#define rs (p<<1|1)int tr[maxn<<3],n;void push_up(int p){tr[p]=tr[ls]+tr[rs];}void build(int p,int l,int r){if(l==r){tr[p]=1;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);push_up(p);}void build(int _n){n=_n;build(1,1,_n);}void print(int p,int l,int r){printf("%d[%d,%d]:%d\n",p,l,r,tr[p]);if(l==r){return;}int mid=(l+r)>>1;print(ls,l,mid);print(rs,mid+1,r);}void print(){print(1,1,n);cout<<endl;}void mdy(int p,int l,int r,int id){if(l==r){tr[p]=0;return;}int mid=(l+r)>>1;if(id<=mid)mdy(ls,l,mid,id);else mdy(rs,mid+1,r,id);push_up(p);}int count(int p,int l,int r,int L,int R){//区间[L,R]的剩余人数 if(L<=l && r<=R){return tr[p];}int mid=(l+r)>>1,ans=0;if(mid>=L)ans+=count(ls,l,mid,L,R);if(mid<R)ans+=count(rs,mid+1,r,L,R);return ans;}int search(int l,int r,int x){//范围[l,r]二分找第x个人的编号 int L=l,mid;while(l<r){mid=(l+r)>>1;if(count(1,1,n,L,mid)>=x)r=mid;else l=mid+1;}return l;}int q(int id,int x){//从id开始向下报x次数int idx;x=(x-1)%count(1,1,n,1,n)+1;//先转整轮，剩下的次数是不够一轮报数的if(count(1,1,n,id,n)>=x)idx=search(id,n,x);//区间[id,n]的剩余人数可以报完else {//不能报完，回到[1,id]区间继续报数x-=count(1,1,n,id,n);idx=search(1,id,x);}mdy(1,1,n,idx);//删人return idx;}#undef ls#undef rs	
}tr;int main(){cin.tie(0)->sync_with_stdio(false);cin>>n>>k;tr.build(n);for(int i=1,idx=1;i<n;i++){
//		tr.print();idx=tr.q(idx,k);cout<<idx<<" ";}return 0;
}

神中神的树状数组倍增写法，直接把大佬的神迹std搬过来，下面再给一个我自己抄的。

有两个亮点：

树状数组利用了辖域这个概念，直接倍增找到了最后一个等于 $k - 1$ 的数，把时间复杂度优化到了 $O(n\log n)$ 。辖域指的是树状数组上某个节点管理的区域（如果节点结合的运算是加法，那么这个节点管理的就是区域的和），对于树状数组某个位置 $i d x$ 上的节点 $t r [i d x]$ ，它的辖域是 $i d x - l o w bi t (i d x) + 1$ 到 $i d x$ 这长为 lowbit(idx) 的区间。
在删人的时候没有取模再分类讨论，而是先找到上次出局的人前面已经报过数的人数，然后再向后报 $k$ 个人，假设此时剩下 $i$ 个人，模 $i$ 就是最后报到了第几个人。

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) { init(n_ + 1); }void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T& v) {if (x < 1)return;for (int i = x; i <= n; i += i & -i) {a[i] = a[i] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i];}return ans;}T rangeSum(int l, int r) { return sum(r) - sum(l - 1); }int select(const T& k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i < n && cur + a[x + i] < k) {x += i;cur = cur + a[x];}}return x + 1;}
};int main() {ios::sync_with_stdio(false);cin.tie();cout.tie(0);int n, k;cin >> n >> k;Fenwick<int> fen(n + 1);for (int i = 1; i <= n; ++i)fen.add(i, 1);int cur = 0, killed = 0;for (int i = n; i > 1; --i) {cur = (fen.sum(killed) + k) % i;if (cur == 0)cur = i;killed = fen.select(cur);// cout << cur << ' ' << killed << '\n';fen.add(killed, -1);cout << killed << ' ';}return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=3e5+5;int n,k;struct tree_array{int tr[maxn],n;int lowbit(int x){return x&-x;}void add(int id,int x){for(int i=id;i<=n;i+=lowbit(i))tr[i]+=x;}void build(int _n){n=_n;for(int i=1;i<=n;i++)add(i,1);}int query(int id){int ans=0;for(int i=id;i;i-=lowbit(i)){ans+=tr[i];}return ans;}int query(int l,int r){return query(r)-query(l-1);}int kth(int k){//倍增找第k大 int id=0,tot=0;for(int i=1<<20;i;i>>=1){if(id+i<n && tot+tr[id+i]<k){tot+=tr[id+i];id+=i;}}return id+1;}
}tr;int main(){cin>>n>>k;tr.build(n);for(int i=n,cur=1,dead=0;i>1;i--){cur=(tr.query(dead)+k-1)%i+1;//取模后的范围不在[0,i)，而在[1,i+1)，所以内部-1，外部+1dead=tr.kth(cur);tr.add(dead,-1);cout<<dead<<" ";}return 0;	
}

碎碎念

这场比赛出题主力是郑州大学大二本科生，组织者、出题人和验题人都是无偿的~~虽然也没几个人来验题，基本都是出题人互相在验~~，出题人都没什么经验，大伙轻喷。

题解一开始是在csdn的编辑器上写的，然后导出为md文档，用typora编辑，再导出为pdf，打包放到赛题文件里了，之后组织者又编辑了一下放到牛客上了。

这个过程里md代码和latex代码有的是不兼容的，导致渲染出错，需要重新修改，比如牛客上面那个有的直接就粘的图片，就是因为放代码格式就乱掉了。csdn编辑器、typora和牛客的行内公式的写法是不一样的。有的题面也是有这个问题，比如说牛客没有加粗，别的地方写的好好的，粘过来就不渲染了。
在这里插入图片描述

题解其实两天前就写好了，但是开赛前一天晚上赛题又重新调整了一下，E题题解也是赛后刚写好，一合并修改，再考虑到各个出题人的版权和隐私，所以题解出的晚了些~~还有就是因为电脑不在我旁边，只能让别人帮我改了~~。挂牛客的时候没想挂名的，感觉有些招摇，而且我写题解又不是为了出名，就像在写日志一样的东西~~最后还是被老大哥挂上了~~ 。

E题验题的时候都没人做出来，搞得出题人紧张兮兮的，生怕出点岔子身败名裂，正赛也是真防住AK了，这下死无对证了，也不知道这题到底是出没出锅。

我验题的时候就说 $H J K L$ 是屎，哎你看正赛果然通过率低的。
在这里插入图片描述
嗯，有点困了，就先写到这吧。