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

@@ 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 ==
-[[File:Aa28d5441d1cbfcbac9c0b9b4d67ff3e.jpg|400px|thumb|right|game]]
-开这道题目仅仅是因为清晰度极高的图片吸引了我。
-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
-题意：给你一个无限大的平面，从一个点开始，让马跳日，每一次可以跳八个方向，问第$n$次跳完后，一共占领了多少个地方。
-题解：手算或者bfs打表找规律，可以发现在$n\ge 4$以后，直接查分就可以得到等差数列
-可以推出公式就是$(n-6)*176+(n-6)*(n-7)*14+473$
-由于这道题目的答案会爆long long,所以需要用unsigned long long，但用unsigned long long需要注意公式里面$n-7$会出问题

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

Latest revision as of 07:59, 28 August 2018

Navigation menu

Search