UOJ Round #9 题解

电路手动分析

from Picks，题目是 vfleaking 造的。

算法一

首先这个问题转换为，选一个子图使得补成团的边数不超过 $r$ 。那么设点数为 $n_{v}$ 边数为 $n_{e}$ 那么就是要使得 $n_{v} (n_{v} - 1) / 2 - n_{e} \leq r$ 。

对于 $n, m \leq 4$ 的情况，我们枚举每一个导出子图就行了。

可以获得 30 分。

算法二

有 20 分的数据满足 $n = 1$ 。

显然我们应该选连续的一段，于是二分答案就可以了。

可以获得 20 分。

算法三

我们可以二分答案，假设我们要判定点数为 $k$ 是否可行，那么我们就是要找点数为 $k$ 且边尽量多的子图。

首先我们要选择的子图肯定是连通的，否则我们肯定可以通过平移变成连通的且点数不变，边数增多。

其次，边数 $=$ 点数乘四再分别减去上下左右方向上没连出边的点数，所以边数 $\geq$ 点数乘四减去最小包围矩形的周长。

反过来，假如给定了最小包围矩形，我们是容易构造的。

于是，就是要找 $w, h$ 满足 $k \leq w h$ ，要求最大化 $4 k - 2 (w + h)$ 。

所以就变成了一个简单的数学问题。不考虑 $w \leq n$ ， $h \leq m$ 这个限制的话，如果 $| w - h | > 1$ 显然可以让 $w$ 加一让 $h$ 减一使得仍然满足条件且要最优化的值不变。所以 $| w - h | \leq 1$ ，于是就好弄了。

现在考虑 $w \leq n$ ， $h \leq m$ ，不妨设 $m < n$ ，如前所述 $w$ 和 $h$ 应该尽量接近，所以如果 $k > m^{2}$ 的话就有 $h = m$ 。

直观点来说，最优策略是这样：随着 $k$ 的增大，一圈一圈绕方形圈圈，当宽度和矩形宽度相等时固定宽度一行一行填充。

于是这题就解决啦！

App 管理器

from taorunz

题意简述

一个混合图，把里面的无向边都定向，使得定向之后的图强连通，求一个方案。

算法一

对于30%的数据有 $n, m \leq 17$ ，我们暴力枚举所有边的方向，再判断定向之后是否强连通。

期望得分：30分

算法二

对于另外30%的数据有所有边都是无向边。

我们首先发现一个强连通图的基图一定是边双连通图（考虑强连通图的一条边 $x \to y$ ，这个图中 $y \to x$ 的路径便可以保证基图中删掉 $x \to y$ 的边后仍然连通）。

我们对这个图进行dfs，把树边都定为父亲到儿子的方向，返祖边都定为后代到祖先的方向。这样构造的图一定是强连通的。

如果不是强连通，那么必然存在一个点，它在dfs树里的后代中，没有返祖边连向这个点的祖先，那么原图就不是双联通图了（其实通过比较求边双连通分量和强连通分量的两个tarjan算法也可以看出来）。

期望得分：60分（加上算法一）

算法三

剩下的数据，有些边已经被定向了，那么如何做呢？

首先我们发现这个图一开始一定满足强连通性质（要不然定向之后更不可能满足）

我们考虑一条无向边 $u - v$ 。

如果从 $u$ 到 $v$ 存在一条不经过这条边的路径，那么我们可以把这条无向边定向成 $v \to u$ ；
反过来从 $v$ 到 $u$ 存在一条不经过这条边的路径，那么我们可以把它定向成 $u \to v$ 。

假设这两种情况都不满足，那么考虑从 $u$ 不经过这条边能到达的节点集合 $S$ 。由于原图是强连通， $u$ 到 $T = V - S$ 里的点都必须经过 $v$ ，也就是说 $v$ 可以不经过 $u$ 到达所有 $T$ 里的点。

而我们可以发现， $S$ 里的任何点都可以到达 $v$ 的，如果某个 $s$ 到 $v$ 不经过 $u$ ，那么 $u - \dots \to s - \dots \to v$ 就是一个不经过那条边的路径，与假设矛盾。所以 $S$ 里任何一个点到达 $u$ 都不用经过 $v$ 。同理 $T$ 里的点到达 $v$ 都不用经过 $u$ 。考虑 $S$ 和 $T$ 集合之间的边，除了 $u - v$ 之外一定还有一条边（注意基图是双连通的），不妨假设这条边是从 $S$ 里面的某个点 $p$ 到达 $T$ 里面的某个点 $q$ 的，那么 $u - \dots \to p \to q - \dots \to v$ 就是一条不经过边 $u - v$ 的路径，与假设矛盾。

所以1、2两种情况必然会出现一种。

我们依次考虑每条边，dfs一次找出符合哪一种情况，并且根据对应情况定向。这样就在 $O (m^{2})$ 的时间复杂度里解决了这个问题。

期望得分：100分

包子晚宴

from SHUXK

大家好，我是SHUXK。

第一次出题出了这样一道复古的提交答案题，不知道大家会不会喜欢呢。

通用方法

如果你只有5分钟时间做这道题，可以对每一个测试点全部输出S。

这样可以轻松获得20分。（每个测试点的 $a_{2}$ ）

如果你只有30分钟时间做这道题，可以只考虑水平和竖直的移动，然后对每个时间在每个位置的得分进行估价，再用一个 $f [t] [x] [y]$ 之类的DP跑一遍，求出一个方案。

这样可以轻松获得很多分。

以上做法很难让人满意。如果想得到更优的解，我们还是来观察每个测试点。

Case 1

所有子弹摆成“Touhou”的图形， $T = 100$ 。

这个测试点直接手玩就行了，可以擦到每一个子弹。

Case 2

你在一个正方形的四个角上来回跑，每个时刻在每个角上有一定概率会出现子弹。有10000个长度不超过20的时间区间， $T = 1000$ 。

这个测试点可以用DP来解决：

$f [i] [p o s] [t]$ 表示当前时间为 $i$ ，当前位置为 $p o s$ ，已经连续 $t$ 秒未中弹的最大得分。

Q: 不考虑走对角线吗？

A: 参见touhou2.in第三行。第一颗子弹位置在 $(5, 5)$ ，半径为 $7$ ，故走对角线必撞。

Case 3

所有子弹排成一个16行的三角形，从上往下子弹的分数呈指数级递增， $T = 30$ 。

这样很容易想到一道叫做“数字三角形”的DP题。

但是很不幸，由于出题人的疏（gu）忽（yi），你可以直接杀到最底下一行去，在最底下一行擦十几个子弹。

最后别忘了在倒数第二行也擦一个。

本测试点灵感来自NOI2010 成长快乐第7个测试点。

Case 4

所有子弹排成一个60行的三角形，从上往下子弹的分数呈指数级递增， $T = 1200$ 。

这样很容易想到一道叫做“数字三角形”的DP题。

但是很不幸，因为每隔20秒才会出现一行子弹，这次真的是数字三角形。

对了，时间允许你在最后一行擦两个子弹。

P.s.:可以发现，相邻两行的距离是 $9 + 2 \sqrt{2}$ ，同一行的相邻两个子弹的距离是 $8 + 4 \sqrt{2}$ 。这两个神秘的常数是怎么回事呢？

$\frac{9 + 2 \sqrt{2}}{8 + 4 \sqrt{2}} = 0.8661165235168155944989445473689 . . .$

这个数和 $\frac{\sqrt{3}}{2}$ 非常接近。啊，等边三角形！（大雾

本测试点灵感来自NOI2010 成长快乐第8个测试点。

Case 5

你身处一个迷宫之中！迷宫的墙全部由可以擦的子弹组成。你必须在 $T = 706$ 以内从起点到达终点。

有若干个高额Bonus：在特定的时间到达特定的地点可以获得Bonus。

这个怎么玩呢？

你定睛一看，整个迷宫呈一棵树的结构， $T$ 正好可以让你遍历整个迷宫然后走到终点。

你又定睛一看，所有的高额Bonus对应着这棵树的所有叶子结点！

这时可以大胆猜想：只要沿着Bonus的指示走，就可以在规定的时间内遍历整个迷宫到达终点，同时获得所有的Bonus！

这个猜想是对的。

然后就是写一个树的遍历了。

Case 6

你又身处一个更大的迷宫之中！迷宫的墙全部由可以擦的子弹组成。你从起点出发，在迷宫内任意游玩，必须在 $T = 4798$ 的时间回到起点。

有1个高额Bonus：在特定的时间到达特定的地点可以获得Bonus。

这个又怎么玩呢？

你定睛一看，整个迷宫呈一棵树的结构， $T$ 正好可以让你遍历整个迷宫然后回到起点。

这时可以大胆猜想：一定可以在规定的时间内遍历整个迷宫回到起点，同时获得Bonus！

那么我们怎么拿到Bonus呢？

对到达Bonus的路径以外的所有子树进行一次背包，看哪些子树需要在获得Bonus之前走，哪些子树需要在获得Bonus之后走。然后就是根据你得到的结果搞出具体的路径。

Case 7

从 $(200, 240)$ 点向四周高密度地发出高速子弹，你位于正下方的 $(200, 480)$ 。你如果能躲过全部子弹将获得9600000分的巨额奖励。 $T = 2640$ 。

由于子弹速度快、密度大，你可以忽略上下的移动，只在左右躲避这些子弹。

这样就可以看成是“接馅饼”的DP啦。

Q: 妈呀，这子弹看着太可怕啦！根本躲不过去啦！我宁愿放弃奖励，直接去 $(200, 240)$ 擦到所有子弹。

A: 恭喜你得到本测试点的正解。

本测试点灵感来自《东方神灵庙》6面BOSS丰聪耳神子的符卡光符「Guse Flash」（救世之光）。

Case 8

你在 $200 \times 2000$ 的矩形的最下面，有一大堆子弹高速飞过来。躲过全部子弹将获得1000000分。

这个数据的特点比较难看出来：每一个子弹都有一个时刻会达到离直线 $y = x + 1800$ 相当近的地方。

如果只沿着这条斜线走，这样就可以看成是“接馅饼”的DP啦。

本测试点灵感来自NOI2010 成长快乐第6个测试点。

Case 9

你在 $400 \times 100$ 的矩形内，一大堆子弹纯随机地飞过来。每180秒是一个阶段，每个阶段躲过全部的子弹可以获得200000分，然后使擦弹分尽量高。

这个数据的特点同样比较难看出来：

如果你把每个阶段里每个子弹的轨迹画出来，那么可以发现中间有位置一定不会被子弹打到；

如果你画子弹轨迹时按照分数的高低使用不同的颜色，那么可以发现有一个位置周围所有的子弹分数都相当高。

这个是故意这样设计的：有一个位置周围所有子弹的分数都是1900+，其它子弹的分数1000+的概率都很低。

如果你能成功发现这个位置，那么就去试一试怎么走到那里吧。

本测试点灵感来自《东方妖妖梦》6面道中BOSS魂魄妖梦的符卡六道剑「一念无量劫」。

Case 10

最后一个测试点本来是纯随机，但是vfk不干，说必须要能搞出最优解，然后就变成现在这个样子。

你在 $100 \times 100$ 的矩形内，每步走的距离是 $0.1$ 。 $0 - 3000$ 的时间里你要从 $y = 0$ 走到 $y = 100$ ， $3000 - 6000$ 的时间里你要从 $y = 100$ 走回到 $y = 0$ 。

有若干个圆形的子弹作为障碍物挡在路上。

这个嘛，如果将这些障碍物的图画出来，你会发现中间只有一条通路能过去。然后就是考验你计算几何的时间了。

Q: 为什么擦弹范围要搞这么大呢？

A: 擦弹范围大，意味着你必须要贴着子弹的边走才能获得更高的得分。去的时候贴着一边走，回来的时候贴着另一边走。

听说有人不会观察数据特点

大家好人群中钻出一个vfk。NOI Linux上有python哦！有python哦！

import Image
import ImageDraw
from math import *

w, h, x0, y0, d, r, R = map(float, raw_input().split())

n = int(raw_input())
q = []
for i in range(n):
    q.append(tuple(map(float, raw_input().split())))

nk = int(raw_input())
qk = []
for i in range(nk):
    qk.append(tuple(map(float, raw_input().split())))

nt = int(raw_input())

z = 5

mvs = raw_input()

for t in range(nt + 1):
    im = Image.new('RGB', (int(w) * z, int(h) * z), color='white')
    dr = ImageDraw.Draw(im)
    for (ta, tb, xq, yq, vx, vy, rq, g) in q:
        if ta <= t <= tb:
            cxq, cyq = xq + vx * (t - ta), yq + vy * (t - ta)
            cxq *= z
            cyq *= z
            rq *= z
            if rq < 1:
                rq = 1
            dr.ellipse((cxq - rq, cyq - rq, cxq + rq, cyq + rq), fill='red')
    im.save('%04d.png' % t)

The End

本题的出题灵感是陈老师的傲娇少女幽香系列。在看了ZJOI2015的题目以后，大家可以深深地感受到陈老师对东方、对幻想乡、对傲娇少女幽香的热爱。

受此启发，我也想出一道关于东方Project的题目，于是这道题目就展现在大家的面前，还是与东方Project原作有关的题目呢。

虽然在vfk魔改了题面之后，已经完全看不出来和东方Project有关的内容了TAT……

感觉UOJ Round只有三个小时，对这道题来说有些短吧，尤其是在还有前两题的情况下。比赛结束以后再来看一看，也许是一道相当好玩的题目吧。

最后，请点击这里。

Special Thanks:

ZUN（上海爱丽丝幻乐团）

WJMZBMR

vfleaking

唐文斌（NOI2010 成长快乐出题人）

And you...

Thank you for playing!

vfleaking的博客

博客