牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共13篇）

远古杂题 1

基因匹配Match（数据结构优化dp）题意 1~n 每个数一定出现五次在s1，s2中。求两个字符串的最长公共子序列。考虑n²的暴力写法，对于每一个i，与他相等的一定只有五个。所以可以记录相等的位置优化，分别查询该位置之前的最大值+1转移，Ans记录即可。对于1~n的带修改RMQ，可以...

线段树 dp 状压字符串矩阵

2019-07-17

0 465

模拟8 题解

A. 匹配 $Hash$直接搞。如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。 B. 回家刚开始以为是割点，打完后仔细一想发现不对。于是打了圆方树，没有什么技巧。另一种简单的做法：只判断割点，但修改判断割点的方法。 ...

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 308

模拟30A 题解

A. 树联想起远古考试时做的题记忆的轮廓。树上走一些步数的期望。显然可以直接解方程。然而复杂度$O(qn^3)$，利用树上的性质优化一下，直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。然而只有20分。预处理出每个点走到每个儿子的期望步...

dp 期望 Hash 二分答案字符串启发式合并

2019-08-25

0 306

模拟47 题解

A. Emotional Flutter 显然第一步的位置只有k种不同的取值。前缀和对步长k取模，那么每条黑线限制的是一段连续区间。问题是是否完全限制k个位置。第一个思路是动态开点线段树，想了想，害怕卡空间，没打。之后的想法是将每条线段离线下来，对线段的左右端点和两条线段之间的区域...

线段覆盖线段树 KMP 字符串

2019-09-20

0 368

模拟87 题解

A. maze 做过类似的题，维护最短路对于$k$的一个凸包，答案就是凸包与$y=s$直线交点的横坐标，这个还挺难打的。然而答案显然具有单调性，所以直接二分答案就完了。实际上，这个二分答案的操作，等价于选定直线$x=mid$，求出$x=mid$与凸包的交点的纵坐标，并通过这个纵坐标与$...

凸包二分答案 dp 线段树字符串

2019-10-25

0 374

省选模拟19 题解

A. 鱼死网破（clash）对于$k=1$的数据，容易发现只要维护每个$x$轴上面的点关于障碍两个端点的极角，并对每个端点对应的极角排序。对于每个$x$轴下面的点，可以通过极角来二分查找哪些点是看得到的。感觉和正解的思想差的不多。正解用到了一步补集转化。考虑每个$x$轴上面的点，...

线段树字符串后缀数组 Hash

2020-02-06

0 413

省选模拟25 题解

A. 环是一道很巧妙的构造题。考虑写出满足条件的 $s_i,s_{i+1}$ 一定满足的式子。设 $x_{i,j}$ 表示 $s_i$ 中第 $j$ 个 $1$ 的位置。由操作A有 $k*t+\sum \limits_{j=1}^k x_{i,j}\equiv \sum \limi...

构造题贪心字符串并查集

2020-02-18

0 344

杂题

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。然后只要考虑每个...

dp 期望容斥字符串组合计数

2020-04-07

0 457

省选模拟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