牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟92 题解

A. 数列要求$ax+by=s$，使得$abs(x)+abs(y)$最小的一组解$(x，y)$。首先用$exgcd$求出一组特解$(x_1,y_1)$。因为$a,b$均为正数，可以将$s$转化为正数。不妨将解$x,y$画到一个坐标系上，显然$abs(x)+abs(y)$在$x$接...

exgcd dp 线段树最短路

2019-10-29

0 315

模拟91 题解

A. Dove 打扑克显然的结论是：超过$\sqrt n$的牌堆不会超过$\sqrt n$个。所以可以分块维护信息：对于牌数小于$\sqrt n$的，用一个桶维护。对于牌数大于$\sqrt n$的，用$vector$暴力插入删除维护。同时维护答案，为了做到$O(1)$修改，也用分...

分块 dp 线段树猫树位运算

2019-10-28

0 386

模拟90 题解

A. 新的世界显然与顺序无关，所以问题转化为最短路问题。用$dijkstra$的思想贪心。 B. 邻面合并看到这个数据范围，显然是状压。矩形上的操作，考虑轮廓线/插头dp。然而逐个转移似乎有些复杂，所以逐行转移，大力分类讨论。压缩状态的方法有很多。 ...

最短路状压 dp 线段树轮廓线

2019-10-27

0 308

模拟89 题解

A. 666 应当注意到一个结论：带着一个剪贴板进行删除操作是没有意义的。可以转化为粘贴之后删除。所以直接跑spfa求最短路。注意到答案不超过48，所以边权超过48的边可以忽略。 B. 1234567 显然用莫比乌斯函数容斥。发现答案为$\sum \lim...

线段树单调栈最短路数论分块莫比乌斯函数杜教筛

2019-10-27

0 430

模拟88 题解

A. 军训队列仔细看题，会发现问题是随便交换位置。为了使答案更小，显然可以进行排序后$dp$。有$dp_{i,k}=dp_{j-1,k-1}+(a[i]-a[j])^2$。拆开平方式会发现是最简单的斜率$dp$式，而且$a$数组是单调的。所以用单调队列维护一下凸包就完了。因为...

dp 模拟凸包状压

2019-10-26

0 321

模拟87 题解

A. maze 做过类似的题，维护最短路对于$k$的一个凸包，答案就是凸包与$y=s$直线交点的横坐标，这个还挺难打的。然而答案显然具有单调性，所以直接二分答案就完了。实际上，这个二分答案的操作，等价于选定直线$x=mid$，求出$x=mid$与凸包的交点的纵坐标，并通过这个纵坐标与$...

凸包二分答案 dp 线段树字符串

2019-10-25

0 374

模拟86 题解

A. 异或位运算所以按位考虑。数位$dp$统计每一位$0/1$的取值个数，随便乘一乘就出结果了。 B. 取石子 $O(n^4)$的$dp$是显然的。可以发现$dp$中必败的状态是很少的。所以直接打表所以可以用必败的状态刷表进行$dp$，复杂度是对的。 ...

数位dp 博弈论 dp 位运算

2019-10-25

0 431

模拟85 题解

A. 表达式密码观察样例，发现答案就是将减法拆为一个减法和多个加法，于是就完了。 B. 电压机制发现问题是认为一条边相邻的两个点颜色相同并不考虑这条边，问图能否二分图染色。暴力做法是$O(nm)$的。仔细想想就可以发现：对于奇环，不能二分图染色，所以必须选择奇...

二分图 tarjan 贪心

2019-10-25

0 697

模拟84 题解

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

单调队列 Hash dp

2019-10-24

0 0

模拟83 题解

A. 最大异或和异或是不进位加法。具有一个很好的性质：$a\ xor\ b=c$ $\rightarrow$ $c\ xor\ b=a$ 若所有点的异或和为$0$,那么显然平手。若异或和不为$0$,先手只要将最高位的$1$选到必胜。 B. 简单的括号序...

dp 结论题组合计数位运算分块最短路

2019-10-23

0 400