大家好,这里是第一次参与造比赛工作的jiry_2..果然造UR是一件累死人的工作..
承蒙大家的厚爱,在UOJ一周年之际,参赛人数创历史新高啦owo
不过这次的UER好像造的有点偏难了(其实偏难的只有A题?)..非常抱歉,是我们在判断难度的时候出现了失误QAQ..下一场UER的时候我们会尽可能地把难度降下来的。
被删除的黑白树
By Starzxy
算法一
枚举每一种不同的染色并判断是否可行,时间复杂度
小插曲:很多人直接将度数=1作为判断是叶子的充分条件,这样会把根也算进去就wa掉了……良心的vfk强行让前30分的数据的根的度数大于1。
算法二
我们观察到若一个树的根到其所有叶节点的路径上的黑色节点数相同,那么对其任意一颗子树这个条件依然成立。
用
那么
其中
算法三
原命题等价与求一颗满足要求的树使得白色节点数量最少。
结论1:若一棵树的根到其所有的叶节点上都经过白色节点,那么一定修其子树的染色方案,使得白色节点数量减小(最坏为数量不变)。具体策略为在dfs时碰到白色节点将其染成黑色并停止对其子树的dfs。
结论2:若一棵树到其最浅的叶节点上经过白色节点,那么根到所有的叶节点的路径上必然经过白色节点。因为该路径上黑色节点数量为(树的最浅叶节点深度-该路径上白色节点数量),而对于其他叶节点,树的最浅叶节点深度
结论3:由结论1与结论2推得一棵满足要求的树到其最浅叶节点上不存在白色节点。
这样每次可以将根节点到其最浅叶节点上的路径中的节点全部染黑,并对剩下的子树的根依据要求看是否染白,之后递归处理即可。
仅需dfs时通过判断(该节点所在子树的最浅叶节点的深度-该节点到根上的白色节点数量>根的最浅叶节点的深度)来确定是否将其染白。
复杂度为
被粉碎的数字
by 绿色夹克衫
题解by C_SUNSHINE
Case 1~2
显然我们可以枚举
时间复杂度
Case 3~5
求
打表!接着发现数字范围可以到
于是整个算法就
Case 6~7
考虑数位DP,这里边DP要边计算乘法,同时还要记录和
通过枚举当前位
这样复杂度约为
Case 8~10
其实我们只是要求
是不是一道很水的数位DP呢?
量子态的棋盘
by jiry_2
大家好这里是打杂的jiry_2 owo
这是我在UOJ上第二次出大暴力玄学题啦(上一道请见 UER#3 C)..感觉还是非常有趣的..
算法一
暴力枚举每一种可行的网格,然后暴力模拟每一次放入小球之后运行的过程。然后把每一个种网格接到的球记录下来拍一个顺序或者打一个表,每一次询问直接查询就好了。
时间复杂度
算法二
后80分的
可以发现在整个试验过程中,如果一个权值为1的格子被
而在这个问题中,我们只关注的是从某些边界运行出去的小球数量,而不在意具体是哪些小球。所以只要求出每一个格子被到达了多少次,就能得到答案。
具体来说,可以使用递推的方法来求解,令
当然初值是
结合算法一的暴力,时间复杂度
算法三
对于后60分的数据范围,直接的
可以从
那么我们先把能确定的进行递推,并用
在进行这样的预处理之后就得到了一个
目前为止,我们只需要对一张01表求出有
考虑从左往右从上到下的轮廓线 DP,对于 DP 的每一个时刻,只有恰好
假设每一个位置的状态数最多是
综上,这个算法的时间复杂度为
如果你没有写轮廓线 DP 而是直接枚举每一列的所有数的权值然后暴力转移,那么应该能得到60分。
如果你偷懒直接用了 map 或者转移的时候把通过每一条轮廓边的小球数目都拆出来了导致转移不是
当然因为时间紧迫部分分都是我瞎BB的,如果有人写部分分没有拿到上述的期望得分,请允许我做一个悲伤的表情。
关于复杂度
可能是因为我姿势水平比较低,对于状态的数量级,我只能分析到最简单的
因为可能的输入有很多,所以我也不可能一个一个常数来计算
显然的是状态数只与篮子的位置以及
于是我在
而在打表的过程中,有几个值得注意的事实:
1.当
2.枚举的过程中最大值很快便被达到。
所以在
当然,这个估计的方法的确也不是特别科学的样子,如果什么时候标程被叉掉了..
那就把数据范围改成