牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

博弈论题解乱写

1.对于一个转移方程 $dp_{i,j}= not (dp_{i-1,j} \ and \ dp_{i,j-1})$。可以发现除了前两行两列，其他每个对角线的取值是相同的。所以只要做前三行三列的 dp 即可得到整个 dp 数组。然后这个东西的初始值不一定要整齐，只要拓展过来两三行都可以解...

线段树博弈论 SG函数

2020-03-27

0 853

省选模拟57 题解

A. Max 看到这个数据范围就想一下是不是可以状压。然后发现只有 $m$ 压的下。容易发现题目中的顺序并不关键，其实可以无视掉原有的操作顺序。然后现在给 $1... n$ 每个元素分配一些操作就好了。这样在给第 $i+1$ 个元素分配操作之前，我们只关注已经分配的操作集合、最大的...

树剖扫描线动态dp dp 线段树状压

2020-03-29

0 353

省选模拟61 题解

A. GTM 考虑一个点 $(x,v)$ ，能够碰到的点 $(x',v')$。有 $(x',v')$ 满足 $x'<x,v'>v$ 或者 $x'>x,v'<v$。然后有这样一个结论，我们将所有的点按照 $v$ 排序，然后在每个点能影响到的是一个连续区间。区间的左...

结论题树状数组容斥线段树

2020-04-03

0 800

省选模拟71 题解

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

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

2020-04-15

0 477

省选模拟70 题解

A. 小 Y 增员操直播群考虑一个暴力做法，每次枚举较小的集合的大小，在判断合法之后可以直接将原问题划分为两个子问题。两个子问题是互不干扰的，所以直接 dp 就好了。然后可以发现枚举大小是没有必要的。考虑与元素 $n-1$ 连边的最小的点 $x$。如果两个集合大小相等，那么 $x...

线段树 dp

2020-04-14

0 362

省选模拟74 题解

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

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

2020-04-18

0 401

省选模拟85 题解

A. rng 有这样一个想法，我们把实数值域变成整数的。具体来说就是把给每个区间的 $r_i$ 都减去 $1$。这样的话期望就不难计算了：以值域作为下标，修改就是每次把 $[l_i,r_i]$ 区间加上一个 $\frac{1}{r_i-l_i+1}$。每次查询逆序对，其实就是求这个...

dp 莫比乌斯反演数学线段树

2020-05-01

0 409

省选模拟104 题解

A. 签到题把每个点向它右侧比他大的第一个点之间连边，如果没有那么向 \(root\) 连边。那么可以构成一棵树。特判一些情况之后，可以认为问题就是： 1.给某节点和它的所有儿子节点权值加上一个值。 2.询问一条路径的权值和。首先考虑如果只询问单点的维护方法，其实就是打一个标记表...

线段树网络流树链剖分

2020-05-23

0 362

字符串乱写

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