牛客237787563号

未归档

/ 注册

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

省选模拟46 题解

A. 俄罗斯方块一道很神奇的 bitset 题。考虑维护每个格子最上面属于哪个块，这个东西可以用一个 set 来维护每个连续段，操作方法类似珂朵莉树。对于每次操作，直接用 set 遍历每个有交的连续段，询问并取 $\max$，以得到当前的高度，然后进行覆盖操作。所以现在的问题是，有一...

容斥多项式 set bitset 提交答案

2020-03-16

0 851

省选模拟45 题解

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

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

2020-03-14

0 467

省选模拟44 题解

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

dp 树状数组数学线段树

2020-03-13

0 368

省选模拟42 题解

A. coin 容易发现每种假钞的期望贡献是独立的。对于每种假钞，做一个 $n^2$的 dp 求出来选择 $i$张假钞的贡献。然后对这个贡献做一个背包就完事了。考虑一个东西，就是对于每种假钞，只能选择一个数目加入背包的贡献中。所以可以考虑对于每种假钞一张张加入贡献。然后发现发现...

矩阵树定理二项式反演 dp 2sat

2020-03-10

0 353

省选模拟41 题解

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

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

2020-03-09

0 359

省选模拟40 题解

A. 染色问题考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。对于一种染色方案，当 $col_a=col_b$，边权为 $x$，否则边权为 $y$。取 $x=1,y=0$，一种染色方案的贡献是所有边权的乘积，那么答案就是对于每种染色方案的贡献的和。发现这个玩意可以合并。...

组合计数状压网络流二项式反演

2020-03-08

0 754

省选模拟39 题解

A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。容易发现交换的次数就是点数减环数。所以原题转化为环的计数问题。考虑把已有的每个连通块的部分表示出来。容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。如果已...

lct 二项式反演后缀自动机容斥组合计数

2020-03-06

0 410

省选模拟38 题解

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

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

2020-03-05

0 428

省选模拟37 题解

A. 奶酪发现问题是求删去每一条边之后两个连通块的直径。也就是子树直径和除掉子树之外的直径。容易发现一个简单的维护三个最值的换根 $dp$ 就解决了。然而换根 $dp$ 容易写错。所以考虑子树直径直接合并就完事了。对于除掉子树之外的直径，可以考虑除掉一段连续的 $dfs$ 序...

dp KMP 高斯消元提交答案直径

2020-03-04

0 376

省选模拟36 题解

A. Alchemy 考虑递归挪动这个塔的过程。然后发现有一些递归是没有必要的。通过初始状态可以判断递归的前半部分或后半部分是没有必要的。直接统计不递归的部分的贡献，然后递归另一部分就好了。这样的复杂度应该可以做到线性。 B. Algebra 要统计这个答案无非两个办法。...

多项式

2020-03-03

0 396