• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

May Lunchtime 2021 Division 1

admin

11月 28, 2021

May Lunchtime 2021 Division 1 Coding Competition | CodeChef

NUMCOMP1

对于质数 (p),显然,所有 (kp) 会被合并到一起,设 (S(p)=kp)。若两个质数 (x,y) 满足 (xyle n),那么 (S(x),S(y)) 会被并到一起。而最优方案显然是所有质数都以 (2) 为媒介相连,只要计算最大的 (2ple n)

CHESUB

简单dp(略)

TRTOKENS

进行dfs,先处理所有 (u) 的子树,若 (u) 为空,最优的一系列移动相当于将当前 (subtree(u)) 中最深的token移动到 (u)。若 (u) 不空,啥事别干。数据结构维护一下

INTMST

若原图中桥的个数 (>1),那么这些桥一定会出现在所有答案中,无法确定答案。

否则,先询问 ((1,2,dots n)(n,1,2dots n-1)(n-1,n,1dots n-2)dots),即每次把左右一个滚到最前面。考虑一条边 (x),若 (x) 为桥,它会出现在所有答案中。否则,存在一个时刻 (w(x)=1),这时它一定在答案中,下一次询问中 (w(x)=n),而它又不是桥,那么一定不在答案中。其它时刻,(w(x)) 不断变小,可能存在一次由不在答案中变为在答案中(不重要,已经做完啦)。

SIMARRAY

最优方案中,对于 (R_i) 相同的一段极大区间,(R_i) 一定选取这段区间的最优值,即 (frac{sum A_iB_i}{sum B^2_i})。可以采用反证法证明(考虑若取不到最优值,合并两段区间后更优)。由此可以得到 (O([n^2,n^3])) 的dp。

进一步推导结论:设所有位置最优解的位置为 (p_1,p_2,dots p_m),若 (p_i<p_{i+1}),则 (R_i=R_{i+1}),可以将它们合并。用单调栈优化至 (O(n))

PARTODD

约定 (sum[1,i]) 为奇数的 (i) 为红色,否则为黑色。原序列被划分成了红黑相间的颜色段。

(n^3) dp显然,可用线段树优化至 (n^2log n)。贪心地观察发现,对于每个位置 (i),可能成为最优解的转移只有两个,一个是能跳到的最大位置 (b_x) ,另一个是 (b_x) 往回走两段的 (c_x),由此可以弄到 (n^2)

考虑连续三段,如果 (sum<m),就把它们并在一起,不断合并,最后任意连续三段都 (>m),那么只有 (3lceilfrac{n}{m}ceil) 段,若有解则答案 (le 3lceilfrac{n}{m}ceil)。那么对于 (mle sqrt{nlog n}),使用 (O(n)) dp;否则,只有 (sqrt{frac{n}{log n}}) 种答案,对每一种二分判断一下界限,(O(nlog n)),总复杂度 (O(nsqrt{nlog n}))

假设当前在 (x),若 (b_x) 可达 (n),走 (b_x) 一定更优。而 (x) 可达 (n) 当且仅当 (c_x) 可达。所以每次通过不断跳 (c) 判断 (b_x) 是否可行,复杂度 (summin(n,(frac{n}{m})^2)=nsqrt{n})

进一步优化,动态维护所有可达 (n) 的位置。考虑随着 (m) 增大,每个颜色段中可达的位置一定是一段后缀,并不断延长,且每次至少延长 (1),从后往前扫即可。知道所有可达位置后,直接贪心地向后跳复杂度为 (sumfrac{n}{m}=nlog n)

注意:本题解漏洞较多(例如颜色段划分方法),还有一些细节没有介绍

发表评论

您的电子邮箱地址不会被公开。