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)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...
洛谷5047 [Ynoi2019模拟赛]Yuno loves sqrt technology II
Luogu分析考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\log n)$ 的，由于这是 Ynoi 所以过不了。由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的个数，另一个是区间中比...
洛谷5070 [Ynoi2015]即便看不到未来
Luogu分析把询问离线，从左往右加入每个数并维护以这个数为右端点时每个左端点的答案。假设当前加入了 $x$，那么它显然不会更新 $a_x$ 上一次出现位置之前的左端点的答案（因为这些区间排序去重后根本没有变化），而且只会和 $[x-11,x+11]$ 的数产生贡献（因为只需要统计 $\leq 10$ 的长度）。而插入 $x$ 后极长值域连续段可能会有以下变化从 $[a,x-1]$ 变成了 ...