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

(第一题)仓库规划

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n, m;

int main()
{
    cin >> n >> m;
    vector<vector<int>> w(n, vector<int>(m));

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> w[i][j];

    for(int i = 0; i < n; i++)
    {
        bool findParent = false;
        int parent = i;
        for(int j = 0; j < n; j++)
        {
            if(i == j) continue;
            bool flag = true;
            for(int k = 0; k < m; k++)
                if(w[parent][k] >= w[j][k])
                {
                    flag = false;
                    break;
                }
            if(flag)
            {
                parent = j;
                findParent = true;
                break;
            }
        }
        cout << (findParent ? parent + 1 : 0) << endl;
    }
}

(第二题)因子化简

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

ll q, n, k;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

int main()
{
    cin >> q;
    while(q--)
    {
        cin >> n >> k;
        ll res = 1;
        for(ll i = 2; i <= n / i; i++)
        {
            if(n % i == 0)
            {
                int t = 0;
                while(n % i == 0) n /= i, t++;
                if(t >= k) res *= qmi(i, t);
            }
        }
        if(n > 1 && k <= 1) res *= n;
        cout << res << endl;
    }
}

(第三题)树上搜索

参考题解：202312-3 csp树上搜索_ccfcsp树上搜索样例-CSDN博客

#pragma GCC optimize(2, 3, "Ofast", "inline")

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

int n, m;

const int N = 2e3 + 10;
int h[N], e[N], ne[N], idx;
ll w[N], sum[N];
set<int> seg;// 递归计算子树权重时,遍历没有删除的结点,将其加入到seg集合中
bool st[N]; // 根结点编号为i的子树是否被删除,true表示已被删除

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void computeDfs(int u)
{
    sum[u] = w[u];
    seg.insert(u);
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            computeDfs(j);
            sum[u] += sum[j];
        }
    }
}

bool checkParent(int parent, int son)
{
    if(parent == son) return true;
    bool flag = false;
    for (int i = h[parent]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) flag |= checkParent(j, son);
        if(flag) break;
    }
    return flag;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(h, -1, sizeof h);
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        add(x, i);
    }

    while (m--)
    {
        memset(st, 0, sizeof st);
        int x;
        cin >> x;

        int root = 1;
        while (true)
        {
            memset(sum, 0, sizeof sum);
            seg.clear();
            computeDfs(root);
            if(seg.size() == 1) break;//只有一个类别就退出循环
            ll minValue = LONG_LONG_MAX;
            int minNum = -1;
            for(auto x : seg){
                ll temp = abs(sum[root] - 2 * sum[x]);
                if (temp < minValue) minValue = temp, minNum = x;
            }

            cout << minNum << ' ';
            if (checkParent(minNum, x)) root = minNum;
            else st[minNum] = true;
        }
        cout << endl;
    }
}