小花生

study & life record.

第33次CCF_CSP认证

发表于 分类于 ，

2024年3月CSP，回顾+题解。

第一次参加CSP，同时也是第一次参与真正上机的算法竞赛，得分 385/500 ，有经验也有教训，故有此文浅做总结。

前置工作

首先要了解CSP支持的c++版本，考场上因为没有提前了解版本以及devcpp配置问题，导致手写iterator，浪费了很多时间和思路。

在devcpp中加入如下命令后，可使用c++14环境语法。

考试开始前可以在编辑器中提前打入模板，这样创建新项目时可以直接在模板基础上进行编程。

还有devcpp的美化问题，浅浅配置一下颜色，避免影响敲代码的心情（bushi

题解

词频统计

考点：计数

完整代码：

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
#include<bits/stdc++.h>
using namespace std;

const int N = 105;
int x[N], y[N];
bool vis[N];

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int n = read(), m = read();
    
    for(int i = 1; i <= n; i++){
        memset(vis, 0, sizeof vis);
        int l = read();
        while(l--){
            int t = read();
            if(!vis[t])
                vis[t] = true, x[t]++;
            y[t]++;
        }
    }	
    
    for(int i = 1; i <= m; i++)
        cout << x[i] << ' ' << y[i] << '\n';
        
    return 0;
}

相似度计算

考点：字符大小写转换，集合

题目本身比较简单，这里给出一个有趣的大小写转换方法。观察ASCII码，不难发现，小写字母与其对应的大写字母ASCII之差恰好为32，是space的ASCII值，故：

  • 若想将字符c统一为小写：c |= ' '
  • 若想将字符c统一为大写：c &= ~' '
  • 若想将字符c小写转大写，大写转小写：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
#include<bits/stdc++.h>
using namespace std;

set<string> A, B;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main(){
    int n = read(), m = read();
    while(n--){
        string s; cin >> s;
        for(int i = 0;i < s.size(); i++) s[i] |= ' ';
        A.insert(s);
    }
    while(m--){
        string s; cin >> s;
        for(int i = 0;i < s.size(); i++) s[i] |= ' ';
        B.insert(s);
    }
    
    int same = 0;
    for(auto &v : B)
        if(A.find(v) != A.end()) same++;
    
    cout << same << '\n' << A.size() + B.size() - same;
    
    return 0;
}

化学方程式配平

考点：字符串处理，高斯消元

在处理高斯消元时，为避免浮点数的出现，这里采用了求lcm后，作线性组合行变换的方式。

（当然题目的数据范围应该也允许直接用两数乘积代替lcm）

完整代码：

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
#include<bits/stdc++.h>
using namespace std;

const int N = 50;
int matrix[N][N];

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

int Rank(int x1, int y1, int x2, int y2){
    if(x1 > x2 || y1 > y2) return 0;
    
    int flag = 0;
    for(int i = x1; i <= x2; i++){
        if(matrix[i][y1]) {
            flag = i;
            break;
        }
    }
    
    if(!flag) return Rank(x1, y1 + 1, x2, y2);
    swap(matrix[x1], matrix[flag]);
    
    for(int i = x1 + 1; i <= x2; i++){
        if(matrix[i][y1] == 0) continue;
        int LCM = lcm(matrix[x1][y1], matrix[i][y1]);
        int t1 = LCM / matrix[i][y1], t2 = LCM / matrix[x1][y1];
        for(int j = y1; j <= y2; j++)
            matrix[i][j] = matrix[i][j] * t1 - matrix[x1][j] * t2;
    }
        
    return Rank(x1 + 1, y1 + 1, x2, y2) + 1;
}

void solve() {
    memset(matrix, 0, sizeof matrix);

    map<string, int> mp;
    int m = read();
    int r = 0, c = 1; // 记录行列 

    char ch; int num = 0; string ele;
    while (ch = getchar()) {
        if (num && (ch < '0' || ch > '9')) {
            if (!mp[ele]) mp[ele] = ++r;
            matrix[mp[ele]][c] = num;
            ele = "", num = 0;
        
            if (ch == '\n' || ch == EOF) break;
            if (ch == ' ') {
                c++;
                continue;
            }
        }

        if (ch >= '0' && ch <= '9')
            num = num * 10 + ch - 48;
        else if (ch >= 'a' && ch <= 'z')
            ele += ch;
    }

    if(Rank(1, 1, r, c) == c) cout << 'N' << '\n';
    else cout << 'Y' << '\n';

}

int main(){
    int n = read();
    while(n--) solve();
    return 0;
}

十滴水

考点：离散化 + 双向链表

分析：需要一个能快速锁定前驱和后继，并且支持删除操作的数据结构，故用双向链表模拟题意即可。

完整代码：

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 3e5 + 10;
vector<int> alls;
vector<PII> storage;
int l[N], r[N], v[N];
priority_queue<int, vector<int>, greater<int>> q;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int to_find(int x) {
    return lower_bound(alls.begin(), alls.nd(), x) - alls.begin() + 1;
}

int main() {
    int c = read(), m = read(), n = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), w = read();
        alls.emplace_back(x);
        storage.emplace_back(x, w);
    }

    sort(alls.begin(), alls.end());
    // 由于不会出现重复位置，就不去重了

    for (auto& u : storage)
        v[to_find(u.first)] = u.second;

    for (int i = 1; i <= m; i++)
        l[i] = i - 1, r[i] = i + 1;
    v[0] = v[m + 1] = 666;

    while (n--) {
        int p = to_find(read());
        v[p]++;
        if (v[p] == 5) q.emplace(p);
        while (!q.empty()) {
            int u = q.top(); q.pop();
            r[l[u]] = r[u];
            l[r[u]] = l[u];
            m--;
            v[l[u]]++, v[r[u]]++;
            if (v[l[u]] == 5) q.emplace(l[u]);
            if (v[r[u]] == 5) q.emplace(r[u]);
        }
        cout << m << '\n';
    }

    return 0;
}

文件夹合并

暂时不会，以后上传，咕咕~

成绩