首页 > 代码库 > Codeforces Round #398 (Div. 2)

Codeforces Round #398 (Div. 2)

这套题。。难度不大,但是普遍都挺恶心的,还容易看错题意

A模拟

B贪心(别像我一样看错题目),注意细节较多,思路要清晰

  If the receptionist would stop working within minutes, he stops serving visitors (other than the one he already serves).

C贪心 发现可以删掉的两个点若一个是另一个的祖先,显然是一样的(除非average=0,需从底向上切)。注意审题,root不能被切

D不太难的二分 注意一下细节,judge好像容易写错,还是要思路清晰

E略难的heap

首先发现只能一个个处理,否则就有后效性。

贪心地想一想:

1.若剩下的coins足够,直接用

2.若coins不够(1)被迫找零 (2)是否以前某一次的决策不够优秀,可以“后悔”以得到一些coins

how to “后悔”?

一个很有用的性质:两种简单决策coins差100

如果得到coins后仍然不够怎么办?——发现不会出现此情况,且是否“后悔”对决策后的coins无任何影响!!!

那么一开始我们关心coins数和ans两个变量,现在只剩下一个,显然可以大大简化题目。

用堆维护所有花掉coins的那些天若“后悔”需对ans产生多少影响,每次和当前天比较即可。

处理起来也要注意细节

Codeforces Round #398 (Div. 2)