和以前的坑比起来这简直是一个看不见底的巨坑啊...

现在UR也进行了好几场了，做过UR之后再打CH的感觉就是UR的题目质量实在是感人肺腑（虽然常常被虐成狗

所以我自己也主观的希望不要浪费这么稳定的高质量题目来源（比起CF这个更贴近OI），争取以后每一场UR都把题目订正完。当然特别丧病的题为了我的人身安全我是不会去碰的。

现在做了几题

52

【UR#1 A】缩进优化 对值处理一个前缀和以及前缀出现次数暴力算就好了。总的时间复杂度是[tex]O(n \log n)[/tex]

【UR#1 B】外星人 [tex]dp_i[/tex]表示值为[tex]i[/tex]的方案数，当值变为[tex]i[/tex]后所有手指数目大于[tex]i[/tex]的外星人就没有贡献了，可以排列组合插到剩下的答案去，使得每一次dp只要考虑不大于[tex]i[/tex]的外星人就好了。

【UR#2 A】猪猪侠再战括号序列 对于取了就不合法的右括号，找到右边第一个左括号交换位置，这样交换的区间出了开头都变成了右括号，所以下一次找左括号可以从右端点后面开始找，这样就是[tex]O(n)[/tex]的了。

【UR#2 B】跳蚤公路 把每一个点拆成若干个点表示[tex]x[/tex]系数分别取不同的值，然后就可以先忽略[tex]x[/tex]，然后用bellman ford求出松弛[tex]n-1[/tex]次和松弛[tex]n[/tex]的最短距离数组，列出不等式组求解就好了。写起来意外的蛋疼，注意在求解一个点的时候要把能到达它的所有点的不等式也一起纳入计算。

【UR#2 C】树上GCD 策爷对GCD爱得深沉（雾）。把问题转化为权值为[tex]i[/tex]的倍数的路径有多少条。树分治，把LCA为重心和重心的父亲分开来考虑。LCA为重心很好计算，为重心的父亲的话对于每一个祖先深度为[tex]i[/tex]的所有孩子，枚举[tex]i[/tex]的约数[tex]d[/tex]，就相当于询问一个公差为[tex]d[/tex]的等差数列的权值和。这个可以对[tex]d \leq \sqrt n[/tex]记忆化一下，复杂度是[tex]O(n \sqrt n)[/tex]的。

【UR#3 A】核聚变反应强度 对[tex]a_1[/tex]分解质因数，然后对[tex]a_i[/tex]算一下最大公约数再除掉最小的公共质因数就好了。

【UR#3 B】铀仓库 显然每次取到的最右端和最左端至少有一端是被取完的。假设最左端是取完的，如果我们已经知道左端点的位置，那么就可以二分出右端点了。而随着出发点的右移最远左端点位置单调不降，于是就可以做到[tex]O(n \log n)[/tex]了。右端点就再做一遍就好了。

【UR#3 C】链式反应 就是解一个微分方程，具体做法还是看UOJ上的题解吧，一句话写不完。

【UR#4 A】元旦三侠的游戏 大于[tex]\sqrt n[/tex]可以直接用奇偶性判，其他直接记忆搜就好了。时间复杂度似乎是[tex]O(\sqrt n log^2 n)[/tex]？

【UR#4 B】元旦激光炮 三个数组一起二分，每一次求出中间值，如果中间下标之和要小于[tex]K[/tex]，那么就可以丢掉值最小的那个数组的前半段，否则可以丢掉值最大的那个数组的后半段。比赛的时候边界写残了> >

【UR#4 C】追击圣诞老人 这道题出的还是很好的。把每一个操作接下来能到达的点表示成一条链，每一次一定是取当前链的最小值或者把这条链从中间断开分别取两端的最小值（其实就是类似左儿子右兄弟的表示方式）。用树链剖分维护就好了，如果不预处理前缀和的话会被出题人卡成97分。

【UR#5 A】怎样提高智商 我自己能YY到的最优方法就是全部都是"A 0 0 0 0"，然后答案就是[tex]4 \times 3^{n-1}[/tex]。至于怎么证明还是去膜拜官方题解吧。

【UR#5 B】怎样更有力气 又在UOJ上出了一道最小生成树的题T^T其实就是把每一个操作拆分成很多个联通块，每一个联通块又可以拆分成一些边和一些树上的链，链和单独的边都是[tex]O(p+m)[/tex]的，可能被删成若干个联通块的操作总点数是[tex]O(p)[/tex]的，然后就直接大力就好了。（平均分比C还低是什么鬼。。

【UR#5 C】怎样跑得更快 感觉是最良心的一道C题了。而且即使推不出来也可以去搜JZPKIL啊。最后可以推出来[tex]b_i=i^d\sum_{D|i}\sum_{j=1}^n[d|j]j^d x_j \sum_{k|D} \mu(k) (\frac{D}{k})^{c-d}[/tex]，然后就可以一点一点推回去得到[tex]x[tex]了。

【goodbye jiawu A】新年的巧克力棒 打表大法好。证明还是看VFK的博客吧。

【goodbye jiawu B】新年的毒瘤 如果输入是一个连通图，一个点可以删除的充要条件是1.度数为[tex]m-n+1[/tex]。2.不是割点。注意特判一棵树加一个孤立点的情况。

【goodbye jiawu C】新年的桌游 首先红太狼肯定是直接丢出去的。美羊羊只能在开局如果可以直接赢的情况下丢出去。其他情况只能起到牵制出灰太狼数量的作用。此时最多一方有美羊羊，稍微判一下就好了。

【goodbye jiawu D】新年的QAQ 只要构造出一个有着极大正确率判断两个数是否相等的方法就好了，不难想到相减判是否是0。所以加减乘除的值都可以通过如下方式得到：给两个变量算这个表达式，如果相等就返回他们的值否则重新赋值。

【UR#6 A】破解密码 有趣的题目，开始VFK和我说这道题的时候，我也是愉快的FST了...坑点在于[tex]26^n \equiv 1\pmod{p}[/tex]，这个时候注意到只要满足了一个Hash值就满足了全部，只要把第一个Hash值用26进制表示就能构造了（我写起来感觉也没有什么难写的啊为什么会有那么多人想到坑点后写残呢）。

【UR#6 B】智商锁 出这道题的时候，虽然我自己也想到利用生成树个数近似随机来乱搞啥的，但是一直在尝试取指标把乘法变成加法然后走进了弯路...多亏了业界良心的策爷！大致的做法就是随机取1000张12个点的图然后用meet in middle拼出答案，对正确性大致的解释可以见UOJ题解。

【UR#6 C】懒癌 感觉这道题应该是我有生之年能出出来的最高能的题目了...从好几个礼拜前我就开始考虑出一道人和狗的题目，然后一直在考虑这个问题的各种变种什么的。大致的思路到最后就是转化成DAG中求能到达第[tex]i[/tex]个点的点的个数算贡献，至于这样转化为什么是对的可以见UOJ题解，那篇除了我有点语死早以外感觉写的还是挺详细的。

【UR#7 A】水题生成器 [tex]n[/tex]最大只有20，那就直接把所有能组成的数都找出来，每一次选一个最大的贪心取，至于为什么这是对的可以见UOJ题解。以上都是JRY在扯淡，刚刚才知道我的做法原来是乱搞。。虽然正确性是对的。感觉标算好神啊，把每一个数表示成[tex]\sum_{i=1}^n a_in^{\underline{i}}[/tex]的形式，可以得到[tex]0 \leq a_i < i[/tex]，显然每一项都是[tex]n![/tex]的约数。 

【UR#7 B】水题出题人 感觉UR的题做到现在，我最喜欢的是这道题（咦感觉用喜欢有点奇怪的样子）。别人家的构造题，比我这个半吊子出题人出的强到哪里去都不知道了呜呜呜。因为有六个task所以就不在博客里细讲了，题解见UOJ把。

【UR#7 C】水题走四方 这题本来是UR6的B！这题本来是UR6的B！这题本来是UR6的B！（因为很重要所以要说三遍）一个最初的思路就是把两个人同时在的点设为关键点，显然整个过程就是经过若干个关键点最后两个人同时走到叶子上。令[tex]f_i[/tex]为同时走到第[tex]i[/tex]个点的最优值，就可以得到一个比较显然的[tex]O(n^2)[/tex]的DP。然后因为这个转移有着一些比较好性质可以优化到[tex]O(n)[/tex]，主要的难点还是在最初得到正确的DP方程，所以优化就不细说了。

【UER#2 A】手机的生产 比赛前看题的时候还没有那么良心的样例解释...看懂题目花了好久。后来改了一下样例解释就变得能看了。大致就是统计每一个函数有多少种状态可以运行它，把每一段连续的and取出来一起处理就好了。

【UER#2 B】信息的交换 找找规律就可以发现给定的数组和图的DFS序的关系，统计不同的满足要求的DFS树可以用一个简单的区间DP来实现，然后每一棵DFS树对答案的贡献取决于可能的返祖边的数量，修改一下DP方程累加进答案即可。

【UER#2 C】谣言的传播 最小值很简单（为了方便我们不管环上的后继叫做儿子），对于一个有儿子的节点，把它设为它的儿子的终止节点，对于环上的没有儿子的节点，把它设为环上指向它的节点的终止节点，其它的叶子随便错排一下就可以得到一个理论最低的方案。而对于最大值的要求就要高很多，考虑用最小值的逆置换来得到最大值，这样就对最小值有了额外的要求，即最后错排的时候一个节点的终止节点不能再它的子树内，我们可以在DFS的时候用一个链表来表示子树中还没有被选为其他节点的终止节点的叶子，然后合并的时候从其他子树里pop一个出来当做终止节点就好了。

【UR#8 A】赴京赶考 先把序列都拓长一倍，然后把连续的0和1都合并到一起，可以发现两位坐标是可以分开的，所以距离就是它们两位坐标差的和。因为把序列都拓长了一倍，所以有挺多种对应的情况，应当都考虑到。

【UR#8 B】决战圆锥曲线 这道题也是出了挺久的吧..再回头看看真的和原来完全不一样了..只能说VFK大法好。因为最优答案只可能存在“台阶”的顶端上，即只可能存在于那些没有任何其它节点的横纵坐标都不小于（且至少有一个比它大）它的点。可以发现这样的点期望是[tex]O(\log n)[/tex]的，所以只要用类似kd tree的方法找到这些点就好了。

【UR#8 C】命运的多项式 把多项式表示成下降幂的形式，然后枚举第[tex]i[/tex]项系数膜[tex](n-i)![/tex]的余数就可以统计答案了..具体可以看UOJ上的题解..而且还有一个看起来比较鬼畜的优化来从90分进化到100分..然而因为JRY90分就被卡常数卡的不行..所以就弃疗了ww

【UR#9 A】电路手动分析 先二分答案，可以发现把点尽可能的排成正方形是最优的，于是就可以得到最优情况下下已经有了多少条边，然后比较一下就好了..要注意框的[tex]n \times m[/tex]的边界以及爆int和long long的情况。

【UR#9 B】App管理器 火车上看的这题..前60分时送的..然后我水平太渣根本不会后40分..想了一些乱搞做法然而都懒得写的样子也不知道会有多少分..膜了题解之后感觉好简单啊QAQ直接按照顺序枚举每一条边然后判断它变成哪种方向联通关系不会变，变成那个方向就好了..

【UER#3 A】开学前的作文 开始这题的标程还错了2333..开始直接用右+下的方式走到底然后一直用右走到右下角，这些操作大部分都是可以用[tex]F_n[/tex]代替的。

【UER#3 B】开学前的日历 挺有趣的题目，考虑每一次操作的具体意义，可以发现就是从一个给定点出发，每一次往右或往下走，把每一个距离超过给定值的点加上路径的方案数。想到这一点就非常方便递推了。

【UER#3 C】开学前的涂鸦 我出的题目..标算是缩图之后压连通性大DP..但是因为时间实在有点紧，没有把所有的暴力都写出来，然后定了一个比较小的数据范围导致被比较高端的算法搜过去咯..虽然我自己后来想吧数据范围加大但是vfk不让所以还是算了吧。

【UER#4 A】被删除的黑白树 当初被喷太难的题..然而感觉这题并不难啊QAQ用户老爷我们冤枉啊..显然最优解每一个叶子到根路径上的黑点个数等于最浅叶子的深度，而且黑点的深度越深♂越好，所以就直接一个DFS贪心就好了。

【UER#4 B】被粉碎的数字 一道简简单单的小清新数位DP题，状态记一下位数，进位，函数值和自变量的差以及大小关系随便转移就好了。

【UER#4 C】量子态的棋盘 我出的题目，改编自51nod上一道挺有趣的题。可以先把能够确定的球的走向用递推推出来，这样每一个每一个格子至多有一个球的离开位置是和这个格子的编号有关，这样就可以确定存在可行解的接到的球的数目最多只有[tex]nm[/tex]个，于是用一个大状压来计算就好了。

【UER#5 A】万圣节的南瓜灯 这题我数据造弱了真是抱歉QAQ可以发现有解的网格一定不会太大，所以对大小超过一定阈值的网格直接输出无解即可。对于其他的情况就可以直接DFS或者并查集来判断是不是一棵树。

【UER#5 B】万圣节的数列 挺有趣的题目，考虑用分治的做法来实现。如果一个数列存在一个分界线，左边全是奇数，右边全是偶数，那么肯定不存在一个等差数列跨过了这个分界线，所以就分治成了两个子问题。这样的分治有[tex]O(\log a_i)[/tex]层，所以直接暴力实现时间复杂度也还是[tex]O(n \log a_i)[/tex]的。

【UER#5 C】万圣节的糖果 一道有趣的计数题..然而我现在还是不知道myy是怎么容斥的。大致的就是可以在题目中要求计数的东西和一个更简单的问题之间建立起数量关系，因为一时也说不清楚所以还是推荐去看UOJ上的题解owo数学迷提供的解释还是非常优美的。

【UR#10 A】汉诺塔 非常小清新的一道题，随便分治一波就行了。

【UR#10 B】世界线 非常有趣的一道题，大致的思想就是把所有位置排成阶梯状的东西，然后第一次询问可以询问出行号，第二次询问可以询问出列号，这样就能在[tex]O(n \sqrt n)[/tex]的时间内确定一个点的坐标从而得到答案，然而处理多出来的部分的方法比较麻烦，我的做法是在第二次询问的时候把多出来的部分放到后若干列的顶上。

【UR#10 C】列队 非常鬼畜的一道抽代题，当初为了搞清楚这题我还突击学习了一个礼拜的抽代..虽然现在都忘光咯。反正就是有一个柿子，然后根据定义随便瞎写一波然后暴力容斥递归子问题就好了。

【UR#11 A】元旦老人与汉诺塔 我出的一道小清新题，其实只要发现能够被移动的圆盘只有最顶上的几个，就能想到强上记忆搜了。

【UR#11 B】元旦老人与丛林 一道挺有趣的题目，有一个结论是一张图是丛林当且仅当对每一个子图都有边数小于等于点数的两倍-2，证明稍微有点复杂。然后就转化成了最大权闭合子图的问题，因为权可能为负，所以需要退流的方法来降低网络流次数。

【UR#11 C】元旦老人与数列 用我营员交流的方法出出来的大水题，不过在营员交流之前应该算是难题了。题解可以看乐滋滋和我的营员交流课件。

【goodbye yiwei A】新年的破栈 非常小清新的送分题，直接贪一波就好了。

【goodbye yiwei B】新年的网警 猜结论题，不过结论也挺好猜的，要注意因为初始时刻未知，所以只认识一个人的人以及认识一个这样的人的人也是安全的。然后hash一下就能A啦。

【goodbye yiwei C】新年的繁荣 原来的版本权值范围很大，那感觉就很鬼畜了..现在把权值范围改小了感觉小清新了许多。可以进行若干轮，每一轮都查找出每一个联通块到其他联通块的最大边，把这些边连上跑一次最大生成树，这样联通块个数一定能除以二。重复[tex]\log n[/tex]轮就行了。查找最大边可以用基本的子集和变换来做到。

【goodbye yiwei D】新年的腮雷 非常有趣的一道题，先二分答案，然后就能贪心一波啦...相当于现在你手上有一个数集[tex]S[/tex]和一个腮雷集合[tex]T[/tex]，你需要进行若干次这样的过程：选[tex]S[/tex]中的一个数然后拆分，把拆分得到的数加入[tex]S[/tex]中并删除原数，最后使得两个集合排序后[tex]S[/tex]的每个数都不小于相应位置的[tex]T[/tex]中的数。贪心的方法是每次找两个集合最大的数，如果拆了最大的数后[tex]S[/tex]中最大数依然不小于[tex]T[/tex]中的最大数，那就直接拆，否则就挑一个最小的和[tex]T[/tex]中最大数匹配。

【goodbye yiwei E】新年的贺电 也是一道非常有趣（毒）的题。开始自己YY了好几个做法但是都非常萎的样子...再加上这个评分标准一副“卡的就是你的常数”的样子，所以就取膜了题解。第一步还是非常容易想的，把所有值给hash到一个非常小的范围，但是这个hash函数非常难找。题解中的方法是每一次把当前集合给均匀的hash成两个部分，然后传的时候不传hash函数，而是传为了得到这个hash函数随机的次数，这样只要统一了随机方法，就能解码了。然后第二个黑科技就是传不等长的数字（这个还是比较好想的），对于一个数，编码方和解码方约定一个标准长度[tex]lim[/tex]，然后如果实际长度没有超过[tex]lim[/tex]，就在这个数之前加一个1再发，否则如果超过[tex]k[/tex]，就先发[tex]k[/tex]个0，然后再发1，最后发这个数。最后一个黑科技是当随机区间很小的时候，可以直接随机一个hash函数一步到位，这样可以避免冗余的信息。用上这几个方法就能A啦。