小鲸鱼的梦境
0%

CSP202203

发表于 更新于 分类于 Valine：
本文字数： 8.6k 阅读时长 ≈ 8 分钟

前言

CSP 2022-03 算法题解析

未初始化警告

链接：http://118.190.20.162/view.page?gpid=T143

  • 时间限制：1.0s
  • 空间限制：512.0MB

问题解析

很简单的模拟题，注意 \(a_0\) 是常量不需要初始化。

运行结果

提交编号 用户名 姓名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用
* * * 未初始化警告 09-17 19:38 363B CPP14 正确 100 93ms 3.328MB

Cpp代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 100007;
int arr[N];
int k, n;

int main() {
    memset(arr, 0, sizeof(arr));
    arr[0] = 1;
    scanf("%d%d", &n, &k);
    int cnt = 0, x, y;
    for (int i = 0; i < k; ++i) {
        scanf("%d%d", &x, &y);
        if (arr[y] == 0) ++cnt;
        arr[x]++;
    }
    printf("%d", cnt);
    return 0;
}

出行计划

链接：http://118.190.20.162/view.page?gpid=T142

  • 时间限制：1.5s
  • 空间限制：512.0MB

问题解析

很简单，根据出行时间和核酸结果所需时间可以推算出所需核酸时间段，要查询某个时间点在多少个时间段内，只需创建一个差分数组，因为查询是单调递增的所以遍历差分数组维护前缀和即可，更好一点的方法是使用有序结构来作为差分数组代替差分数组。实际上出行时间有没有顺序无所谓，但查询要求是有序的。

运行结果

前面三次错误都是只设置了 1e5 的数组偏移值，实际上范围是 2e5 所以一直报错

第一行是使用有序结构（实质是红黑树）插入总时间是 \(O(n \log n)\) 但查询是 \(O(n)\) 的.

后面四行时间比起前一点的是差分数组，插入时间是 \(O(n)\) 但查询是 \(O(C)\) 的，这里 \(C = 10^6\) (这里稍微设置大了一点，其实 \(5\times 10^5\) 应该也是够用了) .

实质上 \(n\) 和 \(C\) 是一个数量级的所以其实直接用个大一点的数组反而更快

提交编号 用户名 姓名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用
出行计划 09-17 21:05 797B CPP14 正确 100 390ms 8.925MB
* * * 出行计划 09-17 20:56 750B CPP14 正确 100 296ms 6.742MB
* * * 出行计划 09-17 20:53 750B CPP14 运行错误 0 15ms 21.94MB
* * * 出行计划 09-17 20:49 738B CPP14 运行错误 0 15ms 21.94MB
* * * 出行计划 09-17 20:48 738B CPP14 运行错误 0 15ms 41.01MB

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

const int N = 1000007, M = 200007;
int arr[N];
int k, n, m;

/**
 * t 时刻核酸 -> t + k 时刻获取结果 -> [t + k, t + k + c - 1] 可以进入
 * 由此反推想在 t 时刻进入，要求 c 小时内核酸结果，
 * 那么测核酸的时间区间为 [t - k - c + 1, t - k]
 */

int main() {
    memset(arr, 0, sizeof(arr));
    scanf("%d%d%d", &n, &m, &k);
    int t, c;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &t, &c);
        arr[t - k - c + 1 + M]++;
        arr[t - k + 1 + M]--;
    }
    for (int i = 0, cur = 0, acc = 0; i < m; ++i) {
        scanf("%d", &t);
        t += M;
        while (cur <= t) acc += arr[cur++];
        printf("%d\n", acc);
    }
    return 0;
}

使用 有序结构 代替差分数组，看运行时间还慢了 100 ms 主要是因为插入慢了些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

// const int N = 1000007, M = 200007;
map<int, int> arr;
int k, n, m;

/**
 * t 时刻核酸 -> t + k 时刻获取结果 -> [t + k, t + k + c - 1] 可以进入
 * 由此反推想在 t 时刻进入，要求 c 小时内核酸结果，
 * 那么测核酸的时间区间为 [t - k - c + 1, t - k]
 */

int main() {
    scanf("%d%d%d", &n, &m, &k);
    int t, c;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &t, &c);
        arr[t - k - c + 1]++;
        arr[t - k + 1]--;
    }
    auto cur = arr.begin();
    for (int i = 0, acc = 0; i < m; ++i) {
        scanf("%d", &t);
        while (cur != arr.end() && (*cur).first <= t) {
            acc += (*cur).second;
            cur++;
        }
        printf("%d\n", acc);
    }
    return 0;
}

计算资源调度器

链接：http://118.190.20.162/view.page?gpid=T141

  • 时间限制：1.0s
  • 空间限制：512.0MB

问题解析

大模拟题，有空再补上吧

运行结果

提交编号 用户名 姓名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用

代码

通信系统管理

链接：http://118.190.20.162/view.page?gpid=T140

  • 时间限制：2.0s
  • 空间限制：512.0MB

问题解析

开始想的是对每个计算机都用 map 来存

PS: 代码参考了 https://blog.csdn.net/weixin_55004347/article/details/125308816?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-125308816-blog-124601672.t5_refersearch_landing&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-125308816-blog-124601672.t5_refersearch_landing&utm_relevant_index=1

运行结果

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;
#define int long long
#define N 200005
#define Prr pair<int, int>
#define fi first
#define se second
int n, m;
int k[N >> 1], l[N >> 1];
int tot1 = 0, u[N], v[N], x[N], y[N], t[N];
int tot2 = 0, num[N];
bool p[N], q[N];

vector<int> e[N], val[N], M[N];

void init() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> k[i];
        for (int j = 1; j <= k[i]; ++j) {
            ++tot1;
            cin >> u[tot1] >> v[tot1] >> x[tot1] >> y[tot1];
            t[tot1] = i + y[tot1];
            e[u[tot1]].push_back(v[tot1]);
            e[v[tot1]].push_back(u[tot1]);
            val[u[tot1]].push_back(0);
            val[v[tot1]].push_back(0);
        }

        cin >> l[i];
        for (int j = 1; j <= l[i]; ++j) cin >> num[++tot2];

        cin >> p[i] >> q[i];
    }
}

struct cmp1 {
    bool operator()(Prr a, Prr b) {
        return a.se == b.se ? a.fi > b.fi : a.se < b.se;
    }
};

set<Prr, cmp1> Val[N];

int ans[N], cntP = 0, cntQ = 0;
void updPr(int u, int v, int x) {
    if (ans[u] == v && ans[v] == u)
        cntQ += x;
    else {
        if (ans[ans[u]] == u) cntQ += x;
        if (ans[ans[v]] == v) cntQ += x;
    }
}

void mod(int u, int v, int x) {
    int p = lower_bound(e[u].begin(), e[u].end(), v) - e[u].begin();
    Val[u].erase(make_pair(e[u][p], val[u][p]));
    val[u][p] += x;
    if (val[u][p] > 0) Val[u].insert(make_pair(e[u][p], val[u][p]));
    if (!ans[u]) --cntP;
    ans[u] = !Val[u].empty() ? (*Val[u].rbegin()).fi : 0;
    if (!ans[u]) ++cntP;
}

void upd(int tm) {
    for (int i = 0; i < M[tm].size(); ++i) {
        int p = M[tm][i];
        updPr(u[p], v[p], -1);
        mod(u[p], v[p], -x[p]);
        mod(v[p], u[p], -x[p]);
        updPr(u[p], v[p], 1);
    }
}

void solve() {
    for (int i = 1; i <= n; ++i) sort(e[i].begin(), e[i].end());

    cntP = n;
    int pos1 = 0, pos2 = 0;
    for (int i = 1; i <= m; ++i) {
        upd(i);
        for (int j = pos1 + 1; j <= pos1 + k[i]; ++j) {
            updPr(u[j], v[j], -1);
            mod(u[j], v[j], x[j]);
            mod(v[j], u[j], x[j]);
            updPr(u[j], v[j], 1);
            M[t[j]].push_back(j);
        }
        pos1 += k[i];
        for (int j = pos2 + 1; j <= pos2 + l[i]; ++j) {
            cout << ans[num[j]] << endl;
        }
        pos2 += l[i];

        if (p[i]) cout << cntP << endl;
        if (q[i]) cout << cntQ << endl;
    }
}

int main() {
    init();
    solve();
    return 0;
}

博弈论与石子合并

链接：http://118.190.20.162/view.page?gpid=T139

  • 时间限制：1.0s
  • 空间限制：512.0MB

问题解析

参考：https://blog.csdn.net/Wu_L7/article/details/126319300

首先题目不难理解，就是足够聪明的小c要使最后一堆石子数最少，绝顶聪明的小z要使最后一堆石子数最多，两人轮流操作，要么合并，要么扔掉最左边或者最右边。

大家沉浸式想象一下，我们担任小c或者小z中的一员，来体验这个游戏。假设我们就是小z，要尽可能保留最后一堆的石子数最大，但是我们的对手是小c，他不断干扰我们，欲使我们的石子数最少，那我们现在对这个问题的求解就有了新的定义，即要求出最少的最大石子数，最少是前提条件（小c的干扰），最大是我们的任务（小z的任务）。

模拟场景一：我们面前有偶数堆的石子，我们（小z）先操作（k==1），我们肯定会先合并最中间的两堆石子，再静观其变，如果小c扔掉最左边的石子堆，那我们就靠右合并，如果小c扔掉最右边的石子堆，那我们就靠左合并，这样目的是为了时刻保持我们合并的石子堆在最中间，以防被小c扔掉，这样就能保证我们合并的石子数是最大的。如果我们合并的石子堆不是在最中间，就算合并的数量再多，最后还是会被小c扔掉，到头来白打工了。当然，足够聪明的小c也知道你会这么做，他也会控制着自己每次扔掉的是最左边还是最右边，以此来使得你最后合并的数量最小，以此来转化成求解问题，即最小的相邻数段和（因为每次合并都要求是相邻的）。同理，当面对奇数堆的石子，小c先操作（k==0）时，我们已经处在一个最中间的状态，小c扔左，我们合并右，小c扔右，我们合并左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int func1(int n)
{
    int ans=0, mid=n/2+1;
    for(int i=1; i<=mid; i++)//最开始的数段和 
    {
        ans=ans+arr[i];
    }
    int temp=ans;
    for(int i=mid+1; i<=n; i++) 
    {
        temp=temp+arr[i]-arr[i-mid];
        ans=min(ans, temp);//不断往后，不断比较迭代，选出最小的 
    }
    return ans;
}

模拟场景二：当我们面对奇数堆的石子，我们（小z）先操作（k==1）或者我们面对偶数堆的石子，小c先操作（k==0）时，即轮到我们（小z）操作的时候，我们面对的永远是奇数堆（因为小c不管是合并还是扔掉，都会是总数减1），我们本已处在最中间最安全的位置，由于我们的操作，会使合并的石子堆位于偏左或偏右的状态，这对于我们来说就是不安全、危险的位置，因为一旦小c发觉你合并的数量多的时候，他就想方设法把你合并的石子堆扔掉。因为你无论怎么合并，小c总有办法把你合并的给扔掉，这样就不能保证合并的石子堆最大并且保留到最后。那怎样才能使得最后的石子堆最大呢？我们知道，当我们面对这种场景二时，小c的操作步数是n/2，即小c只能合并或者扔掉（n/2）次。如果这些个石子堆中有大于（n/2）个x，则小c无论怎样都不能扔完（就算他先合并再扔也相当于操作两次扔两堆），此时能保留到最后一堆的石子数至少有x，所以我们场景二的任务就是要找到最大的那个x，即刚好能满足大于（n/2）的x（刚好等于（n/2）不行，这样会刚好被扔掉）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
bool check(int x, int n)//x的判断
{
    int sum=0, num=0;
    for(int i=1; i<=n; i++)
    {
        sum=sum+arr[i];
        if(sum>=x)
        {
            sum=0;
            num++;
        }
    }
    return num>n/2;//当个数大于n/2时，小c才不会扔完，因为小c只能操作n/2次 
} 
int func2(int n)
{
    int r=1e9, mid=r/2;
    int ans=0;
    while(mid<=r)//用二分法不断逼近刚好能达到check条件的x
    {
        if(check(mid, n))
        {
            ans=mid;
            if(mid==r)return ans;//如果相等且满足，说明最大值r（mid）就是ans
            mid=(mid+1+r)/2;
        }
        else 
        {
            if(mid==r)break;//如果相等且不满足，说明ans就是上一次的mid，直接退出 
            r=mid-1;
            mid=r/2;
        }
    }
    return ans;
}

运行结果

提交编号 用户名 姓名 试题名称 提交时间 代码长度 编程语言 评测结果 得分 时间使用 空间使用

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
using namespace std;
int arr[100001]={0};
int func1(int n)
{
    int ans=0, mid=n/2+1;
    for(int i=1; i<=mid; i++)//最开始的数段和 
    {
        ans=ans+arr[i];
    }
    int temp=ans;
    for(int i=mid+1; i<=n; i++) 
    {
        temp=temp+arr[i]-arr[i-mid];
        ans=min(ans, temp);//不断往后，不断比较迭代，选出最小的 
    }
    return ans;
}
bool check(int x, int n)//x的判断
{
    int sum=0, num=0;
    for(int i=1; i<=n; i++)
    {
        sum=sum+arr[i];
        if(sum>=x)
        {
            sum=0;
            num++;
        }
    }
    return num>n/2;//当个数大于n/2时，小c才不会扔完，因为小c只能操作n/2次 
} 
int func2(int n)
{
    int r=1e9, mid=r/2;
    int ans=0;
    while(mid<=r)//用二分法不断逼近刚好能达到check条件的x
    {
        if(check(mid, n))
        {
            ans=mid;
            if(mid==r)return ans;//如果相等且满足，说明最大值r（mid）就是ans 
            mid=(mid+1+r)/2;
        }
        else 
        {
            if(mid==r)break;//如果相等且不满足，说明ans就是上一次的mid，直接退出 
            r=mid-1;
            mid=r/2;
        }
    }
    return ans;
}
int main() 
{
    int n=0, k=0;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) 
    {
        scanf("%d", &arr[i]);
    }
    int ans=0;
    if(((n%2==0)&&k==1)||(n%2==1)&&k==0)ans=func1(n);//小z面对偶数局面 
    else ans=func2(n);//小z面对奇数局面 
    printf("%d", ans);
    return 0;
}
--- ♥ end ♥ ---

欢迎关注我呀~