CF1375H Set Merging
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
标签 构造 下的文章
- 首页
- 构造
CF734F Anton and School
Codeforces Luogu 分析 事实上有 $(a \operatorname{and} b) + (a \operatorname{or} b) = a + b$。那么 于是我们可以求出所有 $a_i$ 的和。这里注意判一下 $\sum b_i + c_i$ 是不是 $2n$ 的倍数。 接着我们就可以求出每个 $a_i$。这里也要注意判一下 $b_i + c_i - \sum a_...
洛谷5361 [SDOI2019]热闹的聚会与尴尬的聚会
Luogu LOJ 分析 题目中的条件相当于 $(p+1)(q+1)\geq n$。 第一问可以每次选一个度数最小的点删去，然后更新答案。用堆维护可以做到 $\mathcal{O}(n\log n)$。 第二问是求独立集，也可以每次选一个度数最小的点，然后把它和与它相连的点都删去。 可以证明这样子一定是满足条件的。设第 $i$ 次删掉的点的度数为 $d_i$，那么有 $\sum_{i=1}^...
洛谷6982 [NEERC2015]Jump
Luogu Gym 分析 我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。 规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。 假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。 考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus...
Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
AGC028E High Elements
AtCoder 分析 因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。 为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。 首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。 证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我...
CF527E Data Center Drama
Codeforces Luogu 分析 这个“所有边的出入度都是偶数”可以想到欧拉回路。可以发现只要造一张边数最小且为偶数的欧拉图出来，然后把欧拉回路上的边依次正向、反向定向即可。 这个很容易造，我们只要把相邻度数为奇数的点两两之间连一条边即可。练完之后边数可能是奇数，再连一个自环即可。显然这样子边数是最小的。 代码 // =================================...
洛谷6776 [NOI2020]超现实树
Luogu LOJ 分析 我们把每个节点都满足有一棵大小 $\leq 1$ 的子树的树称作「树枝」。 那么，$\mathrm{grow}(\mathscr{T})$ 是几乎完备的当且仅当所有高度为 $h$ 的树枝都在 $\mathrm{grow}(\mathscr{T})$ 中，这里的 $h$ 为 $\mathscr{T}$ 中树高的最大值。证明比较简单，因为任意一棵高度 $>h$ 的...
洛谷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$ 的情况。所以我们只要每次把最少的和最多的拿出来即可。 再考虑...
AtCoder Grand Contest 006 简要题解
比赛地址 只会做 A，自闭了 Prefix and Suffix 枚举重叠部分的长度即可。 代码 Median Pyramid Easy 显然 $x=1$ 和 $x=2n-1$ 的情况无解。 我们在中间放上 $x$，在它左边放 $x-1$，右边放 $x+1$ 和 $x-2$，可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。 然而 $n=2$ 时只有三个数，需要特判掉。 代码 Rabb...