2022年第十三届蓝桥杯省赛C++研究生组

A. 裁纸刀

$4 + 19 + 20 \times 21=443$

B. 灭鼠先锋

输入

XOOO
OOOO
XXOO
OOOO
OXOO
OOOO
OXXO
OOOO

代码

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

#define frein freopen("in.txt", "r", stdin);
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) (x & -x)
#define gcd __gcd
#define fi first
#define se second
#define pl (p << 1)
#define pr (p << 1 | 1)
#define pb push_back
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)

typedef long long LL;
const int N = 1 << 8;
char s[10];
bool f[N]; //f[i] 记录状态 i 是否必赢

//存放剩余 k 个格子未占满的状态
vector<int> p[9];

//可以横放两个的左边位置下标
vector<int> pos = {7, 6, 5, 3, 2, 1};

int main(){
    frein;

    //预处理，得到每种状态有几个位置没有放棋子
    fir(i, 0, (1 << 8) - 1) {
        int cnt = 8;
        fir(j, 0, 7) {
            if((i >> j) & 1) cnt--; 
        }
        p[cnt].pb(i);
    }

    //缺2个位置肯定赢，缺1个必输
    fir(i, 0, 7) {
        fir(j, 0, 7) {
            int k = (N - 1) ^ (1 << i) ^ (1 << j);
            f[k] = true;
        }
    }

    //从小到大枚举差 k 个位置放满棋盘的局面输赢
    //k = 1的全输，k=2的全赢，在前面已经处理过
    fir(k, 3, 8) { // 6
        for(int i:p[k]) {
            //放 1 个可以到达必输局面
            fir(j, 0, 7) {
                if((i >> j) & 1) continue;
                if(!f[i ^ (1 << j)]) f[i] = true;
            }

            //放 2 个可以达到必输局面
            for(int j:pos) {
                if(((i >> j) & 1) || ((i >> (j - 1)) & 1)) continue;
                if(!f[i ^ (1 << j) ^ (1 << (j - 1))]) f[i] = true;
            }
        }
    }


    fir(test, 1, 4) {
        scanf("%s", s);
        scanf("%s", s + 4);

        // 得到当前状态
        int t = 0;
        fir(i, 0, 7) {
            if(s[i] == 'X') t = t * 2 + 1;
            else t = t * 2; 
        }

        //注意当前输入是已经放置了小蓝的，所以是小乔的局面
        //小乔输，小蓝才赢，小乔赢则小蓝输
        printf(!f[t] ? "V" : "L"); 
    }
    puts("");

    return 0;
}

C. 质因数个数

代码

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

#define fi first
#define se second
#define pb push_back
#define gcd __gcd
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)

typedef long long LL;
typedef pair<int, int> PII;

LL n;
int res;

void divd(LL x) {
    for(int i = 2; i * 1ll * i <= x; i++) {
        if(x % i == 0) {
            while(x % i == 0) x /= i;
            res++;
        }
    }

    if(x > 1) res++;
}

int main(){
    cin >> n;
    divd(n);
    cout << res << endl;
    return 0;
}

D. 选数异或

分析

从后往前遍历，对当前的数，判断其右边是否存在与他异或为 $x$ 的数，若存在，需要找到存在的那个数的最近的位置下标，若当前数的匹配数的位置相比于下一个数的匹配数的位置要远，则当前位置的最优解等于下一个位置的最优解。

代码

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

#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fi first
#define se second
#define gcd __gcd
#define pb push_back
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 5;
int n, m, x, a[N], l, r;
map<int, int> mp;
int Right[N];

bool solve() {
    return Right[l] > 0 && Right[l] <= r;
}

int main() {
    cin >> n >> m >> x;
    fir(i, 1, n) scanf("%d", &a[i]);
    rif(i, n, 1) {
        int v = a[i] ^ x;
        if(mp.count(v)) {
            if(Right[i + 1] == 0) Right[i] = mp[v];
            else if(Right[i + 1] >= mp[v]) Right[i] = mp[v];
            else Right[i] = Right[i + 1];
        }
        else Right[i] = Right[i + 1];
        mp[a[i]] = i;
    }

    while(m--) {
        scanf("%d%d", &l, &r);
        puts(solve() ? "yes" : "no");
    }
    return 0;
}

E. GCD

代码

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

#define fi first
#define se second
#define pb push_back
#define gcd __gcd
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)

typedef long long LL;
typedef pair<int, int> PII;

int T;
LL a, b;

int main(){
    cin >> T;
    while(T--){
        scanf("%lld%lld", &a, &b);
        LL c = b - a;
        if(a >= c) {
            if(a % c == 0) printf("%lld\n", c);
            else printf("%lld\n", (a + c - 1) / c * c - a);
        }
        else printf("%lld\n", c - a);
    }

    return 0;
}

F. 爬树的甲壳虫

分析

记 $f[i]$ 表示从高度 $i$ 出发到达高度 $n$ 的期望时间，则 $f[i]$ 可以表示为 下一步能到达的高度到 $n$ 的花费的时间期望，再加上1（到达下一高度所花费一个单位时间），如下：

$f[i] = (1-p_{i+1})f[i+1] + p_{i+1}f[0] + 1$

上述式子表示其有 $(1-p_i)$ 的概率成功达到高度 $i+1$，也有 $p_i$ 的概率到达高度 $0$（即回到树根），下两个高度到终点的时间期望加上从当前出发到那两个状态花费的一个单位时，即为当前高度的期望花费。

同时，由 $f[i]$ 的定义，显然可以知道 $f[n] = 0$。而我们的最终目标就是求出 $f[0]$。

接下来对式子进行化简，对上述式子左右同时减掉 $f[0]$ 有：

$\begin{aligned} f[i] - f[0] &= (1-p_{i+1})f[i+1] + p_{i+1} f[0] + 1 - f[0] \\ &= (1-p_{i+1})f[i+1] + (p_{i+1} + 1)f[0] + 1 \\ &= (1-p_{i+1})(f[i+1] - f[0]) + 1 \end{aligned}$

可以发现其中出现了 $f[i+1]-f[0]$ 的项，将其解出来：

$\begin{aligned} &f[i] - f[0] = (1 - p_{i+1})(f[i+1] - f[0]) + 1 \\ &\Rightarrow f[i] - f[0] - 1 = (1-p_{i+1})(f[i+1] - f[0]) \\ &\Rightarrow \frac{f[i] - f[0] - 1}{1-p_{i+1}} = f[i+1] - f[0] \\ &\Rightarrow f[i+1] - f[0] = \frac{f[i]-f[0]}{1-p_{i+1}} - \frac{1}{1-p_{i+1}} \end{aligned}$

由最后一行的变换结果，可以发现 $(f[i+1] - f[0])$ 能由 $(f[i] - f[0])$ 表示出来，为了后续推导方便，将 $i + 1$ 改为 $i$，得到如下递推式子：

$f[i]-f[0] = \frac{f[i - 1] - f[0]}{1-p_i} - \frac{1}{1-p_i}$

再依次将 $(f[i - 1] - f[0]), \dots,(f[1]-f[0]), (f[0] - f[0])$ 的公式代入可以得到：

$\begin{aligned} f[i] - f[0] &= \frac{f[i - 1] - f[0]}{1-p_i} - \frac{1}{1-p_i} \\ &= \frac{f[i-2]-f[0]}{(1-p_i)(1-p_{i-1})} - \frac{1}{(1-p_i)(1-p_{i-1})} - \frac{1}{1-p_i} \\ &= \frac{f[i-3]- f[0]}{(1-p_i)(1-p_{i-1})(1-p_{i-2})} -\frac{1}{(1-p_i)(1-p_{i-1})(1-p_{i-2})} -\frac{1}{(1-p_i)(1-p_{i-1})} - \frac{1}{1-p_i} \\ & \vdots \\ & \vdots \\ &= \frac{f[0] - f[0]}{\prod\limits_{j=1}^{i}(1-p_j)} - \frac{1}{\prod\limits_{j=1}^{i}(1-p_j)} - \frac{1}{\prod\limits_{j=2}^{i}(1-p_j)} - \cdots - \frac{1}{\prod\limits_{j=i}^{i}(1-p_j)} \end{aligned}$

注意到上式最后一排的式子中， $f[0] - f[0] = 0$，则有：

$f[i] - f[0] = -\left(\frac{1}{\prod\limits_{j=1}^{i}(1-p_j)} + \frac{1}{\prod\limits_{j=2}^{i}(1-p_j)} + \cdots + \frac{1}{\prod\limits_{j=i}^{i}(1-p_j)}\right)$

而已知 $f[n] = 0$， 则有：

$\begin{aligned} &f[n]-f[0] = 0-f[0] =-\left(\frac{1}{\prod\limits_{j=1}^{n}(1-p_j)} + \frac{1}{\prod\limits_{j=2}^{n}(1-p_j)} + \cdots + \frac{1}{\prod\limits_{j=i}^{n}(1-p_j)}\right) \\ &\Rightarrow f[0] = \frac{1}{\prod\limits_{j=1}^{n}(1-p_j)} + \frac{1}{\prod\limits_{j=2}^{n}(1-p_j)} + \cdots + \frac{1}{\prod\limits_{j=i}^{n}(1-p_j)} \\ &\Rightarrow f[0] = \cfrac{1}{\prod\limits_{j=1}^{n}(1-\cfrac{x_j}{y_j})} + \cfrac{1}{\prod\limits_{j=2}^{n}(1-\cfrac{x_j}{y_j})} + \cdots + \cfrac{1}{\prod\limits_{j=i}^{n}(1-\cfrac{x_j}{y_j})} \\ &\Rightarrow f[0] = \cfrac{1}{\prod\limits_{j=1}^{n}\cfrac{y_j-x_j}{y_j}} + \cfrac{1}{\prod\limits_{j=2}^{n}\cfrac{y_j-x_j}{y_j}} + \cdots + \cfrac{1}{\prod\limits_{j=i}^{n}\cfrac{y_j-x_j}{y_j}} \\ &\Rightarrow f[0] = \prod_{j=1}^n\cfrac{y_j}{y_j-x_j} + \prod_{j=2}^n\cfrac{y_j}{y_j-x_j} + \cdots + \prod_{j=n}^n\cfrac{y_j}{y_j-x_j} \end{aligned}$

综上，可以得到最终的结果，即高度 $0$ 到 $n$ 的期望时间 $f[0]$。

接下来就是使用乘法逆元求解结果即可。

代码

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

#define fi first
#define se second
#define pb push_back
#define gcd __gcd
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 5, MOD = 998244353;
int n, f[N], x[N], y[N];

int qpow(int a, int n) {
    int s = 1;
    a = a % MOD;
    while(n) {
        if(n & 1) s = s * 1ll * a % MOD;
        a = a * 1ll * a % MOD;
        n >>= 1;
    }
    return s;
}

inline int inv(int x) {
    return qpow(x, MOD - 2);
}

int main() {
    cin >> n;
    fir(i, 1, n) scanf("%d%d", &x[i], &y[i]);

    int res = 0, p = 1;
    rif(i, n, 1) {
        p = p * 1ll * y[i] % MOD * inv(y[i] - x[i]) % MOD;
        res = (res + p) % MOD;
    }
    cout << res << endl;

    return 0;
}

G. 全排列的价值

分析

我们考虑每一个数在排列中的对最终答案的贡献，如排列 $2, 3, 1$ 中，数字 $2$ 的贡献为 $2$。

首先，对于 $1-n$ 的全排列，$1$ 的贡献是：

累加起来就是 $(n-1)!\times\frac{n(n-1)}{2}$ ，我们记这个式子为 $f(n)$。

从上面我们可以推算出一个结论：对从于 $i$ 到 $j$ 的长度为 $j - i +1$ 的全排列，其最小的元素 $i$ 所占的贡献为 $f(j-i+1)$。

那么，对于一个数 $i,i\gt1$，我们如何求其在 $1-n$ 的全排列中的贡献呢？

对于 $i$，只对排在其后面的且大于它的数才有贡献，所以

$ans = \frac{n(n-1)}{4}n!$

代码

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

#define fi first
#define se second
#define pb push_back
#define gcd __gcd
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)

typedef long long LL;
typedef pair<int, int> PII;

const int MOD = 998244353;
int n;
LL res = 1;

int qpow(int a, int n) {
    int s = 1;
    a = a % MOD;
    while(n) {
        if(n & 1) s = s * 1ll * a % MOD;
        a = a * 1ll * a % MOD;
        n >>= 1;
    }
    return s;
}

int main (){
    cin >> n;
    fir(i, 1, n) {
        res = res * i % MOD;
    } 
    res = res * n % MOD * (n - 1) % MOD * qpow(4, MOD - 2) % MOD;
    cout << res << endl;
    return 0;
}