上海市计算机学会2023年1月月赛程序设计题解
T1 实验日志
题目描述：小爱进行物理实验持续n天，第i天记录a_i条实验数据。每页日志最多可记录m条数据。每天结束后合上日志，次日从第一页开始翻阅，直到找到第一个有空白位置的页面为止。求每天需要翻多少页才能找到起始记录位置。
解题思路：设截至当前已记录的数据总量为sum，则已写满的页数为sum/m（整数除法）。由于从下一页开始记录，因此需要翻动的页数即为sum/m。
参考实现：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
long long total = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cout << total / m << " ";
total += x;
}
return 0;
}
T2 凯撒加密
题目描述：将明文中的每个英文字母向后移动3位得到密文，字母z之后循环回字母a。空格及其他非字母字符保持不变。
解题思路：遍历输入的每个字符，若是小写字母则转换为大写字母的对应密文字母，转换公式为：(c - 'a' + 3) % 26 + 'a'。
参考实现：
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
getline(cin, s);
for (char &c : s) {
if (c >= 'a' && c <= 'z') {
c = (c - 'a' + 3) % 26 + 'a';
} else if (c >= 'A' && c <= 'Z') {
c = (c - 'A' + 3) % 26 + 'A';
}
}
cout << s << endl;
return 0;
}
T3 找零
题目描述：自动售票机每张票5元，可接受5元、10元、20元纸币。初始无零钱，顾客每人购买一张票且只投一张纸币。求最多能卖出多少张票。
解题思路：采用贪心策略。收到20元时优先找零一张10元和一张5元；收到10元时找零一张5元。使用变量记录当前拥有的5元、10元、20元数量。
参考实现：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int cnt5 = 0, cnt10 = 0, cnt20 = 0;
int result = 0;
for (int i = 0; i < n; ++i) {
int bill;
cin >> bill;
int change_needed = bill - 5;
// 先用20元找零
int use20 = min(change_needed / 20, cnt20);
change_needed -= use20 * 20;
// 再用10元找零
int use10 = min(change_needed / 10, cnt10);
change_needed -= use10 * 10;
// 最后用5元找零
int use5 = change_needed / 5;
if (use5 <= cnt5) {
cnt20 -= use20;
cnt10 -= use10;
cnt5 -= use5;
++result;
if (bill == 5) ++cnt5;
else if (bill == 10) ++cnt10;
else ++cnt20;
}
}
cout << result << endl;
return 0;
}
T4 新年灯会
题目描述：道路上有编号1到n的灯笼，现有p个灯笼不亮。求最少修复多少个灯笼，使得道路上存在连续m个亮着的灯笼。
解题思路：使用前缀和数组记录到每个位置为止不亮灯笼的总数。枚举所有长度为m的连续区间，计算每个区间内不亮灯笼的数量，取最小值即为答案。
参考实现：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, p;
cin >> n >> m >> p;
vector<int> broken(n + 1, 0);
for (int i = 0; i < p; ++i) {
int x;
cin >> x;
broken[x] = 1;
}
vector<int> prefix(n + 1, 0);
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i - 1] + broken[i];
}
int answer = INT_MAX;
for (int i = 1; i <= n - m + 1; ++i) {
int broken_in_range = prefix[i + m - 1] - prefix[i - 1];
answer = min(answer, broken_in_range);
}
cout << answer << endl;
return 0;
}
T5 积木染色（二）
题目描述：n块积木排成一排，有m种颜色可供染色。从第二块积木开始统计，恰有p块积木与前一块积木颜色不同。求满足条件的染色方案数模10^9+7。
解题思路：动态规划。定义dp[i][j]表示处理到第i块积木时，已有j块与前一块颜色不同的方案数。状态转移时考虑当前积木与前一块颜色相同或不同的情况。
参考实现：
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
int n, m, p;
cin >> n >> m >> p;
vector<vector<long long>> dp(n + 1, vector<long long>(p + 1, -1));
function<long long(int, int)> solve = [&](int idx, int diff) -> long long {
if (diff > p) return 0;
if (idx == n) {
return diff == p ? m : 0;
}
if (dp[idx][diff] != -1) return dp[idx][diff];
long long result = solve(idx + 1, diff);
result = (result + solve(idx + 1, diff + 1) * (m - 1) % MOD) % MOD;
dp[idx][diff] = result;
return result;
};
cout << solve(1, 0) << endl;
return 0;
}
数学推导：设f(i,j)为处理到第i块积木时已有j个颜色不同的方案数。状态转移方程为：
- 当j < p时：f(i,j) = f(i+1,j) + (m-1) × f(i+1,j+1)
- 当j = p时：f(i,j) = f(i+1,j)
边界条件：处理完所有n块积木时，若恰好有p个不同则返回m（最后一块有m种颜色选择），否则返回0。
