2017 CERC

Problem A:Assignment Algorithm

题目描述：按照规则安排在飞机上的座位。

solution
模拟。

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

Problem B:Buffalo Barricades

题目描述：将二维平面划分为一个个单位格，在平面上有一些被标记的格子。将(x,y)轴当成是围栏，现在以此给出一些坐标，每次从那个坐标出发向(x, y)轴建围栏，并输出新围栏围住的被标记格子数。

solution
待解决。

C:Cumulative Code

题目描述：给出一棵深度为(K)的满二叉树，逐层从左到右编号，然后写出满二叉树的prufer code(假设为(P)序列)。prufer code：每次选择一个编号最小的叶子节点，然后记录它的邻居编号，再把这个叶子节点删去，重复操作，直至只剩下两个节点。记录下来的编号序列就是prufer code。现在有(q)个询问，每次询问有三个参数(a, d, m)，表示求(P_a, P_{a+d}, ... , P_{a+(m-1)d})的和。

solution
将子树分成两类。
(A)：

这类子树是先移除左子树，再移除右子树，最后移除根。

(B)：

这类子树是先移除左子树，再移除根，最后移除右子树。

先分析(A)类子树，(B)类子树做法类似。

设(f_x(k))，表示根为(x)的子树深度为(k)(只有(x)时深度为(1))的prufer code和。则
(f_x(1)=x/2)
(f_x(2)=2x+x/2)
(f_x(3)=10x+2+x/2)
设(f_x(k)=a_k cdot x+ b_k + c_k cdot (x/2))
则
(f_x(k)=f_{2x}(k-1)+f_{2x+1}(k-1)+x/2)
(=a_{k-1} cdot 2x +b_{k-1}+c_{k-1} cdot x + a_{k-1}(2x+1) +b_{k-1}+c_{k-1} cdot x +x/2)
(=(4a_{k-1}+2c_{k-1})x+(a_{k-1}+2b_{k-1}) + x/2)
( herefore a_k=4a_{k-1}+2c_{k-1}, b_k=a_{k-1}+2b_{k-1}, c_k=1)
设(Q={a, a+d, ..., a+(m-1)d}), (next_{Q}(i))表示(Q)序列内大于等于(i)的最小编号。
设(g_x(k, i))表示以(x)为根，深度为(k)的子树，在对该子树进行操作前已有(i)个prufer code(原树的)，在(Q)中的(P)和。按照类似(f_x(k))的记录方式，同样也可以如此记录(g_x(k, i))。则
(g_x(k, i)=g_{2x}(k-1, i)+g_{2x+1}(k-1, i+2^{k-1}-1)+((i+2^k-1) in Q) cdot (x/2))
加快(g)的递归计算。

如果([i+1, i+2^k-1])中没有在(Q)中的编号，则直接返回
记忆化一些状态：当(k leq K/2)且([i+1, i+2^k-1] in [a, a+(m-1)d])时进行记忆化，记忆化的关键字为((k, next_Q(i)-i))

由于有条件(1)，所以(next_Q(i) leq i+2^k-1)，所以最多有(2^{K/2})种状态需要记忆化。
剩下还有几种情况：

(B)类树，但(B)类树最多计算(K)次
当(k>K/2)时，这里会调用(2^K)次。
([i+1, i+2^k-1])与([a, a+(m-1)d])相交，但([i+1, i+2^k-1])不在([a, a+(m-1)d])内，这种情况最多有(K)次。
所以每个询问的时间复杂度为(O(2^{K/2}))

时间复杂度：(O(2^{K/2}q))

Problem D:Donut Drone

题目描述：有一个(r imes c)的网格，每个格子有一个整数。现在从第一列的指定一格出发，每次移动一步是这样的：选择右边相邻一列的相邻三个格子（右上，右，右下）中整数最大的格子。第一列与第(c)列是相邻的，第一行与第(r)行也是相邻的。现在有两种操作：1、移动(k)步，输出移动后的坐标。2、修改某个格子的数字。

solution
预处理出(jump[row])表示从第一列的第(row)行出发，移动(c)步回到第一列的第(jump[row])行。这样就可以(O(1))移动(c)步，根据鸽巢原理，(jump[row])是一个环，所以(O(r))能完成任意步的移动。
问题在于操作2。通过观察，可以得知第一列能走到((x, y))的行是一个连续区间，而且修改某个格子的值只会影响左边三个格子的走向，即另外形成三条路径，这几条路径可以暴力跑一遍，然后暴力修改那个连续区间的(jump[row])值。

时间复杂度：(O(r+c))每次询问。

Problem E:Embedding Enumeration

题目描述：给出一棵树，有(n)个节点，(1)为树根。现在要将这棵树放在一个(2 imes n)的网格中，每个格子放一个节点，树上相邻的点要放在相邻的格子，(1)号点要放在左上角的格子，问有多少种放置方法。

solution
首先可以确定这棵树是一个二叉树，否则无解。
(f(x, delta))表示只剩下(x)的子树（不含(x)）还没放置，(x)放置的那一行放得比另一行长，长(delta)格的方案数。
现分情况讨论：

(x)没有儿子，则找到一种可行方案。
(x)有一个儿子(y)，
1. (y)可以放在(x)的右边，转移状态至(f(y, delta+1));
2. 也可以放在下面。
  1. 若(y)的一个儿子(z)要放在(y)的左边，则(z)只能是一条长度不超过(delta-1)的链。
  2. 若(y)的一个儿子(v)放在(y)的右边，则转移状态至(f(v, 1))。
(x)有两个儿子(y, u)，(y)有一个儿子(v)放在(y)的右边。这样(u, v)的子树都还没有放置，也只能沿着自己所在那行一直延伸，直至某一行不能延伸，设另一行延伸到(w)，则转移状态至(f(w, 1))

接下来就是想办法把(delta)省掉，具体方法是注意如果将(f(x, 2))视为(f(x, 1))，会算漏什么。具体还没实现。。。

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

Problem F:Faulty Factorial

题目描述：将(n)的阶乘中的一个数(x)换成比它小的数(y>0)，使得换了之后的乘积模(p)(质数)等于(r)。

solution
分情况讨论：

(n geq 2p)。如果(r eq 0)，则无解，否则将(p)变成(1)即可。
(2p > n geq p)。如果(r==0)，则将一个非(p)的数变成(1)即可，注意：当(n==p==2)时无解。若(r eq 0)，则将(p)变成另一个数，枚举一下就好。
(p>n)。(frac{M}{x} y equiv r mod(p), M=n! mod (p)), 则(y equiv rx cdot inv(M) mod (p))。枚举(x)，求对应的(y)，求出一个可行解即可，否则无解。

时间复杂度：(O(p))

Problem G:Gambling Guide

题目描述：给出一个(n)个点(m)条边的无向图，现在从(1)号点出发到(n)号点，假设现在在(i)号点，然后买票，但买到的票是随机的，即这张票通向的是(i)号点相邻点的随机一个，买到的票可以不立刻用，也可以不用。问需要期望买多少张票能从(1)号点到(n)号点。

solution
设(f(x))为从(x)号点到(n)号点的期望买票数。按照最优策略，当买到去(y)的票时（(y)为(x)的邻居），若(f(y)<f(x))，则移动到(y)，否则不动。
现在只知道(f(n)=0)。假设(f(x))已知的集合为(S)，初始时(S=) { (n) }，然后按(f(x))递增的顺序添加点进(S)。考虑那些不在(S)中，但有邻居在(S)的点(x)，则

[f'(x)=1+sum_{neighbour_y in S} frac{f(y)}{degree(x)} + sum_{neighbour_y otin S} frac{f'(x)}{degree(x)} ]

[f'(x)=frac{degree(x)+sum_{neighbour_y in S} f(y)}{degree(x)-sum_{neighbour_y otin S} 1} ]

选择(f'(x))最小的点添加到(S)，(f(x)=f'(x))。
这个过程与Dijkstra很像，所以可以按照Dijkstra的实现方法来实现。

时间复杂度：(O(mlogn))

Problem H:Hidden Hierarchy

题目描述：给出一些文件的大小，按规则展开目录，输出目录树

solution
模拟

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

Problem I:Intrinsic Interval

题目描述：给定一个(n)排列(P)。若排列中([x, y])的数从小到大排序后是连续的，则称它是一个好区间。现有(m)个询问((a, b))，问包含((a, b))的最小好区间是哪一个。

solution
离线处理，分治。假设现在处理的询问都包含在([L, R])中，设(mid=frac{L+R}{2})。然后将包含在([L, mid], [mid+1, R])的区间分治处理。剩下的就是包含([mid, mid+1])的询问，然后找出包含([mid, mid+1])的所有好区间，用这些好区间更新询问的答案。

时间复杂度：(O(n(logn)^2))

Problem J:Justified Jungle

题目描述：给定一个有(n)个节点的数，找出所有的整数(k)，满足在树上删掉(k)条边后，形成的每棵树的节点数相同。

solution
首先，(k+1)一定是(n)的因数。随意找一个点做根，求出每棵子树的大小。如果某一个(k)是答案，则子树大小是(frac{n}{k+1})的倍数的个数应该是(k+1)。可以证明这是充要条件。

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

Problem K:Kitchen Knobs

题目描述：有(n)个转盘，每个转盘在边缘上均等写着(7)个数字（(1)~(9)），现在每次可以选定一个区间([L, R])，将区间内的转盘顺时针同时转动若干次，使得最终每个转盘表示的数字最大（转盘表示的数字为：转盘指向的数字为七位数的最高位，然后顺时针依次连接），问应该选择多少个区间（输出次数即可）

solution
以下的讨论都是基于模(7)的情况。
首先观察可得，每个转盘转动次数要么是确定的，要么怎么转都可以。所以可以假设只有(n)个转动次数确定的转盘，每个转盘的转动次数为(a_i)。问题转化为每次选择一个区间加上一个相同的数，使得最终(a_i=0)
设(b_i=a_i-a_{i-1})，将区间操作转化为点操作。将(b_i)分成尽量多的组，使得每一组的和等于(0)，原题的答案等于(n)-组数。因为将某一组(b_i)全变为(0)的次数为该组中的个数减一。
问题就转化为将(b_i)分成尽量多的组，使得每一组的和等于(0)。
首先将每个(0)归为一组，然后(1, 6;2, 5;3, 4)匹配，最终只剩下最多三种不同的数字，然后用(dp)算出答案。(f[i][j][k])表示每种数剩下多少个分得的最多组数。

时间复杂度：(O(n^3))

Problem L:Lunar Landscape

题目描述：在二维平面上有(n)个正方形，这(n)个正方形的中心的坐标和顶点的坐标都是整数，而且这些正方形的边要么与(xy)轴平行，要么成(45^{circ})。问正方形覆盖的面积。

solution
将平面上的每个格子用对角线分成(4)格，将两种正方形分别进行二维部分和，然后将部分和合并。

时间复杂度：(O(平面大小))