【题解】【LGR-(-13) 】SCP 2021 第一轮（初赛）模拟

· · 个人记录

前言

由于自己太菜了，连初赛题都不会做了，所以写篇题解充充电。

UPD（2021.9.16）：

在经历了十二天的咕咕咕打磨以后，这篇题解终于赶在 CSP2021 第一轮（9.19）前公开。（虽然还是有四道题不会做……）

祝各位 CSP2021 第一轮 RP++！

完整题面 & 标准答案

见比赛界面。

题解

一、单项选择题

二、阅读程序

题面注：程序输入不超过数组或字符串定义的范围。

#include <cstdio>
#include <cstring>

using namespace std;

char s[10000];
int cnt[26];

int main() {
    scanf("%s", s);
    for (int i = 0; i < strlen(s); ++i) {
        if (cnt[s[i] - 'a'] <= 50) {
            s[strlen(s)] = s[i];
        }
        ++cnt[s[i] - 'a'];
    }
    printf("%s\n", s);
    return 0;
}

P.S. 第 11 行即为 for 循环。

#include <cstdio>

const int N = 5010;
const int M = 20010;
const int inf = 1073741823;

int e, bg[N], nx[M], to[M], wt[M];
inline void link(int u, int v, int w) {
    to[++e] = v;
    nx[e] = bg[u];
    wt[e] = w;
    bg[u] = e;
}

int n, m, u, v, w;
int f[N], h[N << 1];

void update(int x, int y) {
    x += n - 1;
    for (h[x] = y; x; x >>= 1)
    h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i != m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        link(u, v, w);
    }
    int nn = n << 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j != nn; ++j)
            h[j] = 0;
        for (int j = 0; j <= n; ++j)
            f[j] = inf;
        f[i] = 0;
        update(i, i);
        for (int j = i; true; j = h[1]) {
            if (f[j] == inf) break;
            for (int k = bg[j]; k; k = nx[k]) {
                if (f[j] + wt[k] < f[to[k]]) {
                    f[to[k]] = f[j] + wt[k];
                    update(to[k], to[k]);
                }
            }
            update(j, 0);
        }
        for (int j = 1; j <= n; ++j)
            printf("%d%c", f[j], "\n "[j != n]);
    }
    return 0;
}

P.S. 第 34 行是给 f 数组赋初值的 for 循环。

#include <bits/stdc++.h>
using namespace std;

#define N 105
#define INF 1e9

int dis1[N][N], dis2[N][N];
int mp[N][N], n, m;

void fun1(int dis[N][N]) {
    static bool vis[N];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = mp[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) vis[j] = 0;
        for (int k = 1; k <= n; k++) {
            int now = 0;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (!now || dis[i][now] > dis[i][j]))
                    now = j;
            }
            vis[now] = 1;
            for (int j = 1; j <= n; j++) {
                if(!vis[j]&&dis[i][j] > dis[i][now]+mp[now][j]){
                    dis[i][j] = dis[i][now] + mp[now][j];
                }
            }
        }
    }
}
void fun2(int dis[N][N]) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = mp[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) mp[i][j] = 0;
            else mp[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        mp[u][v] = w;
    }
    fun1(dis1);
    fun2(dis2);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis1[i][j] != dis2[i][j])
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

P.S. 第 19 行是函数 fun1() 中的第五个 for 循环。

完善程序

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1005;

int n;
int a[maxn], b[maxn], c[maxn];

bool Comp(const int &x, const int &y) {
    // 你可以简单地认为括号内的内容等价于 (int x, int y)
    return ①;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        int u = c[i];
        if (②) {
            x += b[u];
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) scanf("%d", b + i);
    for (int i = 1; i <= n; ++i) c[i] = i;
    sort(c + 1, c + 1 + n, Comp);
    int ans = 1145141919;
    for (int l=1, r=ans, mid=(l+r)/2; ③; mid=(l+r)/2)
        if (check(mid)) {
            ans = mid;
            ④;
        } else {
            ⑤;
        }
    printf("%d\n", ans);
    return 0;
}

#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    if(m==n) {
        cout<<①<<endl;
        return 0;
    }
    long long M=10000000;
    int ans=②;
    int lst=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j>=0;--j) {
            int lower=max(0,③);
            int upper=i-j;
            int base=④;
            ans+=upper-lower+1;
            if(lower+base<=lst) ans-=lst-(lower+base)+1;
            lst=⑤;
        }
    }
    cout<<ans<<endl;
    return 0;
}

P.S. 第 5 题 D 选项为 base + lower + 1。