Luogu分析没想到差分 /ll根据要求的东西,不难想到线性基。现在既然有一个区间询问,而且线性基还很好合并,那么可以想到在外面套一层线段树。问题是区间修改时一个线性基如何整体异或一个值。考虑差分,变成单点修改,直接把叶节点线性基清空然后 pushup 上去即可。可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的,所以...
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来,然后树状数组求逆序对数,再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的,所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
比赛地址Bugged如果所有数的和不是 $10$ 的倍数答案就是所有数的和,如果所有数都是 $10$ 的倍数答案是 $0$,否则答案为所有数的和减去最小的不是 $10$ 的倍数的数。代码Widespread二分答案 $mid$,那么相当于先把所有怪物的血量减去 $b\times mid$,再补 $mid$ 次伤害为 $a-b$ 的攻击。我们只要对减去 $b\times mid$ 血后仍然活着...
CodeforcesLuogu分析建 AC 自动机,那么暴力就是把匹配到的位置全部加 $1$,然后把每个在集合中的串的 fail 树上子树和加起来。我们转化一下,先把在集合中的串对应的位置加 $1$,然后累加匹配到的每个节点到根链上的和。这样子可以直接树链剖分维护。再转化一下,把每个点的点权设成到根链上的和,这样子修改时修改子树权值,询问时直接询问单点即可。可以用树状数组维护。代码// ==...
比赛地址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$,那么...
LuoguLOJ分析先考虑什么样的排列是满足条件的。冷静分析一下,达到下界当且仅当排列中没有长度 $\geq 3$ 的下降子序列,因为如果有的话一定有一个元素需要移过目标位置再移回来,从而不能达到下界。先考虑忽略字典序的限制怎么做。设 $dp_{i,j}$ 表示长度为 $i$、首项为 $j$ 的合法排列数,转移有三种情况第二个元素 $k$ 比 $j$ 大:那么如果 $k$ 不能与后面的元素构...
比赛地址只会做 A,自闭了Prefix and Suffix枚举重叠部分的长度即可。代码Median Pyramid Easy显然 $x=1$ 和 $x=2n-1$ 的情况无解。我们在中间放上 $x$,在它左边放 $x-1$,右边放 $x+1$ 和 $x-2$,可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。然而 $n=2$ 时只有三个数,需要特判掉。代码Rabbit Exercis...
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,...
LuoguLOJ分析先不考虑 $a$ 的限制,则答案为这样子可以发现,我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。于是只要把所有询问按 $a$ 排序,然后将 $\sigma(k)$ 从小到大加入即可。代码// =======================...
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)$。考虑无解的情况。一种情况是出现负环,另一种情况是出现一个全是...