牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟61 题解

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

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

2019-10-06

0 416

模拟60 题解

A. 嘟嘟噜约瑟夫问题，然而线性过不去。观察本题的特殊性质：m远小于n。再看递推公式，发现当m很小的时候取模次数并不多，所以在这种情况下可以直接用一次乘法代替多次加法。 B. 天才绅士少女助手克里斯蒂娜拆一拆式子就可以将i和j分离出来。然后用分治的思想在线...

分治线段树树状数组 dp

2019-10-06

0 341

模拟59 题解

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

dp set 最短路容斥

2019-10-04

0 436

模拟58 题解

A. Divisors 看题看了很长时间。然后发现似乎是弱智题。用一个哈希表统计每个因子出现了多少次就可以了。 B. Market 显然将物品和询问都排序，单调指针就不用管时间限制。刚开始看成了无限背包，看到数据范围就傻了，$c=10^9$还无法矩阵快速幂。打...

并查集离线直径 dp 分治线段树启发式合并

2019-10-03

0 383

模拟57 题解

A. 天空龙一个很好的性质是：最优方案可以不存在一个颜色A，转化为B再转化为C。因为将A直接转化为C一定更优。所以无需分类讨论，直接用一个sum判断正负就可以了。 B. 巨神兵有向图无环，所以存在拓扑序，所以用分层图dp。设f(i,j)表示已经考虑点集i，并且...

dp 容斥状压拓扑排序

2019-10-03

0 410

模拟56 题解

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

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

2019-10-03

0 322

模拟55 题解

A. 联一眼线段树。觉得T1似乎不应该这么难打。然而看了几分钟没有想出更好的做法。于是花了二十多分钟码了线段树。段错误一会之后，一遍过样例就交了。后来对拍也过了，很偷税。所以直接维护一下出现位置最靠坐的0 1就行了。一种比较好的离散化做法是将左闭右闭的区间转化为左闭右...

线段树三分 dp

2019-09-29

0 286

模拟54 题解

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

并查集搜索 dp 模拟

2019-09-29

0 804

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

模拟52 题解

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

二分答案矩阵 dp 线段树

2019-09-27

0 338