2014 ACM/ICPC Asia Regional Xi'an Online

FD大法好!买买买！

买买买！索尼大法好！每个需要识别的串长度最长只有6，暴力就好啦。

在线询问给定字符串的字典序第K小的子串，需要去重，相同输出左边界最小的。用后缀数组来做最好理解，排好序后每个后缀对子串的贡献为$|S|-sa[i]-height[i]$。就可以用二分来定位子串在哪以及长度$len$。

但对于相同的还要输出最靠左的，如果找到的子串的位置并不是$sa[i]$最小的，更小的只可能出现在$i$位置的下面。所以再进行一次二分，找到LCP为$len$能伸到的最大后缀，再区间取$sa[]$的$min$。

有一段序列，涂连续一段子序列的代价为该子序列出现不同数字个数的平方，求最小代价涂完整个序列。

朴素的$O(n^2)$动态规划很明显，发现答案的上界是序列的长度，所以每个状态可转移的位置只有$O(\sqrt{n})$个，可以把DP优化为$O(n\sqrt{n})$的时间复杂度。

华丽的爆搜题。

空格最多只有32个，动物最多只有5只是关键。每个动物就可以用6位bits记录状态（位置5位，是否存活1位）。正好30位，用int可以存。然后就可以hash一下来BFS了，有效状态很少。

暴力出SG函数后找规律。

人肉出4种翻转的置换，就可以BFS啦。

设$F(i,j)$为现在都在$i$号景点，剩下人的集合为j的期望。只需枚举$j$的子集$k$，乘上对应的概率从$F(i+1,k)+$baliliba转移来。但这样是$O(n3^m)$的。

分析转移方程，发现可以省去枚举子集的过程，用一个$O(m2^m)$的DP可以预处理两个量的子集和。复杂度优化为$O(nm2^m)$。

有个trivial的是$p$可以为1，而转移方程有$\frac{1}{1-p}$这种东西，为了避免特判可以将等于1的$p$都减一个eps……

每个数都能找到一个数拼成$2^k-1$，从大到小贪心的构造。

每一列的数都是上一列的数字与1的线性组合。矩阵乘法+快速幂优化递推。

先做一次最短路，求出每个点被哪个点控制，记为二元组$D[]$。假设在$x$点建超市，能控制的节点$y$必须满足$pair(dis(x,y) , x) < D[y]$。需要计算每个点建立超市可以控制的节点数量。

这是一个用树点分治可以解决的问题，确立了根节点后，两个不同子树节点间的距离就是根到两个节点的距离和，所以很好统计。

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

因为原点一定在椭球里面，所以猜$x^2+y^2+z^2$是单峰的。所以先三分一个$x$，再三分一个$y$，就可以解出$z$，取$|z|$小的那一个。无解的情况返回1e10，为了保证函数是单峰的，又在1e10上面加了个$x^2+y^2$，这样估计就没问题了，三分的左右边界可以尽情设大。