牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共73篇）

模拟100 题解

A. 组合将两个字符之间建边，问题转化为一笔画，也就是欧拉路问题。所以直接用dfs压栈的方法解决，注意正确使用当前弧优化。 void dfs1(int x){ for(int i=head[x];i;){ if(vis[i>>1]){ head[x]...

dp 线段树图论欧拉路状压

2019-11-05

0 369

模拟102 题解

A. 你相信引力吗显然是单调栈处理。然而优弧/劣弧两种情况，加上高度存在相同，就比较难处理。然而环是可以平移的，所以一个好的方法是将其中的最大值移到一个端点，于是跨环端点的情况只出现在右半部分形成一个单调不降的序列。顺便去重就可以了。 B. 停不下来的团长奥...

图论 dp 线段树单调栈拓扑排序并查集

2019-11-06

0 327

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394

模拟104 题解

A. 中间值二分答案在数组$a$中的排名，则得到期望的在数组$b$中的排名。当数组$b$中对应的数恰好是大于二分值的第一个数，代表二分到了答案。通过对应的数与当前数的大小关系，可以确定二分方向。同理还应当二分答案在数组$b$中的排名。然而这个做法实现比较困难，还有另一个更帅的二分...

分治二分答案线段树 dp 单调栈

2019-11-07

0 405

模拟106 题解

A. 合并集合显然的区间dp。断环成链，预处理出每个连续区间集合的元素个数。然后直接dp就完了。 B. climb 想了一些简单的贪心，然后都伪了。所以考虑如何暴力$O(n^2)$来做这个题。枚举最终用来跳最后一步的药丸，显然前面的药丸可以按$a_i-b_i...

并查集博弈论区间dp dp 拓展域分治线段树

2019-11-09

0 490

模拟111 题解

A. 物理课发现每次反弹之后移动的距离是上一次的$d^2$倍。计算出第一次反弹之前移动的距离的答案$k$，总的答案即$\sum \limits_{i=0}^{inf}d^{2*i}*k$。发现这个东西就是一个等比数列求和。设答案为$s$，那么有$s=\sum \limits_{i...

线段树分治并查集启发式合并组合计数

2019-11-12

0 343

数据结构+插头dp+多项式题解乱写

可持久化数据结构 A.森林树上的数据结构常可以启发式合并，用启发式合并的思路合并树上主席树就可以了。 B.影魔一个常见的这种数据结构题的套路是：离线询问，按右端点排序。在右指针扫过去的同时在数据结构（常为线段树）中更新该右端点能产生的答案。同时在数据结构中查询统计右端点对应的区间就好...

单调栈线段树状压 dp 多项式

2019-12-29

0 450

省选模拟4 题解

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

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

2020-01-12

0 875

省选模拟7 题解

A. 翻转硬币第一眼以为只要保证给定的$k$个点反面就好了，是弱智水题，于是感觉秒切了。然后考完20分，就被秒切了。所以实际上是一道原题。思路大概是对原序列进行异或意义下的差分，于是区间修改转化为两个点的修改。于是问题变化为将初态共$2k$个$1$消为$0$。然后发现每个有意...

状压最短路线段树平衡树差分 dp manacher

2020-01-14

0 400

省选模拟8 题解

A. 序列发现较难维护的是后一个信息。所以考虑直接分块维护。为每个块开一个vector，表示这个块中所有元素对vector中的所有元素依次取过max。因为取max的性质，这个vector中的元素只需要保留单调递增的部分。在查询的时候和暴力重构一些块的时候，可以直接在vector中...

网络流二分图分块线段树

2020-01-17

0 553