牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

省选模拟47 题解

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

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

2020-03-16

0 378

省选模拟49 题解

A. Manager 问题是每个子树的中位数。每次的修改操作是改成最大值。所以只要考虑修改前的值是 $x$，如果 $x$ 大于一个祖先的中位数，那么对中位数无影响，否则将答案更新为中位数右移一位的数即可。然后发现只要预处理出两种答案。每次的操作就是询问一条祖先链，这个只要用一个数据...

线段树启发式合并莫比乌斯反演 dp

2020-03-18

0 354

dp 题解乱写

AGC034E 枚举根节点表示最终汇聚的点。发现有祖先关系的点对是没必要进行操作的。关注的是深度的和，不妨把深度为 $x$ ，转化为有 $x$ 个点需要匹配。只有不同子树的点可以匹配。如果对于一个点，最大的儿子的大小 $maxsz*2 \leq sumsz$，那么显然可以全部匹配。...

dp 轮廓线数位dp dp套dp

2020-03-19

0 404

省选模拟56 题解

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

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

2020-03-28

0 399

省选模拟51 题解

A. 数学利用本题的特殊性质，可以得到如果 $n$ 为奇数，那么答案为 $(ab)^{\frac{n+1}{2}}$ ，对这个玩意平方一下即可发现是对的。对于 $n$ 为偶数，可以把 $2$ 全都提取出来，然后对剩余的部分取得一个解。然后不断缩小 $2$ 的次数以迭代，当缩小为 $2^0...

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟52 题解

A. 图两个二分图，可以直接对应出一个四分图来。第二个操作要求连通性，所以可以考虑先生成一棵树，这棵树显然是二分图。对于剩下的边，考虑是否形成二分图。如果能够形成，那么可以对应出合法的四分图。如果不能，那么说明剩下的边中存在奇环。因为树边已经连通了，所以这个奇环是合法解。 ...

交互构造题 dp

2020-03-22

0 334

省选模拟54 题解

A. space 首先考虑建个图，发现每个点的入度出度均为 $1$，其实就是形成了若干个环排列。起点为 $(1,1,1,1)$ ，但是最终还要经过一次起点。所以在 $n \neq 1$ 时，考虑直接无视这个起点，转化为自选起点，但是要花钱来，然后要求经过每个点一次的最小代价。发现代价显...

折半搜索莫比乌斯反演 dp

2020-03-25

0 314

省选模拟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

省选模拟59 题解

A. 杨柳考虑实际上有这样一个结论，棋子之间是互不干扰的。可以使得最优方案上不存在两个棋子中途碰上的情况。然后问题就是一个二分图最小匹配，一个简单的想法就是 bfs 然后跑一个费用流，点数不多，边数很多。另外一个做法是直接在原图上建图跑个费用流，点数很多，边数不多。经过实验，只有...

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336