高兴地达成了AK的成就。

不过是因为题目难度堪比Div.2的原因……

下面是Solution。

413A. Data Recovery

不会做的枪毙五分钟。

413B. Skype Chatting

不会做的枪毙五分钟。
[tex]Ans_i = -Send_i + \sum_{P_i\in C_j} Cnt_j[/tex]

413C. Jeopardy!

贪心。其实一开始我不会证明，然后结果过了。
贪心策略如下：先拿光所有非Auction，再从大到小拿走所有Auction。

由于[tex]a \ge b \Rightarrow f(x,a) \ge f(x,b)[/tex]，显然我们可以使用调整法。
考虑[tex]u \ge v[/tex]，为目前方案中相邻的两个Auction。
我们按照这两个Auction前的分值S进行讨论：
1. [tex]S \ge u[/tex]
若先取u, 结果为4S。
若先取v, 结果为4S。
先取u不更劣。
2.[tex]S \le v[/tex]
若先取u, 结果为2(S + u)。
若先取v, 结果为[tex]max(S + u + v, 2(S + v))[/tex]。
其差为[tex]min(S + u - v, 2(u - v)) \ge 0[/tex]。
先取u不更劣。
3.[tex]v < S < u[/tex]
若先取u, 结果为2(S + u)。
若先取v, 结果为[tex]max(4S, 2S + u)[/tex]。
其差为[tex]min(2(u - S), u) > 0[/tex]。
先取u不更劣。
综上，不存在比从大到小取更优的策略。
然后这题就水过去了。

413D. 2048
显然，只有最右侧的递减的一段方块和已经达到[tex]2^k[/tex]的方块是有意义的。
于是可以状压。
把所有方块的权值/=2。
令[tex]F=2^{k-1}[/tex]。
令状态i[tex](0 \le i < F)[/tex]代表最右侧递减的一系列方块。i=F代表已经产生了目标方块。
状态的转移如下：

[tex]S' = \begin{cases}
S (S = F) \\
S + x (S < F, lowbit_S \ge x) \\
x (Otherwise)
\end{cases}[/tex]

这题就艹掉了。

413E. Maze 2D
看到这道题第一反应是前不久刚做到的SHOI的traffic。
后来发现其实更水。
因为切掉的是点而不是边，所以不需要讨论绕一圈的情况。
直接线段树上开2*2数组就可以了。
注意讨论N=1的情况。
@qwer大爷有一种O(n)的乱搞一样的做法，真是不能膜拜更多……

• 相关文章
• 全局相关文章