牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共241篇）

模拟80 题解

A. 贝尔数这个数据范围，似乎显然是矩阵快速幂。对模数质因数分解就会发现每个质因子只出现一次且很小。所以考虑求出$mod$每个质因子的结果并$crt$合并。题中已经给出了贝尔数在模$p$意义下的一个公式，所以直接保存$p$个贝尔数，矩阵快速幂转移就可以了。 B...

线性代数矩阵 AC自动机 dp 二分图网络流

2019-10-20

0 368

模拟79 题解

A. 树发现问题是树上对祖先链维护单调栈，然后分别二分权值和深度。因为已经做过一个类似的题，直接维护一个基于倍增进行二分的链栈（或者叫可持久化单调栈？）就完了。 B. 环 circle 一个结论是：在竞赛图中，要么不存在环，要么存在的最小环为三元环。虽然想不到，...

单调栈图论桶结论题

2019-10-20

0 365

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

模拟77 题解

A. 位运算位运算，显然可以按位处理。所以大力分类讨论就完了。 B. 集合论通过维护一个$add$标记，直接进行全体的加减法。因为值域只有$10^6$，直接维护一个桶。求并集的操作是简单的，直接尝试加入。求交集涉及到删除的操作，然而在桶中删掉元素并不是简单...

容斥位运算

2019-10-17

0 359

模拟76 题解

A. 序列观察部分分，可以得到一些奇怪的构造方法。比如当$N=A*B$，直接将数按$A$的大小或$B$的大小分块就可以了接着打表，发现似乎全部的情况都可以通过类似的方法构造出来。只要对后面的部分分块，前面不足的部分不用分块。 B. 购物奇妙的数的范围很宽泛，达...

构造题 dp 组合计数

2019-10-17

0 297

模拟75 题解

A. 导弹袭击想到了凸包，推出了题中的式子，然而没有继续推下去。或者说，高考数学线性规划没有学好。一种导弹的飞行时间函数为： $z_i=A*\frac{1}{a_i}+B*\frac{1}{b_i}$ 似乎显然是一个线性规划式，设$x=\frac{1}{a_i},y=\frac{1}...

dp 单调栈凸包高斯消元倍增

2019-10-16

0 0

模拟74 题解

A. 梦境已经做过很多类似的套路题。都是排序后贪心就完了。将所有的区间以右端点排序，因为每个区间对答案贡献相同为1，区间右端点不断增加，那么显然可以直接取尽量靠左的点。用$multiset$维护一下点，支持后继操作就可以了。因为题中有相同的点，用$set$必死。 ...

dp 贪心组合计数 set 图论树状数组

2019-10-15

0 374

模拟73 题解

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

模拟结论题最小生成树

2019-10-14

0 363

模拟72 题解

A. 简单的序列将‘（’视作1，‘）’视作-1。那么问题转化为给定中间一段序列，要求前缀和恒不小于0，且权值和等于0的方案数。暴力dp求出i位产生j个左括号剩余的方案数，显然右侧是对称的。然后直接暴力枚举左侧有多少个左括号就完了。需要注意中间一段应当对前缀和不断取min，得出左侧...

dp 结论题组合计数

2019-10-14

0 382

模拟71 题解

A. 毛一琛暴搜复杂度$O(3^n)$，所以显然的优化是$meet\ in\ the\ middle$ ，可以优化为$O(\sum \limits_{i=1}^{n} \binom{n}{i}2^{\frac{i}{2}})$。只要将每个状态都分成两半，分别求出可能的方案，再枚举左侧一种...

搜索 dp 拓扑排序二分答案

2019-10-13

0 378