感觉UOJ的题目还是不错的，只不过以前没有好好重视。比赛也因为各种时间关系没有打。如果有时间的话还是做一做比较好。
现在做了几道：
9
【UTR#1 A】排序
【UTR#1 B】考虑到优先级越大越早完成，那么我们就可以二分这个未知的优先级，然后O$（nlogn）$枚举整个过程。这样可以拿到$90$分。然后$100$分只能$O（nlogn）$。我们可以考虑构造算法，比如先让未知的优先级为$-1$这样做一遍，然后我们可以得出在时间段$[tx,T]$中每个任务做的时间。然后不妨找到前$i$小优先级的存在时间和为$sx$，那么我们让未知的优先级比第$i$小的大且最小就是一种合法的方案。为什么一定存在$==sx$的前$i$小呢？因为如果不存在的话就没解了啊。无论如何调整未知的优先级也不会使它恰好在$T$时刻完成。
【UTR#1 C】考虑暴力的做法，我们从每个黑点$x$往下$dfs$找出所有最远点，那么能阻碍$x$的点一定位于$x$到所有最远点的$LCA$这段路上。我们给这一段$ans++$。然后考虑优化暴力，我们可以存一下向上最远距离以及最远点的$LCA$。然后$balabala$一通讨论。$CF$上的傻逼数据连菊花图都没有卡。为了避免被菊花图卡成$O（n^2）$我们可以给每个节点保留三个子树的最远距离较优值。代码写起来很简单。写之前感觉很麻烦，写开就不觉得了。
【UER#1 A】答案显然是$2\sqrt{ab}$和$a+b$
【UER#1 B】看懂题之后就是傻逼模拟了。可以以字符串为单位建成$trie$，也可以直接以字符为单位。后者好写点儿。然而我写的前者。
【UER#1 C】终于明白了并查集的按秩合并，这样保证树高至多是$O（logn）$的，所以我们就可以不路径压缩。这样我们就可以在并查集上删除一条边。当然只是删除。只要还原它加入之前的状态即可。于是看这题，加入的权值是递增的。所以删边直接删就好了，不会有其他边加进去。$70$分很好拿。满分算法我们可以考虑把一开始到现在加了多少条边，每条边加进去之后的连通块的数目，$MST$的权值以及修改的哪个点的父亲记录下来，这样就可以$O（1）$访问删除$k$条边的版本。所以我们就可以根据下一个是否是$return$操作来看这$k$条边到底是真删还是不删。然而我的并查集写的是启发式合并
【UR#1 A】UR题的难度明显上来了。题意为最小化$\sum_{i=1}^{n}\frac{a_i}{x}+a_i\%x$ 注意到$a_i\%x=a_i-\frac{a_i}{x}x$ 所以实际上是最小化
$\sum_{i=1}^{n}a_i+\frac{a_i}{x}(1-x)$ 这样我们仍不能得出答案，考虑对$x$求出$\sum_{i=1}^{n}\frac{a_i}{x} $
如果注意到$\frac{a_i}{x}$只有$\sqrt{a_i}$种取值，那么就可以分块然后差分。这样复杂度是$O（n\sqrt{n})$，只有70分。
定式思维的锅
考虑反向思考，我们直接对$x$算答案，而不是对每个$a_i$算贡献。这样$\frac{a_i}{x}$只可能有$\frac{1000000}{x}$个可能的取值，然后取到这个值的时候是一段连续的区间。我们可以预处理。由调和级数可知这样的复杂度是$O（nlogn）$
考虑反向思考，我们直接对$x$算答案，而不是对每个$a_i$算贡献。这样$\frac{a_i}{x}$只可能有$\frac{1000000}{x}$个可能的取值，然后取到这个值的时候是一段连续的区间。我们可以预处理。由调和级数可知这样的复杂度是$O（nlogn）$
【UR#1 B】这题做的我好酸爽。看到题后想了一会儿过了第一问。注意到模两次一个数是没有意义的。所以每个数只有模和不模两种情况，当个$01$背包做一下就好了。第二问是个计数，原来一直不怎么会计数当然现在也不会。考虑继续挖掘题目的性质，一个有效的取模序列一定是一个递减的序列。这启发我们可以从大往小$DP$。可以枚举上一个比它大的数，然后把它插入到之后的序列中。这样我们发现是不好搞的，因为中间的数并不确定放到哪，方案数也不好计算，所以得多开一维记录。这样好像就是$O（n^5）$了正难则反，考虑反过来处理。先将序列从大到小排序，然后令$dp_{i,j}$表示$i$作为当前取模序列最前面的一个，如果之前的取模结果是$j$，那么有多少种方案安排$i$及以后的序列使其成为$ans$。这样就好$DP$了。因为枚举前一个数$k$的时候，$i$和$k$之间的数一定放在i之后，就可以一个阶乘艹过去了。
正难则反，考虑反过来处理。先将序列从大到小排序，然后令$dp_{i,j}$表示$i$作为当前取模序列最前面的一个，如果之前的取模结果是$j$，那么有多少种方案安排$i$及以后的序列使其成为$ans$。这样就好$DP$了。因为枚举前一个数$k$的时候，$i$和$k$之间的数一定放在i之后，就可以一个阶乘艹过去了。
$dp_{i,j\%a_k}+=dp_{k,j}*calc(i-k-1,n-i+1)$ 其中$calc(x,y)$表示把$x$个数插入到$y$个数中的方案数，显然是$\frac{(x+y-1)!}{(y-1)!}$
这样可以有$76$分。继续优化，考虑把枚举上一维去掉。不用有$i$是取模序列中的一环的限制，直接$dp_{i,j}$表示如果之前的取模结果是$j$，那么后$n-i+1$个数有多少种方案安排顺序使其变成$ans$。我们发现递推的时候只需要$i$是取模序列中的一环直接插入到已有的序列前面即可，否则可以插入到$n-i$个位置的任何一个。所以新的$dp$方程就是$dp_{i,j}=dp_{i+1,j\%a_i}+(n-i)*dp_{i+1,j}$。复杂度$O（n^2）$，可以通过。
【UR#2 A】我们的策略就是每次找到一个$（$，然后把它翻转到当前的最左边。这样一定不超过$n$次。所以模拟一下就好了.
评论 (0)
