牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共10篇）

模拟35 题解

A. 公园长度放不进状态，那就把遍历的点的个数放进状态，使长度最小。然后就变成了DAG上最短路问题。设个源点汇点，直接拓扑排序就完了。 B. 计划设$mn(i)$表示左端点选i，最小的愉快的旅行。显然$mn(i)$是单调的，单调指针扫过去就完了。然后对询问...

dp 拓扑排序单调指针分块期望高斯消元

2019-09-03

0 308

模拟42 题解

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

bitset 拓扑排序 set 贪心数位dp

2019-09-13

0 384

模拟57 题解

A. 天空龙一个很好的性质是：最优方案可以不存在一个颜色A，转化为B再转化为C。因为将A直接转化为C一定更优。所以无需分类讨论，直接用一个sum判断正负就可以了。 B. 巨神兵有向图无环，所以存在拓扑序，所以用分层图dp。设f(i,j)表示已经考虑点集i，并且...

dp 容斥状压拓扑排序

2019-10-03

0 410

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365

模拟66 题解

A. 棋盘打表发现$ans_i=ans_{i-1}*i+[i$&$1]?-1:1$ 然后写高精度就完了。所以这个式子的原型其实是： $ans_i=ans_{i-1}*(i-1)+ans_{i-2}*(i-1)$，其含义可以直接画图理解。对于前一个ans的每一种方案，可...

组合计数 bitset 拓扑排序数位dp

2019-10-09

0 376

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

模拟78 题解

A. 串串香送分题。发现用$kmp$复杂度也是$O(n)$，和直接哈希的复杂度是一样的。所以直接双模哈希硬干就完了。 B. 糊涂图在不加边的情况下，因为存在拓扑序，问题是简单的。所以可以先处理出不加边情况下，每个点达哥获胜的概率，其实这个数组也表示走奇数步后无...

Hash KMP 拓扑排序 dp 倍增直径

2019-10-18

0 360

模拟102 题解

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

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

2019-11-06

0 327

模拟112 题解

A. 装饰分类讨论即可。标程的做法似乎更简单一些：答案为$min(\lfloor \frac{a+b+c}{3} \rfloor,a+b+c-max(a,b,c))$。证明并不难，显然答案不会超过这两个上界。对于两种情况分别取得较小的值，都可以构造出一种方案来达到答案的要求。 ...

拓扑排序 dp

2019-11-12

0 294

省选模拟10 题解

A. 食物链在拓扑序上dp。 B. 选点游戏要求支持合并两棵树，并同时维护树上最大独立集。考虑特殊情况，每次只加一个标号最大的点，问题是一个简单的动态dp。离线出最终树的形态，考虑加入的一个叶子节点，更新该节点到1号节点的轻链上信息就可以了。其实想到这里，一个动态dp的做...

拓扑排序树链剖分 dp 期望动态dp

2020-01-29

0 365