1461
【求助+半题解】BZOJ1461字符串的匹配
先说思路: 因为我们是比对较短的$B$与较长的$A$的子串,所以我们求不变的$B$的$next$ 对于这道题我们可以使用树状数组查询前缀和维护数的排名。 对于相同的数我们查询的排名是有误的,因此不仅要比对小于等于该数的前缀和,也要比对小于该数的前缀和。 如:对于$A=2$ $2$,$B=1$ $2$ ......
BZOJ 1461 题解
考虑设计一个哈希函数 $hash(x) = f(x) \times base^x$。 其中 $f(x)$ 表示 $\sum_{j=1}^{i-1} [j #define int unsigned long long #define lowbit(x)(x&(-x)) using namespace ......
BZOJ1461字符串的匹配
[题目](https://tg.hszxoj.com/contest/37/problem/10 "题目") 具体思路与KMP板子很像; 大致思路是将两个数字的排名来当字符比较 用树状数组 $log_2(n)$ 的复杂度来找排名。 一定要注意边界问题 具体实现思路可以看代码 (PS:有奆佬说这题很板 ......