牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共14篇）

模拟6 题解

A. 那一天我们许下约定在写出来复杂度为$O(nmd)$的简单dp后，我们考虑优化。题中D的范围远大与N和M，我们在dp的过程中，很多一个饼干都不给的天数是无效的一天。于是我们dp出用i的有效天分完n个饼干的方案数，然后把这i个有效天分配到d天里即可。 $ans= \sum \...

dp 组合计数最短路基环树

2019-07-21

0 239

模拟36 题解

A. 字符题中保证$p_i<=1e5$，还可以很显然地发现当总长度大于$p_{max}+c$，一定不会更优。于是枚举长度的大小。将每一个限制对长度取模。显然如果相邻两个字符所在的区间存在交集，就表示状态非法。于是得到$O(m*p_{max})$的暴力。发现在取模的过程中...

最短路 ST表区间dp dp

2019-09-05

0 282

模拟48 题解

A. String Master $O(n^3)$随便做。 B. Tourist Attractions 因为数据范围$n^2$没有任何问题。考虑设$dp(i,j,k)$表示节点i从节点j来，并再走k步的方案数。显然$dp(i,j,1)=du(i)-1$，除了返回j，...

最短路 bitset dp

2019-09-22

0 282

模拟49 题解

A. 养花利用根号的一些性质，可以得到很多在最坏情况下$n\sqrt n logn$的算法，然而出题人似乎根本没有给这个算法分的意思。正解是分块。预处理出每个块内对于每个k的答案。对于询问，大块直接统计，小块暴力就可以了。设值域为s，块的大小为q，那么总共有$\frac{n}...

分块 dp 最短路

2019-09-22

0 299

模拟59 题解

A. Reverse 手玩第二个样例，发现可以dp。但是似乎没有显然的拓扑序，所以直接跑最短路。然而暴力建图$n^2$，解决方法是线段树优化建图。利用$bfs$每个点只在第一次被更新时最优的性质，直接用$set$或者链表维护也是可以的。 B. Silhouette ...

dp set 最短路容斥

2019-10-04

0 341

模拟83 题解

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

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

2019-10-23

0 325

模拟89 题解

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

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

2019-10-27

0 336

模拟90 题解

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

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

2019-10-27

0 218

模拟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 249

模拟98 题解

A. 线性代数 (algebra) B. 装饰 (decoration) 暴力记录每个点的当前状态和上传状态，可以做到$O(4^n)$ 注意到答案并不大，不妨设最终答案为$k$，考虑在时间点$i$，选择点$j$对最终态的贡献，即对每一层祖先的状态取反。所以可以直...

状压模拟构造题最短路 dp

2019-11-04

0 304