牛客237787563号

未归档

/ 注册

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

远古杂题 1

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

线段树 dp 状压字符串矩阵

2019-07-17

0 465

图论杂题

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解，然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是...

图论二分图树上差分桶线段树 wqs二分

2019-07-16

0 386

线段树/莫队杂题

高速公路(road) 如果直接维护一个点到其它点的距离，维护起来很困难。不妨转换思路，考虑每个点对答案的贡献，设询问区间为$l,r$，则点$i$的贡献为$(i-l)*(r-i)*w[i]=(-i^2+(l+r)*i-l*r)*w[i]$。对于$i^2*w[i],i*w[i],w[i...

线段树莫队分块

2019-07-26

0 420

模拟10 题解

A. 辣鸡(ljh) 模拟。对于同一块内的答案，直接统计。对于不同块内的，枚举i和大于i的$j=i+1～n$，一个有效的剪枝：以$x_1$为第一维排序，当$x_{1j}>x_{2i}+1$时break退出循环。然而如果用纵向链状的数据还是会被卡成$O(n^2)$，然而...

数学期望启发式合并线段树模拟

2019-07-30

0 344

模拟11 题解

A. string 类似 HEOI2016排序。排序这道题因为只询问单点最终答案，二分答案，将小于和大于等于答案的数分别设为0 1，用线段树维护0 1的排序即可。算法一：本题中的1～n变成了0～25（即a～z），单点询问变成了全体询问。仿照排序那道题的做法，线段树优...

线段树 dp trie树组合计数

2019-08-02

0 442

模拟12 题解

A. 斐波那契(fibonacci) 首先想到a,b<=1e6的暴力：建树，直接向上标记求lca。建树的过程中发现一个性质。斐波那契第n代兔子，是n-2代及以前的兔子的儿子。因为编号连续且与父亲编号大小有关，设该节点的编号为$x$，在第$k$代，则$f(x)=x-fib(...

数列线段树 dp 单调队列贪心拓展域并查集

2019-08-03

0 399

模拟13 题解

A. 矩阵游戏　　通过前40%的部分分，我们发现程序复杂度不能为$O(nk)$。　　设$h(i)$表示第$i$行最终乘的总系数，$l(i)$表示第$i$列。　　考虑每个点$(i,j)$，它对最终答案的贡献是$((i-1)*m+j)*h(i)*l(j)$。　　发现可以拆分为$(i-1)...

线段树映射分块 ST表

2019-08-06

0 409

模拟16 题解

A. Blue 贪心完了。这道题学到了很多使用stl set的技巧。 B. Weed 线段树维护栈的操作。一个重要的操作是递归结束时$O(logn)$复杂度的向下寻找分界点。因为延伸出的一定是一条链，复杂度是$O(nlog^2n)$ ...

线段树贪心十字链表

2019-08-10

0 328

模拟24 题解

A. Star Way To Heaven 如果二分答案，问题就转化为不经过一些等大的圆，能否从左侧到达右侧。然后我就不会了。其实问题很简单：不能从左侧走到右侧，等价于能从下侧沿障碍走到上侧，也就是说一些圆将路阻断开。二分答案，用并查集或者dfs都可以做到$O(k^2)$建边之后$...

启发式合并线段树单调栈最小生成树凸包

2019-08-17

0 355

模拟25A 题解

A. Lighthouse m的范围极小，显然的容斥。总的方案数，减去受任意一个限制的方案数，加回受两个限制的方案数。就能得到受所有限制的的方案数。将选择的一些边所指向的点放在同一个联通块里。方案数其实就是这些联通块的圆排列，再乘上$2^{不为1的联通块个数}$，因为每个联通块...

容斥欧拉路点分治线段树

2019-08-19

0 436