A.awa开小车

我们可以将“小车发射器”看作小车在某个位置、起始运动方向为某个方向的描述，那么考虑按照小车运行方向和位置进行模拟即可，在遇到没有触发过的导向板时执行相应的转向，计数，并将其标记为已经过，离开边界的时候结束模拟。

时间复杂度为。

B.JokerXuan的明星梦

定义两个变量t0 与 t1 ，将他们的二进制的形式初始化为000000……与111111……，每次进行幸运数字的更新，同时以相同的方式更新这两个变量。当遇到“null”时，在当前幸运数字的二进制形式中找到0的位置，如果t0中的相应位置变成了1，那么就需要将这个0所在的位置改成1，其余同理。

C.What is ACM

签到题，循环判断每个位置上的字符是不是关键信息，以及前一个位置是不是关键信息，如果连续则说明属于同一个字符串，最后将所有字符串用空格隔开输出。

D.呼风唤雨

前缀和，枚举所有情况求ans，时间复杂度O(n)。

E.急急国王修公路

F. 绒绒的括号序列

考虑将字符串左右拓展出一个合法的括号序列，通过拓展的方案数来确定的数量。 为了避免重复计数，固定串为扩展后串上第一次出现串的位置。

我们称一个括号序列的“匹配值”为其未匹配的左括号的数量，若匹配值为负数则其绝对值为未匹配的右括号数量。

我们知道，一个括号序列是合法的，当且仅当其每一个前缀的匹配值都是非负数，且整个序列的匹配值为0。

设为在串左边拓展长度、匹配值，其任何一个前缀的匹配值都是非负数，且保证是第一次出现串的位置的方案数。 设为在串右边拓展长度、匹配值，且其每一个后缀的匹配值都是非正数的方案数。可以发现其实和拓展长度、匹配值，且每一个前缀的匹配值都是非负数的方案数相等。

首先考虑比较简单，其转移方程可以直接列出

然后对于，我们考虑从中去掉一些部分来得到。 那么就需要考察一下和有什么区别，比多的唯一一个限制是要求是串第一次出现的位置，那么我们就需要去掉会使得串在之前出现的位置。

如果串在之前出现，由于，这个串一定是由左边长度的拓展出的部分的一个后缀与串本身的一个前缀（可以为空）构成的。

此处有的一个前缀等于的一个后缀，而，所以其实的这个前缀是的一个Border，也可以称为公共前后缀。这样一来，前面长度为的部分的后缀就是去掉一个为Border的后缀之后的前缀部分，设Border长度为，则i这部分的后缀实际上是。 那么是不是只要得到的所有Border，然后直接去掉前面相应的部分就行了呢？当然是不行的，如果两个需要删除的部分满足其中一个是另一个的后缀，那么在去掉短的那种情况的时候就已经把长的去掉了。

此处在去掉的情况时，已经被去掉了。 那么这种情况怎么避免呢，继续考虑较短的那部分实际上是的一个前缀，在中同样包括这个前缀，换句话说，较短的这部分就是在前内这部分的一个Border。

我们考虑将串的Border树建出来，每个点表示串长度为的前缀，的父节点是的最大Border，那么只要在树上沿着树边向父节点走，就可以找到串的所有Border，也就是说子树内的串都含有长度为的Border，所以我们只需要将所有需要删的长度对应位置打上标记，然后在Border树上dfs，遇到标记就直接删去贡献并停止向下dfs，避免重复删。

时间复杂度。

G.神奇的礼物

假设三种礼物的数量分别为, , 不妨设经过一次改变后变为 , 考虑任意两者之间差的绝对值

发现与变换前任意两数之差的绝对值模3是相同的

不妨假设最后需要的结果为, 那一定有, 即需要有, 对每种情况分别判断即可。

H.小F的圣诞树

I.优雅 太优雅了

题目意思即 讨论不等式 min(A[l],A[l + 1],....A[r − 1],A[r]) >= gcd(A[l],A[l + 1],....A[r − 1],A[r + 1]) 成立的条件 我们可以转换一下 求不成立的条件 首先我们知道 对于区间[l, r] min{A[l,...., r]} >= gcd({A[l,...., r]}) 肯定是成立的 那么 考虑变化的点 明显题目里面的区间gcd A[r] 换成了 A[r + 1] 讨论： 1、A[r] > A[r + 1] : 1） A[r + 1] > min{A[l],....,A[r - 1]} 那么明显 区间[l, ... , r - 1, r + 1]的最小值在 [l, ... r - 1]取得 故 gcd({A[l, ..., r - 1, r + 1]}) < min{A[l, .... , r - 1]} == min{A[l, .... , r - 1, r]} (因为A[r] > A[r + 1] [l,... ,r]最小值 所以也不会在A[r]处取得) 2）A[r + 1] < min{A[l], .... , A[r - 1]} 也就是说区间[l, .... , r - 1, r + 1] 的最小值在A[r + 1] 取得 => gcd({A[l, ..., r - 1, r + 1]}) < A[r + 1] < min{A[l], .... , A[r - 1]} 同时 A[r + 1] < A[r] 所以 gcd({A[l, ..., r - 1, r + 1]}) < A[r + 1] < min{A[l], .... , A[r - 1], A[r + 1]} 得证 2、A[r] <= A[r + 1] 对于不等式 min{A[l,...., r]} >= gcd({A[l,....r - 1, r + 1]}) 显然若是 A[r] 不是区间[l, r] 的最小值 即 A[r] > min{A[l,...., r - 1]} 而 min{A[l,...., r]} = min{A[l,...., r - 1]} >= gcd({A[l,....r - 1]}) >= gcd({A[l,....r - 1]}, A[r + 1]) 那么只需考虑A[r] == min{A[l,...., r]}的情况 那么原不等式等价于 A[r] >= gcd(A[l],A[l + 1],....A[r − 1],A[r + 1]) 当不等式右边的最大值 gcd(A[r - 1], A[r + 1]) > A[r] 的时候那么就是不等式不恒成立的情况出现了 即(l = r - 1) 这时候数组是rude A[r] > A[r + 1] 时 A[r] > gcd(A[r - 1], A[r + 1]) 恒成立 所以我们只需对每个A[i] 看是否存在 A[i] < gcd(A[i - 1], A[i + 1]) 若存在则输出 rude 若不存在则输出 elegant

J.逆序对

知识点：01字典树

对于这个式子是不好计数的

但是求或者都很好计算

可以考虑如何利用这两个式子

对于

令

肯定是如下形式： 即二进制下的高前位相同，高第位不同，且的为1，的为0 令 如果的高第位为0，那么 也就有 整理得，即所求式子

如果的高第为1，则可以整理得，对于答案就没有贡献

对于也可以类比分析出来，只有的高第为1才有贡献

使用01字典树以建树，同时在树上维护的数量和即可