牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟91 题解

A. Dove 打扑克显然的结论是：超过$\sqrt n$的牌堆不会超过$\sqrt n$个。所以可以分块维护信息：对于牌数小于$\sqrt n$的，用一个桶维护。对于牌数大于$\sqrt n$的，用$vector$暴力插入删除维护。同时维护答案，为了做到$O(1)$修改，也用分...

分块 dp 线段树猫树位运算

2019-10-28

0 386

模拟92 题解

A. 数列要求$ax+by=s$，使得$abs(x)+abs(y)$最小的一组解$(x，y)$。首先用$exgcd$求出一组特解$(x_1,y_1)$。因为$a,b$均为正数，可以将$s$转化为正数。不妨将解$x,y$画到一个坐标系上，显然$abs(x)+abs(y)$在$x$接...

exgcd dp 线段树最短路

2019-10-29

0 315

模拟93 题解

A. 序列一眼二分，然后发现二分有点不对？一测大样例果然不对，因为有两个限制，问题并不具有单调性。作前缀和后问题其实是个三维偏序问题，似乎还得一个$log$复杂度。先打个$cdq$分治套树状数组，结果极限数据$0.3s$，所以就$AC$了。正解确实是一个$log$。最后一维偏...

dp 树状数组分治高斯消元

2019-10-30

0 400

模拟94 题解

A. 凉宫春日的忧郁数据范围就长得很可写高精度的样子。可以维护高精度的高位，舍弃低位信息。正解是取对数。 $x^y=y*log\ x$ $y!=\sum \limits_{i=1}^{y}log\ i$ 然后可以直接比较两个取对之后的$double$类型。 B....

启发式合并分治虚树 dp 差分

2019-10-30

0 343

模拟96 题解

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

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

2019-11-04

0 408

模拟98 题解

A. 线性代数 (algebra) B. 装饰 (decoration) 暴力记录每个点的当前状态和上传状态，可以做到$O(4^n)$ 注意到答案并不大，不妨设最终答案为$k$，考虑在时间点$i$，选择点$j$对最终态的贡献，即对每一层祖先的状态取反。所以可以直...

状压模拟构造题最短路 dp

2019-11-04

0 356

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

模拟101 题解

A. 五子棋简单模拟。注意获胜条件有四种情况不是三种 B. 迷宫对于每个点封掉$d$条路。考虑反向$dijkstra$跑最短路。对于每个元素$i$，当第$d+1$次取出时视作$dis(i,n)$，更新相邻的点。 C. 三华聚顶考场上的思...

dp 模拟最短路

2019-11-05

0 328

模拟102 题解

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

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

2019-11-06

0 327

模拟104 题解

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

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

2019-11-07

0 405