9.8~9.9联考模拟赛

解题报告

首先是各个题目的状况

A

签到题

自信写完90分

B

感觉有更优的选取策略：对于相同的一段字符串都取或者都不取

然后因为代码写错跳左右端点的时候多跳了一个位置就把答案剪没了。。。

C

啥题啊这是。。。

期望10分实际30

D

。。。
woc$\Theta(n^3)$的复杂度能过多少啊好虚啊

写太丑了。

dfs最后如果两个字符串的最长公共连续子串包含第n个字符那么答案会忽略这个位置。。。

E

调了一个半小时的错误思路代码。

然后又调了近一个小时的暴力

期望40

F

8分钟写出来1.36个K~~还拿了24分~~

以后谁TM再说我手速慢我就把这个记录摔他脸上

考场代码

A

B

C

D

E

F

正解思路及代码

A

签到题

被卡常什么的是最难受的。

注意到ai<=1e6

考虑对每个a[i]，维护其整数倍的出现次数

具体来讲：维护$maxx=\max_{i=1}^na[i]$，然后对所有的$a[i]$从它到$maxx$将$a[i]*k(k=1,2,3...)$出现次数+1表示$a[i]*k$在a数组中的约数个数+1

这里对每个数的约数个数维护用一个数组vis

最后输出时输出vis[a[i]]-1表示忽略其本身

正解代码

B

用s[a][i]表示对于字母a(注意不是'a')到i位置的总个数

那么答案就是某个(s[a][i]-s[a][j])-(s[b][i]-s[b][j])

稍做变形:(s[a][i]-s[b][i])-(s[a][j]-s[b][j])

那么考虑先维护最小的s[a][j]-s[b][j]，对于每个枚举到的i，再枚举a和b，求出s[a][i]-s[b][i]，然后减去前面已经存下来的s[a][j]-s[b][j]的最小值

正解代码

C

原题USACOSafe Travel安全出行

首先求出最短路树

最短路树就是假设点v由点p更新，则p向v连一条边

那么这题相当于是删除掉了从i到fa[i]的边，走的时候就是一条非树上路径和另外两条树上路径

这样我们只要求min{w(u,v)+d(u)+d(v)-d(f)}

枚举点f，统计答案时再用并查集维护u,v是否联通即可

正解代码

D

签到题

对于两个字符串，分别枚举最长公共连续子串的起始点

从两个位置开始往后走，把k次机会用完或者走到最后匹配完某个串

由于每次计算匹配数是最坏O(n)的，枚举两个起始点是O(n^2)

总复杂度O(n^3)

正解代码

E

容斥+状压

题目意思就是对一个有向图有多少边集是没有环的

考虑如何去不重不漏地统计某个有向图，运用拓扑排序，对图进行分层，每个点所在的层数为它入队的时间，那么这些点构成的数列是唯一的

对拓扑排序的过程进行dp，统计这样做出来的有向图是什么样子。

f[s][s']表示当前进行拓扑排序已经排序了s，最后一层是s'

然后加上q，要求q之间不能连边，只关心从s和s'向q连的边，那么q中至少要有1条边连向了s'（因为保证只有删掉s'之后q才度数为0）同时其他的边是可选可不选的

那么假设有x条边和q点连向了s'，有y条边连向了x，那么答案就是$(2^x-1)\times 2^y$（其中减去的1是空集）

如果q是一个点集那么q的代价就是$\prod(2^{x_i}-1)2^{y_i}$

另外，考虑到一共只有三种状态
1.既不在s也不在s1
2.在s不在s1
3.在s也在s1

那么用三进制，0表示第一种状态，1表示第二种状态，2表示第三种状态
以上状压DP可得60分

然后考虑如何优化这个过程

假设不计s'，那么可能有某些点放到了不该放的位置，那么在只有s一个限制的时候，没有办法保证s3连到的就是最后一层

换个思考方向

定义f[s]表示s中合法边集的方案数

对于一个拓扑图，只考虑最后一层的时候会被哪个位置更新

也就是说，只按最后一次来分类，只关心经过那一次操作，某一次的所有点都经过了拓扑

那么当前层的任意一个子集都是合法的

考虑这样一个过程：

for(int i=0;i<(1<<n);++i)
    ans+=power(-1,counter[i]+1)=0

对于'2'， 包含'00','01','10','11'

注意到'00'和'11'的贡献是-1，而'01','10'的贡献都是1

$2=\sum_{i=0}^C(n,i)*(-1)^{i+1}$

同时注意到在之前的统计中对于最后一个集合是空集没有统计

也就是少了'00'，也就减去了一个-1，所以2的贡献就变成了1

这也就是为什么在容斥的时候可以通过乘以$-1^{k+1}$

解释容斥的做法：

举例：

最后一层拓展了4个点，继续关心这些点和前面点的连边情况，假设这四个点中每个点

和前面的点加起来一共x个点

定义这个状态为s，那么f[s]=$2^x\times(-1)^{k+1}$此处$k=4$

上面计算的时候就已经假设了外面还有其他情况

考虑对每个合法方案算最后一层时其每个子集都是合法的，最后这些集合的和刚好为1
就成功地容斥了。。。

正解代码

F

问题转化:
给一个有向图，问对于哪些点，删除它和它的临边之后，图是一个DAG

再次转化:
对图中所有的环，求环的交集，所有环的交集即为答案

首先是两个特判:

1.如果图本来就是个DAG，那么直接输出所有点
2.如果删除图中某个环之后仍然存在环，那么输出0

对于一般情况:

首先类似网络流中的拆点：把每个点拆成入点和出点，入点向出点连一条边，而后每条边从u的出点连向v的入点，而后环交从点的集合变成了边的集合，更好处理

然后把环近似地看做链，那么有两种情况：

对于第一种情况，在非环边组成的DAG上面DP出每个点顺着非环边能走到的最靠前的环上的点，再求出逆着环边能走出的最靠后的环上的点

那么对于环上的一个点x，若x能通过非环边走到x之前的点，那么环上x之后的点都不在环交中

同理对于一个点x，若x能逆着非环边走到x之后的点，那么环上x之前的点都不在环交中

而对于第二种情况在非环边组成的DAG上DP出每个点顺着环边能走到的最靠后的环上的点

对于一个点x，若x能通过非环边走到的环上最靠后的点y在x之后，那么环上(x,y)区间内的边一定不会在环交上，同时由于y是能走到的最靠后的点，那么不会出现把非环交的边算入环交的边的情况

综上：先拓扑排序进行特判，然后找环，再做三次DAG上的DP，之后扫一遍环上的点区间打删除标记，最后扫一遍环输出答案

拓扑排序+三次DAG上DP+打标记，总的时间复杂度$\Theta(n+m)$