Day 22 学生讲义：阶段模拟 4（S T1-T3 综合卷）——括号贪心、位运算统计、前缀计数与状压 DP

学习方式：先理解题型的核心想法，再手算例子，最后不看答案独立实现。完成后复盘关键变量、复杂度和边界。

适用班级：已完成 Day16 状压 DP、Day18 位运算建模、Day19-21 图论与字符串综合，进入第二阶段全真模拟的学生。

学习重点：Day22 是第 4 次阶段模拟，卷型为 S T1-T3 综合卷（210-270 分钟）。本卷与旧版 Day22 完全不同：原 34C/1516B/1151B/1703G/1847C 均为 Day2/Day16/Day18 已练题，模拟已失效，全部移出；六题全部换为新题，难度阶梯 1000→1900。训练目标是"现场识别模型"，而不是回忆做过的题。压轴题 1950G 在本日正式引入新模型：哈密顿路径状压 DP。

配套题单（本卷 6 题全部为正卷题，无选做）：

赛位	题号	题目	rating	考察模型	模型来源
T1	1374C	Move Brackets	1000	括号失配计数	Day2
T2	1615B	And It's Non-Zero	1300	按位独立统计 + 值域前缀	Day1 / Day18
T3	1878E	Iva & Pav	1400	按位前缀 + 二分最远右端点	Day1 / Day5
T4	466C	Number of Ways	1700	前缀和三等分计数	Day1
T5	1720D1	Xor-Subsequence (easy)	1800	线性 DP + 位运算不等式剪枝	Day6 / Day18
T6	1950G	Shuffling Songs	1900	哈密顿路径状压 DP（新模型）	Day16 + 本日

0. 模拟的目标：识别模型并做出决策

模拟不是只统计做对几题。读完题后，应能写出“它像什么、能否先交保底、怎样升级”。

题	题面信号	第一模型	保底到正解
T1	括号可移到两端	失配计数	消去匹配对 -> 一遍扫描
T2	AND 非零、询问多	按位独立	扫区间 -> 值域前缀
T3	固定 l、求最远 r、AND	单调二分	向右扫 -> 前缀求 AND + 二分
T4	三段和相等、数方案	前缀计数	枚举两刀 -> 一遍结算
T5	最长子序列、值域小	结尾型 DP	O(n²) -> 256 转移窗口
T6	n<=16、任意重排、相邻限制	图 + 状压	全排列 -> `mask+last`

每题草稿先写四行：

输入规模与目标复杂度
状态或 check 的含义
能交的保底方案
保底怎样利用题目性质升级

20 分钟还没有正解方向时，先完成保底并换题；这是比赛策略，不是放弃。

1. T1 1374C Move Brackets：括号失配计数

1.1 题目大意

给一个长度为 n 的括号串（n 为偶数，左右括号各 n/2 个）。一次操作：取出任意一个括号，放到整串最前面或最后面。求把串变成合法括号序列的最少操作次数。多组数据，t <= 2000，n <= 50。

1.2 题型定位

签到实现题，CSP-S T1 / CSP-J T2 位置。模型就是 Day2 的括号栈计数：合法性只由"未匹配数量"决定，不需要真的模拟移动。

1.3 暴力与部分分

n <= 50，但"移动括号"的状态空间是排列级的，搜索不现实。可写的暴力是 O(n^2) 反复消去相邻匹配对 ()，剩下的串必然形如 )))...(((，答案就是剩余右括号个数。这个暴力其实已经等价正解，说明签到题的"暴力"常常就是结论本身。

1.4 正解升级

一遍扫描，维护未匹配左括号数：

遇 '('：未匹配左括号数 +1
遇 ')'：能配对就配对；配不上的记为"失配右括号"
答案 = 失配右括号个数

不要真的模拟“拿出一个括号再插回去”。合法串要求每个前缀都有 左括号数 >= 右括号数。扫描到一个 ) 时，若前面没有可配的 (，它已经使某个前缀非法，必须被搬到后面；已经配上的 ) 不该动。

例如 ))(())(( 的前两个 ) 都失配，答案至少是 2；把它们搬到串尾后，正好与最后两个未配的 ( 成对，所以答案就是 2。

正确性两个方向：

下界：左右括号总数相等，所以失配右括号数 = 失配左括号数 = moves。一次操作最多修复一对失配（把一个失配 ) 挪到串尾，恰好与一个失配 ( 配上），所以至少 moves 次。
上界：把每个失配 ) 依次挪到串尾，moves 次后串合法，构造达到下界。

以样例 )))((((()) 为例：扫描到前三个 ) 时没有左括号可配，失配数 3，答案 3。

1.5 从推导到落笔

写之前先在纸上写出两个量：open（尚未配对的左括号数）和 bad（已经失配的右括号数）。从左到右读每个字符时，只需判断它是让 open 增加、让 open 减少，还是让 bad 增加。

实现完成后用下面三类串自检，不要先看别人的程序：

串	应得到什么	检查什么
`()()`	0	已匹配的右括号不能误记
`)(`	1	第一个字符失配
`)))(((`	3	连续失配与后缀左括号配对

复杂度应为每组 O(n)，且只需要常数个计数器。

1.6 赛场策略与易错点

这题必须 15 分钟内拿满，超时说明 Day2 模型不熟，记入短板卡。
易错：把答案写成"失配左 + 失配右"（两者相等，只算一侧）；题面先给 n 再给串，n 要读掉。

模型卡：括号移到两端
扫描未匹配左括号；遇失配右括号就记一次
答案只数失配右括号

2. T2 1615B And It's Non-Zero：按位独立统计

2.1 题目大意

数组由区间 [l, r] 内全部整数组成。求最少删除多少个数，使剩余所有数的按位与（AND）非零。多组数据，t <= 1e4，1 <= l <= r <= 2e5。

2.2 题型定位

CSP-S T1-T2 位置的位运算 + 前缀和题。核心是 Day18 反复强调的第一句话：AND 非零 ⇔ 存在某一位在所有保留数中都是 1。每一位独立统计，这是位运算题的通用起手式（Day1 位运算入门 + Day18 建模）。

2.3 暴力与部分分

单组数据直接扫 [l, r]，对 18 个位各数一遍 1 的个数，O((r-l+1) * 18)。但 t = 1e4 组、每组区间可达 2e5，总量 3.6e10，超时。暴力能过小数据，是部分分。观察点：询问多、值域固定 → 把"每位 1 的个数"做成前缀数组，全部询问共用。

2.4 正解升级

枚举保留哪一位 bit：保留 [l, r] 中该位为 1 的全部数（多留不劣——留下的每个数都含该位，AND 的该位仍是 1），删除数 = 区间长度 − 该位 1 的个数。对 18 个位取最小值（2e5 < 2^18，位 0..17 够用）。

为什么不是枚举“保留哪些数”？最终 AND 非零，等价于至少有一位 bit 在所有保留数中都是 1。若最优方案靠这一位成功，那么区间里其他同样第 bit 位为 1 的数也能一起留下，不会破坏 AND，只会少删。因此每个最优方案都能还原成：固定一位，保留该位为 1 的全部数。

AND 非零 -> 至少选一位全为 1
固定一位 -> 能留的数完全确定
枚举所有位 -> 取删除数最小者

预处理 onesCnt[bit][x] 表示 1..x 中第 bit 位为 1 的数的个数，则每组询问 O(18)：

keep(bit) = onesCnt[bit][r] - onesCnt[bit][l-1]
答案 = min over bit ( (r-l+1) - keep(bit) )

用样例第 4 组 l=1, r=5 手推：

位 bit	[1,5] 中该位为 1 的数	个数	需删除
0	1, 3, 5	3	2
1	2, 3	2	3
2	4, 5	2	3

答案取最小值 2，与样例一致。

2.5 从推导到落笔

不要先想循环怎么写，先回答这三个问题：

前缀表的行是谁？是二进制位 bit；列是谁？是数值 x。
onesCnt[bit][x] 到底统计哪个闭区间？固定为 1..x，这样查询 [l,r] 才能统一减去 l-1。
为什么答案是“区间长度减最大可保留数”？固定一位后，所有该位为 1 的数都能留，其他数都必须删。

落笔顺序应是：先一次性预处理 18 行前缀表，再读每组 l,r，最后枚举 18 位更新最小删除数。实现后立刻检查 l=r、[1,5] 和含最高第 17 位的区间。

复杂度应为预处理 O(18\cdot2\times10^5)，每组 O(18)；若每组又遍历整个区间，说明还停留在部分分。

2.6 赛场策略与易错点

卡住时先写单组暴力交部分分，再想"多询问 → 预处理"。
易错：预处理写进 solve() 里（每组重算一遍直接超时）；位数写 17（2^17 = 131072 < 2e5，会漏最高位）；l = r 时答案 0（单个正数 AND 是它自己），公式自然覆盖，不需特判但要想到验证。

模型卡：AND 非零
枚举最终保留的那一位
按位前缀统计区间内 1 的数量
答案 = 区间长度 - 最大可保留数

3. T3 1878E Iva & Pav：区间 AND 单调性 + 二分最远右端点

3.1 题目大意

给长度 n 的数组（n <= 2e5，元素 <= 1e9），定义 f(l, r) 为区间按位与。q 次询问 (l, k)：求最大的 r，使 f(l, r) >= k；不存在输出 -1。每组数据的所有询问答案在同一行空格分隔输出。多组数据，Σn, Σq <= 2e5。

3.2 题型定位

CSP-S T2 位置：预处理 + 二分的标准组合。两块前置各自都学过——Day1 的按位前缀计数、Day5 的"答案单调就二分"。考的是把它们拼起来。

3.3 暴力与部分分

每次询问从 l 向右累积 AND，直到小于 k 停止，O(nq) 最坏 4e10，超时（5 秒时限是留给带 log 做法的，不是留给暴力的）。小数据部分分可拿。观察暴力过程能直接看到关键性质：AND 越与越小。

3.4 正解升级

两个零件：

单调性：固定 l，r 增大时 f(l, r) 每一位只会从 1 变 0，不会回头，所以 f(l, r) >= k 的 r 构成前缀区间 [l, rmax]，二分 rmax（Day5 的"最后一个 true"模板，上取整中点）。
区间 AND 快速求：某一位在 [l, r] 内全为 1 ⇔ 该位前缀 1 个数之差等于区间长度。维护 30 个位的前缀计数（1e9 < 2^30），单次求区间 AND O(30)。

Day5 的 ST 表同样能做区间 AND（AND 和 max/gcd 一样满足可重复贡献），二者选熟练的即可；本讲义以按位前缀计数作为主路线，便于从定义检查每一位。

按位前缀的来源：区间 AND 的某一位为 1，当且仅当区间内这一位的 1 数量等于区间长度。每一位独立判断后再拼回答案，就得到 rangeAnd(l,r)。

固定 l 向右扩区间时，AND 只会丢掉 1 位、不会长出新的 1 位。因此 rangeAnd(l,r)>=k 的 r 一定形如一段前缀：先真后假。只有先证明这个单调性，才可以二分最后一个 true。

无解判定：f(l, l) = nums[l] < k 时直接输出 -1，再进二分。

用样例第 1 组、询问 l=1, k=7（数组 15 14 17 42 34）手推：

r	新加入	当前 f(1, r)	>= 7？
1	15		是
2	14		是
3	17	0	否

最远 r = 2，与样例一致。

3.5 从推导到落笔

本题要拆成两个可独立验证的函数：

函数	输入	应回答什么	依据
`rangeAnd(l,r)`	一个区间	30 个位中哪些能留下	该位的 1 个数是否等于区间长度
`check(r)`	固定 `l` 后的右端点	是否仍有 `rangeAnd(l,r) >= k`	AND 随 `r` 右移不增

先手算 rangeAnd(l,l)：若它已小于 k，二分没有意义，答案必为 -1。否则再写“最后一个 true”的二分。写完不要只测有解情况；必须测“第一个位置就无解”“答案恰好是 n”和“AND 在中间突然降为 0”。

目标复杂度是 O((n+q\log n)\cdot30)。若二分中重复线性扫区间，复杂度仍是 O(nq)，并没有真正升级。

3.6 赛场策略与易错点

想不到按位前缀时，退一步用 Day5 的 ST 表维护区间 AND，同样能过。
易错：-1 特判漏掉；求"最后一个 true"用下取整中点导致死循环（mid = (lo + hi + 1) / 2）；位数按值域写 20 位（必须 30 位，k 也到 1e9）；输出格式是同行空格分隔，抄成每行一个在 OI 赛制下会判错格式。

模型卡：固定 l，求最大 r
AND 随 r 增大不增
按位前缀求区间 AND
二分最后一个满足 >=k 的位置

4. T4 466C Number of Ways：前缀和三等分计数

4.1 题目大意

给 n 个整数（可为负，n <= 5e5，|元素| <= 1e9），求把数组切成连续三段、三段和相等的切法数量。切法由两个刀口位置决定，两刀不能重合（每段至少一个元素）。

4.2 题型定位

CSP-S T2-T3 之间的计数题：思路 5 分钟（前缀和），细节 30 分钟（计数顺序、边界、溢出）。模型全部来自 Day1：前缀和 + 一遍扫描结算。

4.3 暴力与部分分

枚举两个刀口 O(n^2)，2.5e11 超时，小数据部分分。升级方向：第二刀合法位置的条件只跟前缀和有关，且与第一刀"独立"——只要求第一刀在它前面。这类"对数统计、只要求先后关系"的题，标准动作是一遍扫描 + 计数器（Day1 讲 313B 时用过同款）。

4.4 正解升级

记前缀和 prefix[]、总和 sum。sum % 3 != 0 或 n < 3 直接输出 0。否则记 third = sum / 3：

第一刀在 p1 合法  ⇔  prefix[p1] == third
第二刀在 p2 合法  ⇔  prefix[p2] == 2 * third 且 p2 <= n-1
方案 = 满足 p1 < p2 的合法对数

扫描 pos = 1 .. n-1，先结算再登记：

若 prefix[pos] == 2 * third：ways += firstCutCnt（它前面已出现的合法第一刀都能配对）；
若 prefix[pos] == third：firstCutCnt++。

顺序不能反：当 third == 0 时同一位置两个条件同时成立，先结算再登记恰好排除"两刀重合"。元素可负导致前缀和不单调，所以不能二分位置，只能计数扫描。

firstCutCnt 的含义是“严格在当前位置之前的合法第一刀数量”。当前 pos 是第二刀时，它可以与每一个已登记第一刀配成一个方案，于是加上这个计数。先结算后登记正好保证两把刀不能落在同一位置。

用样例 1（1 2 3 0 3，prefix = 1 3 6 6 9，third = 3）手推：

pos	prefix[pos]	先结算（==6？）	后登记（==3？）
1		否	否，firstCutCnt = 0
2	3	否	是，firstCutCnt = 1
3	6	是，ways = 1	否
4	6	是，ways = 2	否

答案 2：[1,2][3][0,3] 与 [1,2][3,0][3]。

4.5 从推导到落笔

这题的代码只有一趟扫描，但在写之前必须把循环不变量说完整：扫描到 pos 以前，firstCutCnt 存的是多少个严格小于 pos 且前缀和等于 third 的位置。

因此当前 pos 若能作第二刀，就把 firstCutCnt 加到答案；只有结算完，才允许把当前位置登记为第一刀。把这句中文写在草稿上，比先敲循环更能防止全零数组的同位双计数。

交前做三次手验：

n<3；
总和不能被 3 整除；
0 0 0 0（答案应为 3）。

前缀和、目标值和方案数都使用 64 位整数。目标复杂度 O(n)。

4.6 赛场策略与易错点

这题挂分几乎全在细节，写完必须用"全 0 数组"自造小样例验证（n=4 全 0 答案应为 3）。
易错：计数溢出——全 0 时方案数约 n^2 / 2 ≈ 1.25e11，int 必爆，ways 与前缀和（最坏 5e14）都要 long long；n < 3 要输出 0；第二刀最右只能到 n-1（第三段非空），循环上界写 n 会多算；负总和取模判断 %3 != 0 在 C++ 中对负数同样成立，不需要额外处理但要心里有数。

模型卡：三等分计数
前缀=1/3 是第一刀，前缀=2/3 是第二刀
扫描时先结算第二刀，再登记第一刀

5. T5 1720D1 Xor-Subsequence (easy)：值域剪枝 DP + 位运算不等式

5.1 题目大意

给长度 n 的数组 nums（0 下标，0 <= nums[i] <= 200）。求最长子序列，使其中相邻两个被选下标 j < i 都满足 nums[j] XOR i < nums[i] XOR j（注意：下标本身参与异或）。多组数据，Σn <= 3e5。

5.2 题型定位

CSP-S T3 位置。骨架是 Day6 的 LIS 型线性 DP；能不能过关键在读出 easy 版的提示：值域只有 200。位运算高位比较的论证方式来自 Day18。

5.3 暴力与部分分

标准 LIS 式 DP：dp[i] 表示以下标 i 结尾的最长合法子序列长度，枚举所有 j < i 检查条件转移，O(n^2) 在 n = 3e5 时约 9e10，超时；n <= 5000 的部分分稳拿。考场上必须先把这个暴力写出来，它离正解只差一个观察。

5.4 正解升级：为什么只需要看附近 256 个 j

比较两个数的大小，看的是最高的不同位（Day18 的基本功）。nums 的值 <= 200 < 256，异或只能改动低 8 位；而条件两边：

左边 = nums[j] XOR i   ——第 8 位及以上完全由 i 决定
右边 = nums[i] XOR j   ——第 8 位及以上完全由 j 决定

若 i 与 j 不在同一个 256 块（即 i / 256 != j / 256，由 j < i 得 i 的高位部分更大），则左边的高位 > 右边的高位，左边必然大于右边，条件必假。同块则 i - j <= 255。所以只有 j >= i - 255 的 j 可能转移成功，窗口大小 256：

dp[i] = 1 + max{ dp[j] : max(0, i-255) <= j < i 且 nums[j]^i < nums[i]^j }

复杂度 O(256 * Σn) ≈ 7.7e7，稳过。

令 i=256I+x、j=256J+y，其中 x,y<256。因为 nums[*]<256，异或只改低 8 位：左式 nums[j]^i 的高位仍是 I，右式 nums[i]^j 的高位仍是 J。若 i、j 跨 256 块，j<i 就有 I>J，左式必大于右式，转移必假。

所以窗口是 256，不是 200：200 只是数组值上界，2^8=256 才是高低位分开的边界。

用样例第 2 组 [5, 2, 4, 3, 1] 手推 dp：

i	nums[i]	可行转移 j（检查 nums[j]^i < nums[i]^j）	dp[i]
0	5	无	1
1	2	j=0：5^1=4 不小于 2^0=2，否	1
2	4	j=1：2^2=0 < 4^1=5，是	2
3		j=1：2^3=1 < 3^1=2，是（j=0、2 否）	2
4	1	j=2：4^4=0 < 1^2=3，是（其余否）	3

答案 3（下标 1→2→4），与样例一致。

5.5 从推导到落笔

先写最朴素的状态含义，而不是先背窗口：dp[i] 是“以 0 下标 i 结尾”的最长长度，初始值为 1。随后把候选前驱从全部 j<i 缩成

[ \max(0,i-255)\le j<i. ]

落笔时按下面顺序检查：

读入数组后，i 和 j 都从 0 开始；
每个 i 先设为单点链，再枚举窗口中的 j；
先验证异或不等式，再尝试用 dp[j]+1 更新；
最后在所有 dp[i] 中取最大值。

这里没有“神奇常数 200”：窗口右边界来自 $2^8=256$ 。若实现中写成 i-200，说明把数组值域和下标高位分界混在了一起。

5.6 赛场策略与易错点

拿分路径清晰：先交 O(n^2) 暴力（部分分），再补 j >= i - 255 一行升级成正解。
易错：这题必须 0 下标——下标参与异或，全篇 1 下标习惯在这里要显式切换并在代码里注释；窗口误写成 i - 200（论证的界是 256 块，不是值域 200，存在 i - j 在 201..255 之间的合法转移）；dp 初值是 1 不是 0；多测用局部 vector，自动清空。

模型卡：异或条件的最长子序列
dp[i] 是以 i 结尾的最优长度
值域 <256，只有同一 256 块内 j 可能转移
下标从 0 开始

6. T6 1950G Shuffling Songs：哈密顿路径状压 DP（新模型正式引入）

6.1 题目大意

播放列表有 n 首歌（n <= 16），第 i 首有曲风 g[i] 与作者 w[i]（均为字符串）。相邻两首歌必须同曲风或同作者。先删除若干首，再把剩下的任意重排，使整个列表满足相邻约束。求最少删除多少首。多组数据，Σ2^n <= 2^16，字符串总长 <= 4e5。

6.2 题型定位

CSP-S T3-T4 压轴。n <= 16 加上 Σ2^n 的约束方式，是裸的状压信号（Day16 第一课：看到 n <= 20 想子集）。把"能相邻"抽象成边后，题目变成图论问题——这一步图建模能力来自 Day8-12。

读到 n<=16，先比较：2^n 只有约 6.5 万，n2^n 仍可做，n! 完全不可做。题目允许任意重排，所以状态不能只记原数组位置；必须记“选了哪些歌”和“当前链尾”。

6.3 新模型：哈密顿路径与 dp[mask][last]

建图：每首歌一个点，两首歌同曲风或同作者就连无向边。一个合法播放顺序 = 图中一条每个点恰好经过一次的路径，这种路径叫哈密顿路径。本题即：选出最大的点子集，使其导出子图存在哈密顿路径；答案 = n - 最大可保留数。

为什么不能只看连通性：连通不代表能排成一条链。反例（6 首歌）：三首歌同作者 alice 构成三角形——(rock, alice)、(pop, alice)、(jazz, alice)，再各挂一个只同曲风的"叶子"——(rock, bob)、(pop, emma)、(jazz, frank)。图连通，但三个叶子度数都是 1，一条路径只有两个端点，最多覆盖两个叶子，必须删 1 首。所以需要 DP 逐点验证，不能 DSU 数连通块。

为什么不能全排列：16! ≈ 2e13 超时。排列枚举的浪费在于：链的延伸只关心"用过哪些点 + 当前末尾是谁"，中间顺序无关。把这两样压进状态：

reach[mask][last]：能否恰好用集合 mask 里的歌排成一条合法链，且链尾是 last
初始化：reach[1 << i][i] = 1（单首歌自成一条链）
转移：reach[mask][last] 为真时，对每个 nxt ∉ mask 且 compat[last][nxt]：
      reach[mask | (1 << nxt)][nxt] = 1
答案：n - max{ popcount(mask) : 存在 last 使 reach[mask][last] 为真 }

mask 从小到大枚举即可保证转移来源已算好。复杂度 O(2^n * n^2)（65536 * 256 ≈ 1.7e7），空间 O(2^n * n)。

为什么只记 mask 不行？以后能接哪首歌由当前链尾决定。若 1 能连 2、1 能连 3、但 2 不能连 3，{1,2} 的链尾为 2 时不能再接 3，链尾为 1 时才能接。ok[mask] 会把这两种情况混掉，故必须加 last。

为什么不必记录完整排列？未来只关心两件事：哪些歌已用（不能重复）和链尾是谁（能否连边）。这两项正是 mask,last；更早的顺序不会再影响下一步。

与 Day16 的衔接：Day16 的状压是"集合选没选"一维状态；今天升级为"集合 + 结尾点"二元状态。这是旅行商（TSP）、哈密顿路径一族的通用模板，Day30 结营重测还会用到。

实现细节：字符串最长 1e4，转移里直接比较字符串会拖慢常数，先用 map<string,int> 把曲风、作者离散化成编号，O(n^2) 预处理邻接矩阵 compat。

6.4 手动模拟表

小例：4 首歌——歌 1 (rock, alice)、歌 2 (rock, bob)、歌 3 (pop, alice)、歌 4 (jazz, dana)。

邻接关系：1-2 同曲风 rock；1-3 同作者 alice；2-3 无共同点；歌 4 和谁都不相邻。

按 mask 从小到大推 reach（只列可达与关键不可达行）：

mask（二进制，歌 4321）	集合	last	可达？	来源
0001	{1}	1	是	初始化
0010	{2}	2
0100	{3}	3
1000	{4}	4
0011	{1,2}	2		{1} 尾 1 + 边 1-2
0011	{1,2}	1		{2} 尾 2 + 边 2-1
0101	{1,3}	3		{1} 尾 1 + 边 1-3
0101	{1,3}	1		{3} 尾 3 + 边 3-1
0110	{2,3}	任意	否	2、3 无边
0111	{1,2,3}	3	是	{1,2} 尾 1 + 边 1-3（链 2-1-3）
		2	是	{1,3} 尾 1 + 边 1-2（链 3-1-2）
		1	否	需要 {2,3} 可达，而它不可达
含歌 4 的多元集合	—		否	歌 4 没有任何边

最大可达集合大小 3（链 2-1-3），答案 4 - 3 = 1（删歌 4）。让学生亲手填一遍 0111 那三行，体会"链尾是谁"决定还能接谁。

6.5 为什么搜索不能替代状态压缩

全排列会反复走到同一个“已选集合 + 当前链尾”。例如已选 {1,2,3}、链尾为 3 时，不管前面是 1-2-3 还是 2-1-3，之后能接的歌完全相同；搜索却会把两条历史都重新向下展开。

更危险的是，不能因为图很稠密就以为 DFS 很快能找到完整链。若 13 首歌两两兼容，另有 3 首歌分别只连接其中一首，图是连通的，却不可能一条路径覆盖全部 16 首：路径只有两个端点，三个挂叶不可能同时保留。此时无记忆 DFS 会在 13 首互相兼容的歌之间产生阶乘级分支，直到穷尽后才知道必须删歌；mask+last DP 只会把同一个子问题算一次。

全排列仅适合 n<=8 的保底或对拍。n=16 时，16! 约 $2\times10^{13}$ ，不能把“找到一条好路径就提前结束”当作复杂度保证。

6.6 从推导到落笔

实现前先把每一层的职责写成一句话：

层次	要维护什么	为什么需要它
字符串层	曲风、作者的整数编号	相邻判断变为两个整数是否相等
图层	`compat[i][j]`	明确哪些歌可以相接
DP 层	`reach[mask][last]`	避免重复枚举同一集合、同一链尾
答案层	最大可达 `popcount(mask)`	题目问删除数，所以用 `n-keepBest`

实际编码顺序也应与推导一致：先读入并离散化，再预处理兼容关系；随后初始化所有单点状态；最后枚举已可达的状态并向未使用且兼容的歌转移。每次转移前都问两句：nxt 是否未出现过？last 与 nxt 是否确实有边？

完成后自查四个小图：单点、全孤立、完整图、三个挂叶的连通图。最后一个专门检查“连通不等于能排成一条链”。

Σ2^n <= 2^16 保证所有组的 DP 总量可控；多组数据时，兼容图和状态表必须按组重新建立。

6.7 赛场策略与易错点

分配 60 分钟：前 15 分钟建图 + 写暴力保底，后 45 分钟上状压。
易错：转移里直接比较原字符串（先离散化）；mask 未按从小到大枚举导致漏转移；答案输出成保留数（要的是删除数）；n = 1 时答案 0（keepBest 初值 1 已覆盖）；状态表若复用全局数组，多测前必须清空，使用按组建立的容器可以自然避免残留状态。

模型卡：n<=16 的相邻排列
建图：能相邻的歌连边
reach[mask][last]：用 mask 排成链且末尾 last
答案：总数 - 最大可保留数

7. 赛后五维复盘

7.1 五个维度与本卷对照

维度	含义	本卷典型场景
读题误差	题意、输入输出格式理解错	T3 漏 `-1`、答案要同行输出；T5 没看到"下标参与异或"且为 0 下标
复杂度误判	选了必超时的做法硬写	T2 预处理放进多测；T3 每询问线性扫；T5 直接交 `O(n^2)` 当正解
边界漏判	特殊输入没覆盖	T4 `n < 3`、总和为 0；T2 `l == r`；T6 `n == 1`
实现 bug	思路对但代码错	T3 二分中点没上取整；T4 结算与登记顺序写反；T6 忘了离散化超时
调试耗时	单点调试超 20 分钟无止损	任何题：不造小样例、不拿暴力对拍、盯代码干瞪眼

7.2 复盘表（交卷后 30 分钟内独立完成）

姓名：            总分：      / 600

| 赛位 | 得分 | 主因维度 | 具体错误一句话 | 重写安排 |
| T1  |      |          |               |          |
| T2  |      |          |               |          |
| T3  |      |          |               |          |
| T4  |      |          |               |          |
| T5  |      |          |               |          |
| T6  |      |          |               |          |

要求：

"主因维度"只能填五维之一，逼自己归因到动作而不是"太难了"。
没做的题也要填：写清是"没时间"还是"没思路"，前者查时间分配，后者查 §9 的知识来源天。
复盘后每题补一张 4 行模型卡（题目/模型/关键变量/易错点），归档到个人错题本——Day30 结营重测按错题本选题。

7.3 重写流程

每道非满分题不要只看 AC 代码，按原因做不同补救：

原因	当天	24 小时后
读题错误	圈出限制并写反例	不看题面复述输入、输出和限制
复杂度错误	写暴力与正解的复杂度对照	从暴力改到正解
边界错误	补最小、全 0、极值样例	不看代码重写边界处理
实现错误	定位错误行与原因	用暴力随机对拍
时间分配错误	写下卡题时间与止损点	练 20 分钟模型识别

验收标准：空白纸上能写出题面信号、状态/check、复杂度和两个边界。

8. 与前期知识的对照表

赛位	题号	核心模型	知识来源	本日新增
T1	1374C	括号失配计数	Day2 栈与括号匹配	无
T2	1615B	按位独立统计 + 值域前缀个数	Day1 前缀和、Day18 位运算建模	无
T3	1878E	区间 AND 单调 + 二分最远右端点	Day1 按位前缀、Day5 二分与 ST 表	按位前缀求区间 AND 的写法
T4	466C	前缀和三等分、一遍扫描双计数器	Day1 前缀和与扫描结算	先结算后登记的去重技巧
T5	1720D1	LIS 型 DP + 高位比较剪枝	Day6 线性 DP、Day18 异或高位比较	值域小 → 转移窗口 256
T6	1950G	哈密顿路径状压 DP	Day16 状压与子集枚举、Day8-12 图建模	正式引入 dp[mask][last] 模板

Day23 会将本卷的前缀计数、二分和“先结算再加入”放进扫描线与区间覆盖；Day24 继续训练数据结构应维护什么；Day25 会把二分和 DP 组合成更完整的判定与优化框架。

收尾口诀：

括号失配各搬一，AND 非零找同位；
区间与只减不增，最远右端点二分给；
三等分先结算后登记，异或比大小看高位；
n 到十六想状压，集合加链尾走一回。

Day 22 讲义：括号贪心、位运算统计、前缀计数与状压 DP