牛客237787563号

未归档

/ 注册

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

省选模拟1 题解

A. 天空碎片正解很麻烦，所以打表找规律 B. 未来拼图发现这个式子是一个简单的循环卷积式，所以要求的实际上是一个多项式在$mod\ x^n$意义下的平方根个数和最小字典序平方根。然而本题所要求的循环卷积与一般情况下的$2^k$不同。然而这个复杂度，可以直接做暴力DFT，即直...

多项式网络流

2019-12-24

0 393

数据结构+插头dp+多项式题解乱写

可持久化数据结构 A.森林树上的数据结构常可以启发式合并，用启发式合并的思路合并树上主席树就可以了。 B.影魔一个常见的这种数据结构题的套路是：离线询问，按右端点排序。在右指针扫过去的同时在数据结构（常为线段树）中更新该右端点能产生的答案。同时在数据结构中查询统计右端点对应的区间就好...

单调栈线段树状压 dp 多项式

2019-12-29

0 450

字符串专题测试1 题解

A. 阿尔法显然只要对位合并，最后查询不同的集合数就好了。似乎听过一个叫倍增并查集的东西，然而考场上没有$yy$出来。 $f_{k,i}$表示点$i$以及$i$往后数$2^k$个元素共同被合并的祖先。对于合并操作，直接用ST表的思路合并即可。考虑最终的下传操作：枚举倍增的次幂数...

并查集斯特林数生成函数多项式倍增

2020-01-02

0 427

数学专题测试1 题解

A. 解方程考虑没有任何限制的东西， m个元素分为n个连续的区间，直接用组合数插板法就好了。考虑如何去掉元素大于$a_i$的限制，只要给最终的元素个数减掉$a_i$就好了。考虑如何搞元素个数小于$a_i$的限制，不妨使用子集反演，要求的是恰好$0$个元素大于$a_i$。只要...

容斥 lucas定理组合计数数学多项式倍增 fwt dp 区间dp

2020-01-02

0 493

数学专题测试2 题解

A. B $[n=1]=\sum \limits_{d|n} \mu(d)$ 于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。设$f_n$表示$gcd$为$n$的倍数的答案。 $g_n$表示$gcd$为$n$的答案。 $g_1=\sum \limits_{i=1}^n\mu(i)...

矩阵线性代数莫比乌斯函数多项式数列

2020-01-05

0 441

数学专题测试3 题解

A. young 大概的意思是说，由低到高考虑不同的二进制位。形成一个最小生成树，那么最高二进制位不同的情况一定只出现一次。所以除掉最高位之后的情况形成两个集合，递归下去$dp$就好了。一个技巧是，将每个方案的最小值的总和，即$\sum \limits_{i}min(i)$转化为$\s...

莫比乌斯函数组合计数多项式数学杜教筛

2020-01-12

0 414

数学专题测试4

A. 猜拳游戏看到这个数据范围多半是高斯消元。所以问题是如何处理出每局的胜率。容易发现平局是没有意义的，要求的是最大的胜/负，这是一个分数问题，无法进行简单加和。所以正确的做法是01分数规划。通过二分答案，将分母部分直接作减法。于是只要维护最大的分子-$k*$分母就可以了。 ...

dp 高斯消元二分答案多项式拉格朗日插值分数规划

2020-01-29

0 499

省选模拟17 题解

A. 选择可以发现问题是$a$ $b$是否在一个边双里。因为没有强制在线，所以将难处理的删边转化为加边。对于一棵树上的加边操作，只要将两个点之间的路径上的点，添加到同一个边双集合里即可。因为边双的特殊性质，加上并查集的操作，这样只考虑树边的做法是正确的。具体的实现方法实际上通过并...

多项式并查集线段树树链剖分拉格朗日插值二分答案矩阵树定理

2020-02-03

0 424

省选模拟24 题解

A. U.N.OWEN就是她吗？字典序最大，只需要贪心。考虑用网络流来做这个题。每次二分一个答案，然后对当前操作和之前进行的操作与每个元素直接建边，判断是否存在完美匹配。因为题中保证了一个特殊性质，考虑通过霍尔定理优化。点集 $X,Y$ 存在完美匹配，仅当 $\forall Z ...

线段树生成函数二分图多项式最短路

2020-02-14

0 412

省选模拟26 题解

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

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

2020-02-22

0 388