第十三届蓝桥杯大赛软件赛省赛（C++研究生组）_蓝桥杯研究生组

A: 裁纸刀

可以证明，只要首先裁剪最外围的 $4$ 条边，之后无论怎样裁剪，次数都是最少。对于 $n$ 行 $m$ 列的二维码，至少需要裁剪 $nm+3$ 次，因此答案为 $20\times 22+3=443$ 。

证明：只需证明裁掉边界后至少还需裁剪 $nm-1$ 次。

• $n=1,m\ge 1$ 时至少还需裁剪 $m-1$ 次，结论显然成立。
• $n>1,m=1$ 时至少还需裁剪 $n-1$ 次，结论显然成立。
• 若对于所有的 $n\le i,m\le j$ 且 $(n,m)\ne (i,j)$ 时结论均成立，当 $(n,m)=(i,j)$（其中 $i,j>1$） 时，
• • 若后续第一刀裁去第 $r$ 行的下边界（$1\le r\le n-1$），则至少还需裁剪 $d_1=1+[rm-1]+[(n-r)m-1]=nm-1$
  • 若后续第一刀裁去第 $c$ 列的右边界（$1\le c\le m-1$），则至少还需裁剪 $d_2=1+[nc-1]+[n(m-c)-1]=nm-1$
  • $d_1=d_2=nm-1$ 故 $n>1,m>1$ 时结论成立。

B: 灭鼠先锋

将棋盘的格子按行优先的顺序从 $1$ 到 $8$ 编号，每一个格子有“已放置棋子”和“未放置棋子”两种状态。因此棋盘的状态可用 $8$ 个二进制位表示。用程序模拟下棋过程即可，答案：LLLV。

#include <iostream>
using namespace std;

const int MASK = (1 << 8) - 1;

// 棋盘状态为 status 时下一步操作者是否可以获胜？
bool dfs(int status) {
    if (status == MASK) {
        return true;
    }
    for (int i = 0; i < 8; ++i) {  // 在一个空位上放置一个棋子
        if (status & (1 << i)) continue;
        if (!dfs(status | (1 << i))) return true;
    }
    for (int i = 0; i < 3; ++i) {  // 在同一行的连续两个空位上各放置一个棋子
        if (!(status & (3 << i))) {
            if (!dfs(status | (3 << i))) return true;
        }
        if (!(status & (3 << i + 4))) {
            if (!dfs(status | (3 << i + 4))) return true;
        }
    }
//    for (int i = 0; i < 4; ++i) {  // 同一列的连续两个空位上各放置一个棋子，不合题意
//        if (status & (17 << i)) continue;
//        if (!dfs(status | (17 << i))) return true;
//    }
    return false;
}

int main() {
    printf(dfs(1) ? "L" : "V");
    printf(dfs(3) ? "L" : "V");
    printf(dfs(2) ? "L" : "V");
    printf(dfs(6) ? "L" : "V");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

C: 质因数个数

对于正整数 $n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}$ ，其中 $p_i$ 为质数且 $p_1<p_2<\cdots <p_k$ .

首先找到最小素因子 $p_1$ 并剔出所有 $p_1$ ；然后找到最小素因子 $p_2$ 并剔出所有 $p_2$ ；依此类推.

时间复杂度 $O(\sqrt{n})$ ，空间复杂度 $O(1)$ .

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    int cnt = 0;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) ++cnt;
        while (n % i == 0) n /= i;
    }
    if (n > 1) ++cnt;
    cout << cnt;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

D: 选数异或

区间中存在两个数的异或等于 x ，等价于区间中同时存在 t 和 t^x .

用 $d{p}_r$ 记录以 $r$ 为右端点的“满足要求的短区间”的左端点。也就是说计算 $d{p}_r$ 使得区间 $[d{p}_r,r]$ 满足要求，但 $[d{p}_r+1,r]$ 不满足要求。

对于每一个查询 $l_i,r_i$ ，只需判断 $l_i\le d{p}_{r_i}$ 是否成立即可。时间复杂度 $O(n)$ .

当然，本题还可以采用莫队算法解决（这不是本题的正解），下面仅给出莫队算法的实现。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct node {
    int l, r, i;
    bool operator< (const node &t) {
        if (r != t.r) return r < t.r;
        return l < t.l;
    }
};

int main() {
    int n, m, x;
    scanf("%d%d%d", &n, &m, &x);
    vector<int> a(n);
    for (auto &p : a) scanf("%d", &p);
    vector<node> q(m);
    {
        int i = 0;
        for (auto &t : q) {
            scanf("%d%d", &t.l, &t.r);
            t.i = i++;
            --t.l;
            --t.r;
        }
    }
    sort(q.begin(), q.end());
    vector<bool> ans(m);
    int step = max(sqrt(n), 1.);
    for (int i = 0; i < n; i += step) {
        int cnt = 0;
        vector<int> st(1 << 20);
        int L = 0, R = -1;
        for (auto &t : q) {
            if (t.l < i || t.l >= i + step) continue;
            if (R == -1) L = t.l, R = L - 1;
            while (R < t.r) {
                int y = a[++R];
                ++st[y];
                if (x == 0 && st[y] == 2) ++cnt;
                else if (x && st[y^x] && st[y] == 1) ++cnt;
            }
            while (L < t.l) {
                int y = a[L++];
                --st[y];
                if (x == 0 && st[y] == 1) --cnt;
                else if (x && st[y^x] && st[y] == 0) --cnt;
            }
            while (L > t.l) {
                int y = a[--L];
                ++st[y];
                if (x == 0 && st[y] == 2) ++cnt;
                else if (x && st[y^x] && st[y] == 1) ++cnt;
            }
            ans[t.i] = (cnt > 0);
        }
    }
    for (int i = 0; i < m; ++i) {
        if (ans[i]) puts("yes");
        else puts("no");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

做真题的好处在于，可以让自己意识到在这个位置的题目不应该离谱到需要莫队来解。

E: GCD

因为 $gcd(a+k,b+k)=gcd(\left|a-b\right|,b+k)$ ，因此问题转化为寻找最小的正整数 $k$ 使得 $b+k$ 是 $|a-b|$ 的倍数。

时空复杂度均为 $O(1)$ .

#include <iostream>
using namespace std;

int main() {
    long long a, b, k;
    cin >> a >> b;
    a = abs(a - b);
    a += b / a * a;
    k = a - b;
    cout << k;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

F: 爬树的甲壳虫

设随机变量 $X_i$ 代表甲壳虫从树根爬到高度 $i$ 需要经过的时间（$1\le i\le n$）.

随机变量 $X_1$ 的期望为

$$E(X_1)=\sum _{k=0}^{\infty }(k+1)\cdot P_i^k(1-P_i)=\frac{1}{1-P_i},$$

随机变量 $X_i$ （$i>1$）的期望为

$$E(X_i)=\sum _{k=0}^{\infty }(k+1)(E(X_{i-1})+1)\cdot P_i^k(1-P_i)=\frac{E(X_{i-1})+1}{1-P_i}.$$

因为 $P=998244353$ 是一个质数，由费马小定理知， $\forall a(\gcd (a,P)=1)$ ，可求得 $a$ 的乘法逆元为 $a^{p-2}$ .

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(1)$ .

#include <iostream>
using namespace std;

long long qpow(long long a, int b, int mod) {
    a %= mod;
    long long t = 1 % mod;
    while (b) {
        if (b & 1) t = t * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return t;
}

int inv(int a, int p) {
    return qpow(a, p - 2, p);
}

int main() {
    int n;
    scanf("%d", &n);
    int ex = 0;
    const int p = 998244353;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        x = y - x;
        ex = (ex + 1LL) * y % p * inv(x, p) % p;
    }
    printf("%d\n", ex);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

值得一提的是，当 $y-x=P$ 时本题无解，比如这组样例：

1

1 998244354

提交本题代码的时候发现使用 INT_MAX 需要 #include<climits> ，否则会出现编译错误。

G: 全排列的价值

对于一个排列 $A=(a_1,a_2,\cdots ,a_n)$ ，必存在一个与之对应的 $B=(b_1,b_2,\cdots ,b_n$) ，其中 $b_i=n+1-a_i$ ，使得 c i = ∣ { a j ∣ j < i , a j < a i } ∣ = ∣ { b j ∣ j < i , b j > b i } ∣ c_i=\left|\{a_j|j < i,a_j < a_i\}\right|=\left|\{b_j|j < i,b_j > b_i\}\right| ci​=∣{aj​∣j<i,aj​<ai​}∣=∣{bj​∣j<i,bj​>bi​}∣ .

所有排列的价值之和为 $\frac{1}{2}\cdot n!\cdot {\mathrm{C}}_n^2$

#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    const int p = 998244353;
    int ans = 1LL * n * (n - 1) / 2 % p;
    for (int i = 3; i <= n; ++i) {
        ans = 1LL * ans * i % p;
    }
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

H: 扫描游戏

由于棒从 $y$ 轴正向开始顺时针扫描，因此首先将所有点按照顺时针排序。对于时针同时扫过的点，距原点近的点在前。

将排好序后的数组视为一个循环数组。让棒从初始位置出发，每次向后寻找第一个可以被棒扫到（距原点距离不超过棒长）的点。最多寻找 $n$ 次之后算法结束。

算法复杂度取决于每次向后寻找下一个点的时间，如果顺序查找，总时间复杂度 $O(n^2)$ . 使用线段树维护区间最小值之后可以二分找到下一个点，可使复杂度降为 $O(n{\log }^{2}n)$ .

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

const long long INF = LLONG_MAX;

int gcd(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

struct A {
    int x, y;
    int dx, dy;  // (dx,dy) 代表向量 OA 的方向
    int z, i;
    long long l2;  // L2 范数
    double cs;  // OA 向量与 y 轴正向夹角的 cos 值
    A(int x, int y, int z, int i) : x(x), y(y), l2(1LL * x * x + 1LL * y * y), z(z), i(i) {
        if (x == 0 && y == 0) {
            dx = 0, dy = 1;
            cs = 1;
            return;
        }
        int d = abs(gcd(x, y));
        dx = x / d, dy = y / d;
        cs = dy / sqrt(1. * dx * dx + 1. * dy * dy);
    }
    bool operator< (const A &t) const {
        if (dx == t.dx && dy == t.dy) return l2 < t.l2;
        if (dx >= 0) {
            return t.dx < 0 || cs > t.cs;
        }
        else {
            return t.dx < 0 && cs < t.cs;
        }
    }
};

class SegTree {
    int n;
    vector<long long> tree;

public:
    void update(int p, long long x, int L, int R, int id) {
        if (L == R) {
            tree[id] = x;
            return;
        }

        int m = L + R >> 1;
        if (p <= m) update(p, x, L, m, id << 1);
        else update(p, x, m + 1, R, id << 1 | 1);
        tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
    }

    SegTree(int n) : n(n) {
        tree.resize(n << 2, INF);
    }
    // 查询 [x, y] 内的最小值
    long long query(int x, int y, int L, int R, int id) {
        if (x <= L && R <= y) return tree[id];
        int m = L + R >> 1;
        long long mi = INF;
        if (x <= m) mi = min(mi, query(x, y, L, m, id << 1));
        if (y > m) mi = min(mi, query(x, y, m + 1, R, id << 1 | 1));
        return mi;
    }
    // 查询 [x, y] 内第一个小于等于 val 的位置，若不存在，返回 -1
    int query(int x, int y, long long val) {
        if (x > y || query(x, y, 1, n, 1) > val) return -1;
        int L = x, R = y;
        while (L < R) {
            int m = L + R >> 1;
            if (query(x, m, 1, n, 1) <= val) R = m;
            else L = m + 1;
        }
        return L;
    }
};

int main()
{
    // 输入
    int n;
    long long L;
    scanf("%d%lld", &n, &L);
    vector<A> a;

    for (int i = 0; i < n; ++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a.emplace_back(x, y, z, i);
    }

    sort(a.begin(), a.end());

//    for (auto &t : a) cout << t.x << ' ' << t.y << endl;

    SegTree st(n);

    vector<int> ans(n, -1);

    int last = 0;

    int r = 0;

    // 线段树初始化
    {
        int i = 0;
        for (auto &t : a) {
            st.update(++i, t.l2, 1, n, 1);
        }
    }


    // 检查向量 Ox Oy 是否同向
    auto check = [&] (A x, A y) -> bool {
        return x.dx == y.dx && x.dy == y.dy;
    };

    // 将数组 A 看作一个循环数组，每次寻找区间 [last + 1, n] U [1, last - 1] 区间内第一个可以扫到的点（即第一个 l2 范数小于等于 L^2 的点）
    while (true) {
        int x = st.query(last + 1, n, 1LL * L * L);
        if (x == -1) {
            x = st.query(1, last - 1, 1LL * L * L);
            if (x == -1) break;
        }
        if (last && check(a[last - 1], a[x - 1])) ans[a[x - 1].i] = ans[a[last - 1].i], ++r;
        else ans[a[x - 1].i] = ++r;
        L += a[x - 1].z;
        if (L > 2e9) L = 2e9;
        st.update(x, INF, 1, n, 1);
        last = x;
    }

    for (auto x : ans) printf("%d ", x);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

I: 数的拆分

对于正整数 $n=p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}$ ，其中 $k_i\in {\mathbb{N}}^{+}$ 、 $p_i$ 为质数 且 $p_1<p_2<\cdots <p_r$ .

可以证明， $n$ 能表示成 $x_1^{y_1}\cdot x_2^{y_2}$ （$x_1,x_2,y_1,y_2\in {\mathbb{N}}^{+}$ 且 $y_1,y_2\ge 2$）的形式当且仅当 ∀ i ∈ { 1 , 2 , ⋯   , r } , k i ≥ 2 \forall i\in\{1,2,\cdots ,r\},k_i \ge 2 ∀i∈{1,2,⋯,r},ki​≥2 .

必要性显然成立，下面证明充分性。若 ∀ i ∈ { 1 , 2 , ⋯   , r } , k i ≥ 2 \forall i\in\{1,2,\cdots ,r\},k_i \ge 2 ∀i∈{1,2,⋯,r},ki​≥2，记 l i = { 1 , k i 为奇数 0 , k i 为偶数 , m i = k i − 3 l i 2 l_i=

$$\begin{cases}1,&k_i \text{为奇数}\\ 0,&k_i为偶数\end{cases}$$ ,m_i=\dfrac{k_i-3l_i}{2} li​={1,0,​ki​为奇数ki​为偶数​,mi​=2ki​−3li​​ . 则 $n=\prod _{i=1}^r{p}_i^{k_i}=\prod _{i=1}^r{p}_i^{2m_i+3l_i}={\left(\prod _{i=1}^r{p}_i^{m_i}\right)}^2{\left(\prod _{i=1}^r{p}_i^{l_i}\right)}^3$ . 证毕.

可见，只要所有素因子 $p_i$ 的个数 $k_i\ge 2$ ， $n$ 一定可以表示成 $x_1^2\cdot x_2^3$ 的形式.

若 $n$ 可以表示成 $x_1^2\cdot x_2^3$ 的形式，由题设知 $x_1^2\cdot x_2^3\le 10^{18}$ ，$\Rightarrow$ $\min (x_1,x_2)\le \sqrt[5]{10^{18}}=10^{3.6}<4000$ . 不难发现，如果除掉 $n$ 中所有 $4000$ 以内的素因子，剩下的部分一定是一个平方数或者立方数。

至此算法思路已然明了：

• 预处理算出 $4000$ 以内的所有质数，共 550 个 .
• 对每一个正整数 $e$ ，除掉其 $4000$ 以内的所有素因子. 若除的过程中发现某个素因子仅出现一次，则该数无法拆分.
• $e$ 剩下的部分不是平方数或者立方数，则该数无法拆分.

时间复杂度 $O((550+\epsilon )T)$ ，其中 $\epsilon$ 是计算平方根和立方根的时间.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

/**
 * Get all prime numbers between 1 and n, inclusively.
 */
void getPrimes(std::vector<int> &primes, int n) {
    std::vector<bool> vis(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) primes.push_back(i);
        for (int p : primes) {
            if (p > n / i) break;
            vis[p * i] = true;
            if (i % p == 0) break;
        }
    }
};

inline bool is_square(long long e) {
    long long x = round(sqrt(e));
    return x * x == e;
}

inline bool is_cubic(long long e) {
    long long x = round(pow(e, 1. / 3));
    return x * x * x == e;
}

int main()
{
    vector<int> primes;
    getPrimes(primes, 4e3);
    int T;
    scanf("%d", &T);
    vector<long long> a(T);
    for (auto &p : a) scanf("%lld", &p);

    for (auto &e : a) {
        bool ok = true;
        for (auto &p : primes) {
            if (e % p) continue;
            e /= p;
            if (e % p) {ok = false; break;}
            do e /= p; while (e % p == 0);
        }
        ok &= is_square(e) || is_cubic(e);
        puts(ok ? "yes" : "no");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

个人认为这是本场思维难度最大的一题，一开始真的毫无头绪。

J: 重复的数

• 如果只有一次查询 ，可以用 $O(n)$ 的时间得到答案。对于 $m$ 次查询，可以用 $O(nm)$ 的时间得到全部答案。
• 维护一个动态区间，并用 $cn{t}_k$ 记录区间内恰好出现 $k$ 次的数的个数， $nu{m}_x$ 记录区间内数字 $x$ 出现的次数。如果已知区间 $[l,r]$ 的答案，则可以用 $O(1)$ 的时间得到区间 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$ 的答案，因此可以使用莫队算法解决，时间复杂度 $O(\frac{n\cdot m}{step}+n\cdot step)$ ，其中 $step$ 代表分块区间长度，当 $step$ 取 $\sqrt{m}$ 时理论时间复杂度可降至 $O(n\sqrt{m})$ .

下方代码实现的 $step$ 取 $\sqrt{n}$ ，总的时间复杂度为 $O(n\log n+(m+n)\sqrt{n})$ .

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct node {
    int l, r, k, i;
    bool operator< (const node &t) const {
        return r < t.r;
    }
};
int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (auto &p : a) scanf("%d", &p);
    int m;
    scanf("%d", &m);
    vector<node> v(m);
    {
        int i = 0;
        for (auto &t : v) {
            scanf("%d%d%d", &t.l, &t.r, &t.k);
            --t.l, --t.r;
            t.i = i++;
        }
    }
    sort(v.begin(), v.end());
    vector<int> cnt(n + 1), num(1e5 + 1), ans(m);
    int L = v[0].l, R = L - 1;
    int step = sqrt(n) + 1;
    bool rev = true;
    for (int i = 0; i < n; i += step) {
        rev ^= 1;
        for (int j = 0; j < m; ++j) {
            auto &t = !rev ? v[j] : v[m - 1 - j];
            if (t.l < i || t.l >= i + step) continue;
            while (R < t.r) {
                int x = a[++R];
                cnt[num[x]] -= 1;
                num[x] += 1;
                cnt[num[x]] += 1;
            }
            while (L > t.l) {
                int x = a[--L];
                cnt[num[x]] -= 1;
                num[x] += 1;
                cnt[num[x]] += 1;
            }
            while (R > t.r) {
                int x = a[R--];
                cnt[num[x]] -= 1;
                num[x] -= 1;
                cnt[num[x]] += 1;
            }
            while (L < t.l) {
                int x = a[L++];
                cnt[num[x]] -= 1;
                num[x] -= 1;
                cnt[num[x]] += 1;
            }
            ans[t.i] = cnt[t.k];
        }
    }
    for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    return 0;
}
num[x]] -= 1;
                num[x] += 1;
                cnt[num[x]] += 1;
            }
            while (R > t.r) {
                int x = a[R--];
                cnt[num[x]] -= 1;
                num[x] -= 1;
                cnt[num[x]] += 1;
            }
            while (L < t.l) {
                int x = a[L++];
                cnt[num[x]] -= 1;
                num[x] -= 1;
                cnt[num[x]] += 1;
            }
            ans[t.i] = cnt[t.k];
        }
    }
    for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90