TCO19 SRM 749 Div1 解题记录

### Easy FightMonsterDiv1
题意：你要打个怪，有$HP$点血。你一开始的攻击力是$ATK(/s)$，攻击力每$1s$会增加原始攻击力$ATK$的$L\%$。你还可以给连续$D(s)$的攻击施放魔法使它伤害变成$5$倍。问最快多久可以打死怪物。
$HP\le 10^{12},ATK\in [100,10^{12}]且ATK\ mod\ 100 = 0$
$L\in [0,100],D\in [1,10^{12}]$

题解：二分一个秒数，验证就是个等差数列求和，然后把后$D$个攻击翻倍就可以验证。复杂度$O(logN)$。

### Medium TransformBoardDiv1

题意：一个$N\times M$的矩形。每个格子都可以是黑色/白色。每一次可以选择同行或同列的两个格子做如下操作：假设靠左上角的那个格子是$A$，另一个是$B$。
1、如果$A,B$不同，那么将$B$涂成白色。
2、否则将$B$涂成黑色。
在这之后再把$A$涂成白色。
给你一个起始状态，一个终止状态，给出一种方案使得在$947$步内将起始状态变成终止状态。

题解：考虑操作的本质，首先发现无论怎么操作，黑色块个数的奇偶性不会改变。首先就判掉无解。不难发现把两个人消掉的这一步操作看成全部匹配到右下角的点在解的有无上是等价的。剩下的相当于把黑块看成很多个人，每个人可以向右、向下走并且穿墙，两个在一行的人可以消掉，问可不可以形成一种局面，实际上充要条件是每个人都匹配一个右下角的人，网络流跑一下就可以了。构造的时候按顺序从右下到左上构造，$O(N^2M^2)$

### Hard TurnOffLightsDiv1

题意：一栋大楼有$n$层($0$到$n-1$)，每层有$m$个房间($0$到$m-1$)。每一层最左边合最右边都是楼梯，可供上下，其他情况下只能在一层间移动。
这其中有些房间的灯是开着的，每次移动花费一分钟，关灯需要花费一分钟，问你从$(0,0)$出发关完所有灯回到$(0,0)$的最小花费。

题解：最暴力直观的做法考虑$f(l,i,j,k)$表示左边有$i$个向上，有$j$个向下，右边有$k$个向上，扫到第$l$层。我们套路地去$dp$它的切面。考虑中间只可能被走一遍，直接讨论它是从两边进来后再出去还是走穿。两边进来的情况枚举分界点即可。
但实际上这道题可能并不需要，考虑一个性质，左右的状态只可能有$4$种：左边一上一下，右边一上一下，左右两边一上一下/一下一上。因为我们整个过程绕一圈肯定是最优的。记$f(l,4)，$讨论第$0$层的初始状态即可。

Rockdu's Blog

导航

最近发表

大佬们的友链