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]制作菜品
Luogu LOJ 分析 感觉同步赛上的我就是个 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$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。 再考虑...
洛谷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$ 表示向上走多少条边能到达虚树上的父...
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...
洛谷5382 [THUPC2019]改善生活
Luogu LOJ 分析 首先有一个结论：存在一个最优解，满足小 Z 只引出了一个话题。 感性理解的话就是如果再引出一个话题的话相当于两个话题取了平均值，答案不会变得更优。 那么直接枚举引出了哪个话题，再直接计算就好了。 注意到题目中要传递闭包，$\mathcal{O}(n^3)$ 做法不够优秀，可以用 bitset 做到 $\mathcal{O}(\frac{n^3}{\omega})$ ...
洛谷5332 [JSOI2019]精准预测
Luogu LOJ 分析 每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。 设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。 另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。 问题变为在建好的图上，从 $(...
CF1097F Alex and a TV Show
CodeForces 分析 对每个集合维护一个 bitset，第 $i$ 位表示 $i$ 作为因数的出现次数的奇偶性。 $1$ 操作预处理后直接赋值即可； $2$ 操作直接异或即可； $3$ 操作直接与即可。下面考虑 $4$ 操作怎么做。 设 $f(i)$ 表示 $i$ 作为因子的出现次数， $g(i)$ 表示 $i$ 的出现次数，那么有 $f(x)=\sum\limits_{x|d}g(d...