2013 ACM-ICPC Asia Chengdu Regional Contest

Contest Info

date: 2017.08.02 10:00-15:00

practice link

Solutions

A. Assignment For Princess

题目大意:给你一个 \(n(10\leq n\leq 80)\) 和一个 \(m(n+3\leq m\leq \frac{n^2}{7})\)。让你构造一个 \(n\) 个点 \(m\) 条有向边的有向图,满足无自环,任意两点之间至多只有一条边。并且:

  • 从任意点出发,可以到达任意其他点
  • 每条边的长度分别为 \(1, \dots, m\)
  • 你可以从任意一点出发,经过一定的点序列(边和点都可以访问多次),然后回到起点。任意的上述序列的总长度是 \(3\) 的倍数

题解:我们先构造一个环,让它的总长度是 \(3\) 的倍数。这显然是能完成的,我们先从 \(i(1\leq i < n)\)\(i+1\) 连长度为 \(i\) 的边,从 \(n\)\(1\) 的边讨论一下即可,因为 \(n+3\leq m\),所以总能满足。然后剩余的 \(m-n\) 条边,我们只用找到 \(u, v\) 满足它们之间不存在边,并且 \(\mathrm{dis}(u, v)\equiv w_i(\mathrm{mod}\;3)\),连上从 \(u\)\(v\) 的长度为 \(w_i\) 的边即可。

B. Beautiful Soup

题目大意:给出一段合法的 \(html\) 代码,要求你将其排版。

题解:只需要识别出三种 \(tag\) ,对应的去改变缩进的个数,以及处理一下其它部分的多余空格,换行和制表符即可。注意的是 \(tag\) 内的内容不能改变,以及判断 \(tag\) 类型的时候不能仅从是否有 \(/\) 去判断。

C. Clumsy Algorithm

题目大意:给你一个 \(1 \sim n\) 的排列 \(p\) ,定义一次操作为交换 \(p_{i}, p_{j}(i \not= j)\) ,代价为 \(2|i-j|-1\) .定义 \(f(p)\) 表示将 \(p\) 变成顺序排列的最小代价, \(g(p)\) 定义为 \(\sum_{i=1}^{n}\mathrm{max}(0,i-p_{i})\) ,现在给定 \(p\) 的长度为 \(k\) 的前缀,问满足 \(f(p)=g(p)\) 的排列有多少种。

题解:先证明 \(f(p)\) 就是 \(p\) 的逆序数。对任何交换 \(i,j(i<j)\) 的操作,我们都可以通过依次进行 \((i,i+1), \cdots, (j-2, j-1), (j-1, j), (j-1, j-2), \cdots,(i+1,i)\) 来代替,代价是 \(2|i-j|-1\) ,故最优解一定可以通过交换相邻元素得到。容易证明最小代价就是 \(p\) 的逆序数。 \[ \begin{aligned}\\ f(p)&=\sum_{i=1}^{n}\sum_{j=i+1}^{n}[p_{i}>p_{j}]\\ &=\sum_{i=1}^{n}i-\sum_{i=1}^{n}p_{i}+\sum_{i=1}^{n}\sum_{j=i+1}^{n}[p_{i}>p_{j}]\\ &=\sum_{i=1}^{n}(i-p_{i}+\sum_{j=i+1}^{n}[p_{i}>p_{j}])\\ \end{aligned}\\ \]

显然所有小于等于 \(p_{i}\) 的数都给 \(i+\sum_{j=i+1}^{n}[p_{i}>p_{j}]\) 做了 \(1\) 的贡献,所以有 \(i-p_{i}+\sum_{j=i+1}^{n}[p_{i}>p_{j}]\ge \mathrm{max}(0,i-p_{i})\) 。要求 \(f(p)=g(p)\) ,即要求对于每个 \(i\)\(i-p_{i}+\sum_{j=i+1}^{n}[p_{i}>p_{j}] = \mathrm{max}(0,i-p_{i})\) ,若 \(i-p_{i}<0\) ,等价于 \(p_{i}\) 左边的都小于 \(p_{i}\) ,若 \(i-p_{i}\ge 0\) ,等价于比 \(p_{i}\) 小的都在 \(p_{i}\) 左边,即要求 \(p\) 的每一个位置都满足前述两个要求之一(这和最长下降子序列长度小于等于 \(2\) 是等价的)。我们用 \(dp\) 来计数。不考虑前缀,设 \(dp[i][j]\) 表示 \(\max\limits_{1 \le k \le i}p_{k}=j\) 的方案数,则转移方程为:

\[ dp[i][j]= \left\{ \begin{aligned} &1,&i=j=0\\ &\sum_{k=0}^{j-1}dp[i-1][k]+[i\le j]dp[i-1][j],&\mathrm{others}\\ \end{aligned} \right. \]

最后考虑前缀,容易发现这是唬人的。按照刚刚说的验证一下就好了。复杂度 \(O(n^{3})\)

D. Dinner Coming Soon

题目大意:你有一个 \(n\) 个点 \(m\) 条有向边的有向图。每条边花费一定的时间,和一定的金钱。你需要在时间 \(T\) 内从点 \(1\) 到达点 \(n\),并且花费的金钱越少越好。

你可以在路途中买卖盐,每个点提供每袋盐的单价,你可以利用差价来赚钱。每次你到达一个点的时候(除了点 \(1\) 和点 \(n\)),都可以买一袋盐,卖一袋盐,或者什么都不干。你身上最多只能带 \(B\) 袋盐,并且从 \(1\) 出发的时候身上没有带盐。交易时间忽略不计。

你有一个可以在 \(K\) 个平行宇宙中穿行的设备,平行宇宙标号为 \(0, \dots, K-1\)。初始你在平行宇宙 \(0\),到达点 \(n\) 的时候也需要在宇宙 \(0\)。当你在宇宙 \(i\) 中使用设备的时候,你可以到达宇宙 \((i+1)\; \mathrm{mod}\;K\) 中的相同地点。使用设备消耗 \(1\) 个单位时间。不同宇宙中每个点提供的盐的单价可能不同,但是每条边的时间和金钱花费相同。除了在宇宙 \(0\) 以外,在其他的宇宙中不能访问点 \(1\) 和点 \(n\)

你初始有 \(R\) 金钱,你需要输出在 \(T\) 时间内到达点 \(n\),并且满足中途任意时刻金钱数非负的,最终最大剩余金钱数。

\(2\leq n\leq 100, 0\leq m\leq 200, 1\leq B\leq 4, 2\leq K\leq 5, 0\leq R\leq 10^5, 0\leq T\leq 200\)

题解:动态规划,考虑状态 dp[i][j][k][t] 表示时间为 \(i\),在点 \(j\),在宇宙 \(k\),当前点交易完成之后身上有 \(t\) 袋盐的最大金钱数。注意到时间是递增的,所以没有后效性。直接枚举状态,然后向后转移即可。限制条件比较多,需要小心一点。

E. Exhausted Robot

题目大意:给你一个平行于坐标轴的矩形房间,房间中有一些家具和一个清洁机器人,它们都是凸多边形。机器人可以在房间内平移,但是只能清洁第一个点所在的位置,并且如果它与家具相交或者有部分超出了房间就不能进行清洁。问机器人能清洁的面积。

题解:zzh 和计算几何有仇系列。感谢昂神的代码

首先容易想到的是根据机器人最左、最右、最上、最下的点缩小矩形的边界。之后我们对每个家具分别考虑机器人被它阻挡的部分,应该是机器人的所有顶点绕着家具表面旋转时,清洁点围成的各个部分的并。这个并可以通过枚举家具的每个顶点与机器人的每个顶点重合时,清洁点所在的位置,然后把这些位置求个凸包来解决。

之后问题就变成了求一些凸多边形的面积并,使用扫描线来解决。

所有事件点包括多边形的顶点,多边形之间的交点和多边形与矩形边界的交点。在事件点之间,容易发现多边形们不改变相对位置,所以这些多边形在每两条相邻的扫描线中形成了一些三角形和梯形,它们互相要么完全包含,要么互不相交。计算它们的面积时我们选取这两条扫描线中间的直线,根据它与多边形们相交的状况计算它在多边形们内的长度,容易知道答案即为长度乘以两条扫描线之间的距离。

F. Fibonacci Tree

题目大意:给你一棵边上黑白染色的树,问你是否存在一棵生成树,满足树中白边的数量是 Fibonacci 数(\(1, 2, 3, 5, 8, \dots\))。

题解:白边权值为 \(1\),黑边权值为 \(0\)。分别做一次最大和最小生成树,如果区间中有 Fibonacci 数,那么一定可以达到。

G. GRE Words Revenge

题目大意:给你两种操作:

  • 往字典中加入一个 \(01\) 字符串
  • 给出一个 \(01\) 母串,问你母串中有多少个子串在字典中出现

题解:用 ac 自动机来维护字典。如果每次询问之前都去构建 fail 指针,那么显然时间复杂度是不符合要求的。我们用两个 ac 自动机来维护这个字典,每次插入字符串到小的 ac 自动机中,然后暴力构建 fail 指针。如果小 ac 自动机的大小达到了 \(\sqrt L\) ,那么我们暴力合并到大 ac 自动机上,暴力构建 fail 指针。

需要注意的是暴力重构的 ac 自动机不能写成 trie 图的形式。

H. Hard Disk Drive

签到题

I. ICPC Ranking

unsolved

贴一个昂神的Code

J. Just Random

题目大意:求 \(\displaystyle \sum_{i=a}^{b}\sum_{j=c}^{d}[i+j\equiv m(\mathrm{mod}\ p)]\)

题解:直接算不太好算,但是转化为求 \(ans([0,b], [0,d])-ans([0, a-1], [0,d])-ans([0,b], [0, c-1])+ans([0,a-1], [0,c-1])\) 以后,每一个就好算了。

Replay and Summary

Replay

补充训练赛惯例在校车上开题,看了两眼就对这场比赛有了一个直观的印象:题面很长。。。

W 先看的 J,然后发现是一道似乎不是很难的数学题,推一推式子就可以了,就交给了 Z。Z 说到机房就能写,然后说 H 是签到题(正好是 W 觉得太长不看的题)。

于是到机房之后 Z 先 A 了 H,然后没过多久也 A 了 J。

W 在车上就看了 G,跟 D 讨论了一下,感觉用两个 ac 自动机,然后根号暴力合并求 fail 似乎可行。于是 W 到了机房就开始写 G。结果吃完饭都还没过。后来检讨了一下暴力合并的 ac 自动机显然不能写成 trie 图,而且指针的写法也不够优秀,梦回数组。调试了几发就开心地拿到了一血。

然后 W 感性理解了一下 F 的过题人数,觉得直接最小最大生成树搞一下,然后傻逼地没处理无解,感人肺腑。

然后 Z 据说猜了一个 C 的结论,wa 了一发之后静态看了看代码然后过掉了。又是一血很开心。

W 之前理解错了 A 的题意,写了个垃圾玩意儿交了几发,看 Z 没事情做就叫过来一起看题。然后发现自己傻逼了,正确理解题意之后也很快过掉了。

D 从到机房开始一直刚 B,期间 wa 了几发。W 帮他造了数据之后发现是没处理 text 中的 /。检讨了一下以后应该相互出数据,也过掉了。

总的来说这场还是不错,就是以后补充训练应该更紧张一点,在现场赛之前应该抓住每一场训练的机会。

coldwater

这场做了 AFG,罚时比较爆炸。对 ac 自动机还是不够熟练,明明要暴力合并重建,一开始还写了一个指针的 trie 图,感觉很智障。然后 A 读错了题也需要背锅。这场没有监督队友紧张起来,场面一度十分休闲,导致 D 题被 A 穿了然而竟然没人读题。最后四十分钟秉持着不能放弃地原则把 D 题磕磕绊绊读完了然而还是没什么想法,样例也没有在草稿纸上通过。以后还是要监督队友,关心一下进度,把锅分好。

ShinriiTin

在校车上读了 A 和 B 的题面,感觉题目很长很烦,懒得去读其它题了,就先开了 B ,写完之后交 wa 了, 调了很久也没有找到 wa 的原因,最后 W 从某个网页上扒下来源代码试了下,发现我处理 tag 的时候如果里面有很多个 / ,我会把它判为 blank tag,然后改掉就 a 了,然后发现队友们已经做完六道题了,于是这场就摸的透彻啊。 其实那个 wa 点在题面中的 example 里就已经出现了,但是没在样例里面我就没有用来测试,以后 debug 的时候这种例子也应该全都用上。还有就是正式的比赛就不能像今天这样死磕一道题了,要合理分配时间,有问题多和队友交流。

zhongzihao

这场题面可以说是又臭又长,看着难受。先是写了签到题 H ,然后 J 是个很水的计数也很快过掉了,后面我的题有 C 和 E ,C 题猜了个结论莫名其妙就 A 了,连我自己都不知道是怎么想到的,最后还有个计算几何 E 不会,这个也是比较遗憾的,进一步说明了我计算几何太菜,以后还是要加油。