洛谷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)$ ...
AtCoder Regular Contest 075 简要题解
比赛地址Bugged如果所有数的和不是 $10$ 的倍数答案就是所有数的和，如果所有数都是 $10$ 的倍数答案是 $0$，否则答案为所有数的和减去最小的不是 $10$ 的倍数的数。代码Widespread二分答案 $mid$，那么相当于先把所有怪物的血量减去 $b\times mid$，再补 $mid$ 次伤害为 $a-b$ 的攻击。我们只要对减去 $b\times mid$ 血后仍然活着...
CF163E e-Government
CodeforcesLuogu分析建 AC 自动机，那么暴力就是把匹配到的位置全部加 $1$，然后把每个在集合中的串的 fail 树上子树和加起来。我们转化一下，先把在集合中的串对应的位置加 $1$，然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。再转化一下，把每个点的点权设成到根链上的和，这样子修改时修改子树权值，询问时直接询问单点即可。可以用树状数组维护。代码// ==...
AtCoder Regular Contest 068 简要题解
比赛地址X: Yet Another Die Game显然是 $6$ 和 $5$ 轮着来，直接算一下即可。代码Card Eater我们可以用这个操作来每次消掉两张有重复的牌。最后可能会有只剩一张有重复，这时只能牺牲掉一张没有重复的。代码Snuke Line考虑某种商品 $i$。如果 $r_i-l_i+1> d$，那么这种商品一定能够被买到。如果 $r_i-l_i+1\leq d$，那么...
洛谷4769 [NOI2018]冒泡排序
LuoguLOJ分析先考虑什么样的排列是满足条件的。冷静分析一下，达到下界当且仅当排列中没有长度 $\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$ 时只有三个数，需要特判掉。代码Rabbit Exercis...
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
洛谷3312 [SDOI2014]数表
LuoguLOJ分析先不考虑 $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)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...