1 条题解
-
0
对某些题目如果有自己比较独特的见解,可以在讨论区里发布你对本题的见解和解题思路。
第十三届校赛(重现赛+改题)暨 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;输入不保证有序且可能有负数,不能省略排序。
- 1
信息
- ID
- 2627
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 57
- 已通过
- 30
- 上传者