牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟58 题解

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

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

2019-10-03

0 383

模拟59 题解

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

dp set 最短路容斥

2019-10-04

0 436

模拟60 题解

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

分治线段树树状数组 dp

2019-10-06

0 341

模拟63 题解

A. Median 线性筛完质数，就会发现给的时间已经快没了。所以只能$O(n)$求$n-k$个中位数？不会做，所以打权值线段树。在权值线段树上二分找第k大值，可以做到$O(nlogn)$。打$zkw$线段树，比传统线段树快一倍，然而并没有什么用，仍然T70。题中确实给出了一些...

dp 桶贪心

2019-10-07

0 407

模拟67 题解

A. 神炎皇尝试枚举$a$,$b$的$gcd$，设为$d$。那么有$$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} [gcd(i,j)==d][i+j<=n][i+j|i=j]$$ ...

dp 数学树状数组

2019-10-10

0 385

模拟69 题解

A. chess 想一下合法方案是怎样的。因为要保证每一个正方形合法，所以新加的一列中棋子个数等于刚刚删去一列的棋子个数。当$m$很大的情况下，$mod\ n$相同的列转移系数都是相同的。接着考虑，其实$m\ mod\ n$列转移了$m/n+1$次，而$n-m\ mod \ n$列转移...

dp 组合计数单调栈莫队离线并查集

2019-10-12

0 304

模拟70 题解

A. 木板相似三角形，简单推出结论。发现要求的是$\sum \limits_{i=1}^{n-1}[n|i*i]$。那么只要把$n$质因数分解，设为$\prod_{j}^{} p_j^{c_j}$，那么设$k$为最小的合法的$i$，有$k=\prod_{j}^{} p_j^{\l...

数学 dp 构造题搜索

2019-10-13

0 301

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

模拟72 题解

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

dp 结论题组合计数

2019-10-14

0 382

模拟74 题解

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

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

2019-10-15

0 374