第三届太原理工大学程序设计新生赛预赛题解

A.口令
输入输出题。仅考察字符串的输入输出。建议直接使用string和getline。
标程：https://paste.ubuntu.com/p/chvDpfvS6N/
难度估计：CF 800
B.小龙的秘密
解法1：对两个字符串进行排序，然后比较两个字符串是否相同。
解法2：使用map映射，分别记录两个字符串中每一个字符出现的次数，然后依次进行比较。
解法3：通过将字符强制转换成数字的思想，读取第一个字符串的时候，其中的字符每出现一次就对记录数组+1，然后读取第二个字符串，如果当前字符出现次数为0则表示两个字符串不相似，否则对每个出现的字符-1。
标程：https://paste.ubuntu.com/p/Pj75wzwfGF/
难度估计：CF 1000
C.「爱」与自动手记人偶
显然，键盘中的大部分空间都没有意义，每次读入字符都检索整个键盘是会超时的。为此，需要建立一个字符--->二维坐标的映射关系，可以用C++STL的map或数组之类的实现。除此之外就是一个有些细节的简单模拟题了，注意大小写的切换和空格的处理。
时间复杂度O(T)
标程：https://paste.ubuntu.com/p/6DnCXvnxfR/
难度估计：CF 1500
D.初恋小号
设Kumiko持上低音号，Reina持小号所登上的高度之和为a，Kumiko持小号，Reina持上低音号号所登上的高度之和为b，两人进行了x次交换。 $(a+b ==∑h_i )$
两人消耗的体力之差的绝对值可以被表示为 $abs(a*w_1+b*w_0-(a*w_0+b*w_1))$ ，提取公因式可得： $abs((a-b)*(w_1-w_0 ))$ ,可见体力之差的绝对值只与a-b有关。
两人消耗的体力之和可以被表示为 $x*2*c+(w_0+w_1 )*∑h_i$ ，可见体力之和只与x有关。
若该问题只有第一问，则可以转化为使a-b的绝对值最小，是一道经典的01背包问题。加上第二问后，我们可以将01背包变形，设dp[i][j][status]为登上i层a-b的值为j,状态为status时两者交换的最小次数，status == 0表示当前位置Kumiko持上低音号，Reina持小号，status==1则反之。
设t =h[i+1],当status == 1时， t= -t，状态转移方程为
dp[i+1][j+t][status]=min⁡(dp[i][j][status],dp[i+1][j+t][status])
dp[i+1][j-t][status^1]=min⁡(dp[i][j][status]+1,dp[i+1][j-t][status^1])
最后,从i=0开始循环检测dp[n][i][0],dp[n][i][1],dp[n][-i][0],dp[n][-i][1],若其中有一项存在，则说明当前的i是最小的abs(a-b)，带入上文的表达式即可求出结果。
时间复杂度 $O(n*∑h_i)$
标程：https://paste.ubuntu.com/p/fV64G2sQHJ/
难度估计：CF 1900
E.Amadeus System
简单模拟后可发现，长度为n的字符串的格式为 $0^x 1^y (0≤x≤n,x+y==n)$ ， $a^x$ 指x个连续的a。如长度为3的满足要求的字符串有111,011,001,000。因此长度不超过 n的字符串有(2+n+1)*n/2种，答案会爆int，需要使用long long计算。
时间复杂度O(1)
标程：https://paste.ubuntu.com/p/Vvb4D8Cbqq/
难度估计：CF 1000
F.漫无止境的八月
对于某个团员而言，其建议被采纳的顺序由时间从前向后排列，显然可以用一个队列来维护。当团员A提出一个建议时，将其建议插入表示A建议的队列，而当A的建议被采纳时则将其队头弹出。
而由于“优先级“只有一种变化：将优先级最高的团员的优先级变为最低。可以发现优先级实际上是一个循环队列，初始时队列中的元素为1，2，3，4,当进行一次操作2后，可以将队头1插入队尾，再将队头弹出即可，此时队列变为2，3，4，1。
每次采纳建议时，取出优先级的循环队列，从队头开始依次检索4个元素，若该元素所对应的建议队列不为空，则采纳该队头的建议。
时间复杂度O(n),由于是简单题就没有卡时间，乱搞也可以过。
标程：https://paste.ubuntu.com/p/gmpXy4Vn5W/
难度估计：CF 1200
G.Qingyu的暗杀名单
考察STL操作，用map记录每句话对应的分值，每个人存一个结构体统计得分等信息，按照题意排序，重载小于号或写cmp函数都可以。坑点，注意“永久”。
标程：https://paste.ubuntu.com/p/S4xwfdTmwj/
难度估计：CF 1400
H.Wood Cube
朴素的想法：将所有对合法的发卡两两枚举比较，显然是会超时的。
对于某个发卡，要确定其是不是可以成为一个备选的答案，只需检查其前面距离不超过d的位置有没有与之相同的发卡(后面也可以，不过为了方便思考，我们只考虑一个方向，两者实际等价)。
为了快速的查找，我们可以用struct定义一个六元组node，重载其<运算符，并定义一个map<node,int>。我们从前到后遍历每个发卡，假设已遍历到位置i，我们检查map中与该六元组所对的位置(若不存在即跳过)，假设该位置为j，若i-j≤d则可用于更新答案。检查完之后，将该元素及其位置插入到map，若map中已有该元素则更新其位置(显然，对于相同的元素只有最后的位置才有作用)。
时间复杂度O(nlog(n))。也可以用哈希做到O(n)
标程：https://paste.ubuntu.com/p/Nr7R8wJr3z/
难度估计：CF 1400
I.放学后茶会的甜点
题目要求“平均甜度最大的矩形区域“。简单思考可以发现，该区域的甜度一定与最大甜度的格子的甜度相同，因为可选该格子为我们要取的矩形区域而任意矩形区域的平均甜度不可能大于该格子。
因此，题目可转变为“每次对一块矩形区域的元素+1，求整个矩形中的最大元素“。这是一个经典的”二维差分“问题，在此不做赘述。
时间复杂度O(T)
标程：https://paste.ubuntu.com/p/ZXkGjqWhkw/
难度估计：CF 1300
J.小幼稚的生日
通过肉眼观察法或是打表法可以很容易发现规律是n/2，需要特判n为1的情况。
常规做法：gcd(n,x)=gcd(n,n-x)，所以与n不互质的数x，n-x成对出现，平均值为n/2。
时间复杂度O(1)
标程：https://paste.ubuntu.com/p/bqZQX4YRDB/
难度估计：CF 1400
K.发放奖金
经典贪心问题，设 $c[i] = \frac{A[i]}{B[i]}$ .题目要求就变为，给出一组 $c[0], c[1], c[2], ..., c[n - 1], c[n]$ 序列.对其重新排序，使得 $\sum_{i = 0} ^ {n - 1} \prod_{j = 0}^{i}c[j]$ ,即 $c[0] + c[0] \times c[1] + c[0] \times c[1] \times c[2] + ... + c[0] \times c[1] \times c[2] \times c[3] \times ... \times c[n]$ 最大.
令 $c[i] > c[i + 1]$ .设 $k = \prod_{j=0}^{i - 1}c[j]$ .
当 $c[i]$ 在 $c[i + 1]$ 前时，
$ans = k\times (c[i] + c[i] \cdot c[i + 1])$ .
当 $c[i + 1]$ 在 $c[i]$ 前时，
$ans' = k\times (c[i + 1] + c[i] \cdot c[i + 1])$ . $\because ans > ans',\therefore c[i]$ 应该排在 $c[i + 1]$ 之前.
综上，当 $c$ 序列为降序排序时，结果 $m \times \sum_{i = 0} ^ {n - 1} \prod_{j = 0}^{i}c[j]$ 最大.
标程：https://paste.ubuntu.com/p/T7tmJFnVwS/
难度估计：CF 1300
L.拯救公主
题意：给出一个起点集合，给出一个终点集合，求任意起点到任意终点的最短路径。
考虑BFS将所有起点入队，一步步扩展未经过的点，扩展到第一个在终点集合中的点，此时步数就是答案。
时间复杂度O(n)
标程：https://paste.ubuntu.com/p/FTvcHwmNxm/
难度估计：CF 1600
M.原马蹄印
由题意易推出规律如下，最中间的图形保持不变，后续图案逐层扩展：

标程：https://paste.ubuntu.com/p/6Hb5xHHd8g/
难度估计：CF 1900
N.蝴蝶翅膀的发散
简单的递推，题目中已经给出递推式，直接两重循环计算即可，注意取模。可以使用前缀和优化。
时间复杂度O(n*d)或O(n)
标程：https://paste.ubuntu.com/p/CYYqt7bdxf/
难度估计：CF 1000</运算符，并定义一个map<node,int>