6
17
2015
0

论蒟蒻的自我修养之UOJ练习记

感觉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)$
【UR#1  B】这题做的我好酸爽。看到题后想了一会儿过了第一问。注意到模两次一个数是没有意义的。所以每个数只有模和不模两种情况,当个$01$背包做一下就好了。第二问是个计数,原来一直不怎么会计数当然现在也不会。考虑继续挖掘题目的性质,一个有效的取模序列一定是一个递减的序列。这启发我们可以从大往小$DP$。可以枚举上一个比它大的数,然后把它插入到之后的序列中。这样我们发现是不好搞的,因为中间的数并不确定放到哪,方案数也不好计算,所以得多开一维记录。这样好像就是$O(n^5)$了正难则反,考虑反过来处理。先将序列从大到小排序,然后令$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$次。所以模拟一下就好了.
 
Category: UOJ | Tags: | Read Count: 603

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com