Difference between revisions of "2017 China Collegiate Programming Contest Final (CCPC2017)"

From EOJ Wiki
Jump to navigation Jump to search
(Blanked the page)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
== 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
 
 
题意:
 
 
题解:
 

Latest revision as of 07:59, 28 August 2018