分析 莫名其妙地想把这道题的题解写了。 设 \(f(i,j,k)\) 为 A 的前 \(i\) 个字符取出了 \(k\) 段，恰好匹配到 B 中 \(j\) 的位置的方案数。 如果 \(A_i \neq B_j\)，那么不会产生任何贡献。 如果 \(A_i = B_j\)，那么有两种情况 \(i\) 接着上一段那么 \(f(i-1,j-1,k) \rightarrow f(i,j

分析 设 \(f(i)\) 为 \(Concatenate(i) \bmod m\) 的值。 那么显然有 \(f(i) = \Big( f(i-1) \cdot 10^k + i \Big) \bmod m\)，其中 \(k = \lfloor \lg i \rfloor +1\)。 这个直接递推绝对是 T 飞的，\(n \in [1,10^{18}]\)。 但是这明显是个线性递推式

分析 很容易发现选择不相邻的两个办公楼是不划算的。 所以记 \(d_i\) 为第 \(i\) 与第 \(i+1\) 个办公楼之间的距离。 由于任一个办公楼都属于唯一的配对组，所以一旦选择了 \(d_i\)，\(d_{i-1}\) 与 \(d_{i+1}\) 也就不能再选择。 考虑特殊情况，当 \(k=1\) 的时候，答案是就 \(\min{\{ d_i \}}\)。 当 \(k=2\

分析 首先转化一下题意。 对于一个 \(n \times m\) 的格子图，每个格子都有一个初始权值 \(a_{i,j}\)，有两种操作： 将两个相邻格子的权值都 +1 将一个格子的权值 +2 求能将所有格子的权值变为相同且满足每个权值都在 \([L,R]\) 范围内的初始局面的个数。 这种题目可以从奇偶性下手。 对于操作 1，实质是同时改变两个相邻格子的奇偶性。 对于操

把区间按照端点递增排序（左右都一样，因为没有包含关系）。断环为链求出每个区间 \(i\) 往右经过一个区间能到达的最远区间。注意只有 \(l<r\) 的区间才需要复制。 对于满足 \(l \le M\) 的区间，倍增求解覆盖 \([l,l+M]\) 即可。 #include<bits/stdc++.h> using namespace std; #define int

有东西被加密了, 请输入密码查看.

分析 手算一下不难发现，一轮冒泡排序会让所有逆序对个数大于 1 的位置减少 1 个逆序对，逆序对为 0 的则不受影响。 设 \(f_i\) 表示位置 \(i\) 的逆序对数，那么经过 \(k\) 轮冒泡排序后，逆序对的个数为 \[ \sum_{ i=1 \text{ and } f_i > k}^n f_i - k \cdot \sum_{i \in [1,n]} [f_i &g

分析 把每个点的点权都搞成 \(a_i - b_i\)，问题转化为把所有节点权值都搞成 \(0\)。 有两种思路。 用并查集维护 \(1\) 操作，因为一个连通块内可以同加减。 用并查集维护 \(2\) 操作，因为一个连通块内可以多次使用，从而让任意节点加\(1\)，任意节点减 \(1\)。 虽然前者也具有传递性，但是对问题却没有帮助。 而后者隐藏着总和不变的信息——只有

分析 分类讨论一下。 对于颜色 \(w_i\) 若 \(w_i =0\)，随便选两个点都可以，\(\frac{n (n-1)}{2}\)。 若 \(w_i = 1\)，设这个点为 \(x\)，那么只要两个点之间的路径经过 \(x\)，就是合法的。为了不重不漏，要按照一定的顺序去计算。对于一条边 \((x \rightarrow y)\)，我们先令答案累加 \(sz_x \cdot

有东西被加密了, 请输入密码查看.