JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
标签 树状数组 下的文章
- 首页
- 树状数组
洛谷5607 [Ynoi2013]无力回天NOI2017
Luogu 分析 没想到差分 /ll 根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。 问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。 可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
CF163E e-Government
Codeforces Luogu 分析 建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。 我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。 再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。 代...
洛谷4769 [NOI2018]冒泡排序
Luogu LOJ 分析 先考虑什么样的排列是满足条件的。冷静分析一下，达到下界当且仅当排列中没有长度 $\geq 3$ 的下降子序列，因为如果有的话一定有一个元素需要移过目标位置再移回来，从而不能达到下界。 先考虑忽略字典序的限制怎么做。设 $dp_{i,j}$ 表示长度为 $i$、首项为 $j$ 的合法排列数，转移有三种情况 第二个元素 $k$ 比 $j$ 大：那么如果 $k$ 不能与...
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...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3312 [SDOI2014]数表
Luogu LOJ 分析 先不考虑 $a$ 的限制，则答案为 这样子可以发现，我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。 于是只要把所有询问按 $a$ 排序，然后将 $\sigma(k)$ 从小到大加入即可。 代码 // ===============...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
洛谷5047 [Ynoi2019模拟赛]Yuno loves sqrt technology II
Luogu 分析 考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的，由于这是 Ynoi 所以过不了。 由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的...