第一届东南大学大学生程序设计竞赛（冬季）- 初赛 题解

冬季赛命题组

A. Hello_Challenger

模拟。输出 "Welcome to the SEU Winter Programming Contest!"。

B. Hello_Number

模拟。对于全为奇数和全为偶数的情况，输出-1，否则如果和为偶数，输出两个奇数的和。如果和为奇数，输出两个偶数的和。

C. Hello_BloodType

模拟。一共只有 $4\times 4=16$ 种可能性，用 if 语句分类即可。对于字符串表示的血型，可以先将其转化成数字 $1\sim 4$，再进行处理。

D. 宾语从句

按照题意模拟即可。奇数时输出 I hate；偶数时输出 I love。最后一个单词输出 it 其余的输出 that。

E. 小雅米与内鬼

考虑不是内鬼的编号出现偶数次，内鬼出线奇数次，直接用异或操作即可。注意读入内容消耗的时间。

F. 旧函数

函数实质是求二进制形式中 $1$ 的位数，从 $1$ 开始竖着写观察每一列的规律(右对齐)，发现存在周期性。

G. 天气之女小雅米

将点按极坐标排序，每次枚举一个点，看它作为起点逆时针的点排列能否在一个半圆上即可。

H. 小 F 和卡池

这是一个基础的概率问题，显然答案为 $\sum_{i=1}^n n/i$。由于题目要求化为模意义下的分数，使用逆元来完成除法即可。逆元的求法使用费马小定理或扩展欧几里得算法均可。

I. 毒瘤的计数

我们发现，对 $x_i$ 的某一个取值 $k$，前 $i-1$ 个数可以组合出 $j$，那么前 $i$ 个数可组合出 $j+k^2$。

令 $f[i][j]$ 表示用前 $i$ 种数字能否组合出 $j$，利用递推的思想暴力转移即可，转移方程 f[i][j] |= f[i-1][j-k*k]。

时间复杂度 $O(n^2 m^3)$，可通过本题。

若需进一步优化，可以采用 C++ 标准库中的 bitset。

J. 优雅的毒瘤

解法1

用二进制法枚举所有子集，然后用 next_permutation 函数枚举某个子集的所有全排列，将每个排列存入 std::string 最后排序即可。

解法2

写一个递归（深度优先搜索），每一步枚举序列的下一位填上哪一个数字。用一个栈记录已经被填入的数字，若每一步的枚举是按从小到大的顺序的，那么栈的所有状态就是答案。

K. 小雅米的无向连通图

直接输出最短路矩阵即可。

我们可以用反证法证明，如果新图的最路矩阵发生了变化，变小了，那么原来的最短路矩阵就不是最短路了，发生矛盾。

L. 抱歉，有钱是真的能为所欲为的

根据同余，$q^i\ mod\ P$ 会构成循环，且循环节小于等于 $P$。所以对于每组数据，可以通过暴力求出 $q^i\ mod\ P$ 的循环节 $len$ 以及一次循环中 $50$ 倍数的数量 $cnt$。那么这道题的答案可以转化成求 $\lfloor \frac{n}{len}\rfloor$ 个循环中、及循环前 $n\ mod\ len$ 个数中 $50$ 倍数的个数。($a\ mod\ b$ 表示 $a$ 除 $b$ 的余数)