牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共12篇）

模拟7 题解

A. 方程的解 a，b均为正整数，exgcd求出x最小和最大的解。作差后除公差再加一，就是方程的解的数量。对于a，b，c中存在0或负数的情况，疯狂加特判。 B. visit 共走t步，要求到达坐标$(n,m)$。即总共向上走了n步，向右走了m步。设u为向上走步数，d为向下...

exgcd 数学组合计数 lucas定理中国剩余定理模拟 set

2019-07-22

0 414

模拟42 题解

A. 世界线毒瘤出题人，bitset题卡空间。于是将所有的点分成两份，做两次拓扑排序，bitset只用开一半，空间就能够了。 B. 时间机器似乎是很显然的贪心，然而没想到。只会打更加显然的网络流暴力。按左端点排序，set维护一下不断取后继就行了，当没有后继即为无解。...

bitset 拓扑排序 set 贪心数位dp

2019-09-13

0 384

模拟59 题解

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

dp set 最短路容斥

2019-10-04

0 436

模拟74 题解

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

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

2019-10-15

0 374

模拟96 题解

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

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

2019-11-04

0 408

模拟97 题解

A. 小盆友的游戏手玩表找规律。 B. 花弱智$dp$题，用逆元随便处理一下就能处理字符集很大的问题。 C. 表格利用了扫描线的思想。首先将横坐标离散化，对纵坐标建线段树。枚举横坐标，则矩形转化为在横坐标的左边界$insert$，在右边界+...

扫描线 set 线段树

2019-11-04

0 729

模拟99 题解

A. 陶陶摘苹果一眼线段树维护单调栈，所以写就完了。当然本题中修改不继承，所以有更好的一个$log$的做法。 B. 开心的金明贪心地选择当前最优的策略。用一个$set$维护备选的集合。当跨月的时候，如果集合中元素个数大于限制数，可以不断去除最劣的选择。 ...

set 贪心线段树单调栈构造题

2019-11-04

0 359

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟45 题解

A. matrix 当然考虑左端点为 $l$的所有矩形的贡献。通过一个 trie，对 trie 上每个节点开一个 set，来找到每个串 $s$ 存在的位置。那么可以把当前答案的形式化成 $ans=\sum \limits_{s} val_s$ ，其中 $val_s$ 表示这个串出现的区间数...

多项式 trie树 set dp 启发式合并扫描线线段树

2020-03-14

0 467

省选模拟46 题解

A. 俄罗斯方块一道很神奇的 bitset 题。考虑维护每个格子最上面属于哪个块，这个东西可以用一个 set 来维护每个连续段，操作方法类似珂朵莉树。对于每次操作，直接用 set 遍历每个有交的连续段，询问并取 $\max$，以得到当前的高度，然后进行覆盖操作。所以现在的问题是，有一...

容斥多项式 set bitset 提交答案

2020-03-16

0 851