0%

You may check this article on cp-algorithms.com (or OI-wiki if you prefer reading in Chinese) for more precise information and proof of complexity about SAM. Here I just want to write about another perspective to understand SAM, which I’ve learned from Huadun Hong, PKU, through Zhengruioi’s online courses on 4th, Feb, 2020.

0

We can get the suffix tree of string S simply by inserting all of its suffixes into a trie (though this will involve O(|S|2) vertices). Note that:

Read more »

桥梁

将所有的操作按照时间顺序分成T个大小为qT的块。对于每个块,将块内的询问按照wj排序,将未被块内的操作修改过的边按照执行这个块内的操作之前的边权排序。

按照wj降序枚举块内的询问,然后将所有重wj的车能够通过的、“未被块内的操作修改过的”边加入;再加入块内修改过的、这次询问的时候的边权wj的边,查询sj所在连通块的大小,然后再撤销掉加入的块内修改过的边。

Read more »

C - Make Good

sum为所有数的异或和,tot为所有数的和。tot显然必须是偶数。所以如果tot是奇数的话,就先往数组里面加入一个1

如果2×sum>tot,就往数组里面加入两个2×sumtot2,这对数组中的数的异或和没有影响。

Read more »

CF1246F Cursor Distance

考虑对于每一个i,求出至多走k步就能够到达它的位置所构成的区间[Li,k,Ri,k]。我们只要对每个i分别求出kLi,k,kRi,k就能得到答案。

最短路不一定是单向的(比如对于baaaaac,从b走到最后一个a),所以L,R可能不独立,不能直接倍增计算L,R的和。

Read more »

LOJ2146 「SHOI2017」寿司餐厅

mx2+cx拆一下就是:只要吃的寿司里面有代号为x的就要付出mx2的代价;每吃一种代号为x的寿司就要付出x的代价。直接令di,i减掉ai,就可以不再考虑cx这部分。

对每个区间[l,r]建一个点,权值为dl,r;对每个代号建一个点,权值为mx2。如果选了dl,r就必须选dl,r1dl+1,r,如果选了di,i就必须选mai2。求出这张图的最大权闭合子图即可。

Read more »

UOJ422 小z的礼物

考虑min-max容斥:

max(S)=TS(1)|T|+1min(T)

对希望得到的物品的每一个子集,求出期望最早什么时候子集里至少有一个物品被拿到了,就能算出答案。

Read more »

loj6485 LJJ学二项式定理

首先枚举i(mod4)的余数t,然后转化成对于每一个t,求

i=0n(ni)si[4(it)]

单位根反演:

Read more »

CF963E Circles of Waiting

圆内的整点形成了一个类似方阵的结构。设fx,y(x,y)期望被经过的次数。我们可以对每一个点列出一个方程:

fx,y=p0fx+1,y+p1fx,y+1+p2fx1,y+p3fx,y1+[(x,y)=(0,0)]

将每一行最左侧的点设为主元,其它的点都用主元表示。从左往右考虑每一列的点:fx,y可以用fx1,y的方程表示出来(因为方程中涉及到的fx1,y,fx1,y1,fx1,y+1,fx2,y在之前都已经考虑过了,只有fx,y是未知的)。

Read more »