4
26
2015
0

Codeforces Round #300

本以为合场容易涨rating就可以黄了,结果还是傻逼了啊。

一直以来感觉cf都不太对胃口,题目是英文的导致没有一种亲切感,总是会出现读不懂题和读错题的事情,然后cf的赛制也让我写代码的时候根本无法放松了写,总是感觉浪费了太多时间在水题上。

说到底还是自己太弱,没有自信心认为自己能做出XXX,结果自然就是弃疗了。

还是说正经的吧:

A.没什么说的

B.2^6+1个数然后DP。直接贪心也可以。

C.傻逼题,但是中途的提示我没有收到,被hack了一次之后还fst了。hack狂魔你能不能敬业点,hack到底不行啊

D.暴力枚举然后暴力判断。刚开始看见群里都问D题题意还以为很难,就拖了很长时间才做。

E.这种树上的博弈论问题,应该想到肯定就是dfs几遍就好了。设计状态至关重要。

  英语不好不想翻译了

Let's first say we are the minimizing player and also allowed to modify the labels.

For the subtree rooted at i, define f(i) = k if the game on that subtree ends on the k-th smallest label among the leaves in that subtree.

There are two kinds of nodes, depending on which player's turn it is. Let's call the current nodei and its children j1, ..., jt.

Case 1: it is our turn. Let j be the child of i with minimal value of f(j). The best solution then is to rearrange the labels in the current subtree so that all the smallest labels end up in the subtree rooted at j and make our move to j. So in this case f(i) = min(f(j1), ..., f(jn)).

Case 2: it is our opponent's turn. As he wants to maximize the result, he will move to the childj where the f(j)-th smallest label is as large as possible. We need to find a rearrangement of the labels to keep that value as small as possible, and we can see that the best we can do for that label is f(j1) + ... + f(jt). For instance, we can place the f(j1) smallest labels below j1, the next f(j2) below j2, and so on. So in this case f(i) = f(j1) + ... + f(jt).

Let's now say we are the maximizing player. This works in fact dually, we now only have to define f(i) = k if the game on that subtree ends on the k-th largest label instead. We can even reuse the code from the minimizing case (something I didn't notice during the contest).

F.看懂了题意之后发现是道水题。i节点当k-ary的时候,父亲是(i-2)/k+1.而这个只有√n个取值。那么就分块完了。

Category: codeforces | Tags: | Read Count: 639

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com