牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

省选模拟35 题解

A. two 考虑现在要通过蓝边删掉红边。其实等价于要找出有哪些红边，满足恰好只有一个端点在蓝边的儿子方向子树中。考虑对蓝树跑出一个 $dfs$ 序来，那么问题转化为恰好一个端点在给定区间中。这像是一个二维偏序问题。考虑以线段树下标为其中的第一维，第二维进行排序处理。然后用一个 $...

单调指针点分治多项式二分图网络流线段树

2020-03-02

0 334

省选模拟41 题解

A. 要换换名字显然二分一个答案，然后问题转化为二分图中是否存在一组完美匹配。然后发现，如果一个字符串的子序列个数超过 $n$ ，那么就没有必要接着连边了。所以对每个字符串建出不超过 $n$ 条边，然后跑个网络流就完事了。 B. 动态半平面交因为太菜了，所以只会用一些套路来做...

数学二分图二分答案差分网络流线段树

2020-03-09

0 359

省选模拟44 题解

A. 跑步对于每次修改，$O(n^2)$ 的 dp 是显然的。然后发现每次修改这个 dp 的变化量只有 $+1,-1$ 两种取值。继续观察性质，可以发现，对于每一行，变化的位置是连续的。对于不同行，变化的左端点和右端点都是单调的。所以通过树状数组差分实现区间修改，单调指针确定每一...

dp 树状数组数学线段树

2020-03-13

0 368

省选模拟45 题解

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

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

2020-03-14

0 467

省选模拟48 题解

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

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

2020-03-17

0 383

省选模拟49 题解

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

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

2020-03-18

0 354

省选模拟50 题解

A. 小A的树超级钢琴、异或粽子、异或之几道题都是这个套路。对于每个右端点不断找区间最优解，然后把原区间分割为两个区间。用一个堆来时刻找到最大值。所以这个题要解决的就是一个点和区间内所有点的最大距离。点集合并的问题，直接搞一个线段树维护直径就好了。 B. 小B的序列考...

单位根反演线段树位运算吉司机线段树

2020-03-20

0 324

省选模拟56 题解

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

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

2020-03-28

0 399

省选模拟53 题解

A. 数（number）对于 $n$ 为偶数，容易发现确定一半就行了，答案为 $10^{\frac{n}{2}}$。对于 $n$ 为奇数，列式子可以发现形如 $\sum 2x_i = \sum 2y_i \ \ +y_{mid}$。一步很神的操作是，把 $y_i$ 转化为 $9-y_i$...

容斥二项式反演二分答案贪心线段树

2020-03-25

0 396

省选模拟55 题解

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

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

2020-03-27

0 442