牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共24篇）

模拟19 题解

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

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

2019-08-14

0 342

模拟26A 题解

A. marshland 考试时想到了网络流，然而不会建图，就死了。正解是最大费用可行流。比较容易想到的是将每个点拆为两个点， s连没有危险值的入点，没有危险值的入点连有危险值的入点，入点出点之间限流有费用，出点再连没有危险值的出点，这些出点连向t。不断跑spfa，通过有流量...

二分答案网络流后缀数组 bitset 树链剖分

2019-08-20

0 385

模拟30A 题解

A. 树联想起远古考试时做的题记忆的轮廓。树上走一些步数的期望。显然可以直接解方程。然而复杂度$O(qn^3)$，利用树上的性质优化一下，直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。然而只有20分。预处理出每个点走到每个儿子的期望步...

dp 期望 Hash 二分答案字符串启发式合并

2019-08-25

0 306

模拟45 题解

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

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

2019-09-18

0 369

模拟52 题解

A. 平均数刚开始没想到。突然想到二分判定。然后想到平衡树，想着这题也太难了。然后想到树状数组离散一下就好打了。然后忘了开longlong，被搞成了60分。其实精度确实有问题，和暴力拍千组左右数据会出错。所以其实问题是求逆序对，打归并排序或许常数会小一点。 ...

二分答案矩阵 dp 线段树

2019-09-27

0 338

模拟56 题解

A. Merchant 看到一次函数，马上想到维护一个凸包，或许可以维护一下前m大一次函数的总和？然而想了想并不会维护，于是转换了下思路。似乎答案具有单调性：除去答案为0的情况，其它一定具有单调性。结论是显然的。不妨考虑任何一个组合。一些一次函数的和仍为一次函数。如果总一次...

二分答案高斯消元树状数组单调指针

2019-10-03

0 322

模拟68 题解

考试过程大概是：上来看T1，看懂了题但是丝毫没有思路，甚至没有想到第一步贪心，心态稍崩。接着看T2，发现似乎可以直接上主席树上树，然后想了想复杂度，直接找前趋后继，复杂度似乎很正确。 T3只会暴力。然后就回去把T2切了，一遍过大样例自信不对拍。结果忘了在线这回事，一个小时之后才发现...

trie树主席树贪心位运算二分答案

2019-10-11

0 401

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

模拟87 题解

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

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

2019-10-25

0 374

模拟96 题解

A. 求和显然可以将式子中的行列贡献分开考虑。于是问题转化为等差数列求和。然而模数比较大，为了避免高精度可以用慢速乘。 B. 分组配对显然问题具有单调性，于是可以二分答案，然而这个算法并没有什么用。考虑使用基于倍增的二分。然后用个归并排序，因为$\sum ...

倍增二分答案 dp set 启发式合并树链剖分

2019-11-04

0 408