2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest ¶

排名	当场过题数	至今过题数	总题数
35/640	8	9	11

C¶

solved by JLK

题意¶

略

题解¶

枚举每个辅音字母的大小写状态，预处理出相邻的每个字符组的个数，然后$O(19^2)$计算。$O(2^{19}19^2)$

E¶

solved by JLK

题意¶

$n$个数的序列$a_i$，每次可以选择一个数，变成它的倍数。$\forall k \in [0,n]$，求出操作$k$次后的整个序列的最小的不同数的个数。

$1 \le n \le 3\times 10^5,1 \le a_i \le 10^6$

题解¶

首先对于一个数$x$，如果序列里有$y$，且$x|y$，那么可以花费（$x$的数量）的操作来减少一个不同数个数。

可以把所有存在倍数的数拉出来排序，从小到大贪心，每次取siz最小的一个数变成倍数，这样可以处理出一种策略。

还有一种策略，就是序列中变出了一个lcm，然后每个数都变成lcm，这样就没有倍数的限制（因为lcm一定是倍数）。同样贪心，取siz最小的一些数全部变成lcm。

$O(n\log n+a_i \log a_i)$

F¶

solved by YZW

题意¶

给出 $m$ 行仅由 for 与 lag 构成的代码，求 lag 语句时间复杂度 $C\cdot n^k$。

代码满足：仅是 for 的嵌套，并且 lag 在最内层且只出现一次。for x in range(l, r) 语句满足 x 是除 n 外的小写英文字母，l 与 r 是外层变量，另外 l 可以为 1，r 可以为 n。

$m\leq 21$。

题解¶

首先将变量（包括 $1$ 和 $n$）看作点。

一条 for x in range(l, r): 语句给出了限制 $l\leq x\leq r$，我们连有向边 $l\rightarrow x\rightarrow r$ 表示偏序关系。

容易发现，连边得到的有向图若存在环，则能执行 lag 语句当且仅当环上的所有点取值相等，因此可以将环缩点，并保留所有连边。

注意到所求的 $k$ 即为缩点后得到的 DAG 中除 $1$ 与 $n$ 外的自由变量个数。

接下来考察 $C$ 如何计算。观察样例，对于下述程序：

for i in range(1, n):
    for j in range(1, i):
        for k in range(j, n):
            lag

一个朴素的想法是利用离散求和维护多元多项式，提取 $n^k$ 项的系数，但是过程中会出现很多对答案无贡献的项。

考虑将变量取值范围均除以 $n$，此时有：

\[\begin{aligned}C=\lim_{n\to\infty}\sum_{i=1}^n{1\over n}\sum_{j=1}^i{1\over n}\sum_{k=j}^n{1\over n}=\int_0^1\int_0^i\int_j^1\mathrm{d}i\,\mathrm{d}j\,\mathrm{d}k={1\over 3}\end{aligned}\]

考虑积分意义，实际上积分求出的是自由变量 $i,j,k$ 在 $[0,1]$ 上任意取值时，满足 $0\leq i\leq 1,0\leq j\leq i,j\leq k\leq 1$ 的概率。

类似 Serval and Bonus Problem，我们只需考虑自由变量构成的排列满足上述条件的概率，容易发现，这个概率为缩点后只考虑除 $1$ 与 $n$ 外的自由变量构成的 DAG 的合法拓扑序数量除以 $k!$。例如对于样例，合法拓扑序数量为 $2$，因此 $C=2/3!=2/6=1/3$。

状压 DP 求出合法拓扑序数量即可，时间复杂度 $O(k2^k)$。

G¶

upsolved by TYB

题意¶

给出$n$个点，$m$条边的无向图，试求是否存在$S\neq T$，使得$S$到$T$有三条边不相交，点在起点和终点外不相交的路径，给出方案或判断无解。

$n,m\le10^5$

题解¶

赛时想到的做法：若有边数大于点数的点双连通分量，则存在一组解。考虑在其中随便找到一个环，去掉这个环上的边，一定还存在着环上两点的路径，否则与点双连通分量的定义矛盾。问题主要出在怎么找到一个点双连通分量里面的所有边。由于一个割点可能在多个连通分量里面，所以直接枚举连通分量中的点连出去的所有边复杂度不对。一开始我误以为不会存在割点和割点连的边，但这是错误的。后面我想到的方法是在Tarjan的时候额外多维护一个边的栈，在找出一个连通分量后也将对应的边出栈，这样虽能包括所有连通分量里面的边，但会存在重边和其他连通分量的边，还需要除去不合法的边和去重，比较麻烦。

多数人的简单做法：

求出DFS树，对于一条非树边$(u,v)$，暴力将$u$到$v$路径上的树边染上这条非树边的颜色。

若一条树边被染了两次色，则说明对应的两个简单环有公共边。

仅保留两个简单环，任取两个度数至少为$3$的点作为起点和终点，然后爆搜出所有路径即可，一定恰好有$3$条简单路径。

H¶

solved by TYB

题意¶

给出一个有根树的森林，要求把这些有根树连起来，得到一棵以$1$为根的有根树，不改变原来的父子关系，且新树的匹配数最大（通过一条边连接的两个节点可以匹配，一个点只能匹配一次），求出最大匹配数并给出方案。

$n\le10^5$

题解¶

首先求出每棵树是否使用根节点的最大匹配数，然后将树分为两类，第一类为使用根节点不能增加匹配数的，第二类为使用根节点可以增加匹配数的。对于第一类节点，其最优方案一定是在树内完成匹配，所以直接将这些树接在$1$所在的树的已匹配节点即可；对于第二类节点，按照未匹配节点个数从大到小排序，维护当前未匹配节点的集合，依次接入空节点即可。

I¶

solved by YZW

题意¶

签到，略

题解¶

J¶

**upsolved by **

题意¶

题解¶

K¶

solved by TYB

题意¶

给出一个$n\times m$的矩阵，初始全为$0$，要求把其中一些格子变成$1$，使得某个格子为$1$当且仅当其所在的行或列全为$1$，且$0$的连通块恰有$k$个，给出一组方案或判断无解。

$n,m\le100,1\le k\le10^9$

题解¶

显然使得连通块最多的方案形如： $$ \begin{aligned} 01010 \\ 11111 \\ 01010 \\ 11111 \\ 01010 \\ \end{aligned} $$ 即$\lceil\frac{n}{2}\rceil\lceil\frac{m}{2}\rceil$个连通块，所以只需判断是否存在$1\le a\le \lceil\frac{n}{2}\rceil,1\le b\le \lceil\frac{m}{2}\rceil$且$ab=k$即可。

L¶

solved by YZW

题意¶

签到，略

题解¶

记录¶

JLK过A(0:05)，YZW写L，WA了两次。

换TYB写K，WA了一次。

YZW改过了L(0:21)，然后JLK过B(0:28)。

TYB改过了K(0:36)。

JLK过C(0:46)。

YZW过I(0:51)。

JLK过E(1:26)。

TYB过H(2:39)。

YZW写F，WA了一次，JLK找到bug后AC(4:09)。

TYB写G，一直没过。

总结¶

TYB：图论太烂了，还是应该先从dfs树这种简单的想法开始。还有就是认真读题，认真对比输出是否和样例完全一致。

YZW：当心 __builtin_popcountll(x)！！！！

Dirt¶

F(-1)

K(-1)

L(-2)

2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest ¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest ¶