第31次CCF计算机软件能力认证-Toy模板网

这篇具有很好参考价值的文章主要介绍了第31次CCF计算机软件能力认证。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

100+100+100+100+60=460

坐标变换 (其一)

题目大意

给定\(n\)个操作，每个操作将坐标 \((x,y)\)变为 \((x + dx, y + dy)\)。

给定 \(m\)个点，问这 \(m\)个点经过这 \(n\)次操作变换后的坐标。

解题思路

注意到操作是可合并的，因此可以先将这\(n\)个操作合并成一个操作，然后对每个点都经过这个操作变换即可，时间复杂度为 \(O(n + m)\)。

本题 \(n,m\)只有 \(100\)，也可以 \(O(nm)\)依次对每个点进行操作变换。

神奇的代码

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int dx = 0, dy = 0;
    for(int i = 0; i < n; ++ i){
        int x, y;
        cin >> x >> y;
        dx += x;
        dy += y;
    }
    for(int i = 0; i < m; ++ i){
        int x, y;
        cin >> x >> y;
        cout << x + dx << ' ' << y + dy << '\n';
    }
    return 0;
}

坐标变换(其二)

题目大意

给定\(n\)个操作，操作分两类，一类将\((x, y)\)变为 \((kx, ky)\)，一类进行坐标旋转，并贴心地给出了旋转公式。

给定 \(m\)个点，问这 \(m\)个点经过第\(l\)次到第\(r\)次操作变换后的坐标。

解题思路

直接模拟的\(O(nm)\)可以拿 \(80\)分。

考虑操作合并，因为在第二类操作里，两维会相互影响，不能像第一题单纯的合并，但由于是线形的，可以写成一个矩阵乘法的方式，因此可以写成矩阵乘法的形式，用线段树维护区间乘，当然也可以分块维护区间操作，但想到第二题应该不会有这么复杂的写法，于是赶紧冷静下来想想有什么其他的写法。

注意到一个操作是改变与原点的距离，一个操作是改变与\(x\)轴所夹成的角度，如果考虑坐标在极坐标系下的表示形式，会发现这两种操作只是分别对其中一维进行操作，且这些操作是可逆的，且不会相互影响。

因此我们就预处理出 \(op[i]\)表示操作 \(1..i\)对距离 \(r\)和角度 \(\theta\)的影响，这是一个前缀和数组。

然后对于一个点问经过操作 \(l..r\)的结果，先对它施加\(1..r\)操作的影响，再消除 \(1..l-1\)操作的影响，即可得到 \(l..r\)操作的结果。

施加影响，就是长度 \(\times k\)，角度 \(+ \theta\)，消除影响，就是长度 \(/ k\)，角度 \(- \theta\)。

最后根据\(r\)和 \(\theta\)还原出\(x = r\cos \theta, y = r\sin \theta\)。

时间复杂度为 \(O(n + m)\)。

神奇的代码

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

const double pi = acos(-1);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<array<double, 2>> op(n);
    for(auto &i : op){
        int opp;
        double k;
        cin >> opp >> k;
        if (opp == 1)
            i[0] = k;
        else{
            i[0] = 1;
            i[1] = k;
        }
    }
    for(int i = 1; i < n; ++ i){
        op[i][0] *= op[i - 1][0];
        op[i][1] += op[i - 1][1];
    }
    for(int i = 0; i < m; ++ i){
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        -- l, -- r;
        double R = sqrt(1ll * x * x + 1ll * y * y), theta = 0;
        if (x == 0){
            if (y > 0)
                theta = pi / 2;
            else 
                theta = -pi / 2;
        }else{
            theta = atan2(y, x);
        }
        R *= op[r][0];
        theta += op[r][1];
        if (l){
            R /= op[l - 1][0];
            theta -= op[l - 1][1];
        }
        cout << fixed << setprecision(10) << R * cos(theta) << ' ' << R * sin(theta) << '\n';
    }
    return 0;
}

梯度求解

题目大意

给定一个仅包含\(+-*\)运算的多元函数，求关于 \(x_i\)在点 \((a_1,a_2,...)\)处的偏导值。

函数以逆波兰形式给出。

解题思路

感觉有意思的题，没接触过，琢磨了许久。

首先我们不能以人的方式考虑对\((x^3)^\prime = 3x^2\)这样的形式的求导，而是像例子给看成的\(x_1 \cdot x_1 \cdot x_1\)用乘法求导的式子计算。这样每个的原子项都是形如 \(x_i\)或者常数这样最简形式。虽然可能计算不如上述的简单，但毕竟是机器算，数据范围也比较小，就尽可能简单一点。

不合并同类项后，考虑对这个表达式的求导，我们尽可能要找一个可以递归的结构进行求导，这个结构其实跟表达式计算是一样的。

通过逆波兰表达式建立这个表达式树，如下图所示，题面也贴心地指出了逆波兰表达式就是这棵树的后序遍历。

树就是一棵有递归结构的表示形式，我们要求整棵树的偏导值，先看根节点的运算符，比如是乘号，由于\((uv)^\prime = u^\prime v + uv^\prime\)，那我们需要求左子树的函数值和偏导值，右子树的函数值和偏导值，然后根据上述求导的式子计算得到当前子树的函数值和偏导值。而求左右子树的函数值和偏导值实际上就是一个子问题，因此就可以递归下去了。如果是加法的话就是偏导值相加。

边界情况就是当前节点是常数或者变量时，根据求导式子可以直接得到函数值和偏导值。

其实最后发现和表达式计算没什么区别。时间复杂度为\(O(nm)\)。

注意减法不满足交换律，在建立表达式树时不要搞错运算符左右两个值的顺序。

考场上模数习惯性写成\(998244353\)找了好久的错误。

神奇的代码

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

const int mo = 1e9+7;
#define CONST -1
#define VAR -2
#define OP -3

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    int n, m;
    cin >> n >> m;
    getline(cin, s); // '\n'
    getline(cin, s);
    istringstream qwq(s);
    vector<int> l;
    vector<int> r;
    vector<int> info;
    vector<int> kind;
    stack<int> id;
    int node_id = 0;
    while(getline(qwq, s, ' ')){
        if (s.size() == 1 && (s[0] == '+' || s[0] == '*' || s[0] == '-')){
            int rson = id.top();
            id.pop();
            int lson = id.top();
            id.pop();
            l.push_back(lson);
            r.push_back(rson);
            info.push_back(s[0]);
            kind.push_back(OP);

            id.push(node_id);
            ++ node_id;
        }else if (s[0] == 'x'){
            int x = stoi(s.substr(1));
            -- x;
            l.push_back(-1);
            r.push_back(-1);
            info.push_back(x);
            kind.push_back(VAR);

            id.push(node_id);
            ++ node_id;
        }else{
            int x = stoi(s);
            l.push_back(-1);
            r.push_back(-1);
            info.push_back(x);
            kind.push_back(CONST);

            id.push(node_id);
            ++ node_id;
        }
    }
    int root = id.top();
    vector<int> a(n);

    function<array<int, 2>(int, int)> solve = [&](int u, int x){
        if (kind[u] == VAR){
            return array<int, 2>{a[info[u]], (info[u] == x)};
        }else if (kind[u] == CONST){
            return array<int, 2>{info[u], 0};
        }else{
            auto lans = solve(l[u], x), rans = solve(r[u], x);
            int sum = 0, dsum = 0;
            if (info[u] == '+'){
                sum = lans[0] + rans[0];
                dsum = lans[1] + rans[1];
                if (sum >= mo)  sum -= mo;
                if (dsum >= mo) dsum -= mo;
            }else if (info[u] == '-'){
                sum = lans[0] - rans[0];
                dsum = lans[1] - rans[1];
                if (sum >= mo)  sum -= mo;
                if (dsum >= mo) dsum -= mo;
            }else{
                sum = 1ll * lans[0] * rans[0] % mo;
                dsum = (1ll * lans[0] * rans[1] % mo + 1ll * lans[1] * rans[0] % mo);
                if (dsum >= mo) dsum -= mo;
            }
            if (sum < 0)
                sum += mo;
            if (dsum < 0)
                dsum += mo;
            return array<int, 2>{sum, dsum};
        }
    };
    for(int i = 0; i < m; ++ i){
        int x;
        cin >> x;
        -- x;
        for(auto &i : a)
            cin >> i;
        cout << solve(root, x)[1] << '\n';
    }
    return 0;
}

阴阳龙

题目大意

二维平面\(n \times m\)，有\(p\)个人，位于不同坐标。

有 \(q\)次事件\((x,y,t)\)发生，每次事件，在\((x,y)\)上会有阴阳龙出现，从该位置的周围的8个方向中，找到切比雪夫距离最小的那些人，它们的位置将进行 \(t\)倍的 \(\frac{1}{8}\)圆的逆时针旋转。注意如果这个最小距离大于该位置\((x,y)\)到边界的切比雪夫距离，则无事发生（因为旋转的话可能会飞到区域外了）。没有人也无事发生。

问这 \(m\)次事件后，所有人的坐标。

解题思路

考虑暴力，对于某个事件，从\((x,y)\)依次往 \(8\)个方向递增，直到碰到人后，暴力旋转。时间复杂度为 \(O(max(n,m)q)\)。

注意到人的坐标互不相同，那么每个事件最多只会更改\(8\)个人的坐标，如果我们能快速找到这 \(8\)个人，复杂度就是 \(O(8q)\)。

考虑如何快速找到，对于同一行的人中，我们用set储存它们的列坐标，这样通过\(lower\_bound\)就可以在\(O(\log)\)的事件内找到 \((x,y)\) 最小的大于\(y\)和最大的小于 \(y\)的人，作为候选者。

同理对于同一列，同一对角线都这么找。同一行的人，它们的 \(x\)相同。同一列的人，它们的 \(y\)相同。同一对角线的人，它们的 \(x+y\)或 \(x-y\)是相同的。

因此就开\(row[x], col[y], ld[x + y], rd[x - y]\)表示第\(x\)行的所有人的 \(y\)集合，第 \(y\)列的所有人的 \(x\)集合，左上\(\to\)右下的对角线满足 \(x+y\)的所有人的\(y\)集合，以及左下\(\to\)右上的对角线满足 \(x-y\)的所有人的 \(y\)集合。

对于当前的阴阳龙位置 \((x,y)\)，分别花\(O(\log)\) 时间找到八个方向的最近的候选人，然后根据距离排个序，得到最近的那些人，再进行题意所述的坐标变换即可。

时间复杂度是\(O(q\log p)\)

神奇的代码

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

const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    vector<array<int, 2>> pos(p);
    unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
    auto insert = [&](int id){
        int x = pos[id][0], y = pos[id][1];
        row[x].insert({y, id});
        col[y].insert({x, id});
        ld[x + y].insert({y, id});
        rd[x - y].insert({y, id});
    };
    auto remove = [&](int id){
        int x = pos[id][0], y = pos[id][1];
        row[x].erase({y, id});
        col[y].erase({x, id});
        ld[x + y].erase({y, id});
        rd[x - y].erase({y, id});
    };
    for(int i = 0; i < p; ++ i){
        cin >> pos[i][0] >> pos[i][1];
        insert(i);
    }
    for(int i = 0; i < q; ++ i){
        int u, v, t;
        cin >> u >> v >> t;
        vector<array<int, 3>> candidate;

        auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
            auto pos = people.lower_bound(array<int, 2>{d, p});
            if (pos != people.end()){
                candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
            }
            if (pos != people.begin()){
                pos = prev(pos);
                if ((*pos)[0] == d && pos != people.begin())
                    pos = prev(pos);

                if ((*pos)[0] != d){
                    candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
                }
            }
        };

        search(row[u], v, 2, 6);
        search(col[v], u, 0, 4);
        search(ld[u + v], v, 3, 7);
        search(rd[u - v], v, 1, 5);

        if (candidate.empty())
            continue;
        sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
            return a[0] < b[0];
        });
        int mindis = min({u - 1, n - u, v - 1, m - v});
        if (candidate[0][0] > mindis)
            continue;
        mindis = candidate[0][0];
        for(int i = 0; i < candidate.size(); ++ i){
            if (candidate[i][0] != mindis)
                break;
            int dis = candidate[i][0];
            int id = candidate[i][1];
            remove(id);
            int dir = (candidate[i][2] + t) % 8;
            pos[id][0] = u + dis * dx[dir];
            pos[id][1] = v + dis * dy[dir];
            insert(id);
        }
    }
    LL ans = 0;
    for(int i = 0; i < p; ++ i){
        ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
    }
    cout << ans << '\n';
    return 0;
}

阻击

题目大意

给定一棵树，边有边权，\(m\)次修改，每次修改一个边权。

问每次修改后树的直径长度。

性质A，一个链。
性质B，边权非负。
性质C，任意两点的路径边数不超过\(100\)。

解题思路

树的直径经典求法就是\(O(n)\)的两次 \(BFS\)或\(DFS\)，但有个前提是边权必须非负。而本题并不保证这一性质，只有数据里的性质B有这个特征。

尽管如此，注意到树的递归特性，直径要么在某个子树里，要么横跨了根节点，而后者是两条到根节点最长的路径拼接起来的。这非常类似分治的想法。

设\(maxd[u]\)表示在\(u\)的子树中到节点\(i\)的最长距离，在分治求解过程中，先求其儿子子树\(v\)的答案，然后求最大值\(max(maxd[u] + maxd[v] + d[u][v])\)，同时更新\(maxd[u]\)的值。

这样同样\(O(n)\)就可以得出直径长度。

时间复杂度是 \(O(nm)\)，有 \(48\)分。

考虑性质 \(A\)的链的做法，就是问一个区间的最大子区间和。这是一个经典问题，同样考虑分治，从中间切开后，答案要么在左右子区间里，要么横跨左右子区间，前者递归求解，后者则是从中间往左右延伸的最大和，这个 \(O(n)\)就能求解。

考虑实时维护信息，注意到这些信息是可合并的，也即一个大区间的答案可以由两个小区间的信息合并得到，因此我们用线段树维护这些区间，维护的信息包括：

区间答案
区间和
前缀最大值
后缀最大值

这样就可以得到大区间的这四个信息，就可以实时维护答案了。每次修改重新求答案的复杂度是 \(O(\log n)\)。总的时间复杂度是 \(O(m\log n)\)。这有\(12\)分。

到这里就\(60\)分了。

考虑性质 \(C\)，还是考虑上述树形态的做法，在边权修改时如何实时维护需要的信息。注意到合并答案时是根据子树的答案和子树的\(maxd\)进行的，我们需要实时维护这些值，当一条边权修改时，从这条边的点一路往父亲方向走的所有点的信息都会改变，由于性质\(C\)，这样的点最多 \(100\)个。因此每次修改重新求答案的时间复杂度是 \(O(100)\)，总的时间复杂度是 \(O(100m \log n)\)，这里的\(\log\)是要维护子树的 \(maxd\)的最大的两个值。时间上是能通过，但一直 \(WA\)，没找到原因，没拿到这\(12\)分。

至于性质 \(B\)，没想到有什么用。

至于正解，不会，只会对着性质拿分了。文章来源地址https://www.toymoban.com/news/detail-710103.html

神奇的代码

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

const int N = 1e5 + 8;

class segment{
    #define lson root << 1
    #define rson root << 1 | 1
    LL ans[N << 2];
    LL lsum[N << 2];
    LL rsum[N << 2];
    LL sum[N << 2];

    public:
    void popup(int root){
        ans[root] = max({ans[lson], ans[rson], rsum[lson] + lsum[rson]});
        lsum[root] = max(lsum[lson], sum[lson] + lsum[rson]);
        rsum[root] = max(rsum[rson], sum[rson] + rsum[lson]);
        sum[root] = sum[lson] + sum[rson];
    }

    void build(int root, int l, int r, vector<int>& a){
        if (l == r){
            ans[root] = (a[l] >= 0 ? a[l] : 0);
            lsum[root] = (a[l] >= 0 ? a[l] : 0);
            rsum[root] = (a[l] >= 0 ? a[l] : 0);
            sum[root] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, a);
        build(rson, mid + 1, r, a);
        popup(root);
    }

    void update(int root, int l, int r, int pos, int val){
        if (l == r){
            ans[root] = (val >= 0 ? val : 0);
            lsum[root] = (val >= 0 ? val : 0);
            rsum[root] = (val >= 0 ? val : 0);
            sum[root] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else 
            update(rson, mid + 1, r, pos, val);
        popup(root);
    }

    LL query(int root){
        return ans[root];
    }
}seg;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n);
    vector<array<int, 4>> edge;
    for(int i = 1; i < n; ++ i){    
        int u, v, w, b;
        cin >> u >> v >> w >> b;
        -- u, -- v;
        G[u].push_back(edge.size());
        G[v].push_back(edge.size());
        edge.push_back({u, v, w, b});
    }
    vector<LL> maxd(n, 0);
    LL ans = 0;
    function<void(int, int)> dfs = [&](int u, int fa){
        for(auto &i : G[u]){
            int v = edge[i][0] ^ edge[i][1] ^ u;
            if (v == fa)
                continue;
            int d = edge[i][3] - edge[i][2];
            dfs(v, u);
            ans = max(ans, maxd[u] + maxd[v] + d);
            maxd[u] = max(maxd[u], maxd[v] + d);
        }
    };
    dfs(1, 1);
    cout << ans << '\n';
    if (m < 100000){
        for(int i = 1; i <= m; ++ i){
            int x, y;
            cin >> x >> y;
            -- x;
            edge[x][2] = y;
            ans = 0;
            fill(maxd.begin(), maxd.end(), 0);
            dfs(1, 1);
            cout << ans << '\n';
        }
    }else{
        int ok1 = true;
        for(int i = 0; i < n - 1; ++ i){
            ok1 &= (edge[i][0] == i && edge[i][1] == i + 1);
        }
        if (ok1){
            // A
            vector<int> a(n);
            for(int i = 1; i < n; ++ i){
                a[i] = edge[i - 1][3] - edge[i - 1][2];
            }
            seg.build(1, 1, n - 1, a);
            for(int i = 1; i <= m; ++ i){
                int x, y;
                cin >> x >> y;
                -- x;
                edge[x][2] = y;
                seg.update(1, 1, n - 1, x + 1, edge[x][3] - edge[x][2]);
                cout << seg.query(1) << '\n';
            }
        }else{
            // C
            vector<set<array<LL, 2>>> anss(n), maxs(n);
            vector<unordered_map<int, LL>> anss_id(n), maxs_id(n);
            vector<int> deep(n), f(n);
            function<void(int, int)> dfs2 = [&](int u, int fa){
                f[u] = fa;
                int leave = true;
                for(auto &i : G[u]){
                    int v = edge[i][0] ^ edge[i][1] ^ u;
                    if (v == fa)
                        continue; 
                    leave = false;
                    deep[v] = deep[u] + 1;
                    dfs2(v, u); 
                    int d = edge[i][3] - edge[i][2];

                    LL ans_val = (*anss[v].rbegin())[0];
                    anss[u].insert({ans_val, v});
                    anss_id[u][v] = ans_val;


                    LL maxs_val = (*maxs[v].rbegin())[0] + d;
                    maxs[u].insert({maxs_val, v});
                    maxs_id[u][v] = maxs_val;
                }             
                anss[u].insert({0, -1});
                maxs[u].insert({0, -1});

                if (maxs[u].size() > 1){
                    auto c1 = maxs[u].rbegin();
                    auto c2 = next(c1);
                    anss[u].insert({(*c1)[0] + (*c2)[0], -2});
                    anss_id[u][-2] = (*c1)[0] + (*c2)[0];
                }
            };
            dfs2(0, -1);
            for(int i = 0; i < m; ++ i){
                int x, y;
                cin >> x >> y;
                -- x;
                edge[x][2] = y;
                int d = edge[x][3] - edge[x][2];
                ans = 0;
                int cur = (deep[edge[x][0]] < deep[edge[x][1]] ? edge[x][0] : edge[x][1]);
                int son = cur ^ edge[x][0] ^ edge[x][1];
                while(cur != -1){
                    maxs[cur].erase({maxs_id[cur][son], son});
                    maxs_id[cur][son] = (*maxs[son].rbegin())[0] + d;
                    maxs[cur].insert({maxs_id[cur][son], son});

                    anss[cur].erase({anss_id[cur][son], son});
                    anss_id[cur][son] = (*anss[son].rbegin())[0];
                    anss[cur].insert({anss_id[cur][son], son});

                    anss[cur].erase({anss_id[cur][-2], -2});
                    if (maxs[cur].size() > 1){
                        auto c1 = maxs[cur].rbegin();
                        auto c2 = next(c1);
                        anss_id[cur][-2] = (*c1)[0] + (*c2)[0];
                        anss[cur].insert({anss_id[cur][-2], -2});
                    }

                    son = cur;
                    cur = f[cur];
                }
                ans = max(0ll, (*anss[0].rbegin())[0]);
                
                cout << ans << '\n';
            }

        }
    }
    return 0;
}

到了这里，关于第31次CCF计算机软件能力认证的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！