第33次CCF计算机软件能力认证

(第一题)词频统计

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

const int N = 1e2 + 10;

int n, m;
int x[N], y[N];
bool st[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int len;
        cin >> len;
        memset(st, 0, sizeof st);
        for(int j = 1; j <= len; j++)
        {
            int ch;
            cin >> ch;
            x[ch] += !st[ch];
            y[ch]++;
            st[ch] = true;
        }
    }

    for(int i = 1; i <= m; i++) cout << x[i] << ' ' << y[i] << endl;
}

(第二题)相似度计算

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>

using namespace std;

typedef long long ll;

const int N = 1e2 + 10;

int n, m;
set<string> A;
set<string> X;//并集
set<string> Y;//交集

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        transform(str.begin(), str.end(), str.begin(), ::tolower);
        A.insert(str);
        X.insert(str);
    }

    for(int i = 1; i <= m; i++)
    {
        string str;
        cin >> str;
        transform(str.begin(), str.end(), str.begin(), ::tolower);
        X.insert(str);
        if(A.count(str)) Y.insert(str);
    }
    cout << Y.size() << endl << X.size() << endl;
}

(第三题)化学方程式配平

参考题解：CCF-CSP认证考试 202403-3 化学方程式配平 100分题解_ccfc化学-CSDN博客

#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;

const int N = 110;
const double eps = 1e-8;

int n;
double a[N][N];

int gauss(int n, int m)
{
//    for(int i = 0; i < n; i++)
//    {
//        for(int j = 0; j < m; j++) cout << a[i][j] << ' ';
//        cout << endl;
//    }
//    cout << endl;

    int c, r;
    for (c = 0, r = 0; c < m; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )  // 找绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i < m; i ++ ) swap(a[t][i], a[r][i]);  // 将绝对值最大的行换到最顶端
        for (int i = m - 1; i >= c; i -- ) a[r][i] /= a[r][c];  // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = m - 1; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < m) return 1; // 有无穷多组解
    else return 0;
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int len;
        cin >> len;
        memset(a, 0, sizeof a);
        map<string, int> mp;//存储某个元素的行号,比如(al,0),(o,1)
        int cnt = -1;
        for (int j = 0; j < len; j++) {//遍历第j个化学式,将对应元素的原子个数存储在第j列
            string str;
            cin >> str;
            for(int pre = 0, post = 0; str[post] != '\0'; pre = post)
            {
                while (str[post] >= 'a' && str[post] <= 'z') post++;
                string x = str.substr(pre, post - pre);
                if(!mp.count(x)) mp.insert({x, ++cnt});

                pre = post;
                while (str[post] !='\0' && str[post] >= '0' && str[post] <= '9') post++;
                int num = stoi(str.substr(pre, post - pre));
//                cout << x << ' ' << num << endl;
                int row = mp[x];
                a[row][j] = num;
            }
        }
        cout << ((gauss(cnt + 1 ,len) == 1) ? "Y" : "N") << endl;
    }
}

(第四题)十滴水

参考题解：CCF-CSP认证考试 202403-4 十滴水 100分题解_十滴水小游戏-CSDN博客

#pragma GCC optimize(2, 3, "Ofast", "inline")//开启优化
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

map<int, int> mp;//mp[i] = j,表示第i个格子的水滴数为j
priority_queue<int, vector<int>, greater<int>> pq;//小根堆,存储水滴数 >=5 的格子编号,编号越小的靠前

int main()
{
    //必须进行读写优化才能AC
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int c, m, n;
    cin >> c >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        int pos, w;
        cin >> pos >> w;
        mp[pos] = w;
    }


    while (n--)
    {
        int pos;
        cin >> pos;

        mp[pos]++;
        if(mp[pos] == 5) pq.push(pos);//只有在水滴数等于5的瞬时时刻才能放入小根堆,若将条件更改为mp[pos] >= 5,格子编号可能会重复入队,进行多次处理

        //必须将水滴数大于等于5的格子处理完才能进一步处理
        while(!pq.empty())
        {
            int t = pq.top();
            pq.pop();
            mp.erase(t);

            auto pre= mp.lower_bound(t);
            if(pre != mp.begin())
            {
                pre--;
                pre->second++;
                if(pre->second == 5) pq.push(pre->first);
            }

            auto post = mp.upper_bound(t);
            if(post != mp.end())
            {
                post->second++;
                if(post->second == 5) pq.push(post->first);
            }
        }
        cout << mp.size() << endl;
    }
}