12.18 update：补充了 $ F $ 题的题解

A 题：

题目保证一定有解，就可以考虑用 $ 2 $ 和 $ 3 $ 来凑出这个数 $ n $

如果 $ n $ 是偶数，我们用 $ n / 2 $ 个 $ 2 $ 来凑出 $ n $ 即可

如果 $ n $ 是奇数，就用 $ n / 2 - 1 $ 个 $ 2 $ 和 $ 1 $ 个 $ 3 $ 凑出 $ n $ 即可

所以只需输出 $ n / 2 $

B 题：

如果一个字符串重排后一定是回文串，说明这个字符串只有 $ 1 $ 种字符

如果有两种不同字符，就可以把一个放在开头，一个放在结尾，这样形成的一定不是回文串

一个简单一点的写法是 $ sort $ 一下这个字符串，判断回文

C 题：

贪心的想，我们如果要使整个序列非降，那么前面的数字要尽量小，后面的数字要尽量大

首先 $ a[1] = 0，a[n] = b[1] $，然后贪心的扫过去，在满足条件的情况下使得前面的数字尽量小，后面的数字尽量大即可

D 题：

发现每条边的两个端点的数字的奇偶性一定不同

所以我们我们只要做一次 $ bfs $ 染色并判断是否能完成染色即可

假设黑点有 $ a $ 个，白点有 $ b $ 个

如果黑点是奇数，方案数是 $ 2^a $ 种，如果白点是奇数，方案数是 $ 2^b $ 种，总方案数是 $ 2^a + 2^b $ 种

然后发现整个图不一定联通

所以我们对每个联通块做一次 $ bfs $ 染色，然后把答案相乘即可

注意不能用 memset，不然 $ T $ 组数据每次 memset 一次肯定凉

E 题：

用 $ pa[i] $ 表示 $ i $ 这个数在第一个排列中出现的位置，$ pb[i] $ 表示 $ i $ 这个数在第二个排列中出现的位置

假设查询区间为 $ l1，r1，l2，r2 $

如果 $ i $ 这个点对答案造成了贡献，那么 $ l1 \le pa[i] \le r1 $ && $ l2 \le pb[i] \le r2 $

容易发现问题变成了二维数点问题，$ cdq $ 分治离线统计答案即可

F 题：

咕咕咕

补锅完毕

发现 $ len $ 的大小非常大，不能放进状态里，又发现 $ k \le 100 $，所以用 $ f[i][j] $ 表示第 $ i $ 个数是 $ j $ 且满足题目所述条件的方案数

发现不能很好的进行转移，所以再用 $ s[i] $ 表示 $ \sum_{j = 1}^{k} f[i][j] $，然后就是容斥转移一下

注意一下需要容斥的条件

可以根据代码理解一下

#include <bits/stdc++.h>

#define CIOS ios::sync_with_stdio(false);

#define rep(i, a, b) for(register int i = a; i <= b; i++)

#define per(i, a, b) for(register int i = a; i >= b; i--)

#define DEBUG(x) cerr << "DEBUG" << x << " >>> ";

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

template <typename T>

inline void read(T &f) {

	f = 0; T fu = 1; char c = getchar();

	while (c < '0' || c > '9') { if (c == '-') fu = -1; c = getchar(); }

	while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }

	f *= fu;

}

template <typename T>

void print(T x) {

	if (x < 0) putchar('-'), x = -x;

	if (x < 10) putchar(x + 48);

	else print(x / 10), putchar(x % 10 + 48);

}

template <typename T>

void print(T x, char t) {

	print(x); putchar(t);

}

const int N = 1e5 + 5, md = 998244353;

inline int add(int x, int y) {

	x += y;

	if(x >= md) x -= md;

	return x;

}

inline int sub(int x, int y) {

	x -= y;

	if(x < 0) x += md;

	return x;

}

int f[N][105], cnt[N][105], s[N], a[N];

int n, k, len;

int main() {

	read(n); read(k); read(len); if(len == 1) { cout << 0 << endl; return 0; }

	for(register int i = 1; i <= n; i++) read(a[i]);

	for(register int i = 1; i <= n; i++) {

		for(register int j = 1; j <= k; j++) cnt[i][j] = cnt[i - 1][j] + (a[i] == -1 || a[i] == j);

	}

	s[0] = 1; if(a[1] == -1) { for(register int i = 1; i <= k; i++) f[1][i] = 1; s[1] = k; } else f[1][a[1]] = 1, s[1] = 1;

	for(register int i = 2; i <= n; i++) {

		for(register int j = 1; j <= k; j++) {

			if(~a[i] && a[i] != j) continue;

			f[i][j] = s[i - 1];

			if(i >= len) {

				int l = i - len;

				if(cnt[i][j] - cnt[l][j] == len) {

					f[i][j] = sub(f[i][j], sub(s[l], f[l][j]));

				}

			}

			s[i] = add(s[i], f[i][j]);

		}

	}

	cout << s[n] << endl;

	return 0;

}

G 题：

习惯性的把曼哈顿距离的绝对值拆出来，用二进制表示

$ 31 $ 的二进制表示是 $ 11111 $，表示 $ 5 $ 维的一个点的坐标加入的正负情况都为正（即 $ x[1] - y[1] + x[2] - y[2] + x[3] - y[3] + x[4] - y[4] + x[5] - y[5] $

$ 29 $ 的二进制表示是 $ 11101 $，表示 $ x[1] - y[1] + x[2] - y[2] + x[3] - y[3] - x[4] + y[4] + x[5] - y[5] $ （注意 $ x[4] $ 和 $ y[4] $ 的符号变化

那么我们要求的就是 max{f[0] + f[31], f[1] + f[30], f[2] + f[29]...}

用线段树维护即可