LOJ6252 「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！
LOJ分析先考虑第一个条件。设 $c_i$ 为经过 $i$ 的 $s\to t$ 的最短路数，那么应该有 $c_a+c_b=c_t$。再考虑第二个条件。我们可以对每个点求出最短路图上不能到达它的且它不能到达的点集，然后存到一个 bitset 里。这可以直接拓扑排序求出。枚举 $a$，合法的 $b$ 应该满足 $c_t-c_a=c_b$。开一个 map 存下每个 $c$ 对应的点集，再和之前预...
标签 bitset 下的文章
- 首页
- bitset
AGC016E Poor Turkeys
AtCoder分析考虑求出如果钦定 $i$ 活到最后，那么有哪些火鸡需要送死。倒着考虑每个人。如果 $x_i,y_i$ 后面都需要送死，那么 $i$ 必死；否则随便找一个后面不要送死的送死即可。可以发现 $i,j$ 可能同时活到最后当且仅当不存在一只火鸡既需要为 $i$ 送死、又需要为 $j$ 送死，可以用 bitset 加速判断。代码// =========================...
UOJ513 【UR #19】清扫银河
UOJ分析结论：如果有解，那么步数必然 $\leq m+1$。证明：首先操作 $2$ 可以合并，所以只需要进行至多一次；其次，我们随便造一个生成森林，那么每条非树边就相当于一个简单环，从而操作 $1$ 的次数不会超过非树边数。所以总操作数至多为 $m-n+2\leq m+1$。于是我们只需要判是否有解即可。那么我们相当于要选若干个简单环异或 $1$，使得所有 $1$ 边变成 $0$，从而有解...
洛谷6775 [NOI2020]制作菜品
LuoguLOJ分析感觉同步赛上的我就是个 SB /kk下面没有证明。为了方便我们把所有 $d_i$ 从小到大排序。先考虑 $m=n-1$ 的情况。此时显然会有 $d_1< k,d_1+d_n\geq k$，于是我们可以把 $d_1$ 和 $d_n$ 放在一起做一道菜，这样子变成了 $n'=n-1,m'=m-1$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。再考虑 $m\geq...
洛谷5355 [Ynoi2017]由乃的玉米田
Luogu分析考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O}(\...
洛谷5891 Fracture Ray
Luogu分析对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f...
BZOJ4722 由乃
BZOJ分析$[l,r]$ 的非空子集数为 $2^{r-l+1}-1$，而子集贡献数至多为 $1000(r-l+1)$。当 $2^{r-l+1}-1>1000(r-l+1)$ 即 $r-l+1>13$ 时，根据抽屉原理显然有解，因此直接输出 Yuno 即可。先考虑操作 $1$ 怎么做。用树状数组维护每个点被修改的次数，然后倍增即可求出答案。再考虑操作 $2$。设 $dp_{i,j...
CF1105E Helping Hiasat
CodeforcesLuogu分析我们以 1 操作为界，划分出若干个块，那么每块只能有一个 id。预处理出每个好友在哪些块中访问过。可以发现，如果两个好友在同一个块中出现过，则她们不能都高兴。于是将在同一个块中出现过的好友连边，问题变为求最大独立集。大力 random_shuffle 即可。如果虚的话可以加个卡时。代码// ==================================...
BZOJ5097 [Lydsy1711月赛]实时导航
BZOJ分析暴力做法是每次修改后跑一遍 dijkstra，显然是过不去的。注意到 $1\leq w\leq 4$，因此我们可以开 $4$ 个队列，分别维护到当前点距离为 $1,2,3,4$ 的点。但是这样子还是过不去。然后有一个很 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 的做法。我们用 bitset 代替队列，即开 $4$ 个 bitset，第...
洛谷3645 [APIO2015]雅加达的摩天楼
LuoguLOJUOJ分析设 $dis_{i,j}$ 表示当前在 $i$ 号楼，从第 $j$ 个 doge 跳过来的最少跳跃次数。那么每次有两种操作：跳、把消息告诉另一只 doge 。这样子边权只有 $0$ 和 $1$ ，跑 0/1 BFS 即可。具体的方法是拿一个 deque 维护，$0$ 边丢到队首，$1$ 边丢到队尾。时间复杂度 $O(nm)$ ，并过不去。重新设 $dis_{i,j}...