zcmimi's blog
avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

枚举长度L,然后判断长度为L的子串能连续出现几次(1次肯定可以,这里判断出现2次以上的)

复杂度\Theta(\frac n1+\frac n2+\cdots +\frac nn)

假设现在枚举到位置j

找到k=\operatorname{LCP}(suf(j),suf(j+L)),\left \lfloor \frac ki \right \rfloor +1就是从j开始到j之后循环的次数

再判断一下j之前是否有再出现过,就可以得出当前答案

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

avatar
zc
2020-05-08 19:19:00
查看原题

点击跳转

首先根据输入的字符串构造trie

然后构建AC自动机

利用了fail树的一个性质:

y节点的fail指针指向x节点,那么 根到x形成的字符串 一定在 根到y形成的字符串 中出现过

那么我们对于每个询问x y,只需要找出根到y上的节点有多少个fail指针直接或间接指向x的,就是答案

构建fail树之后使用dfs序+树状数组统计

avatar
zc
2020-05-05 09:31:00
查看原题

点击跳转

f(i,j,0/1,0/1)表示第i轮的第j场,你是否是胜利者的粉丝,是否是失败者的粉丝

可以发现轮数有点像堆,如果轮数从0开始编号,第i轮的第j场由第i-1轮的第2j场、第i-1轮的第2j+1场转移而来

avatar
zc
2020-05-05 00:18:00
查看原题

点击跳转

枚举变换情况(6!),然后kmp\Theta(n)判断即可

avatar
zc
2020-05-04 01:28:00
查看原题

点击跳转

容易发现,只要这个点与1之间存在某条路径长度(\le阶段数)+阶段数为偶数的,那1就得提供原材料

我们分别求出长度为奇数、偶数的最短路长度即可判断

avatar
zc
2020-05-03 21:39:00
查看原题

点击跳转

可以发现如果要字典序最小,那么就需要让靠前的数字变小

那么最终形成的平均数是递增的

可以用单调栈维护平均数递增

avatar
zc
2020-05-03 11:51:00
查看原题

点击跳转

交互题

我们从叶子节点开始搜索,把所有叶子节点添加到队列中

每次从队列中弹出两个叶子节点,

如果lca为其中一个,那么这个lca就是树根

否则删除这两个节点,可能会形成新的叶子节点,加入队列

因为最坏情况下每次都会删掉两个节点,那么重复\frac n2次后,也就只剩下根节点了

avatar
zc
2020-05-03 11:09:00
查看原题

点击跳转

可以发现有三种路径:

  1. a \leftrightarrow b

  2. a \leftrightarrow x \leftrightarrow y \leftrightarrow b

  3. a \leftrightarrow y \leftrightarrow x \leftrightarrow b

只需要判断这三条路径是否满足就可以了

可以发现只要dis\le k而且和k同奇偶就是符合的

(比如x\leftrightarrow y可以一直循环,变成x\leftrightarrow y \leftrightarrow x \leftrightarrow y \dots,每次长度+2)

avatar
zc
2020-05-03 01:04:00
查看原题

点击跳转

暴力枚举即可

19/74
Search
search