ICPC2016 香港解题报告

Posted on By 二价氢

A Colourful Graph

给定一个不超过100个点的无向图,点有颜色,现在要改点的颜色,每次可以进行以下几种操作中的若干种。

  1. 将若干条边两边的节点的颜色交换
  2. 某条边两头的一个节点的颜色变成另一个节点的颜色

求在两万步内完成这些操作

解法

Tag: 暴力

按照下面顺序完成操作即可:

  1. 暴力交换某条链两端的颜色(至少有一边的颜色为对面的目标颜色)
  2. 暴力将某条链一端的颜色变成另一端的颜色(要求不能进行前面一种操作)

任意一项操作之后,颜色不对的点数至少减少1,同时每条操作至多产生200次交换,因而可以解决此题。

B Doors

题目大意

平面上有两堵墙,长度为无穷大,分别在的位置上,每堵墙上的地方上有一扇门,门的轴在处,的门开门的角度分别为

现在有一个圆在的位置上,需要将它移动到处,问它的半径的最大值。

解法

Tag: 计算几何

分情况讨论:

Case 1: 两扇门的角度均大于90度。此时第一扇门仅需考虑门框,同时计算第二扇门与上面那堵墙的距离即可,答案为

Case 2: ,此时需要考虑的是第一扇门的门缝和第二扇门与上面那堵墙的距离,在1的基础上,答案还应与取小

Case 3: ,此时需要考虑门B与门A的距离,和门A转轴与门B的距离

Case 4: ,此时需要考虑门A转轴与门B的距离

Code

C Playing with Numbers

题目大意

给定50000个形如的数,现在要对其进行以下两个操作:

  1. 取两个数A, B将gcd(A, B)放回去
  2. 取两个数A, B将lcm(A, B)放回去

现在要进行次操作1,和次操作2,顺序任意。你的任务是对于所有可能的,求出最后得到的数的最大值与最小值。

做法

Tag: 数学

猜想1: 最大值与最小值最多只有3种

猜想2: 最大值的取得,一定是先进行若干次gcd,再进行若干次lcm,最小值的取法相反。

**猜想1的证明: ** 设,则最大值一定是,取得这个值最多需要两次lcm操作,而最小值一定是,取得这个值同样最多只需要两次gcd操作,因此显然最大值与最小值的取值最多只有3种。

**猜想2的证明: ** 如果某次lcm操作不在最后,那么将其放在最后答案不会变小,如果某次gcd操作不在最后,那么把它放在最后答案不会变大。

通过这两个猜想,我们发现问题在于,如果只进行一次gcd或者一次lcm,如何取得最小值与最大值。

解决这个问题并不难,只需要枚举最后gcd的那个数,或者lcm的那个数,进行计算即可。同时计算的时候只需要取,因为通过枚举可以发现

Code

D Peak Tram

(TBD)

E Peak Tower

(TBD)

F Perfect k-ary Tree

(TBD)

G Scaffolding

(TBD)

H Slim Cut

(TBD)

I Special Tour

(TBD)

J Taboo

题目大意

给定若干个长度和不超过20000的字符串集合,求一个最长的字符串,使得任何不为的子串。

做法

Tag: 字符串, 数据结构

考虑AC自动机

对于此题,可以将构建AC自动机,同时答案就是这个AC自动机删掉危险节点之后得到的图上的最长链,如果这个自动机上有环,那么答案就是无穷大。

找到这个最长链很简单,只需要bfs即可,我的做法是用SPFA找最长路。

Code

K Team Up

题目大意

给定有300000个集合组成的一个有重集,集合之间只有包含关系和相等关系。

现在要求这个有重集的尽量多的不相交子集,使每一个子集的并集为全集。

做法

Tag: 大力出奇迹, 数据结构

注意到集合之间只有包含关系和相等关系,这提醒我们,集合之间是一个树形结构,考虑使用树的方式实现。

仍然注意到集合之间是树形结构,这提醒我们,可以对叶子节点打标记,从而得出每个集合的最小超集,即可构建出这个树。

现在将每一个集合安放在这棵树上,然后用并查集维护每一个节点,同时暴力维护即可,可以证明,最差的复杂度是的(考虑近似于一条链的情况,在这种情况下,每一个节点的元素个数相等,此时要合并次,同时注意到每一层处理完之后的元素个数是单调不增的,但同时我们也发现,对于其它的情况,复杂度也是类似的)

虽然这么说,但是比赛的时候谁会想那么多,不要怂就是干大不了20啊(比赛时候,可以认为整个过程类似于归并排序,复杂度不会大于

Code