牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共18篇）

模拟19 题解

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

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

2019-08-14

0 342

模拟27 题解

A. 小奇挖矿2 看完题，小凯的诱惑？大于17的点可以直接转移，反之则暴力枚举。去一下重，记录前缀最大值转移就完了。 B. 小奇的矩阵(matrix) 题中要求输出答案的整数，然后就不理解。暴力化简式子。最终化为： $(n+m-1)\sum \limits_...

位运算结论题 dp

2019-08-20

0 352

模拟33 题解

A. 春思比较简单的一道题，甚至是见过的原题。约数和是积性函数，搞一搞等差数列求和，乘到一起就可以了。 B. 密州盛宴显然，方案合法的条件是苏轼每轮都能吃到菜。所以就发现任意后缀0,1个数必须满足，$sufcnt_0-sufcnt_1<=1$。所以当不满...

dp 数学结论题单调指针

2019-09-03

0 348

模拟34 题解

A. 次芝麻显然答案是$min(n*2^k$%$(n+m),(n+m)-n*2^k$%$(n+m))$ 因为每一次乘2，在取模意义下，选大选小是等价的。 B. 喝喝喝 $a_x$%$a_y=k$ $a_x-k=a_y*m$ 所以直接对$a_x-k$质因数分解，两个单调指针乱...

dp 中国剩余定理结论题单调指针

2019-09-03

0 367

模拟45 题解

A. kill 显然本题可以二分答案。于是问题转化为判断一个距离是否可行。将人和怪物分别按位置排序，那么每个人选择范围内可以选择的最靠左的怪物，不会使答案更差。单调指针扫一遍就可以了。 B. beauty 统计每条边儿子方向上的关键点数量，设为$cnt[i]$...

二分答案单调指针结论题 lct 最小生成树

2019-09-18

0 369

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365

模拟72 题解

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

dp 结论题组合计数

2019-10-14

0 382

模拟73 题解

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

模拟结论题最小生成树

2019-10-14

0 363

模拟79 题解

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

单调栈图论桶结论题

2019-10-20

0 365

模拟83 题解

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

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

2019-10-23

0 400