2017 China Collegiate Programming Contest Final (CCPC 2017)

From EOJ Wiki
Jump to: navigation, search

Website

https://vjudge.net/contest/250470#overview

Problem A

Solved by dreamcloud.00:08:07

题意:超级签到题,1至n,任意排列,求有多少个数不在原位置的期望

题解:输出n-1即可。每个数在自己位置上的期望是$\frac{(n-1)!}{n!}$。

Problem B

Unsolved.

Problem C

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

题意:签到题

题解:分情况讨论一下即可,变量名敲反了wa了两发……

Problem D

Unsolved.

Problem E

Solved by dreamcloud.00:18:27

题意:超级大水题,输出从1到n的数乘以1.1求和。

题解:如上操作一番

Problem F

Upsolved by dreamcloud.

题意:n组人,每组$a_i$个人,每组要么全选,要么不选,总人数不超过m。设计多种选择方案,给每种方案一个概率,使得每个组被选中的概率相等,并最大化。(n <= 10)

题解:因为n很小,所以可以枚举$2^n$种方案,并且设选择每种方案为$x_i$,那么满足$\sum_{i=0}^{2^n-1} x_i = 1$,对于所有总人数超过m的方案,$x_j = 0$。设最后最后每个队伍被选中的概率为$x_{2^n}$,可以列出每个式子,对于i从1到n,满足 $\sum_{j = 0}^{2^n-1}{ 2^n and j}x_j = x_{2^n} $。用单纯形法可以解出$x_{2^n}$的最大值。

Problem G

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

题意:$n$个区间,取$k$个区间,使得这些区间并里不同的整数最多。

题解:三方的dp轻松推出来O(mnk),然后优化成平方。

对于区间长度那一维可以在更新完所有区间后再更新,那么复杂度为O(nk+mk)。

Problem H

Upsolved by oxx1108.

比赛时候oxx提出了正确做法,结果dreamcloud霸占着电脑导致没有能够顺利ac。

题意:给定$m$个$n$维的点,两两之间距离为1,求最多能加多少个点保证这一性质,并输出坐标。

题解:考虑从$m$个点加新的一个点的情况,只需要找到$m$个点所在的$m-1$维平面上的中心以及法向量,可以找规律发现新加的点离$m$维平面的距离为$\sqrt{\frac{m + 1}{2 * m}}$

中心非常好求,法向量则可以通过两点之间的中垂面(高维中不知道叫什么)的交线来确定,这个可以利用高斯消元求出来(没用的维数用1来代替,最后乘以距离的权重就可以)。

oxx列的方程是 $(\vec{p_{i + 1}} - \vec{p_{i}}) \times \vec{x} ^ {T} = 0$ ($p$是已添加的点,由于方程个数少于未知数,将未知数后若干位直接标为1就可以求出确定的向量了)。

Problem I

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中要用来遍历路径的迭代器开成了全局变量,一口巨锅飞向dreamcloud

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$会出问题