HS
菜单
HS的博客
Codeforces Round #624 (Div. 3)

Codeforces Round #624 (Div. 3)

这题怎么回事,感觉 $E$ 和 $F$ 放反了。

$A. Add Odd or Subtract Even$

签到题,分 $a>b$ , $a=b$ , $a<b$ ,同时分奇偶讨论一下就行。

code

$B. WeirdSort$

$p$ 数组将 $a$ 数组分为了若干段,被覆盖的那些,其中的元素可以随意排列,没被覆盖的只能保持原位。

排序得到答案数组,然后在原数组中将被覆盖的段排序,比较两者是否相同即可。

注意,当 $[l,r]$ 均被 $p$ 覆盖时,能排序的为 $[l,r+1]$ 。

code

$C. Perform the Combo$

在 $k$ 处失误, $1\sim k$ 中的所有元素均被覆盖一次。

最后成功, $1\sim n$ 均被覆盖一次。

用差分统计即可。

code

$D. Three Integers$

直接暴力枚举 $a,b,c$ ,满足 $b=k_1a,c=k_2b$ 。

由调和级数可知时间复杂度为 $O(n\log n\sim n\log^2 n)$ 。

code

$E. Construct the Binary Tree$

考虑先构造一条链,设此时的深度和为 $sum$ 。

从 $n\sim1$ 依次调整,设当前能调整到的最小深度为 $k$ ,那么这一次调整中,可以构造出的答案范围是 $[sum-(dep_i-k),sum]$ 。

若 $d$ 在这个范围内,找到一个合法的位置,将 $i$ 调过去即可得到解。否则将 $i$ 调整至最浅的位置, $sum$ 减去 $dep_i-k$ 。

若 $dep_i=k$ ,那么结束调整,无法构造出合法解。

code

$F. Moving Points$

$vp$ 的时候 $codeforces$ 出问题了,就没打了。

解法很简单,按位置排序,然后分类讨论,用树状数组统计答案即可。

TheShadow

文章作者

发表评论

textsms
account_circle
email

HS的博客

Codeforces Round #624 (Div. 3)
——TheShadow
扫描二维码继续阅读
2020-03-30