牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

模拟12 题解

A. 斐波那契(fibonacci) 首先想到a,b<=1e6的暴力：建树，直接向上标记求lca。建树的过程中发现一个性质。斐波那契第n代兔子，是n-2代及以前的兔子的儿子。因为编号连续且与父亲编号大小有关，设该节点的编号为$x$，在第$k$代，则$f(x)=x-fib(...

数列线段树 dp 单调队列贪心拓展域并查集

2019-08-03

0 399

模拟32 题解

A. chinese 要求的答案是所有情况总的炼字个数。观察到题中k的范围比较小，所以对k下手。枚举炼字的大小，限制与它同一行同一列的数的大小，其它数随便选就可以了。直接快速幂，$O(klogmod)$可过。写的帅一点，弄个线性筛，直接推一些东西，复杂度就变成$O(\frac{kl...

单调队列期望组合计数

2019-09-03

0 307

模拟84 题解

A. Smooth 考虑用已有的光滑数推出新的光滑数。显然每次可以取出最小的光滑数，并乘每个质因子插入堆中。需要通过哈希表打标记来解决重复计数的问题。复杂度为$O(kblogk)$，空间应该也承受不住。正解显然不带$log$。因为我们每次取出的都是最小的光滑数，其实堆有些多余。...

单调队列 Hash dp

2019-10-24

0 0

CSP-S 2019 题解

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

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

2019-12-02

0 477

数据结构乱写

loj6515 贪玩蓝月容易发现本题中要求的信息不支持快速合并，不支持快速删除，但是支持快速插入。所以一个简单的离线做法就是线段树分治。只要按照时间建线段树，把每个操作插入到对应节点上。最后 \(dfs\) 一遍线段树顺便插入，在叶子节点输出答案即可。然而这个信息是支持快速合并两个信息的。...

dp 单调队列分块启发式合并线段树 lct

2020-07-13

0 448