8.9总结

今天我们考的内容不是单纯的某一个算法，基本上都是把几个算法揉到一起考。实际上就是考我们对算法的熟悉度。但是我因为最后一题RE只得了96分，没有成功AK（这个比昨天还可惜）

我发现了，边写题目边写思路和细节处理AC率会变高

（还有就是总结写的快一点）

CF1374C Move Brackets (签到题)

链接：Move Brackets - 题目详情 - QY code

题意

给定一个长度为 n（n 为偶数）的括号串 s，其中包含 n/2 个 ( 和 n/2 个 )。

一次操作可以选中一个括号，将其移动到字符串的最前面或最后面。

求使 s 成为合法括号序列的最少操作次数。

合法括号序列定义：

• () 是合法的

• 若 s 合法，则 (s) 合法

• 若 s、t 合法，则 st 合法

思路

用 balance 记录当前未匹配的 ( 数量，遍历整个串：

• 遇到 (：balance++

• 遇到 )：

  - 若 balance > 0：正常匹配，balance--

  - 若 balance == 0：此 ) 前面没有可匹配的 (，属于"错位"括号，必须移动，ans++

关键观察：每个错位的 ) 都可以通过一次操作移到末尾，与后面多余的 ( 配对；错位 ) 的数量恰好等于末尾多余 ( 的数量，因此答案就是错位 ) 的个数。

复杂度

• 时间：$O(n)$ 每组测试

• 空间：$O(n)$

代码

#include <bits/stdc++.h>
using namespace std;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        string s;
        scanf ("%d", &n);
        cin >> s;
        int tmp = 0, ans = 0;
        for (int c : s) {
            if (c == '(') tmp ++;
            else {
                if (tmp == 0) ans ++;
                else tmp --;
            }
        }
        printf ("%d\n", ans);
    } 
    return 0;
}

CF1615B · And It's Non-Zero

链接：And It's Non-Zero - 题目详情 - QY code

题意

给定 $t$ 组询问，每组给出 $l, r$（$1 \le l \le r \le 2 \cdot 10^5$）。

将区间 $[l, r]$ 内所有整数组成一个数组，问最少删除多少个元素，才能使剩余元素的按位与（bitwise AND）非零。

思路

关键观察

按位与结果非零 $\Leftrightarrow$ 存在某个二进制位 $b$，使得所有留下来的数在该位上都是 1。

因此问题转化为：选一个目标位 $b$，把 $[l, r]$ 中第 $b$ 位为 $0$ 的数全部删掉，剩下的数按位与在该位上必为 1，结果非零。

要让删除数最少，就要让"留下的数"最多，即选一个位 $b$，使 $[l, r]$ 中第 $b$ 位为 $1$ 的数尽可能多。

答案

设 $total = r - l + 1$，$cnt_b$ 为 $[l, r]$ 中第 $b$ 位为 $1$ 的数的个数，则

$$\text{answer} = total - \max_{b} cnt_b$$

如何快速求 $cnt_b$

定义 $f(n, b)$ 为 $[0, n]$ 中第 $b$ 位为 $1$ 的数的个数。第 $b$ 位的 0/1 以周期 $2^{b+1}$ 循环，每个周期里前 $2^b$ 个为 0、后 $2^b$ 个为 1。于是

$$f(n, b) = \left\lfloor \frac{n+1}{2^{b+1}} \right\rfloor \cdot 2^b + \max\!\left(0,\; (n+1) \bmod 2^{b+1} - 2^b \right)$$

进而

$$cnt_b = f(r, b) - f(l-1, b)$$

复杂度

• 每个询问枚举约 18~20 个二进制位（$r \le 2\cdot 10^5 < 2^{18}$），每位 $O(1)$。

• 总复杂度 $O(t \cdot \log r)$，可轻松通过 $t \le 10^4$。

代码要点

• countBit(n, b)：计算 $[0, n]$ 中第 $b$ 位为 1 的个数（按周期公式）。

• count(l, r, b)：用前缀和思想做差得到 $[l, r]$ 上的统计。

• 主流程：对每个询问枚举所有位，取最大保留数，输出 $total - best$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll countbit (ll n, int b) {
    ll block = 1LL << (b + 1);
    ll full = (n + 1) / block;
    ll rem = (n + 1) % block;
    ll one = full * (1LL << b) + max (0LL, rem - (1 << b));
    return one;
}
ll count (ll l, ll r, int b) {
    return countbit (r, b) - countbit (l - 1, b);
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        ll l, r;
        scanf ("%lld%lld", &l, &r);
        ll tot = r - l + 1;
        ll best = 0;
        for (int b = 0; b < 20; b++) {
            ll c = count (l, r, b);
            best = max (best, c);
        }
        printf ("%lld\n", tot - best);
    }
    return 0;
}

这道题目推公式成功硬控了我将近半个小时

CF1878E · Iva & Pav

链接：Iva & Pav - 题目详情 - QY code

题意

给定长度为 $n$ 的数组 $a$，定义 $f(l,r) = a_l\ \&\ a_{l+1}\ \&\ \dots\ \&\ a_r$（按位与）。

有 $q$ 次查询，每次给出 $l, k$，求最大的 $r\ (l \le r \le n)$，使得 $f(l,r) \ge k$；若不存在则输出 $-1$。

数据范围：$t \le 10^4$，$n, q$ 之和均不超过 $2 \times 10^5$，$1 \le a_i, k \le 10^9$。

思路

关键性质

固定 $l$ 时，$f(l, r)$ 随 $r$ 增大而单调不增：因为 $f(l,r+1)=f(l,r)\ \&\ a_{r+1}$，按位与只会把某些二进制位从 1 变成 0，不会把 0 变成 1。

因此对每个询问 $(l,k)$，可以在 $[l,n]$ 上二分最大的 $r$ 使 $f(l,r)\ge k$。    

快速求 f(l, r)

$a_i \le 10^9 < 2^{30}$，只需考虑 30 个二进制位。对每一位 $b$ 维护前缀和：

$cnt[i][b] = \text{a[1..i] 中第 } b \text{ 位为 1 的元素个数}$

那么 $f(l,r)$ 的第 $b$ 位为 1，当且仅当 $[l,r]$ 内所有元素的第 $b$ 位都是 1，即：

$cnt[r][b] - cnt[l-1][b] = r - l + 1$

遍历 30 位即可在 $O(30)$ 时间内算出 $f(l,r)$。

复杂度

• 预处理：$O(30n)$

• 每次询问：$O(30 \log n)$

• 总复杂度：$O\big(30(n + q\log n)\big)$，可通过。

细节

• 若二分后 ans 仍为 $-1$，说明连 $f(l,l)=a_l < k$，输出 $-1$。

• 位运算结果用 long long 存储以防溢出（实际上 30 位不会溢出 int，但比较时用 long long 更稳妥）。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 30;
int main () {
	int T;
	scanf ("%d", &T);
	while (T--) {
		int n;
		scanf ("%d", &n);
		vector <vector <int> > cnt (n + 1, vector <int> (B, 0));
		for (int i = 1; i <= n; i++) {
			int x;
			scanf ("%d", &x);
			for (int b = 0; b < B; b++) cnt[i][b] = cnt[i - 1][b] + ((x >> b) & 1);
		}
		int q;
		scanf ("%d", &q);
		while (q--) {
			int l;
			ll k;
			scanf ("%d%lld", &l, &k);
			int L = l, R = n, ans = -1;
			while (L <= R) {
				int mid = (L + R) / 2;
				int len = mid - l + 1;
				ll val = 0;
				for (int b = 0; b < B; b++) {
					if (cnt[mid][b] - cnt[l - 1][b] == len) val |= (1LL << b); 
				}
				if (val >= k) ans = mid, L = mid + 1;
				else R = mid - 1; 
			}
			printf ("%d ", ans);
		}
		printf ("\n");
	}
	return 0;
}

CF466C. Number of Ways

题目链接：Number of Ways - 题目详情 - QY code

题意

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$，请计算有多少种方法可以将数组分成三个连续的非空部分，使得每一部分的元素之和相等。

解题思路

核心分析

1. 必要条件：数组总和必须能被 3 整除，否则无解，直接输出 0。同时 $n \ge 3$。

2. 设总和为 $total$，则每一部分的和应为 $target = total / 3$。

3. 我们需要找到两个分割点 $i$ 和 $j$（$0 \le i < j < n-1$，0-based），使得：

   - 前缀和到 $i$ 等于 $target$（第一部分）

   - 前缀和到 $j$ 等于 $2 \cdot target$（前两部分之和）

   - 剩余部分自然等于 $target$

算法：一次遍历 + 计数

从前到后遍历数组，维护前缀和 prefix：

• 用 cnt1 记录当前遇到了多少个位置前缀和等于 target（这些都是可以作为第一个分割点的候选）。

• 每当遇到一个位置前缀和等于 2 * target，说明这里可以作为第二个分割点。此时，之前遇到的所有第一个分割点都可以与它配对，所以将 cnt1 加到答案 ans 中。

关键顺序：先检查是否为 2*target（加答案），再检查是否为 target（更新 cnt1）。这样保证了第一个分割点严格在第二个分割点之前，不会出现 $i = j$ 的情况。

边界注意：第二个分割点 $j$ 必须在 $n-2$ 之前（即不能是最后一个元素），这样第三部分才非空。因此遍历只需要到 $n-2$ 为止。

复杂度分析

• 时间复杂度：$O(n)$，只需一次遍历。

• 空间复杂度：$O(n)$ 存储数组，或者可以优化到 $O(1)$（边读边算）。

关键实现细节

1. 使用 long long 存储前缀和，因为 $5 \cdot 10^5 \times 10^9 = 5 \cdot 10^{14}$，会超过 int 范围。

2. 遍历到 n-2 为止（即循环条件 i < n-1），确保第三部分非空。

3. 先判断 2*target 再判断 target，避免同一个位置同时作为两个分割点。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
	int n;
	scanf ("%d", &n);
	vector <ll> a (n + 1);
	ll tot = 0;
	for (int i = 1; i <= n; i++) {
		scanf ("%lld", &a[i]);
		tot += a[i];
	}
	if (tot % 3 != 0 || n < 3) {
		puts ("0");
		return 0;
	}
	ll get = tot / 3;
	ll pre = 0, cnt1 = 0;
	ll ans = 0;
	for (int i = 1; i <= n - 1; i++) {
		pre += a[i];
		if (pre == 2 * get) ans += cnt1;
		if (pre == get) cnt1 ++;
	}
	printf ("%lld", ans);
	return 0;
}

CF1720D1. Xor-Subsequence (easy version)

题目链接：Xor-Subsequence (easy version) - 题目详情 - QY code

---

题目大意

给定一个长度为 $n$ 的数组 $a_0, a_1, \ldots, a_{n-1}$（easy version 保证 $0 \le a_i \le 200$）。

你需要从数组中选出一个子序列 $b = [b_0, b_1, \ldots, b_{m-1}]$，满足：

• $0 \le b_0 < b_1 < \ldots < b_{m-1} < n$（即下标严格递增）

这个子序列称为美丽的（beautiful），当且仅当对任意相邻的一对 $(b_p, b_{p+1})$ 都满足：

$$\boxed{a_{b_p} \oplus b_{p+1} \;\;<\;\; a_{b_{p+1}} \oplus b_p}$$

其中 $\oplus$ 表示按位异或（XOR）。

怎么理解这个条件？

子序列中相邻的两个元素，前一个的下标是 $b_p$、后一个的下标是 $b_{p+1}$。

• 左边 $a_{b_p} \oplus b_{p+1}$：前一个元素的值 异或 后一个元素的下标

• 右边 $a_{b_{p+1}} \oplus b_p$：后一个元素的值 异或 前一个元素的下标

要求左边严格小于右边。

注意：这里异或的对象是「值」和「下标」的交叉组合，而不是单纯的值比大小。

求最长美丽子序列的长度。

---

解题思路

1. 为什么想到动态规划？

这道题求的是最长子序列，且子序列需要满足一个相邻元素之间的约束条件。

这和经典的「最长递增子序列（LIS）」非常类似：

• LIS 的约束是：相邻元素满足 $a_{b_p} < a_{b_{p+1}}$

• 本题的约束是：相邻元素满足 $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$

LIS 的标准 DP 做法是：$dp[i]$ = 以 $a_i$ 结尾的 LIS 长度。我们完全可以照搬这个思路。

---

2. 状态设计

设 $dp[i]$ 表示以索引 $i$ 结尾的最长美丽子序列的长度。

• "以索引 $i$ 结尾"意味着子序列的最后一个元素的下标是 $i$。

• 初始值：$dp[i] = 1$（每个元素自身构成长度为 1 的子序列）。

---

3. 朴素转移方程的推导

对于每个 $i$，我们尝试把 $i$ 接在某个以 $j$ 结尾的子序列后面（$j < i$），形成更长的美丽子序列。

能接上的条件是什么？

设原来以 $j$ 结尾的子序列是 $\ldots, j$。现在把 $i$ 接在后面，变成 $\ldots, j, i$。

新增的相邻对是 $(j, i)$，必须满足美丽条件：

$a_j \oplus i \;<\; a_i \oplus j$

满足条件时怎么转移？

如果 $j$ 能作为 $i$ 的前驱，那么以 $i$ 结尾的子序列长度可以是 $dp[j] + 1$。

遍历所有可能的 $j$，取最大值：

${dp[i] = \max\Big(1,\;\; \max_{\substack{0 \le j < i \\ a_j \oplus i < a_i \oplus j}} (dp[j] + 1)\Big)}$

• 外层的 $\max$ 中包含 $1$，表示最差情况下 $i$ 自己单独成一个子序列。

• 内层遍历所有 $j < i$ 且满足条件 $a_j \oplus i < a_i \oplus j$ 的，取 $dp[j] + 1$ 的最大值。

最终答案： $\max_{0 \le i < n} dp[i]$。

---

4. 朴素做法的复杂度

对每个 $i$（共 $n$ 个），需要遍历 $j \in [0, i-1]$，时间复杂度 $O(n^2)$。

对于 $n = 3 \times 10^5$，$n^2 = 9 \times 10^{10}$，远超时限，必须优化。

---

5. 关键观察：利用 $a_i \le 200$ 的性质

这是 easy version 的核心限制：$0 \le a_i \le 200 < 256 = 2^8$。

这意味着 $a_i$ 的二进制表示只有最低 8 位可能非零，第 8 位（即 $2^8$ 那一位）及以上全是 0。

我们回到转移条件：

$a_j \oplus i \;<\; a_i \oplus j$

核心断言：当 $i - j \ge 256$ 时，上述条件恒不成立（即左边恒大于右边）。

换句话说，只有 $j \in [i - 255, i - 1]$ 范围内的 $j$ 才有可能成为 $i$ 的合法前驱。

---

6. 断言的严格证明

设 $i > j$ 且 $i - j \ge 256 = 2^8$。

我们需要证明：$a_j \oplus i \;>\; a_i \oplus j$（即条件恒不成立）。

步骤 1：找到 $i$ 和 $j$ 的最高不同位。

设 $k$ 是 $i$ 和 $j$ 在二进制下从高位到低位第一个不同的位。

因为 $i > j$，所以在这个最高不同位上，$i$ 的第 $k$ 位是 $1$，$j$ 的第 $k$ 位是 $0$。

步骤 2：证明 $k \ge 8$。

反证法：假设 $k \le 7$，即 $i$ 和 $j$ 的最高不同位在第 $0 \sim 7$ 位之中。

这意味着第 8 位及以上，$i$ 和 $j$ 完全相同。那么 $i$ 和 $j$ 的差只来自低 8 位：

$i - j \le 2^8 - 1 = 255 < 256$

与 $i - j \ge 256$ 矛盾，因此 $k \ge 8$。

步骤 3：比较 $a_j \oplus i$ 和 $a_i \oplus j$ 在第 $k$ 位的值。

因为 $k \ge 8$，而 $a_j \le 200 < 2^8$，所以 $a_j$ 的第 $k$ 位是 $0$；同理 $a_i$ 的第 $k$ 位也是 $0$。

• $(a_j \oplus i)$ 的第 $k$ 位 $= a_j\text{的第}k\text{位} \oplus i\text{的第}k\text{位} = 0 \oplus 1 = \mathbf{1}$

• $(a_i \oplus j)$ 的第 $k$ 位 $= a_i\text{的第}k\text{位} \oplus j\text{第}k\text{位} = 0 \oplus 0 = \mathbf{0}$

步骤 4：得出结论。

在第 $k$ 位（即 $i$ 和 $j$ 的最高不同位）上：

• $a_j \oplus i$ 的第 $k$ 位是 $1$

• $a_i \oplus j$ 的第 $k$ 位是 $0$

而第 $k$ 位以上的所有高位，$a_j \oplus i$ 和 $a_i \oplus j$ 完全相同（因为高位上 $i$ 和 $j$ 相同，$a_i$ 和 $a_j$ 的高位都是 0）。

因此，比较大小取决于第 $k$ 位，$1 > 0$，所以：

$a_j \oplus i \;>\; a_i \oplus j$

条件 $a_j \oplus i < a_i \oplus j$ 不成立。**

---

7. 优化后的 DP

根据上面的结论，对每个 $i$，只需要检查 $j \in [\max(0, i - 255),\; i - 1]$ 的范围即可（最多 255 个前驱）。

写代码的时候不小心取了 $i - 256$ 作为下界（但其实多检查一个也没关系）。

for (int j = i - 1; j >= max (0, i - 256); j--) {
    if ((a[j] ^ i) < (a[i] ^ j)) dp[i] = max(dp[i], dp[j] + 1);
}

时间复杂度变为 $O(n \cdot 256)$，对于 $\sum n \le 3 \times 10^5$，运算量约 $7.68 \times 10^7$，可以通过。

---

复杂度分析

• 时间复杂度： $O(n \cdot 256)$，每个位置最多检查前面 256 个前驱。总复杂度 $O(256 \cdot \sum n) \le 7.68 \times 10^7$。

• 空间复杂度： $O(n)$，用于存储数组 $a$ 和 DP 数组 $dp$。

---

总结

| 要点 | 说明 |

|------|------|

| 题目本质 | 带 XOR 约束的最长子序列（类似 LIS） |

| 状态设计 | $dp[i]$ = 以索引 $i$ 结尾的最长美丽子序列长度 |

| 转移条件 | $a_j \oplus i < a_i \oplus j$ |

| 关键优化 | $a_i \le 200 < 2^8$，所以 $i - j \ge 256$ 时条件恒不成立 |

| 优化后复杂度 | $O(256n)$，可以过 |

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int a[N], dp[N];
void solve () {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i - 1; j >= max (0, i - 256); j--) {
            if ((a[j] ^ i) < (a[i] ^ j)) dp[i] = max (dp[i], dp[j] + 1);
        }
        ans = max (ans, dp[i]);
    }
    cout << ans << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--) solve ();
    return 0;
}

这道题的证明我推红温了

CF1950G. Shuffling Songs

题目链接：Shuffling Songs - 题目详情 - QY code

题意

Vladislav 有一个由 n 首歌组成的播放列表，第 i 首歌有流派 $g_i$ 和作家 $w_i$。他希望重新排列播放列表，使得每对相邻歌曲要么流派相同，要么作家相同（或两者都相同），这种播放列表称为"激动人心"的（exciting）。

不一定能用所有歌曲组成 exciting 播放列表，因此分两步操作：

1. 先删除若干首歌（可以为 0）；

2. 再把剩下的歌重新排列成 exciting 播放列表。

问最少需要删除多少首歌，才能让剩下的歌可以排成 exciting 播放列表。

数据范围

• $1 \le t \le 1000$，测试组数；

• $1 \le n \le 16$，每组的歌曲数；

• $1 \le |g_i|, |w_i| \le 10^4$，流派和作家字符串长度；

• 所有测试组 $2^n$ 之和不超过 $2^{16}$；

• 所有字符串长度之和不超过 $4 \times 10^5$。

思路

第一步：转化问题

题目要求"最少删除数"。删得越少越好 ⟺ 保留得越多越好。设最多能保留 $k$ 首，答案就是 $n - k$。所以问题转化为：

求最多能保留多少首歌，使它们能排成一条 exciting 序列。

第二步：建图模型 —— 哈密顿路径

把每首歌看作图中的一个顶点。两首歌 $i, j$ 之间连一条无向边，当且仅当它们"可以相邻"，即满足

$g_i = g_j \quad \text{或} \quad w_i = w_j.$

这样得到一张无向图 $G$。

哈密顿路径（Hamiltonian path）的定义：图中一条经过每个顶点恰好一次的简单路径。换句话说，它是图顶点的一个排列 $v_1, v_2, \dots, v_m$，使得任意相邻两项 $(v_k, v_{k+1})$ 之间在图中都有边相连。

在本题中，"把保留的 $m$ 首歌排成 exciting 序列"恰好等价于"在这 $m$ 个顶点的子图上找一条哈密顿路径"：排列中相邻两首要满足"同流派或同作家"，正是图中有边的定义。于是问题进一步转化为：

在图 $G$ 的所有"存在哈密顿路径"的顶点子集中，求最大的子集大小 $k$。

第三步：为什么用状压 DP

判断整张图是否存在哈密顿路径是经典 NP-hard 问题，但本题 $n \le 16$，且 $\sum 2^n \le 2^{16}$，可以用状压 DP 在 $O(2^n \cdot n^2)$ 内同时判断所有子集是否合法，并取最大。

第四步：DP 状态定义

设

$\text{dp}[\text{mask}][i] \in \{0, 1\},$

表示：能否用 mask 这个子集里的所有歌，排出一条以第 $i$ 首歌结尾的 exciting 序列（即子图上以 $i$ 为终点、经过 mask 中全部顶点的哈密顿路径）。

其中 mask 是 $n$ 位二进制数，第 $i$ 位为 1 表示第 $i$ 首歌在子集中。要求 mask 必须包含第 $i$ 位（即 (mask >> i) & 1 == 1），否则该状态无意义。

第五步：初始化

单独一首歌本身就是一条长度为 1 的合法序列：

$\text{dp}[1 \ll i][i] = 1, \quad \forall\, i \in [0, n).$

其余状态初始化为 0。

第六步：状态转移（核心）

按 mask 从小到大枚举（保证 mask & (1 << (j - 1))，转移到的状态更大，自然形成拓扑序）。对每个状态 (mask, i)，若 $\text{dp}[\text{mask}][i] = 1$，说明 mask 中的歌能排成以 $i$ 结尾的 exciting 序列。此时尝试把一首不在 mask 中的歌 $j$ 接到序列末尾：

• 条件 1：$j$ 尚未被使用，即 (mask >> j) & 1 == 0；

• 条件 2：$i$ 和 $j$ 可以相邻，即 $g_i = g_j$ 或 $w_i = w_j$（等价于图中 $i, j$ 之间有边）。

两个条件都满足时，把 $j$ 接到末尾，得到新序列（子集变为 mask | (1<<j)，结尾变为 $j$），因此：

$\text{dp}[\text{mask} \,|\, (1 \ll j)][j] = 1.$

直观理解：DP 实际上是在枚举所有"以 $i$ 结尾、覆盖 mask 的合法路径"，转移就是把路径再延长一格，把 $j$ 作为新的终点接上去。

第七步：统计答案

对任意一个可达状态 $\text{dp}[\text{mask}][i] = 1$，子集 mask 中的歌都能排成 exciting 序列，所以这个子集是合法的保留方案，其大小为 $\text{popcount}(\text{mask})$（mask 中 1 的个数）。在转移过程中记录所有可达状态中 popcount(mask) 的最大值 best：

$\text{best} = \max_{\text{dp}[\text{mask}][i] = 1} \text{popcount}(\text{mask}).$

最终答案为 $n - \text{best}$。

由于单首歌一定合法，best 初始化为 1（下界），保证非空。

复杂度

• 状态数：$O(2^n \cdot n)$（每个 mask 配每个可能的终点 $i$）。

• 转移：每个状态枚举 $j$，耗时 $O(n)$。

• 总复杂度：$O(2^n \cdot n^2)$。由 $\sum 2^n \le 2^{16}$，总运算量约 $2^{16} \times 16^2 \approx 1.7 \times 10^7$，可接受。

• 内存：dp 数组大小 $2^{16} \times 16$ 字节约 1 MB。

关键细节

• 单首歌一定是 exciting 的，所以 best 至少为 1。

• 字符串比较用 string 的 == 即可，无需离散化（数据范围允许）。

• 用 char 而非 bool 存储 dp 以兼容旧编译器（避免 vector<vector<bool>> 的位压缩带来的潜在问题，并解决 >> 嵌套模板参数的解析问题）。

• 边的判断是"或"关系，所以图中两点只要满足任一条件就有边，无需分别建两种边再合并。

代码

#include <bits/stdc++.h>
using namespace std;
int main () {
	int T;
	scanf ("%d", &T);
	while (T--) {
		int n;
		scanf ("%d", &n);
		vector <string> g (n + 10), w (n + 10);
		char c[100010], ch[100010];
		for (int i = 1; i <= n; i++) {
			scanf ("%s %s", c, ch);
			g[i - 1] = c, w[i - 1] = ch;
		}
		vector <vector <char> > dp (1 << (n + 1), vector <char> (n + 10, 0));
		for (int i = 1; i <= n; i++) dp[1 << (i - 1)][i - 1] = 1;
		int best = 1;
		for (int mask = 1; mask < (1 << n); mask++) {
			for (int i = 1; i <= n; i++) {
				if (!dp[mask][i - 1]) continue;
				int cnt = __builtin_popcount (mask);
				if (cnt > best) best = cnt;
				for (int j = 1; j <= n; j++) {
					if (mask & (1 << (j - 1))) continue;
					if (i != j && (g[i - 1] == g[j - 1] || w[i - 1] == w[j - 1])) dp[mask | (1 << (j - 1))][j - 1] = 1;
				}
			}
		}
		printf ("%d\n", n - best);
	}
	return 0;
}

就是因为这道题目，我的g, w还有dp数组一开始开的都是n + 1还有1<<(n+1)，我赛后调了半个小时才把这一个RE的点解决，就一个RE的点啊。