牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418

省选模拟6 题解

A. Yist 首先考虑怎样的情况答案是不收敛的。操作中涉及到对一个权值非$0$，并且不作除法的点的加法贡献。因为只要最终的答案，可以想到对每个点作为出边的贡献分别处理。部分分提示求出第一次迭代的贡献，发现对于每个点，贡献都是一个等比数列，所以只要代入求和公式就好了。然而暴力做的复...

分块图论后缀自动机 dp 树状数组

2020-01-13

0 393

省选模拟11 题解

A. 组合数问题还没想明白如何做，待补。 B. recollection 因为原图为trie树，树上两个点的lcp长度等于两个点的lca深度。考虑通过广义sam来维护两个点的lcs。树上同时对应着一个$endpos$，树上两个点对应的$endpos$对应的广义sam上节点在后缀...

并查集平衡树后缀自动机线段树

2020-01-29

0 405

省选模拟12 题解

A. Colorado Potato Beetle 暴力做法是直接bfs。优化的方法是离散化。将特殊的点的横纵坐标抽出来，然后用这些横纵坐标为1e12*1e12分成一个个块，容易发现每个块内的状态是一致的。然后用与暴力类似的方法即可，注意最后统计的是每个块的实际大小。 B. D...

后缀自动机 dp 状压搜索树链剖分线段树

2020-02-01

0 359

省选模拟15 题解

A. 倒计时考虑50%的部分分。分块来削这个数。后四位形成一块，预处理出9991~9999在前五位的最大值为0~9情况下分别会削到的值和削的次数。对于零散的后四位暴力削，这样就可以通过根号预处理，根号削$n$了。容易发现，对于$n$比较大，我们多分几次块，每次用较小一级的块来预处...

网络流后缀自动机分块容斥

2020-02-02

0 366

省选模拟39 题解

A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。容易发现交换的次数就是点数减环数。所以原题转化为环的计数问题。考虑把已有的每个连通块的部分表示出来。容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。如果已...

lct 二项式反演后缀自动机容斥组合计数

2020-03-06

0 410

省选模拟48 题解

A. 事情的相似度问题是区间内最大的点对 $LCS$。容易发现 $LCS$ 其实就是两个前缀的终止节点的 $lca$ 的 $len$。考虑对每个 SAM 上节点搞一个 set 维护 endpos 集合。每次的操作就是合并两个集合，然后节点 $x$ 上 endpos 集合中两两可以形成...

搜索扫描线后缀自动机 lct 线段树启发式

2020-03-17

0 383

省选模拟86 题解

A. 人生有一点 dp 套 dp 的意思，内层的 dp 就是直接在拓扑序上进行的简单 dp。外层记录的是 dp 的状态，然后 $O(n^3)$ 的做法是显然的。当转移到第 $i$ 个位置的时候，只要关心前面有多少个黑点 dp 值为 $1$，前面有多少个白点 dp 值为 $1$，前面的 d...

字符串状压后缀自动机 dp

2020-05-02

0 380

字符串乱写

loj6158 考虑在一个位置放上加号，\(S=A+B\)。若末尾存在 \(0\) ，一定是说 \(A\) 的最后一个数字与 \(B\) 的最后一个数字相加为 \(10\)。（特别的，需要特判二者末尾均为 \(0\) 这个情况）对于进位的问题，其实就是要求 \(A\) 前面的数字与 \(B\) ...

字符串 AC自动机 ST表分块后缀自动机线段树

2020-07-06

0 379

noi前第九场题解

A. s1mple 可以发现 0/1 这个限制类似于求路径数，使得路径经过的边权恰好合法。显然可以用容斥来求，这样可以将问题转化为钦定其中若干条边权为 \(1\)，其他边权任意的路径数。这样做有一个好处，原来问题中的 \(2^{n-1}\) 的集合可以缩减状态数。对于钦定之后的若干条 \(1...

dp 多项式后缀自动机拉格朗日插值启发式合并状压字符串

2020-07-21

0 379