binary(x, y):
ans := inf
for i in 1..60:
if x * 2^i > y then break
for j in 0..i:
ans [min]:= i + j + (y + j - x * 2^i) / 2^i + popcount((y + j) mod 2^i)
return ans
[Current Time: 08:30]
[Self Evalution #4]
...
Test 16: Accepted (1.6 s)
Test 17: Time Limit Exceeded (> 4.0 s)
...
-----------------------
Score: 64 / 100
总算没有 WA 了，但 64 分看上去很烂啊！
试试优化：
binary(x, y):
ans := inf
for i in 1..60:
if x * 2^i > y then break
j := 0
while j <= i:
ans [min]:= i + j + (y + j - x * 2^i) / 2^i + popcount((y + j) mod 2^i)
j := j + lowbit(j)
return ans
[Current Time: 08:40]
[Self Evalution #5]
...
Test 21: Accepted (0.3 s)
Test 22: Time Limit Exceeded (3.2 s)
Test 23: Time Limit Exceeded (3.2 s)
Test 24: Time Limit Exceeded (> 4.0 s)
Test 25: Time Limit Exceeded (> 4.0 s)
-----------------------
Score: 84 / 100
# Part 2
对于 T2，首先把 $x - t$ 图画出来……在进一步思考前写个离散化吧。
```plain
[Current Time: 08:50]
C139:~/AH-004/game# cp template_game.cpp game.cpp
```
```cpp
game(n, m, k, mice):
segments := []
for mouse in mice:
segments := segments + convert(mouse)
segments.coordinates.discretize(index=1)
p, q := segments.coordinates.max
// To be completed
return -1
```
```plain
[Current Time: 09:20]
C139:~/AH-004/game# cp game.cpp game.cpp.save
```
那么旋转 $45$ 度得到了：
- $a < b$：得到线段 $(t + a, t - a + m) - (t + 2b - a, t - a + m)$。
- $a > b$：得到线段 $(t + a, t - a + m) - (t + a, t - 2b + a + m)$。
- $a = 0$ 时，向横轴负方向无限延伸线段。
- $a = m$ 时，向纵轴负方向无限延伸线段。
- $b = 0$ 时，向横轴正方向无限延伸线段。
- $b = m$ 时，向纵轴正方向无限延伸线段。
- 需要从 $(0, 0)$ 向右或向下走到 $(2 \times 10^9, 2 \times 10^9)$ 并让它必须穿过至少 $k$ 个线段。
对于特殊性质 C，只需要判断答案是否为 $-1$，离散化后得到了 $O(n^2)$ 做法。
那么开始写吧！
```plain
[Current Time: 09:30]
C139:~/AH-004/game# cp game.cpp.save game.cpp
```
```cpp
game(n, m, k, mice):
...
dp := [inf]
dp[1][1] := 0
horizonal, vertical := [[0]]
for segment in segments:
if segment.horizonal then:
for i in (segment.left.x)..(segment.right.x - 1):
horizonal[i][segment.y] := horizonal[i][segment.y] + 1
if segment.vertical then:
for i in (segment.left.y)..(segment.right.y - 1):
vertical[segment.x][i] := vertical[segment.x][i] + 1
for i in 1..p:
for j in 1..q:
dp[i][j] := min(dp[i][j - 1] + vertical[i][j], dp[i - 1][j] + horizonal[i][j])
if dp[p][q] <= k then return -1
return 0
```
```plain
[Current Time: 10:00]
C139:~/AH-004/game# g++ grader.cpp game.cpp -o -O2 -std=c++14 -static
C139:~/AH-004/game# ./game < game3.in
0
-1
-1
0
-1
-1
-1
-1
C139:~/AH-004/game# cat game3.ans
0
-1
-1
0
-1
0
-1
0
```
嗯？……原来是血量扣减到 $0$ 也算达成目标。
```cpp
game(n, m, k, mice):
...
if dp[p][q] <= k - 1 then return -1
return 0
```
```plain
[Current Time: 10:10]
C139:~/AH-004/game# g++ grader.cpp game.cpp -o -O2 -std=c++14 -static
C139:~/AH-004/game# ./game < game3.in
0
-1
-1
0
-1
0
-1
0
C139:~/AH-004/game# cat game3.ans
0
-1
-1
0
-1
0
-1
0
```
```plain
[Current Time: 10:20]
[Self Evalution #9]
Test 1: Wrong Answer
Test 2: Wrong Answer
Test 3: Accepted
Test 4: Accepted
Test 5: Runtime Error
Test 6: Runtime Error
Test 7: Accepted
Test 8: Accepted
Test 9: Runtime Error
...
-----------------------
Score: 16 / 100
```
啊！接下来对于暴力分 $O(2^k)$ 枚举选择的线段就好了。
```cpp
partial_game(p, q, segments):
...
if dp[p][q] <= k - 1 then return FALSE
return TRUE
game(n, m, k, mice):
...
if n <= 10:
for S in segments.subsets:
W = S.w.sum
if partial_game(p, q, S) then ans [min]:= W
if ans = inf then return -1
return ans
...
```
```plain
[Current Time: 10:30]
[Self Evalution #10]
Test 1: Accepted
Test 2: Accepted
Test 3: Accepted
Test 4: Accepted
Test 5: Runtime Error
Test 6: Runtime Error
Test 7: Accepted
Test 8: Accepted
Test 9: Runtime Error
...
-----------------------
Score: 24 / 100
```
# Part 3
T1 中那个 $i$ 的枚举看上去很慢啊！试试优化：
```cpp
pp := []
t := 32768
self_popcount_init():
for i in 0..(t - 1):
pp[i] := popcount(i)
self_popcount(x):
if x <= t - 1 then return pp[x]
return pp[x mod t] + pp[x / t mod t] + pp[x / t^2 mod t] + pp[x / t^3 mod t]
init():
self_popcount_init()
binary(x, y):
ans := inf
for i in (log2(y / x) - 1)..60:
if x * 2^i > y then break
j := 0
while j <= i:
ans [min]:= i + j + (y + j - x * 2^i) / 2^i + self_popcount((y + j) mod 2^i)
j := j + lowbit(j)
return ans
```
```plain
[Current Time: 10:40]
[Self Evalution #11]
...
Test 21: Accepted (0.1 s)
Test 22: Accepted (2.8 s)
Test 23: Accepted (2.8 s)
Test 24: Time Limit Exceeded (> 4.0 s)
Test 25: Time Limit Exceeded (> 4.0 s)
-----------------------
Score: 92 / 100
```
$92$ 分……？这个分数这么这么奇怪。
但这个 Test 24 纹丝不动啊！去看 T3 了。
# Part 4
那么我们有一个最暴力的想法：在 $2, 3, \ldots, n$ 号结点各放两对铅笔橡皮，第一对将树改为菊花，第二对达成目标。
```cpp
dfs1(tree, now, father):
for x in tree.neighbours(now):
if x != father then dfs1(tree, x, now)
if now != 1 then alter(now - 1, 1, father)
dfs2(tree, now, father):
if now != 1 then alter(n - 1 + now - 1, father, 1)
for x in tree.neighbours(now):
if x != father then dfs1(tree, x, now)
paint(n, T1, T2):
setting(2 * n - 2, [2, 3, ..., n, 2, 3, ..., n])
dfs1(T1, 1, 0)
dfs2(T2, 1, 0)
```
```plain
[Current Time: 11:00]
[Self Evalution #16]
...
Test 1: Accepted (14 / 14 points)
Test 2: Accepted (23 / 23 points)
Test 3: Partially Correct (1 / 26 points)
Test 4: Wrong Answer (0 / 37 points)
-----------------------
Score: 38 / 100
```
# Part 5
```plain
[Current Time: 13:00]
[Self Evalution #21]
<Task "binary">
...
Score: 92 / 100
<Task "game">
...
Score: 24 / 100
<Task "binary">
...
Score: 38 / 100
```
？？？后面 2h 我什么也没做，于是比赛结束了。
# Part 6
```plain
[Current Time: 15:00]
Login: AH-004
Password: xkjegh
-----------------------
[Final Evalution]
binary: 92 / 100
game: 24 / 100
paint: 38 / 100
-----------------------
Total Score: 154 / 300
```