Chenyao

Codeforces Round 310 (Div. 2)

Posted at — Jun 28, 2015

我脑子里全是草泥马…

A. Case of the Zeros and Ones

题意:给你一串01串,每次可以选择一个”0”和一个”1”消掉,问最后长度最短是多少。

串的长度减去0或1最小的数量的2倍就行了。

B. Case of Fake Numbers

题意:有n个数$a_0, a1, …, a{n-1}$,问是否存在一个$k$,使得满足对于所有的$i$,有$a_i + (-1)^{i}*k mod n = i$。

显然求出来对于$a_0$的$k$,之后判定一下是否全部满足就就可以了。

C. Case of Matryoshkas

题意:有n个套娃,之后有一些已经放在桌子上嵌套在一起了。问把n个全部套在一起需要几次操作。(对于几个套在一起的如果分开只能从上方拿掉一个!差不多类似放在桌子上然后只能一个手操作。)

模拟吧,对于1开始有序的那部分不用拆开,其他都要拆。这个题意我看了好长时间才看懂TAT

D. Case of Fugitive

题意:每个小岛在轴上是一个区间,然后有一些距离确定的桥,问是否存在一种桥使用方案使得相邻的岛之间有桥。

把相邻的岛可以接受的桥的长度搞出来,之后相等于一群区间是否有方案使得每个区间覆盖一个不同的点。区间左端点和桥一起排下序,贪心匹配一下就行了。

E. Case of Chocolate

题意:有一个n*n的巧克力,之后从左下方到右上有一条对角线,对角下方已经被吃完了。现在有一些询问,每个询问给一个对角线上的点和一个方向(上或者左),从这个点开始朝着给定方向吃,吃到空格子结束。问每次可以吃多少个格子。

考虑向上吃对向左吃的影响,反之一样。可以发现每次向上吃完之后,可能影响的是吃的这个区间的点。而每次求向左的方案就相当于求最近的上。离散化一下用线段树实现区间更新最大值,单点求值即可。


我脑子里全是草泥马…不要问我为什么E没有过…

然后大家似乎FST的很欢脱….我下一场就可以打div1了好开心…