1 条题解

  • 0
    @ 2026-11-2 20:10:21

    对某些题目如果有自己比较独特的见解,可以在讨论区里发布你对本题的见解和解题思路。


    第十三届校赛(重现赛+改题)暨 SYUCTACM 周赛 #1 题解

    难度与考点一览:

    • A 二次整性:签到 / 构造,O(1)O(1)
    • B 齿轮装配线:0/1 背包计数,O(nW)O(nW)
    • C 排位复盘:前缀和最小值,O(n)O(n)
    • D 浸出液检测:分类计数,O(n)O(n)
    • E 逐级加训:求和公式,O(1)O(1)
    • F 日历翻页:日期模拟,O(k)O(k)
    • G 约数清点:枚举到 n\sqrt{n},O(n)O(\sqrt{n})
    • H 中位训练:排序 + 绝对值求和,O(nlog⁡n)O(n\log n)

    整体难度:A、D 为签到,C、F 为简单模拟,E、G 为数学/数论基础,B、H 需要一点算法意识。赛时提示「TLE 时优先减少不必要的运算」主要针对 E(用公式代替循环)、G(只枚举到 n\sqrt{n})、B(跳过 wi>Ww_i>W 的齿轮)。


    A. 二次整性

    **题意:给定质数 pp,输出实数 xx,满足 x2∈Zx^2\in\mathbb{Z},并使 ∣x∣\lvert x\rvert 最小。

    思路:取 x=0x=0,则 x2=0∈Zx^2=0\in\mathbb{Z},合法;又对任意实数都有 ∣x∣≥0=∣0∣\lvert x\rvert\ge 0=\lvert 0\rvert,所以 00 已经是全局最优。题目明确说明 xx 不必与 pp 有任何关系,因此 pp 读入后即可丢弃,任何 pp 的答案都是 00。

    复杂度:O(1)O(1)。

    **参考代码:

    #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. 齿轮装配线

    题意:nn 个齿轮,第 ii 个占用 wiw_i 长度,求满足 ∑i∈Swi=W\sum_{i\in S}w_i=W 的编号集合 SS 的数量,对 109+710^9+7 取模。齿轮按编号区分。

    思路:标准 0/1 背包计数。设 dp[s]dp[s] 表示用已处理的齿轮恰好凑出长度 ss 的方案数,初值 dp[0]=1dp[0]=1,其余为 00。对每个齿轮 ww,倒序枚举 ss 从 WW 到 ww:

    dp[s]←dp[s]+dp[s−w]dp[s]\leftarrow dp[s]+dp[s-w]

    倒序枚举保证同一齿轮不会被重复选取。最终 dp[W]dp[W] 即答案。由于「按编号区分」,相同重量的齿轮作为独立物品逐个转移即可,无需任何去重。

    复杂度:O(nW)≤106O(nW)\le 10^6,时限 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;
    }
    

    易错点:内层若正序枚举会退化成完全背包(同一齿轮被用多次);wi>Ww_i>W 时倒序循环边界为负,需特判或保证循环从 WW 到 ww。


    C. 排位复盘

    题意:给定 d1,…,dnd_1,\dots,d_n,pk=∑i=1kdip_k=\sum_{i=1}^k d_i,求 min⁡0≤k≤npk\min_{0\le k\le n}p_k。

    思路:边读边累加,维护当前前缀和 ss 与历史最小值 ansans,初值 ans=0ans=0 对应 p0p_0。每读入一个 dd 就更新 ss 和 ansans。注意初始时刻 00 也参与比较,因此全为正数时答案为 00。

    复杂度:O(n)O(n)。

    参考代码:

    #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;
    }
    

    易错点:∣di∣≤109\lvert d_i\rvert\le 10^9、n\le 10^5$,前缀和绝对值可达 101410^{14},必须用 long long;答案初值应为 00 而不是第一个前缀和。


    D. 浸出液检测

    题意:统计 xi<7x_i<7、xi=7x_i=7、xi>7x_i>7 的个数。

    思路:一次遍历,三个计数器分别累加即可。等号必须单独判断,xi=7x_i=7 只计入中性。

    复杂度:O(n)O(n)。

    参考代码:

    #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. 逐级加训

    题意:求

    ∑i=1n(i+i2),1≤n≤106.\sum_{i=1}^{n}(i+i^2),\qquad 1\le n\le 10^6.

    思路:直接用求和公式:

    $$\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}.$$

    n≤106n\le 10^6 时 n(n+1)(n+2)≈1018n(n+1)(n+2)\approx 10^{18},在 long long 范围内(<9.22×1018<9.22\times 10^{18}),可以先乘后除。

    复杂度:O(1)O(1)。用 O(n)O(n) 循环也能过,但公式更稳。

    参考代码:

    #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. 日历翻页

    题意:给定合法日期 yy 年 mm 月 dd 日,向后翻 kk 天,输出新日期。y≤4×109y\le 4\times 10^9,k\le 10^5$。

    思路:kk 很小,直接逐日推进:日期加一,若超过当月天数则回到 11 号并进位到下一月;月份超过 1212 则进位到下一年。每月天数用数组,二月按闰年规则特判:

    $$\text{闰年}\iff (y\bmod 400=0)\ \lor\ (y\bmod 4=0\land ybmod 100\ne 0).$$

    复杂度:O(k)≤105O(k)\le 10^5。

    参考代码:

    #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;
    }
    

    易错点:yy 可达 4×1094\times 10^9,超出 int 范围,必须用 long long;闰年判断不能只写 %4,21002100 不是闰年;跨年时月份与年份要同时进位。


    G. 约数清点

    题意:求 nn(1≤n≤10121\le n\le 10^{12})的正约数个数。

    思路:约数成对出现。枚举 dd 从 11 到 ⌊n⌋\lfloor\sqrt{n}\rfloor,若 d∣nd\mid n,则 dd 与 n/dn/d 都是约数,答案加 22;当 d2=nd^2=n 时两个因子相同,只能加 11。这样恰好每个约数被统计一次。

    复杂度:O(n)≤106O(\sqrt{n})\le 10^6。

    参考代码:

    #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)(浮点误差);d≤106d\le 10^6 时 d2≤1012d^2\le 10^{12},不会溢出。


    H. 中位训练

    题意:nn 为奇数,排序后中位数 med=b(n+1)/2\mathrm{med}=b_{(n+1)/2},求 med\mathrm{med} 与 ∑i=1n∣ai−med∣\sum_{i=1}^{n}\lvert a_i-\mathrm{med}\rvert。

    思路:排序后中位数位于下标 n/2n/2(从 00 开始),再遍历一次累加绝对差。由于 nn 为奇数,中位数一定是数组中的某个实际元素,不受重复值和负数影响。

    复杂度:O(nlog⁡n)O(n\log n)。

    参考代码:

    #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;
    }
    

    易错点:∣ai∣≤109\lvert a_i\rvert\le 10^9、n≤2×105n\le 2\times 10^5,绝对差之和可达 4×10144\times 10^{14},必须用 long long;输入不保证有序且可能有负数,不能省略排序。


    信息

    ID
    2627
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    57
    已通过
    30
    上传者