0%

1st Ucup Stage 19 America 题解

D

假设不考虑依赖的限制,显然我们可以贪心按\(\frac{c}{1-p}\)来排序得到最优序列。

考虑依赖,我们还是按照\(\frac{c}{1-p}\)从小到大考虑,对于一个点,如果依赖已经执行,那么我们直接执行它就好,如果依赖没有执行,有一个观察就是,当这个点的依赖执行后,这个点肯定立刻执行,所以实际上这两个点是被捆绑到一起的,我们可以将其等价地合成一个点,假设父亲为\((c_1,p_1)\),儿子为\((c_2,p_2)\),那么新点就是\((c_1+p_1\cdot c_2,p_1\cdot p_2)\),维护一下当前的优先队列就好。

总时间复杂度\(O(n\log n)\)

AGC023D

E

真傻逼啊,怎么会有人中间26个字母旁边3个字母的。

只关心首尾字母,又只有3个字母,所以字母当点,单词当边。然后发现两条性质,同一个点自环可以%=2,\(u\to v\)\(v\to u\)可以相消,然后剩下来的图跑个SG就好。

真傻比啊。

J

先处理两个一摸一样的字串拼起来的情况,这个\(n^3\)预处理\(lcp\)或者哈希都可以做。

然后处理拼起来的情况。拼起来的话一定是一个形如\(ABA\)和一个形如\(B\)的拼起来。\(n^2\)枚举\(ABA\)中间的那个\(B\),然后\(O(n)\)在那个\(B\)旁边枚举\(A\),然后需要\(O(1)\)地算出有多少个与这一段\(ABA\)不交的\(B\)。这个可以在枚举\(A\)之前先用哈希或者\(lcp\)做个预处理,算个前缀和。总体是\(O(n^3)\)