大家好，这里是第一次参与造比赛工作的jiry_2..果然造UR是一件累死人的工作..

承蒙大家的厚爱，在UOJ一周年之际，参赛人数创历史新高啦owo

不过这次的UER好像造的有点偏难了（其实偏难的只有A题？）..非常抱歉，是我们在判断难度的时候出现了失误QAQ..下一场UER的时候我们会尽可能地把难度降下来的。

被删除的黑白树

By Starzxy

算法一

枚举每一种不同的染色并判断是否可行,时间复杂度 $O(n2^n)$。可以获得30分。(多良心！)

小插曲：很多人直接将度数=1作为判断是叶子的充分条件，这样会把根也算进去就wa掉了……良心的vfk强行让前30分的数据的根的度数大于1。

算法二

我们观察到若一个树的根到其所有叶节点的路径上的黑色节点数相同，那么对其任意一颗子树这个条件依然成立。

用 $F[i][j]$ 表示树第 $i$ 个节点到其所有叶节点都经过 $j$ 个黑色节点的方案中黑色节点数量的最大值。

那么

\begin{equation} F[i][j]=max(\sum_{k}F[k][j],\sum_{k}F[k][j-1]+1) \end{equation}

其中 $k$ 为节点 $i$ 的孩子。复杂度为 $O(n^2)$，可以获得60分。

算法三

原命题等价与求一颗满足要求的树使得白色节点数量最少。

结论1：若一棵树的根到其所有的叶节点上都经过白色节点，那么一定修其子树的染色方案，使得白色节点数量减小（最坏为数量不变）。具体策略为在dfs时碰到白色节点将其染成黑色并停止对其子树的dfs。

结论2：若一棵树到其最浅的叶节点上经过白色节点，那么根到所有的叶节点的路径上必然经过白色节点。因为该路径上黑色节点数量为(树的最浅叶节点深度-该路径上白色节点数量)，而对于其他叶节点，树的最浅叶节点深度$\le$该叶节点深度，又满其与最浅叶节点经过的黑点数量相等，则在这条路径上必然存在白色节点。

结论3：由结论1与结论2推得一棵满足要求的树到其最浅叶节点上不存在白色节点。

这样每次可以将根节点到其最浅叶节点上的路径中的节点全部染黑，并对剩下的子树的根依据要求看是否染白，之后递归处理即可。

仅需dfs时通过判断（该节点所在子树的最浅叶节点的深度-该节点到根上的白色节点数量>根的最浅叶节点的深度）来确定是否将其染白。

复杂度为 $O(n)$，可以获得100分。

AC代码在这

被粉碎的数字

by 绿色夹克衫

题解by C_SUNSHINE

Case 1~2

显然我们可以枚举 $ [1,R] $ 内每一个整数，对于每一个数字 $ x $ ，采用 $ log_{10}^x $ 的复杂度求出 $ f(x) $ ，同理求出 $ f(kx) $

时间复杂度 $ O(RlogR) $ ，期望得分 $ 20 $ 分。

Case 3~5

求 $ f(x) $ 的复杂度是 $ log(x) $ 的，我们来想办法把它优化到 $ O(1) $ 。有什么算法是 $ O(1) $ 的呢？

打表！接着发现数字范围可以到 $ 10^{12} $ ，于是我们可以打到 $ 10^6 $ 然后计算的时候可以写成 $ f(x)=w[x\%1000000]+w[x/1000000] $ 。

于是整个算法就 $ O(n) $ 了。

Case 6~7

考虑数位DP，这里边DP要边计算乘法，同时还要记录和 $ R $ 的大小关系，我们可以采用从低位到高位的数位DP。

$ f[x][r][s][t][c] $ 表示当前DP到了第 $ x $ 位，前面乘法的进位是 $ r $ ，当前 $ f(x) $ 的值为 $ s $ ， $ f(kx) $ 的值为 $ t $ ， $ c $ 表示当前位与 $ R $ 的关系，例如 $ 0 $ 表示小于等于， $ 1 $ 表示大于。

通过枚举当前位 $ i $ ，可以得到简单的转移：

$ x \rightarrow x+1，r \rightarrow (k*i+r)/10，s \rightarrow s+i，t \rightarrow t+(k*i+r)\%10，c \rightarrow 0(i < R_x),1(i > R_x),c(i=R_x) $

这样复杂度约为 $ 22*9*180*180*2 $ 应该是能跑出来 $ k < 10 $ 的。

Case 8~10

其实我们只是要求 $ s=t $ ，所以我们可以不必记录 $ s $ 和 $ t $ ，而直接记录 $ s-t $ 就可以了，这样复杂度大约是 $ 22*999*360*2 $ ，就可以AC了。

是不是一道很水的数位DP呢？

量子态的棋盘

by jiry_2

大家好这里是打杂的jiry_2 owo

这是我在UOJ上第二次出大暴力玄学题啦（上一道请见 UER#3 C）..感觉还是非常有趣的..

算法一

暴力枚举每一种可行的网格，然后暴力模拟每一次放入小球之后运行的过程。然后把每一个种网格接到的球记录下来拍一个顺序或者打一个表，每一次询问直接查询就好了。

时间复杂度 $O(K(n+m)2^{nm}+Q)$，期望得分20分。

算法二

后80分的 $K$ 的值都很大，所以可以先考虑这样一个子问题：如何快速判断一个网格可以接到多少个球。

可以发现在整个试验过程中，如果一个权值为1的格子被 $i$ 个球到达过，那么必定有 $\lceil \frac{i}{2} \rceil$ 个小球从它的右边界出去，有 $\lfloor \frac{i}{2} \rfloor$ 个小球从它的下边界出去。同理也可以得到权值为-1的情况。

而在这个问题中，我们只关注的是从某些边界运行出去的小球数量，而不在意具体是哪些小球。所以只要求出每一个格子被到达了多少次，就能得到答案。

具体来说，可以使用递推的方法来求解，令 $f_{i,j}$ 为在整个运行过程中第 $i$ 行第 $j$ 列被到达了多少次，$w_{i,j}$位第$i$个格子的权值，那么就有：

$$ f_{i,j}=\lfloor \frac{f_{i,j-1}+[w_{i,j-1}=1]}{2} \rfloor + \lfloor \frac{f_{i-1,j}+[w_{i-1,j}=-1]}{2} \rfloor $$

当然初值是 $f_{1,1}=K$。 这样通过一个简单的递推就能得到答案了。

结合算法一的暴力，时间复杂度 $O(nm2^{nm}+Q)$，期望得分40分。

算法三

对于后60分的数据范围，直接的 $2^{nm}$ 次的枚举已经无法承受，考虑简化状态。

可以从$K$入手，尝试在网格权值尚未确定的情况下进行递推，可以发现如果一个格子，有$i$个球到达了它，那么可以确定的是至少各有 $\lfloor \frac{i}{2} \rfloor$ 个球从右边界和下边界出去。只有当 $i \mod 2=1$ 的时候，才有唯一一个小球的运行轨迹和这个格子的权值有关。

那么我们先把能确定的进行递推，并用 $w_{i,j}$ 表示这个格子上是否有待定的小球，具体来说就是使用如下的递推：

$$ f_{i,j}=\lfloor \frac{f_{i,j-1}}{2} \rfloor + \lfloor \frac{f_{i-1,j}}{2} \rfloor $$

$$ w_{i,j}=f_{i,j} \mod 2 $$

在进行这样的预处理之后就得到了一个 $n \times m$ 的01表。这就意味着只有至多 $nm$ 个球我们不知道它能否被篮子接到，所以有解的球数至多只有 $nm$ 个，因此只需要对于每一个有解的值求出来有多少个满足条件的棋盘就好了，多组区间询问完全就是吓吓你的。

目前为止，我们只需要对一张01表求出有 $i$ 个球从指定位置运行出来的方案数。

考虑从左往右从上到下的轮廓线 DP，对于 DP 的每一个时刻，只有恰好 $n+1$ 条边在轮廓上。DP 的状态为：当前 DP 到的位置，通过每一条轮廓边从已知区域运行到未知区域的球的个数以及当前已经掉到篮子中的球的个数。只要枚举当前格子的权值就可以完成转移了。

假设每一个位置的状态数最多是 $S$，那么 DP 的复杂度就是 $O(nmS)$， 经过实践 $S$ 的数目不会超过 $5 \times 10^5$（实际上我只能造出来 $S$ 在 $2.7 \times 10^5$ 左右的数据）。

综上，这个算法的时间复杂度为 $O(nmS + Q)$，期望得分100分。

如果你没有写轮廓线 DP 而是直接枚举每一列的所有数的权值然后暴力转移，那么应该能得到60分。

如果你偷懒直接用了 map 或者转移的时候把通过每一条轮廓边的小球数目都拆出来了导致转移不是 $O(1)$，那么应该能得到80分。

当然因为时间紧迫部分分都是我瞎BB的，如果有人写部分分没有拿到上述的期望得分，请允许我做一个悲伤的表情。

关于复杂度

可能是因为我姿势水平比较低，对于状态的数量级，我只能分析到最简单的 $O(nm \frac{n^nn!}{2^n})$为止（当然这是远远达不到的）。如果有老司机能分析出更低的上界，欢迎来找我讨论owo

因为可能的输入有很多，所以我也不可能一个一个常数来计算 $S$ 的值取最大值。上面我瞎BB的上界 $5 \times 10^5$ 是以这种方式估算出来的：

显然的是状态数只与篮子的位置以及 $K$ 有关。更进一步地，$K$的影响只在它的后 $n+m-1$ 位的数值。因为当 $i \geq n+m$ 的时候，$2^{i}$ 这一位的贡献在最开始的递推中就已经全部离开了网格，对 $w$ 数组没有影响。

于是我在 $n=m=9$ ，所有位置都没有篮子时，枚举了所有可能的 $K$ 的后17位。这时得到的最多的状态数为15000左右。这意味着在所有情况下，$n=m=9$ 时的 $S$ 不会超过 $15000 \times nm$，所以在 $n=m=9$ 时我可以保证最大的状态数不会超过标程的承受范围。

而在打表的过程中，有几个值得注意的事实：

1.当$K$较大时（即不是1，2这种显然 $S$ 非常小的情况）$S$ 分布在一个较小的范围内。

2.枚举的过程中最大值很快便被达到。

所以在 $n=m=10$ 的时候，我随机了一个比较大的样本（差不多几万次）并统计出来了它们中的 $S$ 的最大值。这时 $S$ 最大为 $2.7 \times 10^5$ ，根据之前打表的结论，我估计实际上最大的 $S$ 不会超过它的两倍，即 $5 \times 10^5$。

当然，这个估计的方法的确也不是特别科学的样子，如果什么时候标程被叉掉了..

那就把数据范围改成 $n,m \leq 9$呗。