UOJ Logo vfleaking的博客

博客

UOJ Round #9 题解

2015-08-09 22:14:23 By vfleaking

电路手动分析

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!

评论

matthew99
shafa
taorunz
前排
wangyisong1996
后排膜
horse
伏地膜!
wzj
前排膜
Neverak
中排!
RAcceleratorPlus
膜.......orz
qmqmqm
伏地膜!
HJWJBSR
伏地膜!
cxzxxjd
@

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。