【转】ZOJ Monthly, August 2011 解题报告

貌似这博客好久好久没有更新了……为了填这个月解题报告,于是就更新一下吧:

顺便说一句,百度空间的格式控制真是烂到不能忍啊,连表格功能都没有

 

ZOJ Monthly, August 2011 解题报告

By 猛犸也钻地 @ FutureGazer

首先这是各个题目及AC情况:

————————————————–
Aya      Hello, Gensokyo         16.58% (349/2104)
Cirno    Fairy Wars              3.11% (9/289)
Flandre  Hide and seek           40.00% (2/5)
Mukyu    Bookcase                20.84% (251/1204)
Nitori   Crazy Shopping          20.00% (5/25)
Remilia  Disappearance           12.82% (15/117)
Suika    Weekend Party           5.11% (65/1270)
Suwako   Shinryaku! Kero Musume  10.98% (20/182)
Yuuka    Parterre                16.19% (108/667)
————————————————–

自从 @watashi 拿了冠军当了教练追到了妹纸后就开始了 [del] 骄奢 [/del] 淫逸的生活,所以本次 Touhou 系列题目没有被 shi 哥摸过,真的都是赤裸裸的简单题(误),共有⑨题。好了废话少说,以下是题解:

 

Problem Aya : Hello, Gensokyo

类型:签名题、构造

题意:幻想乡里 N 位少女,任意 3 位之间最多有两组百合关系(一条无向边),问这 N 位少女之间最多有多少组百合关系。

这题出完后过了几天就发现和 CodeForces 41E 撞车了,本想换一道题,想来想去想不出什么好的 idea,于是就这样挂出来吧,反正也是给人涨自信的题。做法很简单,想一想就可以想出来了:最优解一定是二分图,左边 n/2 个点,右边 (n+1)/2 个点,左右两两之间的边全都连上,这样任取 3 个点,还是满足条件的,而边已经极大了,也可以从 1 个点开始逐步构造地那样去想。

 

Problem Cirno : Fairy Wars

类型:悲剧的被各种水过去的题、线段树、树状数组

题意:TH 12.8 都玩过吧?给出 N 个子弹,一开始给出一个大圆,把半径 R 内的子弹先冰冻住,然后每个被冰冻住的子弹都会产生一个 L × L 大小的正方形冰块,被冰块碰到的其他子弹也会形成相同大小的冰块并产生连锁反应,问连锁反应结束后有多少颗子弹被冰冻住。

本来不是那么容易过的题,但数据还是悲剧了,有些 N^2 的算法或是一些其他不靠谱算法没能卡住,整理题目时就这题最难搞,折腾了很久的数据。标准解法是 YY 了一阵才想出来的:

将子弹划分进 (L/2) × (L/2) 的网格中,这样每个网格内部的子弹就能够互相冰冻,而一个网格内的子弹是否会冰冻,也只需要检查与之相邻的 8 个网格就行了。于是做法是这样,首先起始的大圆套住了一些子弹,把那些子弹所在的网格加入队列,从队列中依次取出一个网格,让它与相邻的 8 个网格(只需检查相邻的且未被加入过队列的网格就行了),分别地两两算一下内部子弹的最小距离,如果小于等于 L 则把那个相邻的网格也加入队列。两两算距离只需要对网格内的点排个序,用个线段树或树状数组维护一下并扫一遍就行了。

 

Problem Flandre : Hide and seek

类型:二小姐、大自然、lca、二分、树链剖分

题意:给出一棵树,边有权值表示两点之间的距离,现在有 M 次询问,每次询问会给出一组 A B L,表示如果在 A 和 B 之间新加入一条长度为 L 的边,那么所有点到 A 缩短的距离之和加上所有点到 B 缩短的距离之和为多少?

超难写的题,虽然先 LCA 然后再在树上二分的想法很容易想到,但是真的超难写的有木有!居然还有人真的在比赛时写出来了,太猛了有木有!仰慕楼教主以及 lch 神牛!

方法嘛,首先记 C = LCA(A,B),然后对于 A B 及向下的点(叶子)和 C 及向上的点(祖先)都很容易计算出结果,难点就在于 A – C – B 这个路径上的点的距离变化(也别忘了它们还有伸展出去的其他子树)。当然,在那个路径上,会有一组点 Ax 和 Ay,在 Ax – Ay 路径上的点到 A 的距离都是缩短的(图像大概是个单峰函数),同样也会有一组 Bx 和 By,为了找这些点,二分吧,树上做二分的方法也有不少,就不多说了。求和的话可以记个前缀和什么的,方法很灵活,用一个能写得出来的就行了。

一开始写标程时没写出来,后来神牛 @edward_mj 用了树链剖分搞定了,代码有 300 行,比赛时楼教主的 LCA 方法也有 250 多行,算法不难想,但就是难写死了,想要 AC 的同学加油写吧!

 

Problem Mukyu : Bookcase

类型:简单题、lis

题意:有一个 N 层书架,每层 M 本书,现在要将每层的书按 ASCII 码的顺序排序,每次可以取出一本书,插入到同一层某个位置,问最少的移动次数。

模型有些 old,最长不 XX 子序列,能看出来就行了,没留什么 trick,也没刻意卡时限,也不需要无视大小写的字典序排序,很厚道的题(其实我想说,明明就是出题人太懒了)。

 

Problem Nitori : Crazy Shopping

类型:背包、dag

题意:给出一个有向无环图,每个点卖一种物品,数量无限,问获得最大价值的情况下消耗的体力最少为多少。

不知为何比赛时很少有人过,或许和那密密麻麻一大堆描述有关系,结果大家都无视了这题。解法:拓扑排序一下,然后按照拓扑排序顺序,先在每个点上做无穷背包,然后再沿着边更新到其他点,就行了。

 

Problem Remilia : Disappearance

类型:线段树

题意:某个迷之生物诱拐了一群少女,已知被诱拐的少女满足 max(B) – min(B) <= LB,max(W) - min(W) <= LW,max(H) - min(H) <= LH,这三个条件,另外每个少女有一个熵值 S,问那个迷之生物通过诱拐少女,最多能获得多少负熵。

这题槽点很多,对吧?顺便说一下,题目名本来叫 The Disappearance of Hakurei Reimu,后来找图时刚好找到了那张图,于是就换主角了。做法是这样的:先按照 B 排序,扫描 B,依次加入或删除相应的少女到一个以 W 排序的集合,对每种 W 集合,再扫一遍,维护一个线段树。每次加入或删除时,在线段树的 H[i] ~ H[i] + LH 这段上加上或删除 S[i],某个时刻整棵线段树的最小值就是解。

 

Problem Suika : Weekend Party

类型:if-else、缩点了再dfs

题意:很多人来到博丽神社参加周末聚会,每个人都有各自的兴趣爱好(但在 ACG 范围内),问一种座位安排方式,使得任意一个人,和她相邻的两个人都有共同话题。

两种做法,可以缩点后搜索,或是用 if-else 判断出各种情况,单个兴趣爱好可以缩成一个,但多个兴趣爱好的至少要保留两个以上才行。标程的做法是 if-else,其实想清楚了也不麻烦。

 

Problem Suwako : Shinryaku! Kero Musume

类型:章鱼形图、dp

题意:给出 N 个点,N 条有向边,在某个点建造神社会获得一定的信仰,但如果这个点有一个有向边指向另外某个建造了神社的地点,那么那个点会失去一定的信仰。问最多能获得多少信仰值。

标题已经是剧透了(乌贼娘第二季期待中),不考虑边的方向,那么图中的每个连通子图都是一个环带上一堆长在环上的树。于是先搞定那些树的部分,从叶子往根dp。然后把剩下的环拆成链(假定某个点上造或不造神社),继续dp一下即可。

 

Problem Yuuka : Parterre

类型:简单题、暴力

题意:给出一个 N × M 的花坛,花坛是一圈一圈的,每一圈都是特定的一种花。现在给出 Q 次查询,问一个子矩阵,这个矩阵中有多少种花,哪种花最多,有多少个。

正如预计,过的人还是很多的。把每圈拆成四条线段,然后查询时就对最多 4N 条线段暴力做个相交,求出长度即可。另外稍微注意一下,在中心部分可能拆不出那么多线段。

 

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注