牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共26篇）

省选模拟25 题解

A. 环是一道很巧妙的构造题。考虑写出满足条件的 $s_i,s_{i+1}$ 一定满足的式子。设 $x_{i,j}$ 表示 $s_i$ 中第 $j$ 个 $1$ 的位置。由操作A有 $k*t+\sum \limits_{j=1}^k x_{i,j}\equiv \sum \limi...

构造题贪心字符串并查集

2020-02-18

0 344

省选模拟28 题解

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

dp 差分多项式贪心

2020-02-22

0 856

省选模拟34 题解

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

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

2020-02-29

0 327

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

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381

省选模拟102 题解

A. island 对于正负不同的情况，\(O(n)\) 枚举左侧的位置然后计算。对于正负性相同的情况，把笛卡尔树建出来，然后每次考虑跨过最小值的贡献。分几种情况：左右均不超过最小值，左右仅有一个超过最小值，左右都超过最小值。然后顺便统计上其中一个端点为划分点的贡献。然后疯狂的写式子拆式子就没...

圆方树贪心单调栈

2020-05-21

0 388