2017 China Collegiate Programming Contest Final (CCPC2017)

Problem A

Solved by dreamcloud.00:08:07

题意：

题解：

Problem B

Unsolved.

题意：

题解：

Problem C

Solved by oxx1108.00:33:54(-2)

题意：

题解：

Problem D

Unsolved.

题意：

题解：

Problem E

Solved by dreamcloud.00:18:27

题意：

题解：

Problem F

Unsolved.

题意：

题解：

Problem G

Solved by oxx1108.02:24:42(-1)

题意：

题解：

Problem H

Unsolved.

题意：

题解：

Problem I

开这道题目仅仅是因为清晰度极高的图片吸引了我。

Solved by Xiejiadong.04:53:38(-4)

题意：联通且颜色相同的边算作一组，会有$m$次修改，求每一次修改以后的组数。

题解：我们用$f[i]$表示结点$i$连出去的边所拥有的颜色数量，因为直接$\sum f[i]$会有$n$条边重复计算，所以一个图上的总的组数就是$\sum f[i]-n$

但是应该很容易的注意到一种特殊情况：当基环树环上的颜色相同时，我们应该把答案变成$\sum f[i]-n+1$

这样一来，我们就可以直接在线处理了

PS：dfs中要用来遍历路径的迭代器开成了全局变量，一口巨锅飞向cmy

Problem J

Solved by Xiejiadong.03:59:12

题意：给出$n$个时刻两个人分别在的位置，求一种可行的相邻车站之间所要花费的时间，使得满足限制条件。

题解：查分约束系统。对于形如$\|d_i-d_j\| \le x$的式子，我们可以条件负号，是的所有的不等式同向，然后添加边$cost(i,j)=x$，在图上直接跑最短路径即可。

这道题目，我们对于两个人都是同时在一个站台的，及a a b b形式的，我们需要两个约束条件

Problem K

Solved by Xiejiadong.00:15:55

题意：

题解：