- 第十三届校赛(重现赛+改题)暨2026级SYUCT-ACM新生第三次部分训练暨SYUCTACM周赛#1
出题人题解
- @ 2026-10-17 10:12:12
对某些题目如果有自己比较独特的见解,可以在讨论区里发布你对本题的见解和解题思路。
第十三届校赛(重现赛+改题)暨 SYUCTACM 周赛 #1 题解
难度与考点一览:
- A 二次整性:签到 / 构造,
- B 齿轮装配线:0/1 背包计数,
- C 排位复盘:前缀和最小值,
- D 浸出液检测:分类计数,
- E 逐级加训:求和公式,
- F 日历翻页:日期模拟,
- G 约数清点:枚举到 ,
- H 中位训练:排序 + 绝对值求和,
整体难度:A、D 为签到,C、F 为简单模拟,E、G 为数学/数论基础,B、H 需要一点算法意识。赛时提示「TLE 时优先减少不必要的运算」主要针对 E(用公式代替循环)、G(只枚举到 )、B(跳过 的齿轮)。
A. 二次整性
**题意:给定质数 ,输出实数 ,满足 ,并使 最小。
思路:取 ,则 ,合法;又对任意实数都有 ,所以 已经是全局最优。题目明确说明 不必与 有任何关系,因此 读入后即可丢弃,任何 的答案都是 。
复杂度:。
**参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long p;
cin >> p;
cout << "0.0\n";
return 0;
}
易错点:输出必须含小数点且小数点后至少一位,0 会格式错误;评测按精确值比较,不设误差容忍,0.0、0.00、-0.0 均可。
B. 齿轮装配线
题意: 个齿轮,第 个占用 长度,求满足 的编号集合 的数量,对 取模。齿轮按编号区分。
思路:标准 0/1 背包计数。设 表示用已处理的齿轮恰好凑出长度 的方案数,初值 ,其余为 。对每个齿轮 ,倒序枚举 从 到 :
倒序枚举保证同一齿轮不会被重复选取。最终 即答案。由于「按编号区分」,相同重量的齿轮作为独立物品逐个转移即可,无需任何去重。
复杂度:,时限 4000ms 非常充裕。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W;
cin >> n >> W;
vector<int> dp(W + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
int w;
cin >> w;
if (w > W) continue;
for (int s = W; s >= w; --s) {
dp[s] += dp[s - w];
if (dp[s] >= MOD) dp[s] -= MOD;
}
}
cout << dp[W] << '\n';
return 0;
}
易错点:内层若正序枚举会退化成完全背包(同一齿轮被用多次); 时倒序循环边界为负,需特判或保证循环从 到 。
C. 排位复盘
题意:给定 ,,求 。
思路:边读边累加,维护当前前缀和 与历史最小值 ,初值 对应 。每读入一个 就更新 和 。注意初始时刻 也参与比较,因此全为正数时答案为 。
复杂度:。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long s = 0, ans = 0;
for (int i = 0; i < n; ++i) {
long long d;
cin >> d;
s += d;
ans = min(ans, s);
}
cout << ans << '\n';
return 0;
}
易错点:、n\le 10^5$,前缀和绝对值可达 ,必须用 long long;答案初值应为 而不是第一个前缀和。
D. 浸出液检测
题意:统计 、、 的个数。
思路:一次遍历,三个计数器分别累加即可。等号必须单独判断, 只计入中性。
复杂度:。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long a = 0, b = 0, c = 0;
for (int i = 0; i < n; ++i) {
long x;
cin >> x;
if (x < 7) ++a;
else if (x == 7) ++b;
else ++c;
}
cout << a << ' ' << b << ' ' << c << '\n';
return 0;
}
易错点:把 ==7 写进 < 或 > 的分支会导致计数错误;输出顺序是酸性、中性、碱性。
E. 逐级加训
题意:求
思路:直接用求和公式:
$$\sum_{i=1}^{n}i=\frac{n(n+1)}{2},\qquad \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}.$$两者相加可化简为
$$\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6} =\frac{n(n+1)(n+2)}{3}.$$ 时 ,在 long long 范围内(),可以先乘后除。
复杂度:。用 循环也能过,但公式更稳。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n * (n + 1) * (n + 2) / 3 << '\n';
return 0;
}
易错点:用 int 计算中间乘积会溢出;若担心乘法溢出,可先算 n*(n+1)/2 与 n*(n+1)*(2*n+1)/6 再相加,或用 __int128。
F. 日历翻页
题意:给定合法日期 年 月 日,向后翻 天,输出新日期。,k\le 10^5$。
思路: 很小,直接逐日推进:日期加一,若超过当月天数则回到 号并进位到下一月;月份超过 则进位到下一年。每月天数用数组,二月按闰年规则特判:
$$\text{闰年}\iff (y\bmod 400=0)\ \lor\ (y\bmod 4=0\land ybmod 100\ne 0).$$复杂度:。
参考代码:
#include <bits/stdc++.h>
using namespace std;
bool leap(long long y) {
return y % 400 ==0 || (y % 4 == 0 && y % 100 != 0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long y, k;
int m, d;
cin >> y >> m >> d >> k;
int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
while (k--) {
++d;
int lim = (m == 2 && leap(y)) ? 29 : md[m];
if (d > lim) {
d = 1;
if (++m > 12) {
m = 1;
++y;
}
}
}
cout << y << ' ' << m << ' ' << d << '\n';
return 0;
}
易错点: 可达 ,超出 int 范围,必须用 long long;闰年判断不能只写 %4, 不是闰年;跨年时月份与年份要同时进位。
G. 约数清点
题意:求 ()的正约数个数。
思路:约数成对出现。枚举 从 到 ,若 ,则 与 都是约数,答案加 ;当 时两个因子相同,只能加 。这样恰好每个约数被统计一次。
复杂度:。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long ans = 0;
for (long long d = 1; d * d <= n; ++d) {
if (n % d == 0) ans += (d * d == n ? 1 : 2);
}
cout << ans << '\n';
return 0;
}
易错点:完全平方数不特判会多算一次;循环条件写 d*d<=n 而不是 d<=sqrt(n)(浮点误差); 时 ,不会溢出。
H. 中位训练
题意: 为奇数,排序后中位数 ,求 与 。
思路:排序后中位数位于下标 (从 开始),再遍历一次累加绝对差。由于 为奇数,中位数一定是数组中的某个实际元素,不受重复值和负数影响。
复杂度:。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
long med = a[n / 2];
long long sum = 0;
for (long long x : a) sum += llabs(x - med);
cout << med << ' ' << sum << '\n';
return 0;
}
易错点:、,绝对差之和可达 ,必须用 long long;输入不保证有序且可能有负数,不能省略排序。