牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共8篇）

模拟26A 题解

A. marshland 考试时想到了网络流，然而不会建图，就死了。正解是最大费用可行流。比较容易想到的是将每个点拆为两个点， s连没有危险值的入点，没有危险值的入点连有危险值的入点，入点出点之间限流有费用，出点再连没有危险值的出点，这些出点连向t。不断跑spfa，通过有流量...

二分答案网络流后缀数组 bitset 树链剖分

2019-08-20

0 385

模拟42 题解

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

bitset 拓扑排序 set 贪心数位dp

2019-09-13

0 384

模拟48 题解

A. String Master $O(n^3)$随便做。 B. Tourist Attractions 因为数据范围$n^2$没有任何问题。考虑设$dp(i,j,k)$表示节点i从节点j来，并再走k步的方案数。显然$dp(i,j,1)=du(i)-1$，除了返回j，...

最短路 bitset dp

2019-09-22

0 384

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

模拟109 题解

A. Adore 似乎是显然的状压。 $dp_{i,S}$表示第$i$层，其中每个点到达终点路径条数的奇偶性为$S$的方案数。直接用位运算转移，复杂度是$O(m*k*2^k)$，然后卡卡常（把$k$循环展开）就过了。似乎考虑单次的变化量，可以继续消掉一个$k$，然后就好了。 ...

贪心 bitset 状压 dp

2019-11-11

0 437

省选模拟46 题解

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

容斥多项式 set bitset 提交答案

2020-03-16

0 851

省选模拟51 题解

A. 数学利用本题的特殊性质，可以得到如果 $n$ 为奇数，那么答案为 $(ab)^{\frac{n+1}{2}}$ ，对这个玩意平方一下即可发现是对的。对于 $n$ 为偶数，可以把 $2$ 全都提取出来，然后对剩余的部分取得一个解。然后不断缩小 $2$ 的次数以迭代，当缩小为 $2^0...

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟74 题解

A. 签到如果权值在边上，那么问题就简单了，弄一棵生成树，然后对每个环权值塞线性基里就完事了。但是如果权值在点上，这个结论就并不成立了。所以可以联想+手玩发现，如果走一条路径然后回来，造成的贡献是两个端点分别状态取反，中间路径不变。然后可以得到一种构造方法，首先从起点走到终点，然后从...

分块点分治 ST表 bitset 线段树虚树线性基

2020-04-18

0 401