牛客237787563号

未归档

/ 注册

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

模拟19 题解

A. count 结论题一棵树可以被分为d块，当且仅当子树节点个数和为d的倍数的节点有$\frac{n}{d}$个。对于任何一个树，size为d的倍数的节点个数不会超过$\frac{n}{d}$个。在以上情况下，在每个符合的节点与父亲的路上截断，是一种合法方案。故得证。 ...

图论最短路计数倍增二分答案结论题

2019-08-14

0 342

模拟75 题解

A. 导弹袭击想到了凸包，推出了题中的式子，然而没有继续推下去。或者说，高考数学线性规划没有学好。一种导弹的飞行时间函数为： $z_i=A*\frac{1}{a_i}+B*\frac{1}{b_i}$ 似乎显然是一个线性规划式，设$x=\frac{1}{a_i},y=\frac{1}...

dp 单调栈凸包高斯消元倍增

2019-10-16

0 0

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

模拟96 题解

A. 求和显然可以将式子中的行列贡献分开考虑。于是问题转化为等差数列求和。然而模数比较大，为了避免高精度可以用慢速乘。 B. 分组配对显然问题具有单调性，于是可以二分答案，然而这个算法并没有什么用。考虑使用基于倍增的二分。然后用个归并排序，因为$\sum ...

倍增二分答案 dp set 启发式合并树链剖分

2019-11-04

0 408

模拟105 题解

A. 小W的魔术考虑问题的逆问题，怎样的字符串是好的字符串。即长度为$n$，前缀与给定字符串的前缀匹配，后缀与给定字符串的后缀匹配的字符串个数。不妨枚举给定字符串的断开点，那么答案即$(len+1)*26^{n-len}$ 然而这里面有重复计算的方案，把它画出来就可以发现，相邻两次...

结论题 dp 倍增组合计数数位dp

2019-11-08

0 357

模拟114 题解

A. A 正解是给二次函数除一个$x$，于是问题转化为简单的单调栈维护凸包问题。最后直接乘回一个$x$就好了。然而考场上并没有想到这个东西，所以维护答案$x$的最优转移点，暴力枚举最优转移点的前后三百个最优的二次函数就好了。本来以为自己打了个乱搞特别没素质，后来发现因为数据保证值域...

倍增单调栈凸包

2019-11-14

0 333

CSP-S 2019 题解

D1T1-格雷码题中给出了构造格雷码的方法。 $solve(n,k)$表示求出$2^n$意义下排名为$k$的格雷码，只要比较一下考虑最高位的0/1取值就好了。部分分提示了要开$unsigned\ long\ long$，注意一下就可以了。 D1T2-括号树子序列...

倍增单调队列 dp 并查集贪心

2019-12-02

0 477

字符串专题测试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

省选模拟26 题解

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

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

2020-02-22

0 388