题解：P12472 [集训队互测 2024] 基础 ABC 练习题
yzc001
·
·
题解
0.前言
在博客园食用更佳
省流：275307894a/对/蒟蒻们/使用了/模拟赛
蒟蒻们/rp++
1.思路
22.5pts(子任务1，3，4，n=15) :
其实就是双倍经验。
思路见这篇题解。也可在博客园食用。
40pts(子任务1，2):
由于串固定，所以可以先枚举 ABC，BCA，CAB 的数量。
容易想到枚举每个 A，B，C 的位置
显然，第一个字符要作为一个字符串的第一个字符，最后一个字符要作为一个字符串的最后一个字符
故考虑贪心
令 ABC 的数量=A，BCA 的数量=B，CAB 的数量=C，则方案如下 |
串 |
ABC |
BCA |
CAB |
| 第一个字符所在位置 |
(1，A) |
(1，B) |
(1，C) |
| 第二个字符所在位置 |
(B+1，B+A) |
(C+1，C+B) |
(A+1，A+C) |
| 第三个字符所在位置 |
(C+B+1，C+B+A) |
(A+C+1，A+C+B) |
(B+A+1，B+A+C) |
这里的位置指的是相对位置。
形式化地，如设所有 A 中的第 i 个 A 为 a_i，则 (1，A) 指 ABC 的 A 应出现在 (a_1，a_A) 范围内。
也即，当每个串最前面的字符出现在每种字符的最前面，最后的字符出现在每种字符的最后面时，若不存在方案，则说明 A，B，C 不是一个可行的方案。
省流：前面在前面，后面在后面，如果没方案，肯定没方案
证明较显然，可在博客园食用 。
于是，你就得到了一种在 O(n^3) 时间内求出一个方案是否成立的方法。
可以由题目推出，n \le 60。
67pts:
考虑给定 A， B 如何计数，则上面的最优分配方案可以转化为对于 p_a，i 和 p_b，B+i 等的顺序限制。
然后设 f_{a，b，c} 表示当前填了前 a 个 A，b 个 B，c 个 C 的方案数。这个dp是 O(n^3) 的。
然后对于一般的情况，只需要枚举哪些子集对是合法的，容斥即可计算答案。
注意到如果两个子集 max 加起来大于 n 肯定是无解的，因此只有
## 100pts
尝试优化枚举集合的过程。
考虑 $|S1| = |S2| = n + 1$ 的情况。
- 假设现在 ABC 个数的子集已经确定，则前 $i$ 个 $A$ 已经确定了。在考虑要将哪些 $B$ 分配进去的时候，会对于 $B$ 有一个限制，可以表示为 $B$ 要大于某个值。
- 对于剩下的分配，限制也总能表示成 $B$ 要大于某个值
或者 $B$ 要小于某个值。换而言之，$B$ 的取值是一个区间。
在得到这个结论以后，只需要判定 $B$ 取值区间非空即可。
对于这样的判定，可以使用点减边容斥：枚举每个 $i ∈ [0， n]$，计算 $B = i$ 合法的方案数，然后对于每个 $i ∈ [1， n]$，减去 $B = i - 1， B = i$ 同时合法的方案数，即可得到 $B$ 取值区间非空的方案数。
对于不满足特殊性质的情况，只需要将所有 $S1$， $S2$ 中的元素拿出来做这个容斥即可。
同理，对于 $A$ 的枚举也可以应用这样的优化，因此总共只需要枚举 $O(n^2)$ 个集合对，时间复杂度 $O(n^5)$。
> 这样，你就吊打了绝大多数的集训队选手。
> ——275307894a
# 2.代码
[click](https://www.cnblogs.com/zan-mei-tai-yang/p/18978893)。
# 3.后记
1. 膜拜巨佬 [**275307894a**](https://www.luogu.com.cn/user/181766)
2. [双倍经验](https://www.luogu.com.cn/problem/AT_agc055_d)，而且呈包含关系
3. ~~给好不容易搞懂此题的本蒟蒻一个赞吧~~
Update on 7.12：修改少量笔误
Update on 7.14：【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格；句子末尾应添加句号，且全文使用的句号应一致；【中文】与【英文、数字或公式】之间应以半角空格隔开。。$\color{#FFFFFF}{\text{~~然而另一篇题解通过了，拜谢审核~~}}