UESTC 第十届 ICPC 趣味程序设计竞赛第一场（热身赛）题解
5/5 Penalty: 03:36:41 Rank 5
英语口试之前打比赛，居然 AK 了…… （说实话真的头一次 AK 一个比赛……）
A. 阴阳师？这游戏没有SSR！
题目大意：给出 n 个式神，砸一次砸中的概率是 pi，求砸两次后砸中式神数的期望。
根据标题，期望数为 0，因此直接输出就好了（大雾）。
根据期望性质，E(X+Y) = E(X) + E(Y)，因此设 X 为砸第一次砸中式神数的期望，Y 为砸第二次砸中式神的期望，两个事件的并就是答案。
那么
时间复杂度：𝒪(n)，空间复杂度：𝒪(1)。
代码见这里。
B. 保护果实
题目大意：有 n 块板子排成一行，如果要买第 i 块栅栏，那么必须要先买第 i − 1 块栅栏（第一块栅栏除外），求至少买多少板子才能构成一个多边形。
构成多边形的条件复习一下：最大边长度小于其余边长度之和。
然后，如果要买第 i 块栅栏，那么必须要先买第 i − 1 块栅栏（第一块栅栏除外）！
考虑买了第 i 块，那一定是买了第 i − 1 块，买了第 i − 1 块，那一定是买了第 i − 2 块，……，由数学归纳法可知，所买板子序列一定是从 1 开始的。
考试的时候想到了这点，然后就去抢 E 的一血，结果一血没抢到就忘了，再看的时候以为是一道双指针扫描，结果发现维护最大值可能复杂度爆炸，然后又想起来了……
时间复杂度：𝒪(n)，空间复杂度：𝒪(1)。
代码见这里。
C. 渐变字符串
题目大意：如果一个字符串，它每个字母（第一个除外）为前一个字母的后一位，则这样的字符串被称为渐变字符串。如：abcde,
bc, m。求 n
个写有小写字母的卡片重排后最少构成多少渐变字符串。
看到数据范围，暴力之即可。
统计出每个字母出现的次数，然后每次从第一个出现次数不为 0 的字母开始，尽可能长地扩展渐变字符串，直到无法扩展，重复这个操作直到所有字符出现次数均为 0 即可。
时间复杂度：𝒪(n)，空间复杂度：𝒪(n)
代码见这里。
D. 可怜的非洲银
题目大意：给出每天攒的 SSR 碎片种类，每天还能获得一个 F 种类的碎片，如果一种碎片凑齐 50 个就能获得 SSR，求最少多少天才能获得 SSR，否则输出无解信息。
根据 A 题，是不可能获得 SSR 的，因此直接无解即可（大雾）。
啥也不说了，还是暴力。开一个桶统计一下每种碎片的出现次数，如果这种碎片出现了 50 次，就输出有解，否则判断 n 与 k 的大小关系输出不同的无解信息。
因为口语考试这题打急了，WA 了三次……
时间复杂度：𝒪(min(n,k)m)，其中 m 为字符串长度，空间复杂度：𝒪(m)。
代码见这里。
E. 简单的数学题
题目大意：给出一个数 n，求它的各个数位重新排列得到的数 m，使得 |n − m| mod 9 ≡ 0，并且 m 最小。
猜结论：m 这个数是 n 的各个排列字典序最小的一个。
证明？err……
下面的证明引自这里。
考虑初始数字为
那么新形成的两个数字之差为：
中间 (10p − q−1) mod 9 ≡ 0，于是互换两个数位后得到的数与原数的差值必然是 9 的整数倍。任意互换数位后的数，必然可由有限次两个数位互换得到。
因此猜想是对的。
就因为抢这道题的一血结果差点把 B 题条件忘了……
时间复杂度：𝒪(nlogn)，空间复杂度：𝒪(n)。
代码见这里。