本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16463496.html

~~你TM告诉我这是萌新赛？~~

比赛地址

比赛情况

排名：34 / 846
AC：6 / 11

爆搜+记忆化

先 $O(\sqrt n)$ 求出所有 $a^k$ ，存到一个数组里面。

显然，当 $n=1$ 时为必胜数，所有能走到必败数的数都是必胜数，怎么走都是必胜数的是必败数

然后爆搜+记忆化就行，记忆化可以拿个map来实现

统计 $s,t$ 中每个字母出现次数为奇数还是偶数，奇数则剩余字母数量+1，复杂度 $O(n)$

链表

一开始按原顺序连起来， $l,r$ 分别代表当前的头和尾

每次操作时就是把这个数删掉它，连到链表尾部

注意维护链表头

先对 $a$ 排序

假设现在前 $i-1$ 个数可以构造 $[1,x]$ ，若 $a_i>x+1$ ，就不行了

否则，算上 $a_i$ ，范围就变成 $[1,x+a_i]$

把每个位置 $a_i$ 复制多一个 $a_i+b_i$ ，然后从前往后逐个点确定

在每个车店维护用优秀队列维护到这个地方的最少辆数

1，3操作简单，重点在2操作

用线段树维护区间积，支持单点修改、区间求积和修改操作，然后套个逆元就行

从后往前，维护最大值

感觉被骗了，根本不是萌新赛

刚开题，看A就想不到思路，发现很多人过了K，跑去打，WA了一次，6min时过了

然后发现B过得多，看完之后9min过了

然后发现很多人过D，一开始没想到思路，纸上画了画发现可以直接套链表，打的时候边思考边打，43min时才过

然后看G，一开始觉得可以重复删，然后wa了

后来发现重叠部分不能累计删，打了个线段树，没过，发现有些细节的地方，改了改94min时过了

F题一开始写了个dp式子，然后行不通，想用单调队列优化，又不知道怎么用，后来干脆直接标记结束点套优先队列，137min时过

回来看A，一开始一直往博弈论的方向想，死活想不出。后来猜测直接爆搜加记忆化能过，调了几次后162min时过了

剩下感觉有希望就E和J，E题感觉很套路，但纸上画了好久想不出。J去年暑假好像做过，但现在全忘了

最后遗憾做出不

E题看完题解后感觉好简单啊，为什么当时想不出呢，呜呜呜