牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共9篇）

模拟17 题解

A. 入阵曲求每一行的前缀和，枚举左右端点，O(n)扫下去，顺便更新桶。维护栈清空桶中的内容。 B. 将军令 k=1，小胖守皇宫弱化版。与小胖守皇宫比较，发现特殊性质：点没有权值。考虑贪心。每次找出深度最深的点，点亮它的k级父亲。 1.点...

差分 dp 贪心桶

2019-08-11

0 821

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

模拟94 题解

A. 凉宫春日的忧郁数据范围就长得很可写高精度的样子。可以维护高精度的高位，舍弃低位信息。正解是取对数。 $x^y=y*log\ x$ $y!=\sum \limits_{i=1}^{y}log\ i$ 然后可以直接比较两个取对之后的$double$类型。 B....

启发式合并分治虚树 dp 差分

2019-10-30

0 343

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394

省选模拟13 题解

A. 同桌的你每个人渴望与一个人当同桌。容易发现这个关系形成内向基环树森林。问题转化为求基环树森林的最大匹配。任意选一条环上的边，分别尝试该边为匹配边、非匹配边即可。 B. 大水题一个常用的但想不到的东西：将每种颜色出现次数的差值为定值，转化为对颜色序列差分后相等。然...

二分图二分答案 Hash 差分基环树 2sat

2020-02-01

0 474

省选模拟7 题解

A. 翻转硬币第一眼以为只要保证给定的$k$个点反面就好了，是弱智水题，于是感觉秒切了。然后考完20分，就被秒切了。所以实际上是一道原题。思路大概是对原序列进行异或意义下的差分，于是区间修改转化为两个点的修改。于是问题变化为将初态共$2k$个$1$消为$0$。然后发现每个有意...

状压最短路线段树平衡树差分 dp manacher

2020-01-14

0 400

省选模拟28 题解

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

dp 差分多项式贪心

2020-02-22

0 856

省选模拟38 题解

A. Inverse 似乎这类问题的套路都是考虑每一个点对。然后考虑一个 dp 。设 $f_{k,i,j}$ 表示考虑后 $k$ 轮，最终 $i$ 在 $j$ 左面的方案数。对于每个 dp 值可以简单枚举翻转区间， $O(n^2)$ 转移。然后发现这个玩意可以优化，如果枚举翻转区间...

分块单调指针差分 dp 计算几何平衡树凸包

2020-03-05

0 428

省选模拟41 题解

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

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

2020-03-09

0 359