opentrains1474题解

	分类	有趣	启发性	思维难度	代码难度（*）	总难度（*）	感受	总评价（17）
A	线性代数	4	4.5	3.5	2	5.5	2	14
B	计算几何	2	2	1.5	3	4.5	0	5.5
C	几何	2	2.5	2.5	1.5	4	1	8
D	后缀自动机/树链剖分/主席树和线段树	3.5	4	4	5	9	2	13.5
E	trie树	4	2	1	1	2	1	8
F	树上莫队/链表	3	3.5	2.5	3.5	6	1	10
G	构造	4.5	4	4	1	5	2	14.5
H	概率/微积分/数学归纳法	4	4.5	4.5	2	6.5	2	15
I	线段树/单调栈	3	3.5	3.5	3.5	7	2	12
J	树dp	2.5	2	1	1.5	2.5	1	6.5
K	图论	4.5	4.5	4.5	2.5	7	2	15.5

题目：BJ(CE)F|IDAGHK

A.ABBA

求矩阵的秩即可。

将$k$次操作的$k$个$\alpha$数组看作$w$维的一组基，则原问题等价于：选取最少的基向量使得它们是给定矩阵代表的线性变换的一组基，那么显然最少基向量的个数即位这个矩阵的秩

具体操作时：普通的高斯消元以及避免了小数运算的类欧几里得消元法均会爆$longlong$。

类欧几里得消元法：在两行相消时，使用辗转相除法让两行轮流互相使用初等行变换，直到某一行主元为0，把主元非0的一行作为梯形矩阵的一行。复杂度与辗转相除法相同$O(n^3logn)$

因此必须使用多个随机质数，在模意义下消元，秩取在这些质数模意义下的最大值。

随机大质数的方法：

inline int randomPrime(int l, int r) {//随机一个在[l,r]范围质数的方法
	int n = myrand() % (r - l + 1) + l;
	while (!isPrime(n)) {
		n++;
	}
	return n;
}

$isPrime$函数可用$miller-rabin$算法实现（但会对卡迈克尔数失效），也可用朴素的$O(\sqrt n)$判断因子实现。而由于素数平均每$ln n$个数就有一个，本题中使用第二种判素数方法即可，复杂度$O(T(\sqrt nlnn+n^3))$,本题取$T=3$即可

B.Black sabbath

每两个圆之间画一条线，共有$n^2$条线，也就是$n^2$个半平面，对于每个点都求一次半平面交即可确定凸包，而且显然这些凸包不会相交

C.Mr.Credo

由于题目里说了这些角度的和小于$360$，因此只需将这些角全部不转的移动到原点，找一个方向使得不被这些角覆盖，然后在这个方向离原点非常远（$1e9$）的地方画圆即可，因为输入绝对值只有$50$而答案要求$1e9$，所以一定是可行的。一个小优化是，取最大的没被覆盖的角的角平分线方向画圆

D.Deep purple

区间$border$模板题

首先建出后缀自动机，并将$parent$树进行轻重链剖分

考虑询问$(l,r)$，即为询问满足$len(lca(x,r))>x-l,l\leq x\leq r$中最大的$x$

考虑枚举$lca(x,r)$，那么这些点都是$r$的祖先

分两类考虑：

1.对于某个祖先$x$,$x$不是$f(x)$的重儿子，则我们把$f(x)$算作第一类祖先，则第一类祖先只有$logn$个

2.其他的祖先可以分成$log$段重链的前缀

这样就可以将一个询问分成两类，每类分成$logn$个询问，将询问标记全部打在树上，两类询问如下：

1.$q1(x,v\in son(x),l)$：在$x$的子树中，除去$v$的子树，剩下的点中，满足$key(i)=i-len(x)<l$（条件1）的最大的$i$

第一类询问有两种方法：

a.以dfs序为标号对$key(i)$建立主席树，然后相当于在主席树的两个区间上进行线段树二分找到最大的$i$

b.也可以用线段树合并，不过个人认为不如a方法

（处理所有第一类询问的）时间复杂度：$O(nlog^2n)$,空间复杂度$O(nlogn)$

a方法是在线的，b方法离线

2.$q2(某个重链前缀,l)$:这个重链前缀的所有点的所有轻子树中，满足条件1的最大的$i$

我们下面称一个点的轻子树中的后缀节点为这个点的轻后代

建造一棵树形态的主席树，维护所有点到根的链上的所有点的所有轻后代的关于$key(i)=i-len(lca(i,他的在这条链上的第一类祖先))$的权值线段树，可以在所有的点的所有第一类祖先上都标记上这个点（也就是维护每个点的轻孙子），由于一个节点最多有$logn$个第一类祖先，因此所有点的轻孙子总数为$nlogn$。那么第一类询问就相当于在主席树的一个区间上进行线段树二分，大体与第一类询问相同

以上方法：在线，时间复杂度$O(nlog^2n)$,空间复杂度$O(nlog^2n)$

可以离线，只需要一个线段树，将所有的第二类询问打在点上，然后一个一个重链的处理，按照深度动态插入点并进行询问，每处理完一个重链就将线段树清空。

以上方法：离线，时间复杂度$O(nlog^2n)$,空间复杂度$O(n)$

综上：可以得到本题的离线方法和在线方法

离线：时间/空间复杂度$O(nlog^2n),O(nlogn)$

在线：时间/空间复杂度$O(nlog^2n),O(nlog^2n)$

本题采用离线方法，省空间

E.Elvis Presley

$a$可到达$b$当且仅当将$a,b$写成二进制，忽略前导零，$lcp(a,b)=len(a)$,这是因为可以把两种边看作在一个数字的后面填上0/1

在trie树上考虑这个事情，如果一个集合是反链，那么把这个集合中的所有数字去掉前导零的二进制按照从高位到低位插进二进制trie树，那么没有一个数字的终止点是另一个数字终止点的祖先

极大反链即为目前反链的所有终止点已经将整棵trie树覆盖

由于越短的二进制位覆盖的范围越大，那么在trie树上$dfs$,答案即为只有一个儿子的节点数+2，也就是说当一个点只有一个儿子时，我们补上另一个儿子并将这个数插入反链

F.Frank Sinatra

树链mex

考虑树上莫队，方便起见，即为在树的欧拉序上跑序列莫队，可以记录每个树上节点在当前区间出现了几次（最大为2），如果变成了1那么就将他的父边对应的数字插入，如果变成了0/2就将他的父亲对应的数字删除

相当于动态插入/删除一个数字，维护全局mex

使用双向链表维护即可，对每个数字维护他前面的/后面的第一个未出现的数字，答案即为0后面链的数字

大于$n$的值可视为$n$

复杂度$O(n\sqrt n)$

G.Green Day

构造题

对于$k$种颜色，选用$2k$个点

对于第$i$棵树，连接以下边：

1.$(i,n+i)$

2.$(i,\forall j<i\ n+j)$

3.$(i,\forall i<j\leq n\ j)$

4.$(n+i,\forall j<i\ j)$

5.$(n+i,\forall i<j\leq n\ n+j)$

相当于两个中心的”类菊花树”，$i$和$n+i$为第$i$棵树的两个中心

对于任意两个点$u,v$,两种颜色$i,j$,两条路径上的点集最大分别为$(u,v,i,n+i),(u,v,j,n+j)$可知满足题意

显然这个构造没有重边

H.Hans Zimmer

I.Ivan Dorn

将询问按照$r$离线，依此考虑。维护一个单调不增的栈，并维护两棵线段树$A,B$，$A$负责维护单调栈元素，$A$的每个节点表示这段区间内的、在单调栈中的元素，在当前的$r$时，作为$canyon$的左端点的最长$canyon$，$B$中维护的是不在单调栈中的元素的同样信息。则只需做以下事情：

1.将初始的$A,B$置为$-inf$

2.当单调栈插入元素时，在$A$中区间加，并将某个位置设为$0$,删除元素时，将$A$中某个位置置为$-inf$，并在$B$中某个位置设置某个值

询问时在$A,B$中分别询问后缀最大值，取较大者即可

复杂度$O(nlogn)$

J.Jimi Hendrix

简单树dp，设$dp[0/1/2/3][x]$表示$x$的子树中的点到根的路径组成的字符串中，能跟$s$从头匹配最长的是多少，这个字符串是从哪个点开始的，能跟$s$从尾匹配最长的是多少，这个字符串是从哪个点开始的。$dfs$树$dp$即可。如果某对兄弟节点$u,v$满足$dp[0][u]+dp[2][v]>=m$则找到一个合法的链

K.Korn

首先这个图必须是欧拉图，也就是所有点的度数都为偶数，否则没有欧拉回路

不可避免点即为每条经过该点的极大不重回路都是原图的欧拉回路。那么，我们想知道每个点成为不可避免点的充分必要条件。

定理：在欧拉图中，一个点是不可避免点，当且仅当这个点包含在任意一个环中

证明：对于充分性和必要性，我们都考虑他们的逆否命题

必要性的逆否命题：若一个点不包含在某个环中，那么他一定不是不可避免点。

设$x$不经过环$P$

考虑在一个经过$x$的极大不重回路的行走路线中，被经过的、从$P$上走到$P$外的边集为$A$，被经过的、从$P$外走到$P$上的边集为$B$。则$|A|=|B|$。想象将$P$缩成一个点，那么在行走路线过程中我们对$P$“一进一出”。这样可将$A$和$B$建立一个完美匹配，那么将$A和B$中的边按照他们在环上的那个端点在环上的位置进行环形排序。则可知一对匹配$a_i,b_j$的中间一定没有任何边，于是可以将$n$对匹配看成是环上$n$个不相交区间，那么一定有至少一条环上的边不在任何区间中，那么它没有被这个回路经过，因此$x$不是不可避免点

充分性的逆否命题：若一个点不是不可避免点，那么存在一个环不包括这个点

若这个点不是不可避免点，那么考虑将某个经过这个点的非原图欧拉回路的极大不重回路拉出来，这个回路上的边称为有效边，将有效边贡献的度数称为有效度数，易知所有点的有效度数均为偶数，考虑将某条没有经过的边也变成有效边，那么势必有两个点的有效度数会变成奇数。但由于原图是欧拉图（所有点度数均为偶数），因此一定可以继续加入其他没有被这个回路覆盖的边。最后会发现至少要加一个环，才能使得所有点的有效度数均变成偶数，然而这一整个环都不在回路中也不经过这个点（否则这个回路就不再是极大回路），因此存在一个环不经过这个点

命题等价于：一个点是不可避免点，当且仅当将这个点以及与他相邻的边去掉，图就会变成无环图

算法：

跑出这个图的$dfs$生成树（这是为了保证非树边一定是返祖边），一个点$x$满足条件，即为所有非树边均跨过或经过他，且不存在他的某个儿子的子树中有一条以上的非树边跨过$x$

简单树$dp$即可