牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

省选模拟35 题解

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

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

2020-03-02

0 334

省选模拟34 题解

A. 倚天剑的愤怒考虑特殊的情况，如果 $a_i <0$ ，那么最优的决策一定是把最差的跳过。然后可以考虑如果存在一个 $a_i>0$ ，那么这个 $i$ 无法对前面的操作产生影响，但是可以是把后面的一些小于 $0$ 的元素抵消掉。抵消之后呢？问题仍然是把最差的跳过。所以...

并查集分治贪心线段树直径

2020-02-29

0 327

省选模拟33 题解

A. 盗梦空间考虑首先构建一棵虚树，然后跑一遍多源点最短路，求出每个虚树上的点到达最近的关键点的距离。分类讨论最终的答案 $u$ 的出现位置。 1.出现在虚树节点的一个满足子树不含虚树节点的儿子子树中。一个很好的性质是我们只关注最大值。所以考虑对每个节点维护一个 multiset ...

容斥莫比乌斯函数二项式反演倍增数学虚树树剖

2020-02-28

0 346

省选模拟32 题解

A. 送你一道签到题这个函数显然是个积性函数。刚开始的想法是可以直接考虑分开每个质因子，然后乘一块的贡献显然是正确的。后来一想这个玩意实际上就是 $id^k$ 点积上 $d(x)$ 的 $m$ 次卷积，所以肯定是积性的。然后看这个数据范围，显然要搞个 min25筛。然后一想，这...

容斥 trie树 min25筛 dp 数学

2020-02-26

0 295

省选模拟31 题解

A. Skip 一眼决策单调性，但是感觉因为带个权值就不好处理了。实际上对权值开个线段树，然后直接在线段树上维护决策单调性就完事了。而且这个式子是一个显然的斜率优化 dp ，在权值线段树上维护凸包也挺套路的。感觉这题没做出来比较可惜，没有想到通过对权值开线段树，来实现权值的无关操作。 ...

状压线段树凸包 dp 决策单调性

2020-02-26

0 410

省选模拟30 题解

A. 任凭风浪起，稳坐钓鱼台其实就是一个优化过的暴力。首先答案 $x^3$ 显然可以转化为 $3$ 个位同时出现的方案数*权值求和。当 $k<=20$ ，直接异或 fwt ，然后做一个超集求和运算，$C(k,3)$ 枚举就行了。这个算法不优秀的原因是只关注三个位同时出现，并不需...

数学构造题分治 fwt

2020-02-26

0 498

省选模拟29 题解

A. circle 容易发现，如果存在一组合法答案，那么 $k$ 个钦定点之间和 $n-k$ 个不被钦定点之间一定都是存在拓扑序的。考虑一个不被钦定点不被删去，一定满足这个点的连边情况恰好满足在 $k$ 个点的排名上存在分界点。上面那个条件使得不存在不被钦定点与两个被钦定点之间的环，另一...

线段树树链剖分 lct dp 竞赛图

2020-02-23

0 313

省选模拟28 题解

A. 战略游戏容易发现完全覆盖的边是连续的。考虑暴力做法，枚举两个点表示完全覆盖的路径，统计答案是两个点相对于父边的权值相乘。可以发现这个权值可以表示为一个简单生成函数的形式，去掉一条边的贡献，可以表示为直接除掉一个简单的多项式 $(k*x+1)$ 。但是不管怎么做复杂度都是 $O(...

dp 差分多项式贪心

2020-02-22

0 856

省选模拟27 题解

A. 飞行棋由于题目中给出了一些奇怪的条件，所以大概可以想到暴力模拟这个过程迭代若干轮。考虑如何比较好的进行迭代的过程，处理出一个数组 $f_{i,j}$ 表示在恰好第 $i$ 轮从 $j$ 这个位置走到 $n$ 的概率。那么考虑随时维护一个数表示游戏还没结束的概率，每次加入一个数转移即...

dp 分治决策单调性容斥

2020-02-22

0 394

省选模拟26 题解

A. 染色问题不然想到一个50分的dp，然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。考虑每次在已有的颜色序列中间插入一段，那么考虑转移的方案数，不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。所以枚举一共经过了多少次转移，转...

dp 倍增多项式二项式反演容斥线段树

2020-02-22

0 388