UESTC 第十届 ICPC 趣味程序设计竞赛第一场（热身赛）题解

5/5 Penalty: 03:36:41 Rank 5

英语口试之前打比赛，居然 AK 了…… （说实话真的头一次 AK 一个比赛……）

A. 阴阳师？这游戏没有SSR！

题目大意：给出 个式神，砸一次砸中的概率是 ，求砸两次后砸中式神数的期望。

根据标题，期望数为 ，因此直接输出就好了（大雾）。

根据期望性质，，因此设 为砸第一次砸中式神数的期望， 为砸第二次砸中式神的期望，两个事件的并就是答案。

那么 ，算出这两个后求和就行了。

时间复杂度：，空间复杂度：。

代码见这里。

B. 保护果实

题目大意：有 块板子排成一行，如果要买第 块栅栏，那么必须要先买第 块栅栏（第一块栅栏除外），求至少买多少板子才能构成一个多边形。

构成多边形的条件复习一下：最大边长度小于其余边长度之和。

然后，如果要买第 块栅栏，那么必须要先买第 块栅栏（第一块栅栏除外）！

考虑买了第 块，那一定是买了第 块，买了第 块，那一定是买了第 块，……，由数学归纳法可知，所买板子序列一定是从 开始的。

考试的时候想到了这点，然后就去抢 E 的一血，结果一血没抢到就忘了，再看的时候以为是一道双指针扫描，结果发现维护最大值可能复杂度爆炸，然后又想起来了……

时间复杂度：，空间复杂度：。

代码见这里。

C. 渐变字符串

题目大意：如果一个字符串，它每个字母（第一个除外）为前一个字母的后一位，则这样的字符串被称为渐变字符串。如：abcde, bc, m。求 个写有小写字母的卡片重排后最少构成多少渐变字符串。

看到数据范围，暴力之即可。

统计出每个字母出现的次数，然后每次从第一个出现次数不为 的字母开始，尽可能长地扩展渐变字符串，直到无法扩展，重复这个操作直到所有字符出现次数均为 即可。

时间复杂度：，空间复杂度：

代码见这里。

D. 可怜的非洲银

题目大意：给出每天攒的 SSR 碎片种类，每天还能获得一个 F 种类的碎片，如果一种碎片凑齐 个就能获得 SSR，求最少多少天才能获得 SSR，否则输出无解信息。

根据 A 题，是不可能获得 SSR 的，因此直接无解即可（大雾）。

啥也不说了，还是暴力。开一个桶统计一下每种碎片的出现次数，如果这种碎片出现了 次，就输出有解，否则判断 与 的大小关系输出不同的无解信息。

因为口语考试这题打急了，WA 了三次……

时间复杂度：，其中 为字符串长度，空间复杂度：。

代码见这里。

E. 简单的数学题

题目大意：给出一个数 ，求它的各个数位重新排列得到的数 ，使得 ，并且 最小。

猜结论： 这个数是 的各个排列字典序最小的一个。

证明？err……

下面的证明引自这里。

考虑初始数字为 ，现在交换两位 与 。

那么新形成的两个数字之差为：

中间 ，于是互换两个数位后得到的数与原数的差值必然是 的整数倍。任意互换数位后的数，必然可由有限次两个数位互换得到。

因此猜想是对的。

就因为抢这道题的一血结果差点把 B 题条件忘了……

时间复杂度：，空间复杂度：。

代码见这里。