2025牛客暑期多校训练营3

这场是 vp 的，大概情况是这样的

STATUS	COUNT
AC	7
赛后补	0

排名是 305，这套简单一点，但是手慢无啊😭，我们是 7 道题的倒数，第一个 7 道题的是七十多名。

A. Ad-hoc Newbie#

这道是我做的，我发现有限制 f_i ≤ i，之后每行至多需要 i 个位置就可以满足要求，利用对称性，如果前 i 个位置填的同时符合第 i 行和前 i - 1 列的要求，沿着对角线对称过去一定还满足，所以问题就简单了，直接随便按要求构造半个矩阵然后对称过去就解决了。

1
#include <iostream>
2
using namespace std;
3
const int N = 1500;
4
int st[N], tp;
5
int a[N][N], b[N];
6

7
int main() {
8
  int T;
9
  scanf("%d", &T);
10
  while (T--) {
11
    int n;
12
    scanf("%d", &n);
13
    for (int i = 1; i <= n; ++i) {
14
      scanf("%d", &b[i]);
15
    }
16
    for (int i = 1; i <= n; ++i) {
17
      tp = 0;
18
      for (int j = 0; j < b[i]; ++j) {
19
        st[++tp] = j;
20
      }
21
      for (int j = 1; j <= i; ++j) {
22
        if (!tp) {
23
                    // 这里是我之前想多了，其实直接全填 0 就行，相当于没写这个循环。
24
          for (int k = 0; k <= n; ++k) {
25
            if (k != b[i] && k != b[j]) {
26
              a[i][j] = k;
27
              break;
28
            }
29
          }
30
        }
31
        else if (st[tp] != b[j]) a[i][j] = st[tp--];
32
        else if (st[tp] == b[j]) {
33
          if (tp == 1) {
34
            for (int k = 0; k <= n; ++k) {
35
              if (k != b[i] && k != b[j]) {
36
                a[i][j] = k;
37
                break;
38
              }
39
            }
40
          }
41
          else {
42
            a[i][j] = st[tp - 1];
43
            st[tp - 1] = st[tp];
44
            tp--;
45
          }
46
        }
47
      }
48
    }
49
    for (int i = 1; i <= n; ++i) {
50
      for (int j = 1; j <= i; ++j) printf("%d ", a[i][j]);
51
      for (int j = i + 1; j <= n; ++j) printf("%d ", a[j][i]);
52
      printf("\n");
53
    }
54
  }
55
  return 0;
56
}

B. Bitwise Puzzle#

这道题也是我做的，思路也比较简单，美中不足的是我没有把情况归纳起来，我是暴力枚举了所有可能的次序都写了一遍，被我做成大模拟了，期间还因为区间归纳的有问题错了两次。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
int main() {
7
    int T;
8
    scanf("%d", &T);
9
    while (T--) {
10
        vector<int> res;
11
        int a, b, c;
12
        scanf("%d%d%d", &a, &b, &c);
13
        if (a == 0 && b == 0) {
14
            if (c == 0) printf("0\n\n");
15
            else printf("-1\n");
16
            continue;
17
        }
18
        int ha = -1, hb = -1, hc = -1;
19
        for (int i = 30; i >= 0; --i) {
20
            if (a >> i & 1) {
21
                ha = i;
22
                break;
23
            }
24
        }
25
        for (int i = 30; i >= 0; --i) {
26
            if (b >> i & 1) {
27
                hb = i;
28
                break;
29
            }
30
        }
31
        for (int i = 30; i >= 0; --i) {
32
            if (c >> i & 1) {
33
                hc = i;
34
                break;
35
            }
36
        }
37
        if (ha <= hb && hb <= hc) {
38
            int d = hc - hb;
39
            for (int i = hb; i >= 0; --i) {
40
                if ((c >> (i + d) & 1) ^ (a >> i & 1)) {
41
                    a ^= b;
42
                    res.emplace_back(3);
43
                }
44
                b >>= 1;
45
                res.emplace_back(2);
46
            }
47
            res.pop_back();
48
            for (int i = d - 1; i >= 0; --i) {
49
                res.emplace_back(1);
50
                if (c >> i & 1) res.emplace_back(3);
51
            }
52
            res.emplace_back(2);
53
            res.emplace_back(4);
54
        }
55
        else if (hc <= ha && ha <= hb) {
56
            for (int i = hb; i >= 0; --i) {
57
                if ((a >> i & 1) ^ (c >> i & 1)) {
58
                    a ^= b;
59
                    res.emplace_back(3);
60
                }
61
                b >>= 1;
62
                res.emplace_back(2);
63
            }
64
            res.emplace_back(4);
65
        }
66
        else if (ha <= hc && hc <= hb) {
67
            int d = hb - hc;
68
            b >>= d;
69
            for (int i = 0; i < d; ++i) res.emplace_back(2);
70
            for (int i = hc; i >= 0; --i) {
71
                if ((a >> i & 1) ^ (c >> i & 1)) {
72
                    a ^= b;
73
                    res.emplace_back(3);
74
                }
75
                b >>= 1;
76
                res.emplace_back(2);
77
            }
78
            res.emplace_back(4);
79
        }
80
        else if (hb <= ha && ha <= hc) {
81
            res.emplace_back(4);
82
            b ^= a;
83
            int d = hc - ha;
84
            for (int i = ha; i >= 0; --i) {
85
                if ((a >> i & 1) ^ (c >> i + d & 1)) {
86
                    a ^= b;
87
                    res.emplace_back(3);
88
                }
89
                b >>= 1;
90
                res.emplace_back(2);
91
            }
92
            res.pop_back();
93
            d = hc - ha;
94
            for (int i = d - 1; i >= 0; --i) {
95
                res.emplace_back(1);
96
                if (c >> i & 1) res.emplace_back(3);
97
            }
98
            res.emplace_back(2);
99
            res.emplace_back(4);
100
        }
101
        else if (hb <= hc && hc <= ha) {
102
            res.emplace_back(4);
103
            b ^= a;
104
            for (int i = ha; i >= 0; --i) {
105
                if ((a >> i & 1) ^ (c >> i & 1)) {
106
                    a ^= b;
107
                    res.emplace_back(3);
108
                }
109
                b >>= 1;
110
                res.emplace_back(2);
111
            }
112
            res.emplace_back(4);
113
        }
114
        else if (hc <= hb && hb <= ha) {
115
            res.emplace_back(4);
116
            b ^= a;
117
            for (int i = ha; i >= 0; --i) {
118
                if ((a >> i & 1) ^ (c >> i & 1)) {
119
                    a ^= b;
120
                    res.emplace_back(3);
121
                }
122
                b >>= 1;
123
                res.emplace_back(2);
124
            }
125
            res.emplace_back(4);
126
        }
127
        else {
128
            return 1;
129
        }
130
        printf("%ld\n", res.size());
131
        for (int i : res) printf("%d ", i);
132
        printf("\n");
133
    }
134
    return 0;
135
}

D. Distant Control ^队友#

赛后补的时候还想错了好几次，用 dp 的惯性我只想到左边长度够了能一直往右开，没想到右边长度够了能往左边开……

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 200010;
6
int a[N];
7

8
int solve() {
9
    int n, m;
10
    scanf("%d%d", &n, &m);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%1d", &a[i]);
13
        a[i] += a[i - 1];
14
    }
15
    for (int i = 1; i <= n - m; ++i) {
16
        if (a[i + m] - a[i - 1] == 0) return n;
17
    }
18
    for (int i = 1; i <= n - m + 1; ++i) {
19
        if (a[i + m - 1] - a[i - 1] == m) return n;
20
    }
21
    return a[n];
22
}
23

24
int main() {
25
    int T;
26
    scanf("%d", &T);
27
    while (T--) {
28
        printf("%d\n", solve());
29
    }
30
    return 0;
31
}

E. Equal ^队友#

这道当时没少踩坑，题解给的是 XOR hashing，我们当时用的是 $O(n \ln n)$ 的方法，刚开始因为没特判只有两个数的情况 WA 了四次，然后好像又因为前面有问题 T 了一次。

1
#include <iostream>
2
#include <cmath>
3
#include <vector>
4
#include <cstdlib>
5
#include <random>
6

7
using namespace std;
8
const int N = 1000010;
9
const int M = 5000010;
10
bool f[M];
11
int a[N];
12
uint64_t hs[M];
13
vector<int> primes;
14

15
void init() {
16
    mt19937_64 rnd(time(0));
17
    int n = 5000000;
18
    for (int i = 2; i <= n; ++i) {
19
        if (!f[i]) {
20
            hs[i] = rnd();
21
            primes.emplace_back(i);
22
        }
23
        for (int p : primes) {
24
            if (i * p > n) break;
25
            f[i * p] = true;
26
            hs[i * p] = hs[i] ^ hs[p];
27
            if (i % p == 0) break;
28
        }
29
    }
30
}
31

32
int main() {
33
    init();
34
    int T;
35
    scanf("%d", &T);
36
    while (T--) {
37
        int n;
38
        scanf("%d", &n);
39
        for (int i = 1; i <= n; ++i) {
40
            scanf("%d", &a[i]);
41
        }
42
        if (n & 1) {
43
            printf("YES\n");
44
            continue;
45
        }
46
        else if (n == 2) {
47
            if (a[1] != a[2]) printf("NO\n");
48
            else printf("YES\n");
49
            continue;
50
        }
51
        uint64_t h = 0;
52
        for (int i = 1; i <= n; ++i) {
53
            h ^= hs[a[i]];
54
        }
55
        if (h) printf("NO\n");
56
        else printf("YES\n");
57
    }
58
    return 0;
59
}

F. Flower ^队友#

本场签到题。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        int n, a, b;
10
        scanf("%d%d%d", &n, &a, &b);
11
        if (n <= a) printf("Sayonara\n");
12
        else {
13
            n %= (a + b);
14
            if (n > a) printf("0\n");
15
            else printf("%d\n", n);
16
        }
17
    }
18
    return 0;
19
}

H. Head out to the Target ^队友#

这道没看着呢么难，实际上可以用比较暴力的办法处理，刚开始我们都没意识到，还 WA 了一发，后来注意到的时候我正在写 B 题的大模拟，打断了我五六分钟左右就过了。

然后我刚开始补题的时候又重蹈覆辙，敲了一个数剖 + 线段树上去，又挂了……

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5
const int N = 1000010;
6
vector<int> ed[N];
7
int f[N][20];
8
bool flg[N];
9
int tr[N * 4];
10
int n, k;
11

12
void dfs(int x) {
13
    for (int i = 1; i < 20; ++i) {
14
        f[x][i] = f[f[x][i - 1]][i - 1];
15
    }
16
    for (int y : ed[x]) {
17
        if (y == f[x][0]) continue;
18
        dfs(y);
19
    }
20
}
21

22
int main() {
23
    // freopen("input", "r", stdin);
24
    scanf("%d%d", &n, &k);
25
    for (int i = 2; i <= n; ++i) {
26
        scanf("%d", &f[i][0]);
27
        ed[f[i][0]].emplace_back(i);
28
    }
29
    dfs(1);
30
    flg[0] = flg[1] = true;
31
    while (k--) {
32
        int u, l, r;
33
        scanf("%d%d%d", &u, &l, &r);
34
        if (flg[u]) {
35
            printf("%d\n", l);
36
            return 0;
37
        }
38
        int dis = 0, x = u;
39
        for (int i = 19; i >= 0; --i) {
40
            if (!flg[f[x][i]]) {
41
                x = f[x][i], dis |= 1 << i;
42
            }
43
        }
44
        // cout << "found: " << x << endl;
45
        // cout << "dis :" << dis << endl;
46
        // cout << flg[6] << endl;
47
        if (dis <= r - l) {
48
            printf("%d\n", l + dis);
49
            return 0;
50
        }
51
        dis -= r - l;
52
        for (int i = 0; i < 20; ++i) {
53
            if (dis >> i & 1) u = f[u][i];
54
        }
55
        // 暴戾
56
        // cout << "marking" << endl;
57
        for (int i = 0; i < r - l + 1; ++i) {
58
            flg[u] = true;
59
            // cout << u << ' ';
60
            u = f[u][0];
61
        }
62
//         cout << endl;
63
        // break;
64
    }
65
    // cout << query(8) << endl;
66
    printf("-1\n");
67
    return 0;
68
}

J. Jetton#

这道是我写的，刚开始没发现特殊性质，感觉直接暴力也未尝不可，甚至还打表验证了一下，后来不出意外就出意外了，T 了一发之后仔细思考了一下，然后换成一个式子每次 $O (log_2 \left(x + y\right))$ 稳定解决了。

被卡的地方是出现死循环（-1）的情况，不合法情况的循环节可能比较大。

1
#include <iostream>
2
#include <set>
3

4
using namespace std;
5

6
set<pair<int, int> > s;
7

8

9
int gcd(int a, int b) {
10
    return b ? gcd(b, a % b) : a;
11
}
12

13
int main() {
14
    int T;
15
    scanf("%d", &T);
16
    while (T--) {
17
        int x, y;
18
        scanf("%d%d", &x, &y);
19
        int g = gcd(x, y);
20
        x /= g, y /= g;
21
        if (x + y & 1) {
22
            printf("-1\n");
23
            continue;
24
        }
25
        s.clear();
26
        s.insert({x, y});
27
        int t = 0;
28
        bool f = true;
29
        while (x && y) {
30
            if (x > y) swap(x, y);
31
            y -= x, x *= 2;
32
            t++;
33
            if (x > y) swap(x, y);
34
            if (s.find({x, y}) != s.end()) {
35
                f = false;
36
                break;
37
            }
38
            s.insert({x, y});
39
        }
40
        if (f) printf("%d\n", t);
41
        else printf("-1\n");
42
    }
43
    return 0;
44
}

Star's Blog

A. Ad-hoc Newbie#

B. Bitwise Puzzle#

D. Distant Control 队友#

E. Equal 队友#

F. Flower 队友#

H. Head out to the Target 队友#

J. Jetton#

D. Distant Control ^队友#

E. Equal ^队友#

F. Flower ^队友#

H. Head out to the Target ^队友#