怎么感觉小白月赛的难度越来越低了

看错题，手速慢了，痛失公仔

A 数字游戏

按照题意模拟即可，每次取最高位可以不断用$x-=lowbit(x)x-=lowbit(x)$减去最低位，直到剩下最高位 每次操作是$logxlog\; x$的，最多操作$logxlogx$次，因为位运算常数小，所以可以通过

$O(Tlo{g}^{2}x)O(Tlog^2x)$

code

B 跳跳跳

首先发现在任意时刻，已经跳的区间都是一个联通块（区间）

直接正向考虑区间dp并不是很好做（其实可以，是我降智了），我一开始的想法是反过来，因为操作是可逆的，反过来跳的也是一个区间

所以考虑把数组复制一份，贴在原数组后面

设$f[l][r]f[l][r]$表示区间$[l,r][l,r]$的答案

转移十分简单

$f[l][r]=max(f[l+1][r]+a[l]\ast len,f[l][r-1]+a[r]\ast len)f[l][r]=max(f[l+1][r]+a[l]*len,f[l][r-1]+a[r]*len)$

len表示的是区间长度

时间复杂度$O(n^2)O(n^2)$

代码实现用记忆化搜索比较好写

code

C 数字匹配

这题看错了5次题，直接导致我痛失rank1

首先如果$i,ji,j$的最大重合位数$\ge k\backslash ge\; k$,那么一定存在重合位数$=k=k$的子串

于是我们枚举$i,ji,j$

类似hash的思想

把$ii$的每$kk$位的值都***一个桶里面，然后把$jj$的每$kk$位得到的值都查一下看看存不存在

看代码应该会比较好理解

$O(n^{2}logn)O(n^2logn)$

code

D 优美字符串

显然如果原字符串相邻两个如果是一样的，在这两个中间插一个不同的即可

所以答案是原长+相邻两个一样的个数

code

E 分组

最多最少，一看就是二分答案

二分最多的小组的人数，然后分组看看组数是否$\le m\backslash le\; m$即可

时间复杂度$O(nlogn)O(n\; logn)$

code

F 过桥

本来以为是什么数据结构优化建边，结果发现数据范围才$20002000$

考虑每个点能连向的是一个区间，暴力连边即可

把边反向，从$nn$开始跑$bfsbfs$,最后看$dis[1]dis[1]$即可

如果数据范围是$n=200000n=200000$就要考虑线段树优化建边了

code

G 空调遥控

因为$a[i]a[i]$不大，我们可以枚举$KK$

那么进入训练状态的人的区间就是$[K-p,K+p][K-p,K+p]$

用前缀和计算即可

code

H 来点gcd

看错题卡了一年

如何判断一个数$xx$能不能选出若干数使得$gcd=xgcd=x$

首先选出来的数一定是$xx$的倍数（显然）

然后要让集合gcd是$xx$,那么显然是$xx$倍数的$a[i]a[i]$全部都选才越有可能是$xx$，（因为是一路取gcd）

所以枚举$xx$（不一定要出现过）,然后在枚举它的倍数,如果出现过就和已选的取个$gcdgcd$

是个调和级数

时间复杂度$O(n\ln n)O(n\backslash ln\; n)$ code

I 体操队形

首先考虑把$ii$连向$a[i]a[i]$表示$ii$必须要在$a[i]a[i]$之前

连出来一定是一个$toptop$图

答案就是$toptop$序数量

这个问题是$NPNP$的，没有多项式复杂度算法，怎么办啊

一看数据范围，$n\le 10n\; \backslash le\; 10$指数级算法爆搜即可

code

看我写的这么认真，要个赞不过分吧