牛客237787563号
牛客237787563号
全部文章
分类
未归档(241)
归档
标签
去牛客网
登录
/
注册
牛客237787563号的博客
全部文章
(共132篇)
数据结构+插头dp+多项式 题解乱写
可持久化数据结构 A.森林 树上的数据结构常可以启发式合并, 用启发式合并的思路合并树上主席树就可以了。 B.影魔 一个常见的这种数据结构题的套路是: 离线询问,按右端点排序。 在右指针扫过去的同时在数据结构(常为线段树)中更新该右端点能产生的答案。 同时在数据结构中查询统计右端点对应的区间就好...
单调栈
线段树
状压
dp
多项式
2019-12-29
0
450
数学专题测试1 题解
A. 解方程 考虑没有任何限制的东西, m个元素分为n个连续的区间,直接用组合数插板法就好了。 考虑如何去掉元素大于$a_i$的限制, 只要给最终的元素个数减掉$a_i$就好了。 考虑如何搞元素个数小于$a_i$的限制, 不妨使用子集反演,要求的是恰好$0$个元素大于$a_i$。 只要...
容斥
lucas定理
组合计数
数学
多项式
倍增
fwt
dp
区间dp
2020-01-02
0
493
省选模拟6 题解
A. Yist 首先考虑怎样的情况答案是不收敛的。 操作中涉及到对一个权值非$0$,并且不作除法的点的加法贡献。 因为只要最终的答案,可以想到对每个点作为出边的贡献分别处理。 部分分提示求出第一次迭代的贡献,发现对于每个点,贡献都是一个等比数列,所以只要代入求和公式就好了。 然而暴力做的复...
分块
图论
后缀自动机
dp
树状数组
2020-01-13
0
393
省选模拟7 题解
A. 翻转硬币 第一眼以为只要保证给定的$k$个点反面就好了,是弱智水题,于是感觉秒切了。 然后考完20分,就被秒切了。 所以实际上是一道原题。 思路大概是对原序列进行异或意义下的差分,于是区间修改转化为两个点的修改。 于是问题变化为将初态共$2k$个$1$消为$0$。 然后发现每个有意...
状压
最短路
线段树
平衡树
差分
dp
manacher
2020-01-14
0
400
省选模拟10 题解
A. 食物链 在拓扑序上dp。 B. 选点游戏 要求支持合并两棵树,并同时维护树上最大独立集。 考虑特殊情况,每次只加一个标号最大的点,问题是一个简单的动态dp。 离线出最终树的形态,考虑加入的一个叶子节点,更新该节点到1号节点的轻链上信息就可以了。 其实想到这里,一个动态dp的做...
拓扑排序
树链剖分
dp
期望
动态dp
2020-01-29
0
365
数学专题测试4
A. 猜拳游戏 看到这个数据范围多半是高斯消元。 所以问题是如何处理出每局的胜率。 容易发现平局是没有意义的,要求的是最大的胜/负,这是一个分数问题,无法进行简单加和。 所以正确的做法是01分数规划。 通过二分答案,将分母部分直接作减法。 于是只要维护最大的分子-$k*$分母就可以了。 ...
dp
高斯消元
二分答案
多项式
拉格朗日插值
分数规划
2020-01-29
0
499
省选模拟12 题解
A. Colorado Potato Beetle 暴力做法是直接bfs。 优化的方法是离散化。 将特殊的点的横纵坐标抽出来,然后用这些横纵坐标为1e12*1e12分成一个个块,容易发现每个块内的状态是一致的。 然后用与暴力类似的方法即可,注意最后统计的是每个块的实际大小。 B. D...
后缀自动机
dp
状压
搜索
树链剖分
线段树
2020-02-01
0
359
省选模拟18 题解
A. 编码 一眼原题,是一道数据结构(?)优化2-SAT建图的题。 2-SAT还是比较容易看出来的,每一个串只有$0/1$两种取值,一个串对另一个串起到了限制的作用。 于是暴力的做法就是先将所有的串按照长度排序,由小到大分别将两个副本插入字典树。 对字典树上每个节点维护一个vector,表示...
单调指针
Hash
dp
高斯消元
二分答案
折半搜索
2sat
trie树
2020-02-05
0
387
省选模拟21 题解
A. 灯 容易发现问题是连通块数,因为原图是树,可以用点数(为$1$的点)减边数(连接相邻的为$1$的点的边)表示。 点数是易于维护的,所以问题是维护边数。 考虑一个情况,每种颜色的出现次数都很少,那么可以直接在原序列上暴力。 另一种情况,每种颜色的出现次数都很多,并且颜色总数不多。 那么...
根号分治
dp
图论
2020-02-08
0
317
省选模拟26 题解
A. 染色问题 不然想到一个50分的dp,然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。 考虑每次在已有的颜色序列中间插入一段,那么考虑转移的方案数,不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。 所以枚举一共经过了多少次转移,转...
dp
倍增
多项式
二项式反演
容斥
线段树
2020-02-22
0
388
首页
上一页
4
5
6
7
8
9
10
11
12
13
下一页
末页