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形式的,我们只需要一个约束条件$b-a\le x$
而对于其余形如a b c d型的,我们则需要两个约束条件$c-b\le x-1$,$d-a\ge x+1$
最后所有的$d[i]-d[i-1]$就是我们所求的答案
Problem K
Solved by Xiejiadong.00:15:55
题意:
题解: