600大洋飘走了~ 并不能奖金回本QwQ

update:16.06.29

热身赛

A Prime

感觉随便搜搜就行，用对数判断大小

剪枝：质因数次数要非增序列

加了这个就能AC了（当然还有其他剪枝

B Colorado Potato Beetle

离散化一发后种子染色

C Distinct Paths

一开始想DP，然后并不会做

正解暴力，搜出一个合法解然后排列组合对应一下即可

#1 乐滋滋

A 奥义商店

技巧题，修改直接修改，询问则需要讨论下

对于 $T=1$ 的情况我们对公差分类讨论，$d$ 小的话可以先预处理出来然后在修改的时候顺带修改，$d$ 大的时候直接暴力找出所有数即可

对于 $T>1$ 的情况我们直接暴力求出每个数被选上的概率，当其小于 eps 的时候就无需继续枚举了

B 访问计划

假如没跳跃的话所有边都会被遍历两次，有跳跃的话相当于用若干条经过不重复边的路径覆盖权值和最大的边

这个有两种做法，每次 dp 求直径并将直径上的边取反，重复 $K$ 次；或者设 $f(i,j,a)$ 表示点 i 的子树已经用了 j 条路径的方案数（a 是指点 i 上面有没有出边）然后每个节点做背包，复杂度都是 $O(n^2)$

C 模范学长

设行列式为 $A$，则 $|A|$ 很明显也是多项式，题目要我们求 $|A|$ 在模2意义下是否为0

由 Schwartz-Zippel 定理可得我们每次判定可以随机给变量扔一个值，然后判断行列式是否为0，若不为0则一定不是

我们需要找到一个有限域，满足 $|F|$ 足够大而且 $x+x=0$（因为在模2意义下）

模素数域下只有 ${0,1}$ 这个模2剩余系满足第二个要求，但是太小

考虑多项式环（可以理解成模多项式剩余系）设这个多项式的最高次数为 $t$，则其模2意义的剩余系中的元素个数为 $2^t$（可以理解成全部元素的次数小于 $t-1$ 且系数为0或1）当 $t=30$ 的时候就够了

我们还能用二进制压缩多项式运算，因为模2意义所以只需要xor就行

最后求行列式值不能有除法，所以 $(A_{j,k}←A_{j,k}A_{i,i}-A_{i,k}A_{j,i})$ 

#2 小火车

A 深邃

二分答案然后贪心扫一遍就可以了

B 黑暗

法1：$O(n^3)$ 推出 n 个点 a 个联通块的方案数

法2：由二项式定理推出 $O(n^2m)$ 的公式：

$$F(n,m)=\sum_{i=1}^n g(i)C(n-1,i-1) \sum_{j=0}^m C(m,j)F(n-i,j)$$

其中 $g(i)$ 表示 i 个点的联通图个数，这个可以通过枚举第一个点所在联通块去容斥得到，$O(n^2)$ 复杂度

法3：$n^m=\sum_i S(m,i)C(n,i)i!$

然后原式变成枚举由 $i$ 个点构成 $k$ 个联通块乘上包含其的方案数

$$F_{n,m}=\sum_i \sum_k H_{i,k}C(n,i)h_{n-i}S(m,k)k!$$

其中 $H_{i,k}$ 表示 $i$ 个点构成 $k$ 个联通块的方案数，$h_n$ 表示 $n$ 个点的方案数

设 $G_{n,k}=\sum_i H_{i,k}C(n,i)h_{n-i}$

$H_{?,?}$ 能由 $H_{1,?}$ 通过分治FFT得到，$H_{1,?}$ 能通过分治FFT得到，$G_{n,k}$ 能通过分治 FFT 得到，$F_{n,m}$ 能通过 $O(m)$ 得到。。

C 幻想

后缀平衡树可以处理添加和删除，每个节点多维护一个 vector 储存当前子树叶子，按从小到大排，可以使用归并排序暴力重构，询问的时候在平衡树上找到相应节点再二分找区间即可

#3 洲鸽

A 哈夫曼树

算出每个数每次被选中的概率（其实不同数的概率是一样的）乘上方案数即是答案

B 线段树

操作类似于区间修改，当 $[a,b]$ 后于 $[c,d]$ 且其有交集，则 $[a,b]$ 的值为其并集的最大值

所以对于一个点我们可以找最晚覆盖它的操作，然后往左右找其并集区间，最后区间最大值

在线可以用持久化线段树，离线则不用持久化

C 接水问题

A*解决第K优解，但是难在记录状态（暴力的话 $O(nk)$ 的空间复杂度）和转移（一次可以产生 $O(n^2)$，转移可以用(u,v)表示将第 u 位的往左移动 v 位）

用可持久化线段树维护序列本身和相邻差（用来新建一个选取最优转移的持久化线段树），每次选取所有已创建的状态的最优转移（这里搞个全局线段树），将其 v 加1，维护此状态的转移信息的线段树，然后从之前通过相同的 u 且 v 相差1的转移得到的状态得到新状态的维护序列的线段树……

无力口胡……具体看题解吧……

#4

A Zbox loves ants

首先碰撞看成穿越即可，然后就枚举最大值看方案数即可

B Zbox loves stack

离线，从左到右考虑询问的点，每个点用线段树维护其数量的折线图，查找后缀第一次到达 k 的时刻

C Zbox loves meizi

每次割中间，然后找最大值，再判断最大值是否高过两旁，不符合的话找左右两边的最大值进行递归，次数最多6000次询问

#5 Claris

A 二进制的世界

首先你可以用可持久化 Trie 来维护之前的数的二进制，然后直接贪心查询，对于 xor 比较容易，对于 and/or 就要用线段树合并左右子树

或者，设 $F[a,b]$ 表示前者的首 8 位为 $a$ 后者的末 8 位为 $b$ 时前者末 8 位和后者末 8 位的最大操作值

询问的话枚举 $a$，修改的话枚举 $b$ 即可

B 可持久化字符串

相当于 KMP 持久化，由于 KMP 的 $O(n)$ 是均摊复杂度，持久化会破坏复杂度分析，所以我们用持久化线段树来加速一下找当前新增节点的 Fail 边

C 反函数

点分治完用 FFT 统计下合法路径条数

#6 厨师

A 回合游戏

首先边的价值要平摊到两点中，然后维护所有点和奇偶位的价值和

B 运河计划

由 Lindström–Gessel–Viennot 定理可得我们需要做个行列式，对于给定起点种点求不经过障碍点的路径个数我们可以再容斥一发，用总数减去枚举第一个遇到的障碍的路径个数

C 陨石坠落

题解？拒绝！

#7

A 人生的经验

把字符看成 0..n，填入 l-1 个 0 然后其余的按字典序最大查找，本地 while 递归即可

l=1 的时候特判

B 基因改造计划

Manacher 后对于奇偶左右建四棵主席树，询问可拆解成四棵树的询问（设中点为 x 且是第 y 小的回文串为在左右两棵树中对应为 x+y 和 x-y）

C 建造记者站

【BZOJ 1835】

#9 叉姐

A Kmp

用并查集维护相等的字符，不等关系则将联通块相连，可以证明新增的联通块能选取颜色数等于颜色总数减去一开始相连的联通块数

B 异或

维护线性基，设基个数为 C，有两种做法 $O(2^C)$ 和 $O(C^22^{n-C})$，不同的 C 取最优即可

最后感谢众多神犇，感谢 BZOJ 给我这个比赛的机会，感谢 QQ 这个开黑平台，感谢 QwX 交易队的无私帮助，感谢屁股学习使我有了动力

谢谢大家！（鞠躬

Upd: YJQ 是最强的！Orz%%%