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

From EOJ Wiki
Jump to navigation Jump to search
Line 71: Line 71:
  
 
题解:我们用$f[i]$表示结点$i$连出去的边所拥有的颜色数量,因为直接$\sum f[i]$会有$n$条边重复计算,所以一个图上的总的组数就是$\sum f[i]-n$
 
题解:我们用$f[i]$表示结点$i$连出去的边所拥有的颜色数量,因为直接$\sum f[i]$会有$n$条边重复计算,所以一个图上的总的组数就是$\sum f[i]-n$
 +
 +
但是应该很容易的注意到一种特殊情况:当基环树环上的颜色相同时,我们应该把答案变成$\sum f[i]-n+1$
 +
 +
这样一来,我们就可以直接在线处理了
  
 
== Problem J ==
 
== Problem J ==

Revision as of 07:31, 28 August 2018

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$

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

Problem J

Solved by Xiejiadong.03:59:12

题意:

题解:

Problem K

Solved by Xiejiadong.00:15:55

题意:

题解: