2018 ICPC 徐州网络赛

A. Hard to prepare

题目描述：\(n\)个数围成一个环，每个数是\(0\)~\(2^k-1\)，相邻两个数的同或值不为零，问方案数。

solution
将环变成链，设\(f[i][0\)~\(2]\)，分别表示与第一个数相同，与第一个数不同，与第一个数相同，与第一个数的反相同。然后\(dp\)即可。

时间复杂度：\(O(n)\)

B. BE, GE or NE

solution
根据题目描述\(dp\)即可。

时间复杂度：\(O(nm)\)

C. Cacti Lottery

题目描述：有一个九宫格，里面是\(1\)~\(9\)，有些数字是知道的，有些是别人知道你不知道，有些是双方都不知道。现在别人从九宫格中选择一行或一列或对角线，得到的分数为选择的格子的和对应的分数，别人会使这个分数尽量大，问期望值。

solution
枚举九宫格的所有情况，对于别人来说，他一定会选择八种情况中期望值最大的，所以记录每种他知道的情况对应的最大期望值，然后再求总的期望值。

时间复杂度：\(O(9! \cdot 8)\)

D. Easy Math

题目描述：给定\(n, m\)，求\(\sum_{i=1}^{m} \mu(in)\)

solution
\[ \sum_{i=1}^{m} \mu(in) \]
\[ =\mu(n) \sum_{i=1}^{m} [gcd(i, n)==1] \mu(i) \]
\[ =\mu(n) \sum_{d|n} \mu(d) (\sum_{x=1}^{m/d} \mu(xd)) \]
括号内的式子是一个子问题。\(m'=m/d, n'=d\)，当\(n'=1\)时，就是一个求\(\mu\)的前缀和的问题，有杜教筛就可以求解。

时间复杂度：\(O(能过)\)

F. Features Track

题目描述：求一个数对连续出现次数的最大值。

solution
排序，计数。

时间复杂度：\(O(nlogn)\)

G. Trace

题目描述：依次给出\(n\)个内部不透明的矩形，矩形在第一象限且紧贴坐标轴，问能看到的边的总长。（矩形没有包含关系）

solution
将\(x, y\)边分开处理。对于\(x\)边，将边按\(x\)从小到大排序，那么他们的长度是递减的。对于第\(i\)条边，用set算出时间比\(i\)小的有多少条，那么这些边的贡献都要减去\(i\)的长度，然后删掉这些边，把\(i\)加进去，算上\(i\)的长度贡献。\(y\)边也一样。

时间复杂度：\(O(nlogn)\)

H. Ryuji doesn't want to study

题目描述：有一个序列，两种操作：1. 给定区间\([L, R]\)求，\(\sum_{i=L}^{R} a[i](R-i+1)\) 2. 改变某个数的值。

solution
线段树，树状数组都可以维护。

时间复杂度：\(O(nlogn)\)

I. Characters with Hash

solution
模拟。

J. Maze Designer

题目描述：有一个\(n \times m\)的网格图，网格边上有权值，表示在这条边建一堵墙的花费，现在要在一些边建墙，使得任意两个格子有且只有一条简单路径，而且花费最小，然后有若干个询问，询问某两个格子之间的距离。

solution
最小生成树+LCA查询树上两点间的距离。

时间复杂度：\(O(nlogn)\)

K. Morgana Net

题目描述：求一个特定的二维卷积。

solution
可以将原矩阵变成一个一维向量，根据\(B\)矩阵求转换矩阵，定义乘法为与操作，加法为异或操作。用矩阵快速幂即可求解。

时间复杂度：\(O(n^6logt)\)