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个α数组看作w维的一组基,则原问题等价于:选取最少的基向量使得它们是给定矩阵代表的线性变换的一组基,那么显然最少基向量的个数即位这个矩阵的秩
具体操作时:普通的高斯消元以及避免了小数运算的类欧几里得消元法均会爆longlong。
类欧几里得消元法:在两行相消时,使用辗转相除法让两行轮流互相使用初等行变换,直到某一行主元为0,把主元非0的一行作为梯形矩阵的一行。复杂度与辗转相除法相同O(n3logn)
因此必须使用多个随机质数,在模意义下消元,秩取在这些质数模意义下的最大值。
随机大质数的方法:
1 | inline int randomPrime(int l, int r) {//随机一个在[l,r]范围质数的方法 |
isPrime函数可用miller−rabin算法实现(但会对卡迈克尔数失效),也可用朴素的O(√n)判断因子实现。而由于素数平均每lnn个数就有一个,本题中使用第二种判素数方法即可,复杂度O(T(√nlnn+n3)),本题取T=3即可
B.Black sabbath
每两个圆之间画一条线,共有n2条线,也就是n2个半平面,对于每个点都求一次半平面交即可确定凸包,而且显然这些凸包不会相交
C.Mr.Credo
由于题目里说了这些角度的和小于360,因此只需将这些角全部不转的移动到原点,找一个方向使得不被这些角覆盖,然后在这个方向离原点非常远(1e9)的地方画圆即可,因为输入绝对值只有50而答案要求1e9,所以一定是可行的。一个小优化是,取最大的没被覆盖的角的角平分线方向画圆
D.Deep purple
区间border模板题
首先建出后缀自动机,并将parent树进行轻重链剖分
考虑询问(l,r),即为询问满足len(lca(x,r))>x−l,l≤x≤r中最大的x
考虑枚举lca(x,r),那么这些点都是r的祖先
分两类考虑:
1.对于某个祖先x,x不是f(x)的重儿子,则我们把f(x)算作第一类祖先,则第一类祖先只有logn个
2.其他的祖先可以分成log段重链的前缀
这样就可以将一个询问分成两类,每类分成logn个询问,将询问标记全部打在树上,两类询问如下:
1.q1(x,v∈son(x),l):在x的子树中,除去v的子树,剩下的点中,满足key(i)=i−len(x)<l(条件1)的最大的i
第一类询问有两种方法:
a.以dfs序为标号对key(i)建立主席树,然后相当于在主席树的两个区间上进行线段树二分找到最大的i
b.也可以用线段树合并,不过个人认为不如a方法
(处理所有第一类询问的)时间复杂度:O(nlog2n),空间复杂度O(nlogn)
a方法是在线的,b方法离线
2.q2(某个重链前缀,l):这个重链前缀的所有点的所有轻子树中,满足条件1的最大的i
我们下面称一个点的轻子树中的后缀节点为这个点的轻后代
建造一棵树形态的主席树,维护所有点到根的链上的所有点的所有轻后代的关于key(i)=i−len(lca(i,他的在这条链上的第一类祖先))的权值线段树,可以在所有的点的所有第一类祖先上都标记上这个点(也就是维护每个点的轻孙子),由于一个节点最多有logn个第一类祖先,因此所有点的轻孙子总数为nlogn。那么第一类询问就相当于在主席树的一个区间上进行线段树二分,大体与第一类询问相同
以上方法:在线,时间复杂度O(nlog2n),空间复杂度O(nlog2n)
可以离线,只需要一个线段树,将所有的第二类询问打在点上,然后一个一个重链的处理,按照深度动态插入点并进行询问,每处理完一个重链就将线段树清空。
以上方法:离线,时间复杂度O(nlog2n),空间复杂度O(n)
综上:可以得到本题的离线方法和在线方法
离线:时间/空间复杂度O(nlog2n),O(nlogn)
在线:时间/空间复杂度O(nlog2n),O(nlog2n)
本题采用离线方法,省空间
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√n)
G.Green Day
构造题
对于k种颜色,选用2k个点
对于第i棵树,连接以下边:
1.(i,n+i)
2.(i,∀j<i n+j)
3.(i,∀i<j≤n j)
4.(n+i,∀j<i j)
5.(n+i,∀i<j≤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中的边按照他们在环上的那个端点在环上的位置进行环形排序。则可知一对匹配ai,bj的中间一定没有任何边,于是可以将n对匹配看成是环上n个不相交区间,那么一定有至少一条环上的边不在任何区间中,那么它没有被这个回路经过,因此x不是不可避免点
充分性的逆否命题:若一个点不是不可避免点,那么存在一个环不包括这个点
若这个点不是不可避免点,那么考虑将某个经过这个点的非原图欧拉回路的极大不重回路拉出来,这个回路上的边称为有效边,将有效边贡献的度数称为有效度数,易知所有点的有效度数均为偶数,考虑将某条没有经过的边也变成有效边,那么势必有两个点的有效度数会变成奇数。但由于原图是欧拉图(所有点度数均为偶数),因此一定可以继续加入其他没有被这个回路覆盖的边。最后会发现至少要加一个环,才能使得所有点的有效度数均变成偶数,然而这一整个环都不在回路中也不经过这个点(否则这个回路就不再是极大回路),因此存在一个环不经过这个点
命题等价于:一个点是不可避免点,当且仅当将这个点以及与他相邻的边去掉,图就会变成无环图
算法:
跑出这个图的dfs生成树(这是为了保证非树边一定是返祖边),一个点x满足条件,即为所有非树边均跨过或经过他,且不存在他的某个儿子的子树中有一条以上的非树边跨过x
简单树dp即可