牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共11篇）

模拟7 题解

A. 方程的解 a，b均为正整数，exgcd求出x最小和最大的解。作差后除公差再加一，就是方程的解的数量。对于a，b，c中存在0或负数的情况，疯狂加特判。 B. visit 共走t步，要求到达坐标$(n,m)$。即总共向上走了n步，向右走了m步。设u为向上走步数，d为向下...

exgcd 数学组合计数 lucas定理中国剩余定理模拟 set

2019-07-22

0 414

模拟10 题解

A. 辣鸡(ljh) 模拟。对于同一块内的答案，直接统计。对于不同块内的，枚举i和大于i的$j=i+1～n$，一个有效的剪枝：以$x_1$为第一维排序，当$x_{1j}>x_{2i}+1$时break退出循环。然而如果用纵向链状的数据还是会被卡成$O(n^2)$，然而...

数学期望启发式合并线段树模拟

2019-07-30

0 344

模拟18 题解

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

数位dp dp 模拟

2019-08-12

0 368

模拟21 题解

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

数学 exgcd 模拟数位dp

2019-08-14

0 410

模拟54 题解

A. x 不妨考虑每一个质因子。那么拥有这个质因子的所有数都应当被分入一个集合中。而不拥有这个质因子的数可以有两种选择。将每个质因子的情况综合起来，用并查集维护一下联通块数量，答案就是$2^{cnt}-2$ B. y 暴力dp的设计是简单的，显然可以使用...

并查集搜索 dp 模拟

2019-09-29

0 804

模拟61 题解

A. 砖块简单模拟。对于最后一问，算一算复杂度就可以知道开map没有任何问题，然而map真的方便很多，所以为什么不用呢。 B. 数字容易发现末尾的0一定是被质因子2和5凑出。并且，对于任意的$n!$，质因子2的个数不小于质因子5的个数。简单的暴力$O(n)$做...

线段树模拟吉司机线段树 Hash 中国剩余定理数学

2019-10-06

0 416

模拟73 题解

A. 小P的2048 简单模拟。 B. 小P的单调数列首先有一个简单的dp。设$dp_{i,j}$表示已经选择的最后一个是第$i$个数，已经有了$j$个单调段。转移并不困难，简单数据结构维护一下可以做到$O(n^2logn)$ 然后发现这个dp的第二维其实可以省去。 ...

模拟结论题最小生成树

2019-10-14

0 363

模拟88 题解

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

dp 模拟凸包状压

2019-10-26

0 321

模拟98 题解

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

状压模拟构造题最短路 dp

2019-11-04

0 356

模拟101 题解

A. 五子棋简单模拟。注意获胜条件有四种情况不是三种 B. 迷宫对于每个点封掉$d$条路。考虑反向$dijkstra$跑最短路。对于每个元素$i$，当第$d+1$次取出时视作$dis(i,n)$，更新相邻的点。 C. 三华聚顶考场上的思...

dp 模拟最短路

2019-11-05

0 328