牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

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

省选模拟52 题解

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

交互构造题 dp

2020-03-22

0 334

省选模拟51 题解

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

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟50 题解

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

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

2020-03-20

0 324

dp 题解乱写

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

dp 轮廓线数位dp dp套dp

2020-03-19

0 404

省选模拟49 题解

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

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

2020-03-18

0 354

组合计数题解乱写

3.组合计数上 1.ARC102E 把当前限制对应的每个二元组提出来。枚举有多少个二元组中的数字出现了，然后问题是每个组中二选一。出现的数字可以出现 $>0$ 次，不在任何一个二元组中的数字可以出现 $\geq 0$ 次。统一一下就可以直接插板法了。 2.小Z的礼物通过...

二项式反演轮廓线容斥组合计数

2020-03-17

0 747

LCT 题解乱写

LCT 水管局长问题是要求支持删边，询问给定两点之间路径的边权最大值的最小值。可以通过动态最小生成树解决。因为不强制在线，考虑将删边转化为加边。于是只要维护链上的最大权值，每次尝试割最大边权边并加入当前边就好了。 GERALD07 对于树形结构，联通块数=点数-边数。 ...

最小生成树 lct

2020-03-17

0 398

省选模拟48 题解

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

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

2020-03-17

0 383

省选模拟47 题解

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

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

2020-03-16

0 378