电路手动分析

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 wh$，要求最大化 $4k - 2(w + h)$。

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

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

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

于是这题就解决啦！

App 管理器

from taorunz

题意简述

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

算法一

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

期望得分：30分

算法二

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

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

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

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

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

算法三

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

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

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

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

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

而我们可以发现，$S$里的任何点都可以到达$v$的，如果某个$s$到$v$不经过$u$，那么 $u-\dots\rightarrow s- \dots \rightarrow v$ 就是一个不经过那条边的路径，与假设矛盾。所以$S$里任何一个点到达$u$都不用经过$v$。同理$T$里的点到达$v$都不用经过$u$。考虑$S$和$T$集合之间的边，除了$u-v$之外一定还有一条边（注意基图是双连通的），不妨假设这条边是从$S$里面的某个点$p$到达$T$里面的某个点$q$的，那么$u-\dots \rightarrow p \rightarrow q- \dots \rightarrow 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][pos][t]$表示当前时间为$i$，当前位置为$pos$，已经连续$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}$。这两个神秘的常数是怎么回事呢？

\begin{equation} \frac{9+2\sqrt{2}}{8+4\sqrt{2}}=0.8661165235168155944989445473689... \end{equation}

这个数和$\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\times2000$的矩形的最下面，有一大堆子弹高速飞过来。躲过全部子弹将获得1000000分。

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

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

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

Case 9

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

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

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

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

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

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

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

Case 10

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

你在$100\times100$的矩形内，每步走的距离是 $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!