HS
AFO
HS的博客
Codeforces Round #623 (Div. 2)

Codeforces Round #623 (Div. 2)

$A. Dead Pixel$

签到题,答案为
$$
\max(a\times\min(b,b-y-1),b\times\min(a,a-y-1))
$$
code

$B. Homecoming$

答案显然具有单调性,考虑二分答案。

假设当前答案为 $now$ 。

算出 $[now,n-1]$ 中的 $A,B$ 的连续段个数 $x,y$ ,那么费用为 $ax+by$ ,若 $ax+by<=p$ ,那么合法。

code

$C. Restoring Permutation$

从前往后,每一个数后面,放没出现的第一个大于它的数。

如果没有,输出 $-1$ 。

code

$D. Recommendations$

按 $a$ 从小到大排序。

若有两个 $a$ 相同的,显然把 $t$ 更小的加 $1$ 更优。

用一个堆维护一下即可。

code

$E. Double Elimination$

显然我们只关心是否关注当前的胜者组赢家,和是否关注当前的败者组赢家。

设 $dp[l][r][0/1][0/1]$ 表示当前区间为 $[l,r]$ ,是否关心胜者组,是否关心败者组时的最大比赛数。

考虑枚举 $[l,mid],[mid+1,r]$ 的后两个数组。

再枚举哪个的胜者组赢了,再转移即可。

因为没有计算胜者对败者,最后再加上即可。

由于数组很大,且有用的较少,用 $map$ 纪录即可。同时将最后两个可以缩成 $[0\sim 3]$ 。

code

TheShadow

文章作者

发表评论

textsms
account_circle
email

HS的博客

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