一个 $n \times n$ 的棋盘上会有 $m$ 次变化, 每次变化都会在某个空的位置上出现一个兵 或者 移去存在棋盘上的某个兵. 一个兵处于坐标 $(x, y)$ 可以移动到 $(x, y + 1)$, $(x − 1, y + 1)$ 或 $(x + 1, y + 1)$, 前面是列, 后面是行. 有一个特殊列 $k$, 每次变化, 你都要计算把所有的兵移动到第 $k$ 列(不可以重叠), 需要在棋盘上第 $n$ 之后额外添加的最少行数.

$1 \le n, m \le 2 \cdot 10^5, 1 \le k \le n$

首先把棋子都用最近的移动方式移动到第 $k$ 列, 可让他们重叠在一格里. 这样就变成一维的问题了.

考虑这个一维的序列, 如图, 我们需要把多的兵往下移.

我们记录这个点的权值为当把所有兵依次往下放, 走的最远的那个兵的行号. 图中即 $w(2) = 5$.

设$f(x)$为$x$二进制下$1$的个数. 给出长度为$m$的$01$序列$a$, 给出$L$, 求有多少个$x \in [0, L]$, 满足$f(x + i) \mod 2 = a_i$

$1 \le m \le 100, 0 \le L \le 10^{18}$

设$g(i) = f(i) \mod 2$

我们把$g(i)$求出$[0, L+m]$个, 排成一排, 然后就类似于字符串匹配一样统计个数.

注意到$L$很大, 我们没办法把这个序列全部求出来. 所以这个序列一定有规律.

注意到, 当$i \in [2^{k-1}, 2^k)$时, 有$f(i + 2^k) = f(i) + 1$, 也就是相当于$i$的二进制下的第$k$位从$0$变成$1$, 所以有$g(i + 2^k) = g(i) \oplus 1$. 这样, 我们就发现了序列$g$的构造方式:

第一个是0, 然后把当前序列取反, 拼在后面. 如下:

0
01
0110
01101001
0110100110010110
...

还注意到 $m$ 很小, 只有$100$, 而$2^7 = 128$. 所以我们可以先构造出$g$的前$128$位, 更大的数一定会包含这个序列多次. 用$h(i)$表示$g$的前$2^i$位的序列, $h’(i)$表示$h(i)$每一位取反的序列.

给你一个$n \times m$的01矩阵, 初始全0, 支持四种操作:

1. 将 $(i,j)$ 变成1
2. 将 $(i,j)$ 变成0
3. 将第 $i$ 行的数字全部零一翻转
4. 回到第 $k$ 次操作后的状态

进行 $q$ 次操作, 每次操作后输出当前矩阵1的个数

$1 \le n, m \le 10^3, 1 \le q \le 10^5$

有回到 $k$ 次操作, 考虑可持久化数据结构.

对一个序列可持久化可以用主席树, 对一个矩阵就不好搞了.

把每一行用bitset存一下, 就变成序列了.

bitset.count() 返回1的个数, bitset.flip() 反转.

因为 bitset 要指定大小, 就会出现指定的大小大于$m$的情况, 翻转以后只能考虑后一段, 此时直接 count() 显然错误. 可以用一个后 $m$ 位全1的bitset去与一下反转以后的bitset.

复杂度$O((n + k) \log n)$

给出两个字符串$s_0, t$, 其中$|s_0| \le 100, |t| \le n$. 设$s_{i+1} = s_i + t_i + s_i$, + 表示字符串连接. $q$ 个询问, 形如 k sq, $k$是整数, $sq$ 是非空字符串, 表示询问 $s_k$ 中, $sq$ 的出现次数.

$k < n \le 10^5, q \le 10^6$

首先注意到, $sk$ 的长度是指数爆炸的, 所以不能完全构造出来.

但是 $sq$ 比较短, 我们可以构造出长度恰好大于等于 $sq$ 的$skk$. 注意到 $|skk| \le 2|sq| + 1$这样的话可以在 $O(2|sq|)$ 内求出 $sq$ 在 $skk$ 中出现了几次. KMP或者hash都能做.

$s_{kk+1} = skk + tkk + skk$, 会发现, $skk$已经算过了, 要计算的就是**包含$tkk$**的字符串中, $sq$ 出现的次数.

以前没学会, 现在感觉好简单啊. 可能是冯佬讲得太好了.

还没理解透彻, 边记着.

在张主席和冯佬的解答下, 应该理解透彻了吧…

$n$个点$m$条边的无向图, 带边权. 定义路径的某种长为 路径上边权的和 - 路径上最大边权 + 路径上最小边权. 求 1 到 其他点的这种路径最小长度.

$2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$

拆点, 分层. 把一个点拆成4个, d[u][0][0] 表示没有走最小值或最大值, dp[u][0][1] 表示没有走最小值而走了最大值, dp[u][1][0] 表示走了最小值没有走最大值, dp[u][1][1] 表示走了最小值和最大值. 每层内的边权就是原来的边权, 并且是双向边; 而跨层的边权需要修改一下, 并且是单向边.

$00 \to 01, 10 \to 11$, 边权为$0$, $00 \to 10, 01 \to 11$, 边权是原来的两倍.

然后跑最短路.

由于最短路的性质和题目的特殊性质, 跑出来一定是减去最大值, 加上最小值的, 否则不是最短路.

分层图的话不用显式建图, 否则不仅很麻烦, 而且很难知道当前点有没有跑最大或最小. 用一个三元组(u, 0/1, 0/1)表示, 既方便了许多, 也能和 d[u][0/1][0/1] 对应. 同时记得 vis 也要写成这种形式.