题解 | 2026牛客寒假算法基础集训营1

比赛链接

B题 #Card Game#

题目描述

将一个长度为2*n的排列分成a,b两个有n个数字的数列，每次比较a1和b1，将大的数字删除，其余数字自动补齐。如果是a数列被删除则得一分。直到a或b被删空。文如何在游戏开始前任意重排a以得到最大的得分，问有多少种重排的方式可以使a的分数最高。

思路

考试的时候一直在想怎么样让a能更多的比b大，但是关键在于我们不知道b的牌，所以只能让已知的a中大的数多往前排（没猜到降序大概是因为还是不习惯贪心的思维吧）。再仔细想，最后我们只会剩下|mina-minb|，也就是说，比minb大的无论如何都会删去，使我加分；比minb小的无论如何都删不去，那么最优情况就肯定是降序了。 或者反过来想最坏的情况则是，如果minb第一个被删掉，那么遇到第一个小于minb的数，a数组将永远停止加分，所以我们抢先删去即可。两个排列数字不重复，则大于minb的部分和小于minb的部分分别随意排列即可。

代码

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

const int MOD = 998244353;

int main(){
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        vector<int> a(n+1), b(n+1);
        for (int i=1; i<=n; i++) cin >> a[i];
        int mn = 400001;
        for (int i=1; i<=n; i++) {
            cin >> b[i];
            mn = min(mn,b[i]);
        }
        int num1=0,num2=0;
        for (int i=1; i<=n; i++){
            if (a[i]>mn) num1++;
            else num2++;
        }
        
        ll ans = 1;//ans要开到ll才能过
        for (int i=1; i<=num1; i++){
            ans = (ans*i)%MOD;
        }
        for (int i=1; i<=num2; i++){
            ans = (ans*i)%MOD;
        }
        
        cout << ans << endl;
    }
    return 0;
}

G题 #Digital Folding#

题目描述

求最大的那个折叠数

思路

直接遍历肯定会超时，观察样例，我们希望反转后高位尽量大，那原数字低位就要尽量大，于是我们直接构造出可能产生最大反转值的候选数字。 对于每个 k，只考虑最大的有效候选数，因为对于相同的末尾9的个数，更大的原数字反转后也更大。

代码

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

ll reverse(ll n){
    ll rev = 0;
    while (n>0){
        rev = rev*10 + n%10;
        n/=10;
    } 
    return rev;
}

int main(){
    int t;
    cin >> t;
    while (t--){
        ll l,r;
        cin >> l >> r;
        ll ans = reverse(r);
        
        for (int k = 1; k <= 18; k++) {//
            ll temp = pow(10,k);//这边精度不是很严格就用pow了
            ll x = (r / temp) * temp + (temp - 1);//将r的最后k位先清零，再变成9
            if (x > r) x -= temp;//防溢出
            if (x >= l) {//确保还在区间内
                ans = max(ans, reverse(x));//每次留下最大的即可
            }
        }
        cout << ans << endl;
    }
    return 0;
}

第一次尝试写题解，如有错误请指出