CSP42 WriteUp

第42次CCF CSP软件能力认证

2026.05.31

---

在本次CSP认证中，我取得了360分的成绩，位于当次认证排名前1.25%，在分数与排名方面均优于过往参加的CSP认证。

“我只不过是一个侥幸的取胜者罢了”

---

T1 银行家舍入

试题描述

Write Up

基础的模拟，过题时间大概在0:06。

#include <bits/stdc++.h>

using namespace std;

double fl[1005];
int tmp;
int ans1[1005], ans2[1005];
int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> fl[i];

    for(int i = 0; i < n; i++){
        tmp = (int)(fl[i]*10);
        if(tmp % 10 <= 4) ans1[i] = tmp / 10;
        else ans1[i] = tmp / 10 + 1;
        if(tmp % 10 <= 4) ans2[i] = tmp / 10;
        else if(tmp % 10 >= 6)ans2[i] = tmp / 10 + 1;
        else {
            if((tmp / 10) % 2) ans2[i] = tmp / 10 + 1;
            else ans2[i] = tmp / 10;
        }
    }

    for(int i = 0; i < n; i++)
        cout << ans1[i] << " ";
    cout << endl;
    for(int i = 0; i < n; i++)
        cout << ans2[i] << " ";
    cout << endl;
    return 0;
}

T2 机器人宿管指南

试题描述

Write Up

根据提示，最后20%测试数据中n的取值较大，且答案不大于\(10^9\)，直接二分搜索答案，过题时间大约0:15。

#include<bits/stdc++.h>

using namespace std;

long long n, m, k, tmp;
long long upb = 1e9, dob = 1, nowb, bd, st;

int ins = 0;

int main(){
    cin >> n >> k >> m ;
    while(upb != dob){
        nowb = (upb + dob + 1) /2;
        ins = 0;
        st = n;
        for(int i = 1; i <= m; i++){
            tmp = st * k;
            if(tmp % 100) bd = tmp / 100 + 1;
            else bd = tmp / 100;
            st -= bd;
            if(st < 0){
                ins = -1;
                break;
            }
            st -= nowb;
            if(st < 0){
                ins = -1;
                break;
            }
        }
        if(ins == -1) upb = nowb - 1;
        else dob = nowb;
    }
    cout << dob << endl;
    return 0;
}

T3 死锁优化

试题描述

Write Up

CSP经典的第3题大模拟，不涉及很复杂的算法，照着写就可以，通过代码模拟各种进程在各个时间段的行为。

两个注意点：首先试题中给出的timeout时限是\(10^{100}\)，这显然是偏大的，依据最后所有数据的范围，其实大概40000个时间段还没有终止的进程就可以认为发生了死锁，最后还没有终止，不放心可以再开大一点。第二就是资源的释放时机，结束时释放是在“上一段末尾”，而A类因为申请不到资源释放是在“本段末尾”，由于没有正确处理A类进程行为导致在答案错误85/100卡了一会。在我的实现中结束时释放被移到了下一时间段开始再处理，是等效的但要注意先跑一遍全量的释放再跑申请。

#include<bits/stdc++.h>

using namespace std;

int n, m;

long long timenow, timemax = 4000000;

int prot[20], stt[20], kt[20], askfor[20][100][2], w[20];

char tmpst;

int stat[105], askfailtime[20][100], cntfinish = 0, gett[20], ptr[20];

int stable[20][50], stablecnt[20], isfinish[20], iswork[20];

long long ans[30], ptime[30];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> tmpst;
        if(tmpst == 'X') {
            prot[i] = 0;
            cin >> stt[i] >> kt[i];
        } else if(tmpst == 'A') {
            prot[i] = 1;
            cin >> stt[i] >> w[i] >> kt[i];
        } else if(tmpst == 'B') {
            prot[i] = 2;
            cin >> stt[i] >> w[i] >> kt[i];
        } else if(tmpst == 'C') {
            prot[i] = 3;
            cin >> stt[i] >> w[i] >> kt[i];
        }

        for(int j = 1; j <= kt[i]; j++){
            cin >> askfor[i][j-1][0] >> askfor[i][j][1];
        }

        askfor[i][0][1] = stt[i];
        askfor[i][kt[i]][0] = -1;
    }



    while(cntfinish != n && timenow < timemax){

//        cout << "At time " << timenow << endl;
        for(int i = 1; i <= n; i++){
            //getValue
            if(iswork[i] && !isfinish[i]){
                ans[i] += stablecnt[i];
//                cout << i << "GetValue =======" << stablecnt[i]<<endl;
            }
            //finish
            if(timenow == askfor[i][ptr[i]][1] && askfor[i][ptr[i]][0] == -1){
                isfinish[i] = 1; cntfinish ++;
                iswork[i] = 0; ptime[i] = timenow - stt[i];
                for(int index = 1; index <= m; index ++){
                    if(stable[i][index]){
                        stat[index] = 0;
                        stable[i][index] = 0;
                        stablecnt[i] --;
                    } 
                } // release all acc
//                cout << i << "Finish!" << endl;
            }
        }
        for(int i = 1; i <= n; i++){
            int tmpaccapt = 0;
            // acc
            if(timenow >= askfor[i][ptr[i]][1] && !isfinish[i] && askfor[i][ptr[i]][0] != -1){
                if(stat[askfor[i][ptr[i]][0]] == 0){
                    stat[askfor[i][ptr[i]][0]] = i;
                    stablecnt[i] ++;
                    stable[i][askfor[i][ptr[i]][0]] = 1;
                    ptr[i] ++;
                    iswork[i] = 1;
                    askfor[i][ptr[i]][1] += timenow;
//                    cout << i << "GetAcc" << stat[askfor[i][ptr[i]-1][0]] << endl;
                    tmpaccapt = 1;
                } else {
                    iswork[i] = 0; //shutdown proc
                }

            }
            if(!isfinish[i] && prot[i] == 2 && !tmpaccapt){
                //B
                if(timenow - askfor[i][ptr[i]][1] >= w[i]-1){
                    // continue the task while give up askfor
                    ptr[i] ++;
                    askfor[i][ptr[i]][1] += timenow;
                    iswork[i] = 1;
                }
            }

            if(!isfinish[i] && prot[i] == 3 && !tmpaccapt){
                //C
                if(timenow - askfor[i][ptr[i]][1] >= w[i]){
                    // 666, i also want to do things like this
                    int tmpn = stat[askfor[i][ptr[i]][0]];
                    stable[tmpn][askfor[i][ptr[i]][0]] = 0;
                    stablecnt[tmpn] --;

                    stat[askfor[i][ptr[i]][0]] = i;
                    stable[i][askfor[i][ptr[i]][0]] = 1;
                    stablecnt[i] ++;
                    iswork[i] = 1;

                    ptr[i]++;
                    askfor[i][ptr[i]][1] += timenow;
                }
            }
        }

        for(int i = 1; i <= n; i++){
            if(!isfinish[i] && prot[i] == 1){
                //A
                if(askfor[i][ptr[i]][0] != -1 && stat[askfor[i][ptr[i]][0]] != 0 && timenow - askfor[i][ptr[i]][1] >= w[i]-1){
                    // release all acc
                    for(int index = 1; index <= m; index ++){
                        if(stable[i][index]){
                            stat[index] = 0;
                            stable[i][index] = 0;
                        } 
                    }
                    stablecnt[i] = 0;
                    iswork[i] = 0;
                }
            }
        }
        timenow ++;
    }
    for(int i = 1; i <= n; i++)
        if(!ptime[i]) ptime[i] = -1;
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " " << ptime[i] << endl;
    return 0;
}

T4 石子游戏

试题描述

Write Up

首先试题已经把必胜的条件放在了题面，其次注意到异或的性质然后预处理做前缀和（奇偶分开）就可以时间超限 60/100，做完这个距离结束大概还有一个小时。后来尝试了预处理，但是由于写的预处理还是\(O(n^2)\)时间复杂度的仍然改变不了时间超限，也算留下了一些遗憾。自己定义一个struct、cmp然后用\(O(nlogn)\)排序后对于异或值相同的最近两个节点（奇偶同性）之间加一条边做预处理应该可以加速，或者用unordered map甚至可以做到\(O(n)\)，留待后续补题了。

这次可能是很长一段时间离400分最近的一次了。依然是算法一道没做出来（悲）。

60分代码如下，看起来还是比较简洁的。

#include<bits/stdc++.h>

using namespace std;

int n, q, l, r, ans;
long long num[1000006];

long long cx[1000006];

int main(){
    cin >> n >> q;
    for(int i = 2; i <= n + 1; i++){
        cin >> num[i];
    }

    cx[0] = 0;
    cx[1] = 0;

    for(int i = 2; i <= n + 1; i++){
        cx[i] = num[i] ^ cx[i-2];
    }

    for(int cnt = 0; cnt < q; cnt++){
        cin >> l >> r; ans = 0;
        l ++; r++;
        for(int i = l; i <= r; i++){
            for(int j = l; j <= i; j++){
                if((i - j) % 2) {
                    if((cx[i-1] ^  cx[j-2]) == 0){

                        ans ++;
                        l = i + 1;
                    }
                } else {
                    if((cx[i] ^  cx[j-2]) == 0){
                        ans ++;
                        l = i + 1;
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}

T5 绝世好串

试题描述

Write Up

考场上没动……等CSP模拟练习开了之后看看能不能过个最小的样例试试（不得不提CSP40T4甚至\(n \le 10\)都答案错误倒闭了）；或者让AI做一下我欣赏一下（雾）。

当然还是有提交记录的，考场上稀里糊涂交了个这个（T4的代码，没看清楚题目就提交导致的）。应该是答案错误 0/100，肯定是0分，不过前一个是什么忘了，也可能是运行错误。

#include<bits/stdc++.h>

using namespace std;

int n, q, l, r, ans, tmp;
long long num[1000006];
int last[1000006], nextjs[1000006];
long long cx[1000006];

int main(){
    cin >> n >> q;
    for(int i = 2; i <= n + 1; i++){
        cin >> num[i];
    }

    cx[0] = 0;
    cx[1] = 0;

    for(int i = 2; i <= n + 1; i++){
        cx[i] = num[i] ^ cx[i-2];
    }
/*
    for(int cnt = 0; cnt < q; cnt++){
        cin >> l >> r; ans = 0;
        l ++; r++;
        for(int i = l; i <= r; i++){
            for(int j = l; j <= i; j++){
                if((i - j) % 2) {
                    if((cx[i-1] ^  cx[j-2]) == 0){

                        ans ++;
                        l = i + 1;
                    }
                } else {
                    if((cx[i] ^  cx[j-2]) == 0){
                        ans ++;
                        l = i + 1;
                    }
                }
            }
        }
        cout << ans << endl;
    }
*/
    l = 2; r = n + 1;
    for(int i = n; i >= 1; i--)
        nextjs[i] = 999999999;

    for(int i = r; i >= l; i--){
        i = min(r+1, i);
        for(int j = i; j >= l; j--){
            if((i - j) % 2) {
                if((cx[i-1] ^  cx[j-2]) == 0){
                    nextjs[j - 1] = min(i - 1, nextjs[j - 1]);
                    r = min(r, j - 1);
                    break;
                }
            } else {
                if((cx[i] ^  cx[j-2]) == 0){
                    nextjs[j - 1] = min(i - 1, nextjs[j - 1]);
                    r = min(r, j - 1);
                    break;
                }
            }
        }
    }
/*
    for(int i = n - 1; i >= 1; i--){
        nextjs[i] = min(nextjs[i+1], nextjs[i]);
    }
*/
    for(int i = 1; i <= n; i++){
        cout << nextjs[i] << " ";
    } cout << endl;

    for(int cnt = 0; cnt < q; cnt++){
        cin >> l >> r;
        ans = 0;
        tmp = nextjs[l];
        while (tmp <= r && tmp != 0){
            ans ++;
            if(tmp + 1 > r) break;
            tmp = nextjs[tmp+1];
        }
        cout << ans << endl;
    }

    return 0;
}

题外话

看未通过合规性分析的参与认证者公示结果甚至有与我同考点的考生（悲）。而且为什么是标注考点名称不是考生学校名称啊……感觉有点容易误解（？）。