牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共8篇）

模拟97 题解

A. 小盆友的游戏手玩表找规律。 B. 花弱智$dp$题，用逆元随便处理一下就能处理字符集很大的问题。 C. 表格利用了扫描线的思想。首先将横坐标离散化，对纵坐标建线段树。枚举横坐标，则矩形转化为在横坐标的左边界$insert$，在右边界+...

扫描线 set 线段树

2019-11-04

0 729

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟45 题解

A. matrix 当然考虑左端点为 $l$的所有矩形的贡献。通过一个 trie，对 trie 上每个节点开一个 set，来找到每个串 $s$ 存在的位置。那么可以把当前答案的形式化成 $ans=\sum \limits_{s} val_s$ ，其中 $val_s$ 表示这个串出现的区间数...

多项式 trie树 set dp 启发式合并扫描线线段树

2020-03-14

0 467

省选模拟47 题解

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

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

2020-03-16

0 378

省选模拟48 题解

A. 事情的相似度问题是区间内最大的点对 $LCS$。容易发现 $LCS$ 其实就是两个前缀的终止节点的 $lca$ 的 $len$。考虑对每个 SAM 上节点搞一个 set 维护 endpos 集合。每次的操作就是合并两个集合，然后节点 $x$ 上 endpos 集合中两两可以形成...

搜索扫描线后缀自动机 lct 线段树启发式

2020-03-17

0 383

省选模拟56 题解

A. 取石子游戏容易发现这个问题的 $sg$ 值就是每堆的石子个数的异或和。问题是后手能赢，也就是求删除 $d$ 的倍数个石子，使得剩余石子的异或和恰好为 $0$ 的方案数。然后发现直接 $dp$ 复杂度就是 $O(n*d*\max(a_i))$ 的。发现题面中给出了一个很特殊的限制...

模拟博弈论 SG函数 dp 容斥扫描线线段树

2020-03-28

0 399

省选模拟55 题解

A. 调兵遣将对于一个确定的右端点，只有 $log$ 种 $\gcd$ 不同的左端点。可以把这个东西写成 $(a,b,R)$ 的形式。在集合中不便于计算，可以考虑转化为总方案数减不在集合中的方案数。可以考虑设 $f_x$ 表示最后一个区间的右端点 $\leq x$ 的方案数，然后对上...

线段树扫描线博弈论 dp SG函数

2020-03-27

0 442

省选模拟57 题解

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

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

2020-03-29

0 353