2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest(Gym 102222)

来自PC Wiki
跳到导航 跳到搜索

Records

Contest

Solutions

A(Solved by : lzy)

维护栈的同时维护栈的前缀最值即可.

B(Solved by : lzy)

本质上是若干个圆弧,算好半径和转角即可.

C(Solved by : zhn)

凯撒加密,直接按照题意模拟即可

D(Solved by : lzy & zhn)

其实很简单的结论,按顺序进飞机的答案是$$\frac{1}{2}$$

随机进飞机的答案是$$\frac{n + 1}{2 * n}$$

具体分析的话,就是枚举丢票的人是第几个进飞机的,坐的几号位置,然后转化为子问题.

E(Solved by : zhn)

按题意模拟即可,题意简直不可描述,难度在于看懂题目在说啥.

F(Solved by: sqc)

Floyd,按$$r$$大小枚举中转点

G(Solved by: sqc)

树形背包,假设这个子树选了$$x$$个叶子,贡献就是$$x*(k-x)*w$$

复杂度参考树形背包合并的复杂度

坑点是$$n=k=2$$时,没有非叶子点

H(Solved by : zhn & lzy)

考虑如果打一个怪兽一定先把这个怪兽打死是最优的.

对所有怪兽进行排序,排序的标准的两个怪兽谁先打会让人受到的伤害较小.

I(Upsolved by:zhn)

首先LIS长度为n-1的新序列一定是1,2,...n选择一个区间[l,r],循环左/右移一位形成的

同时冒泡后的新序列的第i项一定是原序列前min(i+k,n)项中未在新序列前i-1项中出现的最小值

所以得到初步结论:对于i=1~n对于新序列第i项,若前i-1项中没有比它大的数,那么它可以在原序列min(i+k,n)-(i-1)个位置任意放置,否则找到最大的j使得a[j]>a[i],则它只能在j之后取位置

进一步,除了最后k个位置外,min(i+k,n)-(i-1)=(k+1),所以是(k+1)的若干次幂,而最后k个位置贡献系数是k!,且一定是最大的k个数n,n-1,n-2,....

而且对于后面那种情况,实际上数值下降时可选位置只有一个,归纳可知只要前面有比它大的值,贡献系数就是1

所以答案就是枚举从1开始的上升子序列长度len,计算n个数时长度为len时的排列个数,然后乘上(k+1)^len*k!,所有len答案加起来就可以了

需预处理出所有LIS长度大于等于n-1的排列并计算len,复杂度$$O(n^4+Tn)$$

J(Upsolved by : sqc)

PQ两侧的点显然不能共存,因此我们分两种情况考虑,最后将两个答案取较优的那个.

考虑在PQ同侧的点$$A_1, \cdots, A_m$$,我们按照∠APQ排序后,按∠AQP做一遍LIS即可求出互相包含的情况.

要求字典序的LIS是经典问题,有多种方法可解决,任选一种即可.

K(Solved by : lzy)

折半之后二进制枚举,保证两边点内部是点覆盖的情况下计算每种情况的值.

之后对第一部分做高维前缀和,枚举第二部分的情况,算出构成全图点覆盖的情况下第一部分点的最小集,事实上就是算出了所有第一部分和第二部分构成点覆盖的情况.

计数即可,复杂度为$$O \left(2^{\frac{n}{2}} * (\frac{n}{2})^2 \right)$$

L(Upsolved by : lzy)

考虑一个区间如果合法,那么有$$\text{max} - \text{min} + 1 = \text{cnt}\Leftrightarrow \text{max} - \text{min} - \text{cnt} = -1$$.

其中$$\text{cnt}$$是不同的数的个数.

枚举区间右端点,利用线段树直接维护左端点的区间值,用单调栈区间维护$$\text{max}$$和$$\text{min}$$,对$$\text{cnt}$$则记录当前位置的数最近一次出现的位置即可.

考虑对任意区间$$\text{max} - \text{min} - \text{cnt} \geq -1$$,我们计算区间最小值以及个数即可.

M(Upsolved by: sqc)

考虑大致想法是求出完全二部图色数多项式,然后按题意代入$$-1$$得到$$DAG$$定向的方案数

定义:$$D(G,k)$$为将图$$G$$划分成$$k$$个完全图的方案数(不能为空),$$f(G,k)$$为图$$G$$的$$k$$染色方案数,

$$S(n,m)$$为将$$n$$个不同的球放到$$m$$个相同的盒子里的方案数,并且每个盒子非空(第二类斯特林数)

引理1:对于一个$$n$$阶完全图$$K_{n}$$ , $$D(K_{n},k)=S(n,k)$$

证明:考虑将$$K_{n}$$是个完全图,所以任取它的一些点生成的子图也是完全图,所以实际上就是将$$n$$个点划入$$k$$个集合,点之间两两不同,集合顺序可以互换,这个的组合意义就是斯特林数

引理2:对于一个一般图$$G=<V,E>$$,它的$$t-$$染色数$$\sum_{k=1}^{t} {f(G,t) = D(K_{n}-G,k)*t^{\underline k}}$$

(其中$$t^{\underline k}$$为$$t$$的$$k$$次下降幂)

证明:考虑若$$G$$的补图中有一个点集$$S$$,$$S$$中的点两两均不存在边相连,那么这个点集中的点可以染成同色,这样就可以将图分成$$k$$块

划分的方案数就是$$D(K_{n}-G,k)$$(按补图中的团划分)

染色的方案数就是$$t^{\underline k}$$($$t$$种颜色涂到$$k$$块上,第一种有$$t$$种选择,第二种有$$t-1$$种,……)

然后由于划分非空,所以需要求和来算上前面划分不满t块的方案数

回到这个题目

$$G=K_{m,n}$$,因此$$f(G,t) = \sum_{k=1}^{t} {D(K_{n+m}-K_{n,m},k)*t^{\underline k}} = \sum_{k=1}^{t} {D(K_{n} \bigcup K_{m},k)*t^{\underline k}}$$

因为这里是完全二部图,所以补图里的$$K_{n}$$和$$K_{m}$$中不能出现颜色相同的点

而在划分中,这两部分独立,可以分别计算,是$$S(n,i)*S(m,j)*[i+j=k]$$

这样展开一下,$$f(G,t) = \sum_{k=1}^{t} { \sum_{i=1}^{k} \sum_{j=1}^{k} S(n,i)*S(m,j)*[i+j=k]*t^{\underline k}}$$

变形一下就是$$f(G,t) = \sum_{k=1}^{t} \sum_{i+j=k} {S(n,i)*S(m,j)*t^{\underline k}}$$

然后代入题目中的$$t=-1$$ , $$f(G,-1) = \sum_{k=1}^{t} \sum_{i+j=k} {(-1)^{k}*S(n,i)*S(m,j)*k!}$$

令$$c_{k} = \sum_{i+j=k} {S(n,i)*S(m,j)}$$

得到$$f(G,-1) = \sum_{k=1}^{t} c_{k}*(-1)^{k}*k!$$

然后我们发现$$c_{k}$$可以看成 $$a_{i} = S(n,i)$$和$$b_{j} = S(m,j)$$的卷积

因此只需要拿这两个做一次FFT

考虑怎么求这两个东西

由斯特林数的容斥形式:

$$S(n,m) = \frac {1}{m!} \sum_{i=0}^{m} {C(m,i)*(-1)^i*(m-i)^n}$$

展开组合数得:

$$S(n,m) = \sum_{i=0}^{m} {\frac {(-1)^i}{i!} * \frac{(m-i)^n}{(m-i)!}}$$

是卷积形式,FFT

这里因为是任意模数FFT,需要用到MTT的板子

这样本题就做完了