2024.7.21 模拟赛(CSPS2022)记录

T1 - P8817

Sol

首先，我们显然要预处理出每两个点需要换乘几次车，这个容易通过在每一个点跑一次 \(bfs\) 得出，时间复杂度 \(O(n^2)\)，可以接受；

我们考虑贪心，从节点 \(1\) 走到离可以走到的最大价值点，再从这个最大价值点走到下一个最大价值点……但这样对吗？好像有点问题；我们走到当前最大价值点时，实际上对下一步的范围有影响，进而影响下一步能走到的最大价值点，因此有后效性，不能直接贪；但是我们如果枚举每个点，\(O(n^4)\) 的时间复杂度显然无法接受，~~所以我直接暴力跑路~~

考虑优化我们的贪心；什么时候不会产生后效性？这个简单， 后面没有点 了呗，因此设路径为 \(1-a-b-c-d-1\)，当我们确定 \(a,b,c\) 时，就可以贪 \(d\)；又注意到整个路径是对称的，因此我们 把整个路径分为两组，即 \(\{a, b\}\) 与 \(\{c, d\}\)；在确定 \(b\) 时可以贪 \(a\)，在确定 \(c\) 时可以贪 \(d\)

因此，我们还要处理出确定一个点 \(node\) 时，可以到达点 \(node\) 且可以到达点 \(1\) 的最大价值点；这其实可以在开始的 \(bfs\) 中一并处理，具体的，当我们确定点 \(node\) 可达 \(i\) 时，再判断点 \(1\) 是否可达 \(i\)；我们记录这样可达的点 \(i\)，直接排序即可

问题是，我们如果记录下所有的点 \(i\)，那时间复杂度又炸了；怎么办？其实不需要用这么多点的，设已知点 \(b\)，点 \(i\) 只可能与点 \(c\)、点 \(d\) 重合，因此最多跳 \(2\) 次，所以我们只需要记录下 \(3\) 个这样的点 \(i\) 即可

代码

C++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2505, MAXL = 5e5+5;

int n, m, k, front, rear;
long long ans;
long long w[MAXN];
vector <int> G[MAXN];

struct Node{
    int node;
    int step;
}q[MAXL];

bool vis[MAXN];
bool cget[MAXN][MAXN];
vector <int> mget[MAXN];

bool cmp(int a, int b){
    return w[a]>w[b];
}

void bfs(int start){
    memset(vis, false, sizeof(vis));
    vis[start] = true;
    front = rear = 0;
    q[rear].node = start;
    q[rear].step = 0;
    rear++;

    while (front != rear){
        int rnode = q[front].node;
        int rstep = q[front].step;
        front++;

        if (rnode != start){
            cget[start][rnode] = true;
            if (cget[1][rnode] == true){
                mget[start].push_back(rnode);
                sort(mget[start].begin(), mget[start].end(), cmp);
                if (mget[start].size() >= 4) mget[start].pop_back();
            }
        }
        if (rstep > k) continue;
        for (int i=0; i<G[rnode].size(); i++){
            if (vis[G[rnode][i]] == false){
                vis[G[rnode][i]] = true;
                q[rear].node = G[rnode][i];
                q[rear].step = rstep+1;
                rear++;
            }
        }
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (int i=2; i<=n; i++){
        scanf("%lld", &w[i]);
    }
    for (int i=1; i<=m; i++){
        int node1, node2;
        scanf("%d%d", &node1, &node2);
        G[node1].push_back(node2);
        G[node2].push_back(node1);
    }

    for (int i=1; i<=n; i++){
        bfs(i);
    }

    for (int i=2; i<=n; i++){
        for (int j=2; j<=n; j++){
            if (i == j || cget[i][j] == false) continue;
            for (int p=0; p<mget[i].size(); p++){
                for (int q=0; q<mget[j].size(); q++){
                    if (i == mget[i][p] || i == mget[j][q] || j == mget[i][p] || j == mget[j][q] || mget[i][p] == mget[j][q]){
                        continue;
                    }
                    ans = max(ans, w[i]+w[j]+w[mget[i][p]]+w[mget[j][q]]);
                }
            }
        }
    }

    printf("%lld", ans);
    return 0;
}

Record

赛时可真是抽象...打完 \(40pts\) 纯 \(O(n^4)\) 暴力后就直接开后面的题，浪费了太多时间；虽然最后也没有想出正解，但也没有时间交上优化后的暴力，比赛前 \(1min\) 卡线没交上，\(60pts \rightarrow 45pts\)；所以还是记得别太极限……

T2 - P8818

P8818

简单题。我们考虑对 \(a[i] (l_1 \le i \le r_1)\) 全正/全负/有正有负进行分讨，对于 \(b[i] (l_2 \le i \le r_2)\) 同理，过程应该可以优化，但这么讨论最直接，适合我这种没脑子的人

分讨中，我们发现需要记录 \(a[i]\) 任意区间的最大值 / 最小值 / 非负数最小值 / 非正数最大值、\(b[i]\) 任意区间的最大值 / 最小值，直接枚举显然会炸，上相关数据结构即可，线段树或者 \(ST\) 表都行；

代码

C++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5, MAXLOG = 20, INF = 1e9;

int n, m, q, l1, r1, l2, r2, len1, len2;
long long m1, m2, m3, m4, m5, m6, m7, m8;
long long a[MAXN], b[MAXN], log_2[MAXN];
long long c1[MAXN][MAXLOG], c2[MAXN][MAXLOG], c3[MAXN][MAXLOG], c4[MAXN][MAXLOG];
long long d1[MAXN][MAXLOG], d2[MAXN][MAXLOG];

void init(){
    log_2[1] = 0;
    log_2[2] = 1;

    for (int i=3; i<=max(n, m); i++){
        log_2[i] = log_2[i/2]+1;
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &q);

    for (int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
        c1[i][0] = a[i];
        c2[i][0] = a[i];
        if (a[i]==0) c3[i][0] = a[i], c4[i][0] = a[i];
        else if (a[i]>0) c3[i][0] = a[i], c4[i][0] = -INF;
        else if (a[i]<0) c3[i][0] = INF, c4[i][0] = a[i];
    }
    for (int i=1; i<=m; i++){
        scanf("%lld", &b[i]);
        d1[i][0] = b[i];
        d2[i][0] = b[i];
    }

    init();

    for (int j=1; j<=MAXLOG; j++){
        for (int i=1; (i+(1<<j)-1)<=n; i++){
            c1[i][j] = max(c1[i][j-1], c1[i+(1<<(j-1))][j-1]);
            c2[i][j] = min(c2[i][j-1], c2[i+(1<<(j-1))][j-1]);
            c3[i][j] = min(c3[i][j-1], c3[i+(1<<(j-1))][j-1]);
            c4[i][j] = max(c4[i][j-1], c4[i+(1<<(j-1))][j-1]);

        }   
    }   
    for (int j=1; j<=MAXLOG; j++){
        for (int i=1; (i+(1<<j)-1)<=m; i++){
            d1[i][j] = max(d1[i][j-1], d1[i+(1<<(j-1))][j-1]);
            d2[i][j] = min(d2[i][j-1], d2[i+(1<<(j-1))][j-1]);
        }   
    }   

    for (int i=1; i<=q; i++){
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        len1 = r1-l1+1;
        len2 = r2-l2+1;
        m1 = max(c1[l1][log_2[len1]], c1[r1-(1<<log_2[len1])+1][log_2[len1]]);
        m2 = min(c2[l1][log_2[len1]], c2[r1-(1<<log_2[len1])+1][log_2[len1]]);
        m3 = max(d1[l2][log_2[len2]], d1[r2-(1<<log_2[len2])+1][log_2[len2]]);
        m4 = min(d2[l2][log_2[len2]], d2[r2-(1<<log_2[len2])+1][log_2[len2]]);
        m5 = min(c3[l1][log_2[len1]], c3[r1-(1<<log_2[len1])+1][log_2[len1]]);
        m6 = max(c4[l1][log_2[len1]], c4[r1-(1<<log_2[len1])+1][log_2[len1]]);
        // cout << m1<< " " << m2 << " " << m3 << " " << m4 << " " << m5 << " " << m6 << endl;
        if (m3 <= 0){
            if (m1 <= 0) printf("%lld\n", m2*m3);
            else if (m2 >= 0) printf("%lld\n", m2*m4);
            else printf("%lld\n", m2*m3);
        }
        else if (m4 >= 0){
            if (m1 <= 0) printf("%lld\n", m1*m3);
            else if (m2 >= 0) printf("%lld\n", m1*m4);
            else printf("%lld\n", m1*m4);
        }
        else{
            if (m1 <= 0) printf("%lld\n", m1*m3);
            else if (m2 >= 0) printf("%lld\n", m2*m4);
            else printf("%lld\n", max(m3*m6, m4*m5));       
        }
    }
    return 0;
}

Record

这题本身没什么难度，主要想说说拍子的事……写了个 \(py\) 文件当生成器，结果运行时写成 \(python3 \ xxx.py\)，电脑恰好没 \(python3\)，再加上我眼瞎把提示看成 \(fc\) 的提示 ~~(什么实力)~~，愣是一直没发现……\(1h\) 后才发现并改成了 \(python \ xxx.py\)；

T3 - P8819

P8819

一个节点 \(i\) 能实现反击，意味着从 \(i\) 可以走到一个环；能实现连续穿梭，意味着图中所有节点的出度都是 \(1\)；事实上，所有节点的出度都是 \(1\) 已经包含从任意节点 \(i\) 都能走到环这一条件，因此我们 只需要记录出度

对于操作 \(1\) 与操作 \(3\)，很容易维护；但是对于操作 \(2\) 与操作 \(4\) 不太好办，因为我们删除或者恢复一个点，操作的是这个节点的入边；如果我们枚举每个与 \(i\) 连边的点，时间开销太大，无法接受；由于操作 \(1\) 与操作 \(3\) 对于入度也很容易维护，因此我们考虑 改为维护入度

出度与入度有什么关系？有一个显然的基本定理：所有点的入度之和等于所有点的出度之和；因此，如果我们已知所有点的入度之和，可以保证结果的 正确性，但是，此时充分性无法保证；例如，我们知道 \(1+1+1+1=4\)，但是只知道和是 \(4\)，无法确定每个点的出度都是 \(1\)；这里是关键点：我们 考虑哈希与随机化的思想

原来所有点的出度都是 \(1\)，算出和来不好反推；我们将 每个点随机赋一个值，代表其入度；记录其一开始的入度之和，如果某次操作后当前所有点的入度之和等于开始的入度之和，那么我们就可以认为此时满足要求

实现时，开一个变量实时维护所有点的入度之和，我们承受不了每次操作后再加在一块统计的时间开销……

代码

C++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+5;

int n, m, q, node1, node2, op;
unsigned int s=0, rs=0;
unsigned int w[MAXN], in[MAXN], r[MAXN];

int main(){
    srand(time(0));
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++){
        w[i] = (unsigned int)rand();
        s += w[i];
    }
    for (int i=1; i<=m; i++){
        scanf("%d%d", &node1, &node2);
        r[node2] += w[node1];
        in[node2] += w[node1];
        rs += w[node1];
    }
    scanf("%d", &q);
    for (int i=1; i<=q; i++){
        scanf("%d", &op);
        if (op == 1){
            scanf("%d%d", &node1, &node2);
            in[node2] -= w[node1];
            rs -= w[node1];
        }
        else if (op == 2){
            scanf("%d", &node1);
            rs -= in[node1];
            in[node1] = 0;
        }
        else if (op == 3){
            scanf("%d%d", &node1, &node2);
            in[node2] += w[node1];
            rs += w[node1];
        }
        else if (op == 4){
            scanf("%d", &node1);
            rs += r[node1]-in[node1];
            in[node1] = r[node1];
        }
        if (rs == s){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

Record

太菜了，考试的时候直接照着最暴力的部分打，甚至没有考虑要求 \(1\) 实际上没有意义；\(40pts \rightarrow 25pts\)；不过这题的正解思想确实精妙，现在根本没有这个实力……

T4 - P8820

P8820

不会捏。\(44pts\) 暴力跑路；其实如果纯写暴力，对于我这种 \(dp\) 极度不好的人来说没有必要去写 \(dp\)，直接暴力建图 + 堆优化 \(dij\) 即可，时间复杂度可能还要更优……

2024.7.21 模拟赛(CSPS2022)记录

T1 - P8817

Sol

Record

T2 - P8818

Record

T3 - P8819

Record

T4 - P8820

评论