T1. 因子问题

任给两个正整数 $n$、$m$，求一个最小的正整数 $a$，使得 $a$ 和 $(m-a)$ 都是 $n$ 的因子。

时间限制：1 s
内存限制：64 MB

• 输入
  包括两个整数 $n$、$m$，$n$ 不超过 $10^6$。
• 输出
  输出一个整数 $a$，表示结果。如果答案不存在，则输出 -1。
• 样例输入

  35 10
  

• 样例输出

  5
  

思路分析

此题考查枚举法，难度入门。

常规思路下，我们可以枚举 $1\sim m/2$ 的所有数字，逐一验证是否满足条件，但是题目中并没有给出 $m$ 的范围，这给我们带来了不小的障碍。不妨转变思路，枚举 $n$ 的所有因子，事实上，由于因子成对出现这一特性，我们只需要枚举 $1\sim \sqrt{n}$ 的所有数字即可，加快枚举效率。

/** Name: T1.cpp* Problem: 因子问题* Author: Teacher Gao.* Date&Time: 2024/11/16 15:06*/#include <iostream>using namespace std;int main()
{int n, m;cin >> n >> m;for (int i = 1; i * i <= n; i++) {if (n % i == 0 && n % (m-i) == 0) {cout << i;return 0;}}cout << -1;return 0;
}

T2. 质数的和与积

两个质数的和是 $S$，它们的积最大是多少？

时间限制：1 s
内存限制：64 MB

• 输入
  一个不大于 $10000$ 的正整数 $S$，为两个质数的和。
• 输出
  一个整数，为两个质数的最大乘积。数据保证有解。
• 样例输入

  50
  

• 样例输出

  589
  

思路分析

此题考查枚举法与素数判定，难度入门。

根据题目描述，$S$ 必定是两个素数之和。由于 $2$ 是唯一的偶素数，为了加快枚举效率，我们可以分情况讨论：

• 如果 $S$ 是奇数，则直接输出 $2\times (S-2)$。
• 如果 $S$ 是偶数，为了求得乘积的最大值，需要保证两数的差值尽可能小，不妨对 $S/2\sim 3$ 范围内的整数进行倒序枚举验证，得到的第一对素数即为答案，输出其乘积即可。

/** Name: T2.cpp* Problem: 质数的和与积* Author: Teacher Gao.* Date&Time: 2024/11/16 15:23*/#include <iostream>using namespace std;bool prime(int n) {if (n < 2) return 0;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return 0;}}return 1;
}int main()
{int s;cin >> s;if (s % 2 == 1) {cout << 2 * (s - 2);}else {for (int i = s/2; i >= 3; i--) {if (prime(i) && prime(s-i)) {cout << i * (s-i);break;}}}return 0;
}

T3. 括号匹配问题

在某个字符串（长度不超过 $100$）中有左括号、右括号和大小写字母；规定（与常见的算术式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用 $ 标注，不能匹配的右括号用 ? 标注。

时间限制：1 s
内存限制：64 MB

• 输入
  输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过 $100$。
• 输出
  对每组输出数据，输出两行，第一行包含原始输入字符串，第二行由 $、? 和空格组成，$ 和 ? 表示与之对应的左括号和右括号不能匹配。
• 样例输入

  ((ABCD(x)
  )(rttyy())sss)(
  

• 样例输出

  ((ABCD(x)
  $$
  )(rttyy())sss)(
  ?            ?$
  

思路分析

此题考查模拟法与栈操作，属于基础题。

对于括号匹配问题，我们可以用栈进行模拟操作，具体来说：

• 若遇到左括号 (，则入栈，注意入栈元素是左括号的下标，这是为了方便后面的标记；
• 若遇到右括号 )，则检测栈是否为空，若不空，则弹出栈顶元素，否则将该右括号标记为不匹配；
• 当字符串遍历完毕之后，若栈中还有元素，则将栈中左括号标记为不匹配。

为了方便输出，这里将标记数组定义为一个空格字符串，长度与输入的字符串保持一致。

/** Name: T3.cpp* Problem: 括号匹配问题* Author: Teacher Gao.* Date&Time: 2024/11/16 15:34*/#include <iostream>
#include <string>
#include <stack>using namespace std;int main()
{string s;while (cin >> s) {string f(s.size(), ' ');stack<int> stk;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') {stk.push(i);}else if (s[i] == ')') {if (stk.empty()) {f[i] = '?';}else {stk.pop();}}}while (!stk.empty()) {f[stk.top()] = '$';stk.pop();}cout << s << endl << f << endl;}return 0;
}

T4. 吃糖果 2

现有 $n$（$0<n<50$）个糖果，每天只能吃 $2$ 个或者 $3$ 个，请计算共有多少种不同的吃法吃完糖果。

时间限制：1 s
内存限制：64 MB

• 输入
  输入的每一行包括一组测试数据，即为糖果数 $n$。最后一行为 $0$，表示测试结束。
• 输出
  每一行输出对应一行输入的结果，即为吃法的数目。最后一行的 $0$ 不用输出。
• 样例输入

  1
  2
  3
  4
  12
  0
  

• 样例输出

  0
  1
  1
  1
  12
  

思路分析

此题考查递推算法，属于基础题。

根据题目描述，容易得出递推公式 $f_i=f_{i-2}+f_{i-3}$，其中 $i\ge 3$，初始条件为 $f_1=0$，$f_2=f_3=1$。由于是多组数据，我们可以将所有可能的答案打表记录，对于每次询问以 $O(1)$ 的时间复杂度给出答案。

/** Name: T4.cpp* Problem: 吃糖果 2* Author: Teacher Gao.* Date&Time: 2024/11/14 16:52*/#include <iostream>using namespace std;int main()
{int f[55] = {0, 0, 1, 1};for (int i = 4; i <= 50; i++) {f[i] = f[i-2] + f[i-3];}int n;while (cin >> n && n) {cout << f[n] << "\n";}return 0;
}

T5. 铺砖

对于一个 $2$ 行 $n$ 列的走道，现在用 $1\times 2$ 和 $2\times 2$ 的砖去铺满，问有多少种不同的方式。

时间限制：1 s
内存限制：128 MB

• 输入
  整个测试有多组数据，请做到文件底结束。每行给出一个数字 $n$，$0\le n\le 250$。
• 输出
  如题。
• 样例输入

  2
  8
  12
  100
  200
  

• 样例输出

  3
  171
  2731
  845100400152152934331135470251
  1071292029505993517027974728227441735014801995855195223534251
  

思路分析

此题考查递推算法与高精度，难度稍高。

根据题目描述，容易得出递推公式 $f_i=f_{i-1}+2\times f_{i-2}$，其中 $i\ge 2$，初始条件为 $f_1=1$，$f_2=3$。由于是多组数据，我们同样可以打表，对于每次询问以 $O(1)$ 的时间复杂度给出答案。

至于高精度，这里用 $f[i][0]$ 表示第 $i$ 项的长度，$f[i][1\sim f[i][0]]$ 表示第 $i$ 项的值，为保证个位对齐，采用了逆序存储。

/** Name: T5.cpp* Problem: 铺砖* Author: Teacher Gao.* Date&Time: 2024/11/16 17:42*/#include <iostream>using namespace std;int f[255][105];int main()
{ios::sync_with_stdio(false);cin.tie(0);// 初始化f[1][1] = 1, f[2][1] = 3;f[0][0] = f[1][0] = f[2][0] = 1;// 递推 f[i] = f[i-1] + 2*f[i-2];for (int i = 3; i <= 250; i++) {// 高精度加法f[i][0] = max(f[i-1][0], f[i-2][0]);int x = 0;for (int j = 1; j <= f[i][0]; j++) {f[i][j] = f[i-1][j] + 2 * f[i-2][j] + x;x = f[i][j] / 10;f[i][j] %= 10;}if (x) f[i][++f[i][0]] = x;}int n;while (cin >> n) {for (int i = f[n][0]; i >= 1; i--) {cout << f[n][i];}cout << "\n";}return 0;
}