牛客237787563号

未归档

/ 注册

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

省选模拟38 题解

A. Inverse 似乎这类问题的套路都是考虑每一个点对。然后考虑一个 dp 。设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。然后发现这个玩意可以优化，如果枚举翻转区间...

分块单调指针差分 dp 计算几何平衡树凸包

2020-03-05

0 428

省选模拟47 题解

A. 老夫发现这个问题有点类似二维偏序。所以考虑类似扫描线的做法，枚举第一个维度，同时在第二个维度上用一个数据结构维护答案。所以枚举 $c$ 的取值，然后发现每次的操作是插入一个点。以值域为下标建立一个数据结构，对应的操作就是前缀加下标，询问操作就是全局查询最大值。所以用一个简单...

凸包扫描线分块 dp 矩阵线性代数

2020-03-16

0 378

省选模拟71 题解

A. 王子这个数据范围加上很奇怪的限制，其实就应该是网络流了。可以首先钦定选择了 $A$ 类，然后将其中的一些替换为 $B$ 类。其实与志愿者招募那个题挺像的，只不过原来是对于每个点选择 $[l,r]$ 个区间。但是现在的问题是要求每个区间选择 $[l,r]$ 个数点。其实并不难...

网络流分块 trie树 AC自动机线段树 set

2020-04-15

0 477

省选模拟74 题解

A. 签到如果权值在边上，那么问题就简单了，弄一棵生成树，然后对每个环权值塞线性基里就完事了。但是如果权值在点上，这个结论就并不成立了。所以可以联想+手玩发现，如果走一条路径然后回来，造成的贡献是两个端点分别状态取反，中间路径不变。然后可以得到一种构造方法，首先从起点走到终点，然后从...

分块点分治 ST表 bitset 线段树虚树线性基

2020-04-18

0 401

省选模拟80 题解

A. 数字如果枚举 $x\ and \ y$ 的取值，可以进行一个简单的dp。 $dp_{i,0/1,0/1,0/1,0/1}$ 表示从高到低到第 i 位，最高的几位分别是否与 $lx,rx,ly,ry$ 相同，然后这个 dp 数组的取值也只有0/1。所以可以 dp 套 dp。在考虑过...

分块多项式 dp套dp dp 根号分治矩阵数位dp

2020-04-25

0 408

字符串乱写

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

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

2020-07-06

0 379

数据结构乱写

loj6515 贪玩蓝月容易发现本题中要求的信息不支持快速合并，不支持快速删除，但是支持快速插入。所以一个简单的离线做法就是线段树分治。只要按照时间建线段树，把每个操作插入到对应节点上。最后 \(dfs\) 一遍线段树顺便插入，在叶子节点输出答案即可。然而这个信息是支持快速合并两个信息的。...

dp 单调队列分块启发式合并线段树 lct

2020-07-13

0 448