牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟24 题解

A. Star Way To Heaven 如果二分答案，问题就转化为不经过一些等大的圆，能否从左侧到达右侧。然后我就不会了。其实问题很简单：不能从左侧走到右侧，等价于能从下侧沿障碍走到上侧，也就是说一些圆将路阻断开。二分答案，用并查集或者dfs都可以做到$O(k^2)$建边之后$...

启发式合并线段树单调栈最小生成树凸包

2019-08-17

0 355

模拟23 题解

A. mine 设dp(i,0/1/2/3,0/1)表示前i位，且第i位填入0/1/2/炸弹的方案数。当第i位填入1的时候，需要关注炸弹在1的左侧或者右侧，故加半维表示炸弹在1的哪一侧，当i为不为1，最后一维无意义。简单转移。 B. water 第一眼：直接考虑临...

dp 最小生成树莫比乌斯函数桶容斥

2019-08-16

0 407

模拟22 题解

A. 数论一条性质：对于一个不良好的数$x$，$x*p^c$一定不是良好的。因为那些小于x，并且因数比x多的数，乘上$p^c$仍然更优。这个性质告诉我们：一个目前认为不优的数，不会贡献出良好的数。显然最大的质因子不会很大，良好的数也不会很多。 ...

dp 数位dp 位运算

2019-08-15

0 372

模拟21 题解

A. 折纸考虑$O(nm)$暴力，对于每次操作，暴力修改n个点的下标，同时维护左右端点下标，最后相减就是答案。对于后40分，n的范围很大。恰好我们并不关注每个点的下标。对于每次翻折， $O(m)$查询并记录下翻折操作时的下标即可。注意每次操作不能单纯向一个方向翻折。 ...

数学 exgcd 模拟数位dp

2019-08-14

0 410

模拟20 题解

A. 周(week) 搜索。 B. 任(duty) 对于树上的联通块。存在性质：点数=边数+1 也就是说：点数-边数=联通块数。预处理出点，横向边，纵向边的二维前缀和，即可$O(1)$回答每个询问。 C. 飞(fly) 题目中定义鬼畜值为$\f...

2019-08-14

0 369

模拟19 题解

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

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

2019-08-14

0 342

模拟18 题解

A. 引子模拟完了 B. 可爱精灵宝贝注意到特殊性质： 1.对于每个位置，只关注第一次到达的时间。 2.人走的区间是连续的。问题转化为区间dp。设$dp(i,j,k,0/1)$表示在$k$时间走完区间$(i,j)$，当前在区间的左/右端点的最优答...

数位dp dp 模拟

2019-08-12

0 368

模拟17 题解

A. 入阵曲求每一行的前缀和，枚举左右端点，O(n)扫下去，顺便更新桶。维护栈清空桶中的内容。 B. 将军令 k=1，小胖守皇宫弱化版。与小胖守皇宫比较，发现特殊性质：点没有权值。考虑贪心。每次找出深度最深的点，点亮它的k级父亲。 1.点...

差分 dp 贪心桶

2019-08-11

0 821

模拟16 题解

A. Blue 贪心完了。这道题学到了很多使用stl set的技巧。 B. Weed 线段树维护栈的操作。一个重要的操作是递归结束时$O(logn)$复杂度的向下寻找分界点。因为延伸出的一定是一条链，复杂度是$O(nlog^2n)$ ...

线段树贪心十字链表

2019-08-10

0 328

模拟15 题解

A. 建设城市（city）相较于那一天我们许下约定，数据范围有所改变。如果不考虑k的限制，是显然的插板法。枚举至少超过限制的个数，大力容斥就完了。 B. 轰炸行动（bomb）论如何看懂题。如果能够理解题意，缩了scc，拓扑排序求个点带权最长链就完...

容斥组合计数数学 tarjan 图论 dp 期望

2019-08-10

0 337