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


第十三届校赛(重现赛+改题)暨 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;输入不保证有序且可能有负数,不能省略排序。


0 條評論

目前還沒有評論...