牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

省选模拟27 题解

A. 飞行棋由于题目中给出了一些奇怪的条件，所以大概可以想到暴力模拟这个过程迭代若干轮。考虑如何比较好的进行迭代的过程，处理出一个数组 $f_{i,j}$ 表示在恰好第 $i$ 轮从 $j$ 这个位置走到 $n$ 的概率。那么考虑随时维护一个数表示游戏还没结束的概率，每次加入一个数转移即...

dp 分治决策单调性容斥

2020-02-22

0 394

省选模拟28 题解

A. 战略游戏容易发现完全覆盖的边是连续的。考虑暴力做法，枚举两个点表示完全覆盖的路径，统计答案是两个点相对于父边的权值相乘。可以发现这个权值可以表示为一个简单生成函数的形式，去掉一条边的贡献，可以表示为直接除掉一个简单的多项式 $(k*x+1)$ 。但是不管怎么做复杂度都是 $O(...

dp 差分多项式贪心

2020-02-22

0 856

省选模拟29 题解

A. circle 容易发现，如果存在一组合法答案，那么 $k$ 个钦定点之间和 $n-k$ 个不被钦定点之间一定都是存在拓扑序的。考虑一个不被钦定点不被删去，一定满足这个点的连边情况恰好满足在 $k$ 个点的排名上存在分界点。上面那个条件使得不存在不被钦定点与两个被钦定点之间的环，另一...

线段树树链剖分 lct dp 竞赛图

2020-02-23

0 313

省选模拟31 题解

A. Skip 一眼决策单调性，但是感觉因为带个权值就不好处理了。实际上对权值开个线段树，然后直接在线段树上维护决策单调性就完事了。而且这个式子是一个显然的斜率优化 dp ，在权值线段树上维护凸包也挺套路的。感觉这题没做出来比较可惜，没有想到通过对权值开线段树，来实现权值的无关操作。 ...

状压线段树凸包 dp 决策单调性

2020-02-26

0 410

省选模拟32 题解

A. 送你一道签到题这个函数显然是个积性函数。刚开始的想法是可以直接考虑分开每个质因子，然后乘一块的贡献显然是正确的。后来一想这个玩意实际上就是 $id^k$ 点积上 $d(x)$ 的 $m$ 次卷积，所以肯定是积性的。然后看这个数据范围，显然要搞个 min25筛。然后一想，这...

容斥 trie树 min25筛 dp 数学

2020-02-26

0 295

省选模拟37 题解

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

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

2020-03-04

0 376

省选模拟38 题解

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

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

2020-03-05

0 428

省选模拟42 题解

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

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

2020-03-10

0 353

省选模拟44 题解

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

dp 树状数组数学线段树

2020-03-13

0 368

省选模拟45 题解

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

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

2020-03-14

0 467