牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟102 题解

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

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

2019-11-06

0 327

模拟101 题解

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

dp 模拟最短路

2019-11-05

0 328

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

模拟99 题解

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

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

2019-11-04

0 359

模拟98 题解

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

状压模拟构造题最短路 dp

2019-11-04

0 356

模拟97 题解

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

扫描线 set 线段树

2019-11-04

0 729

模拟96 题解

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

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

2019-11-04

0 408

模拟95 题解

A. 简单计算发现向下整除会损失一些贡献，然后就无法直接用等差数列考虑。如果不计损失，那么答案是一个等差数列求和。可以考虑损失的是什么，即$\sum \limits_{i=1}^{p}i*q\ mod\ p$。这个式子就很好，不妨设$gcd(p,q)=1$，因为$gcd$不为1的情况...

贪心桶

2019-10-31

0 338

模拟94 题解

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

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

2019-10-30

0 343

模拟93 题解

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

dp 树状数组分治高斯消元

2019-10-30

0 400