Prefixes

洛谷传送门 CF 传送门 考虑一个很类似的题。我们把正数和负数分开来考虑，最后用 \(0\) 连接一些连续段，形如 \(0 - \text{正} - 0 - \text{正} - 0 - \text{负}\)。 先考虑正数。设 \(f_{i, j}\) 为考虑了 \(\ge i\) 的正数，形成了 ......

题目链接：https://codeforces.com/problemset/problem/1919/E 题意 输入一个单调非减序列 \(p\)，求问有多少个序列 \(a\)，使得： \(|a_i| = 1\)； 令 \(s_i = \sum_{j = 1}^i a_j\)，则 \(s\) 排序后 ......

思路: 利用操作 使得题目更好分析, t 的后缀,反转t , 来看t 的前缀, 实际操作的时候, 把s 和 t 的前缀在反转一下进行交换就可以了, 发现性质 1 C(si, ti) 他们的相对位置不会变化, 一直是匹配的 然后利用 翻转的性质, 一定会产生任意我想要的排列 (从后开始构造, 先把目标 ......

UPD 23.10.3 更新的对思路的描述，以及代码。 思路 对于每一个 \(a_i = 0\)，如果我们将它变为 \(x\)，都可以直接将 \(i \sim n\) 位置上的前缀和加 \(x\)。 设 \(a_j\) 是 \(a_i\) 后第一个 \(0\)，那么，在 \(j\) 时同样有上述规律 ......

首先发现后缀和前缀比较不好看，所以翻转第二个字符串，记为 $T'$。 这样就变成了操作两个字符串的前缀。 观察发现，操作 $k$ 等价于交换 $S[1\sim k]$ 和 $T'[1\sim k]$，然后翻转 $S[1\sim k]$ 和 $T'[1\sim k]$。 结论 1：同一个下标上的字符对 ......

[题目传送门](https://www.luogu.com.cn/problem/CF1092C) 一道字符串题。 我们考虑还原字符串后再一个一个的判断。很显然，这个字符串是由一个长度为 $n-1$ 的前缀和后缀组成的。因此我们可以找到这 $2$ 个长度为 $n$ 的字符串，然后枚举哪个是前缀，哪个 ......