ACGO 第 10 次排位赛题解
本场排位赛的所有题目的难度评级为：
A B C D E F ASCII 码 挑食的小码君 奇怪的机器 独特三元组 道路削减 分面包 入门 入门 普及- 普及/提高- 普及/提高- 普及+/提高
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的 AC 代码与复杂度分析，请点击题目标题查看。
A - ASCII 码
对于任意给定的 ASCII\tt{ASCII}ASCII 值，我们可以使用强制类型转换，获取其字符形式。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 挑食的小码君
可以将问题转化为：“在 B1,B2,…,BKB_1, B_2, \ldots, B_KB1 ,B2 ,…,BK 中，有没有一种食物的美味度是 NNN 个食物中最高的（允许并列）？”
对于这个问题我们可以通过以下流程解决：
1. 找出 NNN 种食物中的最高美味度（假设该值为 MMM）。
2. 对于 j=1,2,…,Kj=1,2,\ldots , Kj=1,2,…,K ，判断是否存在 ABj=MA_{B_j}=MABj =M 。
3. 如果有一个或多个这样的 jjj ，则答案为 Yes；否则，答案为 No。
可以用 for 语句和 if 语句来编写。
注意数组下标的范围。此外，注意不要多次输出 Yes，或在 Yes 后输出 No。
这一点，对于 C++ 程序可以在找到满足条件的 ABj=MA_{B_j} = MABj =M 之后使用 return 0 直接退出程序；对于 Python 程序可以使用 exit(0) 直接退出程序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 奇怪的机器
每个转轴一共只有 0, 1, …\ldots…, 9 共 101010 个字符；
我们可以尝试枚举最终停下来显示的字符，最终从 101010 个答案中取最小的即可。
对于转轴 iii 若想其显示字符 SjS_jSj ，那么根据题目意思，在每 101010 秒一个周期中只能选择第 jjj 秒按下按钮。即时间 ttt 需要满足 t=10×d+jt = 10 \times d + jt=10×d+j。
又每秒只能按一次按钮，我们可以使用一个数组 st 来标记 ttt 秒是否按过按钮, 然后可以枚举 ddd，找到没有按按钮的最小的 t=10×d+jt = 10 \times d + jt=10×d+j，将 st[t]st[t]st[t] 标记为 111。
对于每个字符 xxx，我们统计让所有的转轴停到 xxx，按下按钮最晚的时间 xtx_{t}xt 即可。最终的答案取所有 xtx_txt 中最小的，即 minxt\min{x_t}minxt 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 独特三元组
可以将问题转化为：“求满足 Ai<Aj<AkA_i \lt A_j \lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i, j, k)(i,j,k) 的数量”。
> 对于满足题目原条件的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [Ai,Aj,Ak][A_i, A_j, A_k][Ai ,Aj ,Ak ] 的排列 PPP，使得 AP1<AP2<AP3A_{P_1} \lt A_{P_2} \lt A_{P_3}AP1 <AP2 <AP3 。
> 反之，对于有 Ai<Aj<AkA_i\lt A_j\lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [i,j,k][i,j,k][i,j,k] 的排列 PPP，使得 P1<P2<P3P_1 \lt P_2\lt P_3P1 <P2 <P3 。
考虑枚举 jjj，那么 iii 和 kkk 可以独立选择。
满足条件的 iii 的数量是 AAA 中数值小于 AjA_jAj 的元素个数；
满足条件的 kkk 的数量是 AAA 中数值大于 AjA_jAj 的元素个数。
因此，只要准备一个数组 cnt，令 cnt[x] 为 AAA 中小于等于 xxx 的数量，便可以很容易地计算出满足条件的 iii 和 kkk 的数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 道路削减
令 DiD_iDi 为从城市 111 到城市 iii 的最短距离。无论选择哪些道路，显然有 di≥Did_i\geq D_idi ≥Di 。
所以如果有选择道路的方案使得 di=Did_i=D_idi =Di 成立，那么这就是最优解。事实上，这样的选择方法总是存在的。
对于每个 i=2,3,…,Ni=2,3,\ldots,Ni=2,3,…,N，只需保留 “从城市 111 到城市 iii 的最短路径中的最后一条道路” 即可。
答案可以通过记录 Dijkstra\tt{Dijkstra}Dijkstra 算法中到达每个城市前的最后一条道路来找到。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 分面包
1. 首先考虑 L=A1+A2+…+ANL=A_1+A_2+\ldots +A_NL=A1 +A2 +…+AN 的情况：
反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,ANA_1, \ldots, A_NA1 ,…,AN 合并为一个面包的最小费用。”
这个问题和原问题等价。
在这里，原问题的最小费用等于在多重集 S={A1,A2,…,AN}S=\{ A_1,A_2,\ldots,A_N \}S={A1 ,A2 ,…,AN } 上重复以下操作 (N−1)(N-1)(N−1) 次的成本之和：
* 令 s1s_1s1 和 s2s_2s2 为 SSS 中最小的两个元素。以 s1+s2s_1+s_2s1 +s2 的成本将长度为 s1s_1s1 和 s2s_2s2 的两条面包拼接在一起。
* 从 SSS 中删除 s1s_1s1 和 s2s_2s2 ，并将 s1+s2s_1+s_2s1 +s2 插入到 SSS 中。
由于每次操作后 SSS 的元素数量减少 111，显然完成以上操作后，SSS 只会剩下一个元素。
2. 考虑 L>A1+A2+…+ANL \gt A_1+A_2+\ldots +A_NL>A1 +A2 +…+AN 的情况：
对于 L>A1+A2+⋯+ANL > A_1+A_2+\cdots+A_NL>A1 +A2 +⋯+AN ，我们可以令 L=A1+A2+⋯+AN+XL = A_1 + A_2 + \cdots + A_N + XL=A1 +A2 +⋯+AN +X。
将剩余的部分当作一条面包，反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,AN,XA_1, \ldots, A_N, XA1 ,…,AN ,X 合并为一条面包的最小费用。”
这个问题同样可以使用上述的方法解决。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
