标签: 前缀和

3 篇文章

【整理】算法竞赛数据结构学习笔记
区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…
CF1555D Say No to Palindromes 题解
题目链接。 解析 考虑最终序列。由于序列较长,先考虑序列短小的情况,即长度为 $3$ 时。 对于一个长度为 $3$ 的序列 $S_{1,2,3}$,要使其不存在回文串,需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$,你发现这三个字母必须是互不相同的,由于字符串仅由三种字母组成,最终序列的前三个字母一定是以下六种…
CF1552F Telepanting 题解
题意 题目链接。 数轴上有若干传送门,初始是关闭或开启。对于关闭的传送门,经过后就会开启;对于开启的传送门,到达后会被传送到一个位置,然后会关闭。求从 $0$ 点走到 $x_n+1$,即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门,则记 $f_…