洛谷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...
标签 bitset 下的文章
- 首页
- bitset
洛谷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}...
洛谷5382 [THUPC2019]改善生活
LuoguLOJ分析很像最近某个考试题...首先有一个结论：存在一个最优解，满足小 Z 只引出了一个话题。感性理解的话就是如果再引出一个话题的话相当于两个话题取了平均值，答案不会变得更优。那么直接枚举引出了哪个话题，再直接计算就好了。注意到题目中要传递闭包，$O(n^3)$ 做法不够优秀，可以用 $\mathrm{bitset}$ 做到 $O(\frac{n^3}{\omega})$ 。代码...
NOIP2018简要题解
PJ标题统计按照题意模拟即可。龙虎斗枚举即可。记得开 $\texttt{long long}$ 。摆渡车设 $f[i]$ 表示前 $i$ 时刻的答案，容易得到 $\displaystyle f[i]=\min_{j\leq i-m}\{f[j]+\sum_{j<k\leq i}i-t_k\}$ 。直接前缀和优化即可得到 $50$ 分。考虑优化。可以发现 $j$ 只需要从 $i-2m+1...
洛谷5332 [JSOI2019]精准预测
LuoguLOJ分析每个人在每个时刻只有 $2$ 种状况，考虑 2-SAT 。设 $(x,t,0/1)$ 表示 $x$ 在 $t$ 时刻活着/死了。那么直接连边就好了。另外还有一个隐藏条件：如果 $x$ 在 $t$ 时刻活着，那么在 $t-1$ 时刻也活着；如果 $x$ 在 $t$ 时刻死了，那么 $x$ 在 $t+1$ 时刻也死了。这个同样要连边。问题变为在建好的图上，从 $(i,T+1,...