2018-2019 ICPC, NEERC, Northern Eurasia Finals

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

Records

Contest

Solutions

A

DP表示状态,然后转移即可.

B

考虑这样建图:

将骑士拆点成两个点,然后如果一个女士和骑士有边那么和这两个点都连边

然后一个骑士拆成的两个点之间连边

答案就是这个图的最大匹配数-$$n$$

考虑为什么这样做是对的:

首先没有女士和骑士有边的时候,那么显然骑士之间的边有$$n$$条,这时候答案是$$0$$

如果存在一个女士和骑士有边,那么匹配中选(女士,骑士)和(骑士,骑士)都无所谓

如果存在两个女士和骑士有边,那么一个bimatching对应的匹配就是选两个女士和骑士拆出的两个点连的两条边,而不选择骑士拆点形成的边

这样一个骑士被选的贡献是$$2$$,不被选的贡献是$$1$$

最后$$-n$$就行了

一般图最大匹配做个带花树就行了

C

考虑这个$$10$$次大概是$$\log n$$级别的

那么我们想到类似点分治的做法,使其可行解集大小每次减少一半以上

容易发现,可行解集是一个连通块

仙人掌有环,没法找重心,那么我们找一个点使其到所有可行解集中的点距离和最小,把这个当成类似重心的东西,每次大小就减半了

然后缩小可行解集的方法是利用GO $$v$$,把所有$$dis(x,u)<=dis(x,v)$$的点标成不可行即可

然后这里因为数据范围只有$$500$$,所以每次暴力找就行了

D

题解

核心思想是先不断将度为$$1$$的点与其相邻点合并

然后考虑题目的特殊条件,易知度数$$> 2$$的点不会太多,将它们作为特殊点分别BFS全图,然后考虑一些情况,做统计.

E

按$$n$$大小分几类构造构造就好了

F

考虑问题等价于从$$n$$的非$$1, n$$的约数中可重复地选取一些,使得和为$$n - 1$$.

最短路经典题,做就行了.

G

超过一周内总和时整除一下,小于等于一周内总和时模拟

H

I

考虑两个能形成一段排列的区间交集也可以形成排列,那么不合法的方案只会是若干个不相交的“小排列区间”或者一头一尾两个“很大的排列区间”

先考虑一头一尾的情况,因为两区间都是连续的,那假定1在前面的区间,然后考虑计算F[n]表示1~n的排列中,长度为2~n-1的前缀均不是排列区间的排列个数

$$F[n]=n!-\sum^n_{k=1}F[k]*(n-k)!$$

再考虑多个不相交区间的情况,那么这些区间最小长度为1,而且可以排序,然后考虑计算G[n][k]表示1~n排列中,按顺序将其划分成k个排列区间的排列个数

$$G[n][k]=\sum^n_{i=1}G[n-i][k-1]*i!$$

那么最终答案就是

$$ans[n]=n!-2\sum^{n-1}_{i=1}F[i]*(n-i)!-\sum^{n-1}_{i=3}G[n][i]*ans[i]$$

J

K

我们记第$$i$$个骑士的抵达时间和会见时间为$$t_i, d_i$$.

我们考虑$$T$$时刻的查询,于是有等待时间为$$\max_{t_i \leq T} \lbrace t_i + \sum_{t_i \leq t_j \leq T}d_j \rbrace - T$$

我们现在在不知道$$T$$的情况下, 不妨将这个式子维护到无穷远,当一个查询到来时,我们很容易发现只要在最终值上减去一个后缀和即可.

可以轻松利用线段树维护这个式子,后缀和可以再加一个BIT.

L

签到题

M

我们考虑每个SCC占据一层,那么现在要构造一个DAG出来.

考虑从拓扑序情况下从第$$i$$层向第$$j$$层坠落的情况,我们构造$$81$$个洞分别对应每种情况即可.