Solution * 2025 - 暑期集训 DAY2

平均难度：5/10

平均AC率：33%

水题$\times3$

数据截止至2025/7/18 10:00

A. 缺失的数字 通过人数25/54 AC率：46% 难度：1/10

基础模拟题。先将数组排序，遍历数组寻找不是上一个数+1的数，输出这个数-1即可。

重要的事情说3遍：freopen！freopen！freopen！

int main() {
    freopen("文件IO.in", "r", stdin);
    freopen("文件IO.out", "w", stdout);
    ...  // 正常代码
}

Sample:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
using namespace std;

int a[110];

int main() {
    freopen("num.in", "r", stdin);
    freopen("num.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    for (int i = 1; i <= n; i++)
        if (a[i+1] != a[i]+1) {
            printf("%d", a[i]+1);
            return 0;
        }
    return 0;
}

水题+1

B. 不及格 24/37 64% 0/10

这题不用讲了吧，枚举判断，语法题

代码还用摆吗？

水题+1 （没有一次AC的用你的爪爪敲敲脑壳，想想你在干嘛）

C. 集会 25/58 43% 3/10

观察数据范围，$N$ 最大仅为 100，第一层循环枚举集会的可能地点，第二层循环求解每个人参加集会的消耗。

==坑点注意：可以证明，集会的地点不一定在0点和最右边住的人的位置之间，有可能超过这个范围消耗反而更少。==所以建议左右各拓宽100个单位来枚举。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
using namespace std;

int a[110];

int main() {
    freopen("jihui.in", "r", stdin);
    freopen("jihui.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    long long _min = INT_MAX;
    for (int p = -100; p <= n+100; p++) {       // 枚举集会地点
        long long sum = 0;
        for (int m = 1; m <= n; m++) sum += pow(a[m] - p, 2);
        _min = min(_min, sum);
    }
    printf("%d", _min);
    return 0;
}

水题+1

D. 统计区间 23/99 23% 4/10

任何高深的算法都是暴力优化而来的。最原始的方法就是枚举区间的左右端点，在循环枚举区间里的每个数，得到结果，时间复杂度 $O(n^3)$。稍微优化，使用前缀和来求解区间和，可以去掉一层循环，时间复杂度 $O(n^2)$，仍会超时（31分）。

由于用到了前缀和算法，计算期间数值可能会超过 int，注意开 long long（下面的暴力代码没有开long long，所以是0分）

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
using namespace std;

const int N = 2e5+10;
int a[N], pf[N]; 

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pf[i] = pf[i-1] + a[i];
    }

    int result = 0;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) 
            if (pf[l-1] == pf[r]-k) result++;
    printf("%d", result);
    return 0;
}

为了高效统计满足条件的 $i-1$ 的数量，我们可以使用哈希表（STL - map）来记录前缀和的出现次数：

1. 遍历数组，计算当前前缀和 pf[r]。
2. 在哈希表中查找 pf[r] - k 的出现次数，这个次数就是满足条件的 $i-1$ 的数量（即有多少个 $i-1$ 使得pf[i-1] = pf[r] - k）。
3. 将当前前缀和 pf[r] 存入哈希表，供后续查找使用。

这种方法将时间复杂度降低到 $O(n)$，因为每个元素只需要常数时间的操作。

正解：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <map>
using namespace std;

using ll = long long;

const int N = 2e5+10;
ll a[N], pf[N];    // 前缀和

map<ll, ll> mp;

int main() {
    freopen("tjqj.in", "r", stdin);
    freopen("tjqj.out", "w", stdout);
    ll n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pf[i] = pf[i-1] + a[i];
    }

    ll result = 0;
    for (int r = 1; r <= n; r++) {
        mp[pf[r - 1]]++;
        result += mp[pf[r] - k];
    }
    printf("%lld", result);
    return 0;
}

水题？

E. 旅行 21/77 27% 5/10

此类图问题可以使用 DFS（BFS 也行，但写起来复杂，不推荐使用）。

对于每个城市，使用深度优先搜索（DFS）来遍历所有可达的城市。这样可以有效地找到从该城市出发可以到达的所有城市。

由于$n$ 最多是 2000，对于每个城市进行一次 DFS 的时间复杂度是 $O(n + m)$，总复杂度是 $O(n\cdot(n + m))$，这在 $n=2000$ 和$m=2000$ 时大约是 $4\times10^6$ 次操作，是可以接受的。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

bool visit[2010];
vector<vector<int> > adj(2010);

void dfs(int u) {
    visit[u] = true;
    for (int v : adj[u])
        if (!visit[v]) dfs(v);
}

int main() {
    freopen("lx.in", "r", stdin);
    freopen("lx.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }

    int total = 0;
    for (int u = 1; u <= n; u++) {
        memset(visit, false, sizeof(visit));
        dfs(u);
        for (int v = 1; v <= n; v++)
            if (visit[v]) total++;
    }

    printf("%d", total);
    return 0;
}

F. 我讨厌非整数 10/50 20% 7/10

我确实很讨厌非整数。

为了解决这个问题，我们需要计算给定序列的所有非空子集中，平均值是整数的子集数量。平均值是整数意味着子集元素之和必须能被子集大小整除。由于序列长度最大为 100，直接枚举所有子集不可行，因此我们采用动态规划的方法来高效计算。

1. 对于每个非空子集，其平均值是整数的条件是子集元素之和（记为 S）能被子集大小（记为k）整除，即 S%k == `。

2. 我们枚举子集大小 k（从1到N），对于每个k，使用动态规划计算所有大小为k的子集中，元素之和模k等于0的子集数量。

3. 状态定义：dp[j][r]表示当前已考虑部分元素，选取了j个元素，且这些元素之和模k的余数为r的方案数。

4. 状态转移：对于每个元素，我们更新dp数组。具体来说，对于每个元素，从大到小更新j（避免重复计数），并更新余数r。

5. 结果累计：对于每个k，将dp[k][0]（即大小为k且元素之和能被k整除的子集数量）累加到最终答案中。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

using ll = long long;     // 注意long long

const int Mod = 998244353;
ll a[110], dp[110][110];

int main() {
    freopen("hate.in", "r", stdin);
    freopen("hate.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    ll result = 0;
    for (int k = 1; k <= n; k++) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for (int i = 0; i < n; i++)
            for (int j = k; j >= 1; j--)
                for (int r = 0; r < k; r++) {
                    int prev_r = (r - a[i]%k + k) % k;
                    dp[j][r] = (dp[j][r] + dp[j-1][prev_r]) % Mod;
                }
        result = (result + dp[k][0]) % Mod;
    }

    printf("%lld", result);
    return 0;
}

G. 图的破坏 7/24 29% 9/10

有点难哈，想做的去看伍衍大佬的题解

©LY 2025/7/18 *

Edit by Typora(Markdown)

Partial by Deepseek

Thanks @WuYan