🎈2025牛客暑寒假多校训练营Day2

A 一起奏响历史之音！

题意

中国传统五声调中包含 1、2、3、5、6，判断一个乐谱是否仅由全部或部分五声调铺成。

思路

按题意判断即可。

代码

1
void solve() {
2
  bool flag = true;
3
  set<ll> st = {1, 2, 3, 5, 6};
4
  ll x;
5
  while (cin >> x) {
6
    if (st.find(x) == st.end()) {
7
      flag = false;
8
    }
9
  }
10
  if (flag) {
11
    cout << "YES\n";
12
  } else {
13
    cout << "NO\n";
14
  }
15
}

B 能去你家蹭口饭吃吗

题意

给出一个数组 $a$ ，找到一个整数，要求整数尽可能大，但是至少要比数组中一半数量的数小。

数据范围

$1\leq n\leq 5e5$
$1\leq a_i\leq 1e6$

思路

如果数组长度为奇数，则取中位数-1，即 $a[n-n/2]-1$ 。

如果数组长度为偶数，则取下标更大的中位数-1，即 $a[n/2+1]-1$ 。

代码

1
void solve() {
2
  ll n;
3
  cin >> n;
4
  for (ll i = 1; i <= n; i++) {
5
    cin >> a[i];
6
  }
7
  sort(a + 1, a + 1 + n);
8
  if (n & 1)
9
    cout << a[n - n / 2] - 1 << '\n';
10
  else
11
    cout << a[n / 2 + 1] - 1 << '\n';
12
}

D 字符串里串

题意

定义字符串 $s$ 的可爱度 $k$ ：最大的满足存在长度为 $k$ 的连续子串 $a$ 和严格不连续子串 $b$ ，使得 $a=b$ 。

给出字符串 $s$ ，求其可爱度。

数据范围

$3\leq m \leq 2e5$

思路

$b$ 是不连续子串，可以设计 $a$ 和 $b$ 仅最后一位或开头一位的在原串中的位置不同，那么只需要寻找符合条件的数量大于等于 2 的字母，并比较分别去掉两端得到的最长的串的长度。

代码

1
void solve() {
2
  ll n;
3
  string s;
4
  cin >> n >> s;
5
  s = " " + s;
6
  map<char, vector<ll>> mp;
7
  for (ll i = 1; i <= n; i++) {
8
    char c = s[i];
9
    mp[c].push_back(i);
10
  }
11
  ll ans = 0;
12
  for (auto [c, v] : mp) {
13
    if (v.size() >= 2) {
14
      ll m = v.size();
15
      ans = max(ans, v[m - 2]);
16
    }
17
  }
18
  for (auto [c, v] : mp) {
19
    if (v.size() >= 2) {
20
      ll m = v.size();
21
      ans = max(ans, n - v[1] + 1);
22
    }
23
  }
24
  cout << ans << '\n';
25
}

C 字符串外串

题意

定义字符串 $s$ 的可爱度 $k$ ：最大的满足存在长度为 $k$ 的连续子串 $a$ 和严格不连续子串 $b$ ，使得 $a=b$ 。构造长度为 $n$ 的由小写字母组成的字符串，使其可爱度为 $m$ ，或报告没有这样的合法字符串。

数据范围

$3\leq m\leq n\leq n\leq 2e5$

思路

$a,b$ 两种字符串至少要有 1 位对应原串的位置不同，当 $n=m$ 时显然无解。

设字符串 $t$ 是 $a,b$ 左端对齐之后公共的部分，长度为 $m-1$ ，小写字母只有 26 个，当 $n-m\gt 26$ 时，不管怎么填后 $n-m$ 的字母，都不可能与让所有在 $i\geq m$ 的范围内的字母只出现一次，出现多次则可爱度会增加。按照这样的思路构造前 $m-1$ 长度的字符串，并保证在后一半的部分中字符 $s[m-1]$ 出现且仅出现一次。

代码

1
void solve() {
2
  ll n, m;
3
  cin >> n >> m;
4
  if (n - m < 1) {
5
    cout << "NO\n";
6
    return;
7
  }
8
  string s;
9
  if (m == n - 1) {
10
    for (ll i = 1; i <= n; i++) {
11
      if (i == n - 1 || i == n) {
12
        s.push_back('b');
13
      } else {
14
        s.push_back('a');
15
      }
16
    }
17
  } else if (n - m <= 26) {
18
    for (ll i = 0; i < n; i++) {
19
      s.push_back('a' + i % 26);
20
    }
21
    s.back() = s[m - 1];
22
  } else {
23
    cout << "NO\n";
24
    return;
25
  }
26
  cout << "YES\n" << s << '\n';
27
}

E 一起走很长的路！

题意

一列多米诺骨牌，质量是 $a_i$ ，有 $q$ 次询问，询问一个区间 $[l,r]$ ，推倒第 $l$ 位的多米诺骨牌，如果 $\sum_{i=l}^{i-1}\geq a_i$ ，则第 $a_i$ 块可以顺利倒下，为了使第 $r$ 块可以顺利倒下，可以进行一种操作：选择某个多米诺骨牌，将其质量+1 或-1，对每个询问返回最少的可以推倒 $r$ 的操作数。

数据范围

$1\leq n,q\leq 2e5$
$1\leq a_i\leq 1e9$
$1\leq l\leq r\leq n$

思路

对于一个区间，如果要进行操作时，肯定是将+1 加在第 $l$ 位的牌上。

当 $l=1$ 时，容易直到，想要第 $i$ 块牌倒下，需要 $\max(a_i-pre_{i-1},0)$ 的操作次数， $pre_i$ 是前 $i$ 项的质量和，故在整个区间上，只需要取 $\max(a_i-pre_{i-1}),(l+1\leq i\leq r)$ 。

在区间 $[l,r]$ 中，如果要推倒第 $i$ 块牌，则需要构造新的以 $l$ 为左端点的 $pre$ ，这个 $pre$ 的值可以由 $pre_i-pre_{l-1}$ 推倒，代入上式，则答案是 $\max(a_i-(pre_i-pre_{l-1}))$ 。用某种数据结构维护区间最大值。

代码

1
// ST表
2
ll dp[maxn][30];
3
void rmq_st(ll n) {
4
  for (ll i = 1; i <= n; i++) {
5
    dp[i][0] = b[i]; // 2^0
6
  }
7
  ll m = log(1 * n) / log(2.0);
8
  for (ll j = 1; j <= m; j++) {
9
    ll t = n - (1 << j) + 1;
10
    for (ll i = 1; i <= t; i++) {
11
      dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
12
    }
13
  }
14
}
15
ll rmq_find(ll l, ll r) { // 从l开始,长度为r的区间
16
  ll k = log(1.0 * (r - l + 1)) / log(2.0);
17
  return max(dp[l][k], dp[r - (1 << k) + 1][k]);
18
}
19

20
void solve() {
21
  ll n, q;
22
  cin >> n >> q;
23
  for (ll i = 1; i <= n; i++) {
24
    cin >> a[i];
25
    pre[i] = pre[i - 1] + a[i];
26
    b[i] = a[i] - pre[i - 1];
27
  }
28
  rmq_st(n);
29
  while (q--) {
30
    ll l, r;
31
    cin >> l >> r;
32
    if (l == r) {
33
      cout << "0\n";
34
      continue;
35
    }
36
    // ans=max(a[i]-(pre[i]-pre[l-1]))
37
    ll t = rmq_find(l + 1, r) + pre[l - 1]; // [l+1,r]需要推倒
38
    ll ans = max(t, 0ll);
39
    cout << ans << '\n';
40
  }
41
}

F 一起找神秘的数！

题意

在区间 $[l,r]$ 中找到两个数 $x,y$ ，使之满足 $x+y=(x\ordinarycolon y)+(x \land y)+(x \oplus y)$ ，求这样的数对的数量。

数据范围

$1\leq T \leq 2e5$
$0\leq l\leq r\leq 1e18$

思路

打表猜结论，发现只有 $x=y$ 时等式成立。

代码

1
void solve() {
2
  ll l, r;
3
  cin >> l >> r;
4
  cout << r - l + 1 << '\n';
5
}

G 一起铸最好的剑！

题意

在 $m$ 的幂次中找到最接近 $n$ 的数。

数据范围

$1\leq T \leq 1e5$
$1\leq n,m\leq 1e9$

思路

模拟。

代码

1
void solve() {
2
  ll n, m;
3
  cin >> n >> m;
4
  if (m == 1) {
5
    cout << "1\n";
6
    return;
7
  }
8
  p[0] = 1, p[1] = m;
9
  ll pi = 1;
10
  ll mx = abs(p[pi] - n);
11
  ll i = 1;
12
  for (; p[i] <= n; i++) {
13
    if (abs(p[i] - n) < mx) {
14
      pi = i;
15
      mx = abs(p[i] - n);
16
    }
17
    p[i + 1] = p[i] * m;
18
  }
19
  if (abs(p[i] - n) < mx) {
20
    pi = i;
21
    mx = abs(p[i] - n);
22
  }
23
  cout << pi << '\n';
24
}

H 一起画很大的圆！

题意

在矩形的边界上找三个不共线的点，使得过这三个点确定的圆的面积最大。

数据范围

$-1e6\leq a,b,c,d\leq 1e6$

思路

合适的点的候选在矩形的四个直角附近一个单位长度的点中选，暴力枚举三个点，并判断取半径最大的圆。

代码

1
ld getcir2(pll p1, pll p2, pll p3) {
2
  auto [x1, y1] = p1;
3
  auto [x2, y2] = p2;
4
  auto [x3, y3] = p3;
5
  ld r;
6
  ld a = x1 - x2, b = y1 - y2, c = x1 - x3, d = y1 - y3;
7
  ld e = ((x1 * x1 - x2 * x2) + (y1 * y1 - y2 * y2)) / 2.0;
8
  ld f = ((x1 * x1 - x3 * x3) + (y1 * y1 - y3 * y3)) / 2.0;
9
  ld det = b * c - a * d;
10
  if (fabs(det) < 1e-5) {
11
    r = -1;
12
    return r;
13
  }
14
  ld x0 = -(d * e - b * f) / det;
15
  ld y0 = -(a * f - c * e) / det;
16
  r = hypot(x1 - x0, y1 - y0);
17
  return r;
18
}
19

20
void solve() {
21
  ll a, b, c, d;
22
  cin >> a >> b >> c >> d;
23
  vector<pll> v = {
24
      {a, c}, {a + 1, c}, {a, c + 1}, {a, d}, {a + 1, d}, {a, d - 1},
25
      {b, c}, {b - 1, c}, {b, c + 1}, {b, d}, {b - 1, d}, {b, d - 1},
26
  };
27
  pll p1 = {a, c}, p2 = {a + 1, c}, p3 = {a, c + 1};
28
  ld r = getcir2(p1, p2, p3);
29
  for (ll i = 0; i < (ll)v.size(); i++) {
30
    for (ll j = 0; j < (ll)v.size(); j++) {
31
      for (ll k = 0; k < (ll)v.size(); k++) {
32
        ld ri = getcir2(v[i], v[j], v[k]);
33
        if (ri != -1 && r < ri) {
34
          r = ri;
35
          p1 = v[i], p2 = v[j], p3 = v[k];
36
        }
37
      }
38
    }
39
  }
40
  cout << p1.first << ' ' << p1.second << '\n';
41
  cout << p2.first << ' ' << p2.second << '\n';
42
  cout << p3.first << ' ' << p3.second << '\n';
43
}

I

题意

数据范围

思路

代码

J 数据时间？

题意

有 $n$ 个数据，每条数据由user_id、login_date、login_time组成，表示员工号，登录日期和登录时间。员工号是不超过 $1e20$ 的整数，登录日期是一个YYYY-MM-DD模式的日期，登录时间是hh:mm:ss模式的时间。

现在查询h年m月的员工在通勤时间（07:00:00-09:00:00和18:00:00-20:00:00）、午休时间（11:00:00-13:00:00）和临睡时间（22:00:00-01:00:00）的登录人次情况，同一个人在同一个时间段的多次登录算作一人次。时间段均包含边界。

数据范围

$1\leq n\leq 1e5$
$2000\leq h\leq 2030;1\leq m\leq 12$
$1\leq user_{id}\leq 10^{20}$
日期和时间的格式如题意所述。

思路

按题意模拟。

代码

1
void solve() {
2
  ll n, h, m;
3
  cin >> n >> h >> m;
4
  map<string, vector<pair<string, string>>> mp;
5
  map<string, bool> mp1, mp2, mp3;
6
  for (ll i = 1; i <= n; i++) {
7
    string id, t;
8
    ll dy, dm, dd;
9
    char c;
10
    cin >> id >> dy >> c >> dm >> c >> dd >> t;
11
    if (dy == h && dm == m) {
12
      string s = t;
13
      ll st = ((s[0] - '0') * 10 + (s[1] - '0')) * 3600 +
14
              ((s[3] - '0') * 10 + (s[4] - '0')) * 60 + (s[6] - '0') * 10 +
15
              (s[7] - '0');
16
      if ((st >= 7 * 3600 && st <= 9 * 3600)||(st >= 18 * 3600 && st <= 20 * 3600)) {
17
        mp1[id] = true;
18
      } else if (st >= 11 * 3600 && st <= 13 * 3600) {
19
        mp2[id] = true;
20
      } else if ((st >= 22 * 3600 && st <= 24 * 3600) ||
21
                 (st >= 0 * 3600 && st <= 1 * 3600)) {
22
        mp3[id] = true;
23
      }
24
    }
25
  }
26
  cout << mp1.size() << ' ' << mp2.size() << ' ' << mp3.size() << '\n';
27
}

K 可以分开吗？

题意

有一块 $n\times m$ 的方块组成的矩阵，其中有一些蓝色方块，其余为灰色方块，定义两块方块的连通的：只有当两块方块在四连通方向有共边。

当一个蓝色极大连通块可以脱离矩阵时，其任何蓝色方块不与任何灰色方块有共边。现在先在矩阵中通过移除灰色方块，取出一个蓝色极大连通块，求最少的操作次数。

数据范围

$1\leq n,m\leq 500$

思路

并查集。

遍历所有的蓝色方块，并查集维护每个蓝色方块寻找它属于的蓝色极大连通块，再通过遍历这些连通块的每个小方块的周围四格，统计需要敲掉的灰色方块的数量。

代码

1
ll n, m;
2
ll a[maxn], b[maxn];
3
ll fa[maxn];
4
char maz[600][600];
5

6
ll find(ll x) {
7
  if (fa[x] == x) {
8
    return x;
9
  }
10
  return fa[x] = find(fa[x]);
11
}
12
void merge(ll u, ll v) {
13
  ll fu = find(u), fv = find(v);
14
  if (fu == fv) {
15
    return;
16
  }
17
  fa[fu] = fv;
18
}
19
vector<pll> dxy = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
20

21
void solve() {
22
  cin >> n >> m;
23

24
  for (ll i = 0; i <= (n + 5) * (m + 5); i++) {
25
    fa[i] = i;
26
  }
27

28
  vector<pll> v;
29
  for (ll i = 1; i <= n; i++) {
30
    for (ll j = 1; j <= m; j++) {
31
      cin >> maz[i][j];
32
      if (maz[i][j] == '1') {
33
        v.push_back({i, j});
34
      }
35
    }
36
  }
37

38
  // 并查集
39
  for (auto [x, y] : v) {
40
    for (auto [dx, dy] : dxy) {
41
      ll px = dx + x, py = dy + y;
42
      if (maz[px][py] == '1') {
43
        merge((px - 1) * m + py, (x - 1) * m + y);
44
      }
45
    }
46
  }
47
  map<ll, vector<pll>> mp;
48
  for (auto i : v) {
49
    ll x = (i.first - 1) * m + i.second;
50
    ll fx = find(x);
51
    mp[fx].push_back(i);
52
  }
53

54
  ll res = n * m - v.size();
55
  for (auto [i, vi] : mp) {
56
    set<pll> st;
57
    for (auto [x, y] : vi) {
58
      for (auto [dx, dy] : dxy) {
59
        ll px = dx + x, py = dy + y;
60
        if (px < 1 || px > n || py < 1 || py > m)
61
          continue;
62
        if (maz[px][py] == '0') {
63
          st.insert({px, py});
64
        }
65
      }
66
    }
67
    res = min(res, (ll)st.size());
68
  }
69
  cout << res << '\n';
70
}

L

题意

数据范围

思路

代码

M 那是我们的影子

题意

在 $3\times n$ 的矩阵中，每个格子要么是 $1\sim 9$ 的数字，要么是?。求将所有的?填入 $1\sim 9$ 的数字，任意 $3\times 3$ 的九宫格中的数字都不重复，求合法的填写方式的数量，答案对 $1e9+7$ 取模。

数据范围

$3\leq n\leq 1e5$

思路

易知，所有 $i\mod 3$ 相同的列的数字组成都是一样的。

几种无合法解的情况：

某一列有重复的数字
某个 $i\mod 3$ 的组中数字的种数多于 3 种

排除不合法的情况后，进行排列组合，将所有九宫格的数字位置情况汇总成一个标准九宫格后，里面有一些位置依然是?，数字不确定，这些不确定的 $k$ 个位置对应 $k$ 个没有出现过的数字，将其分成 $3$ 组，分别对应每列的空缺位，这样的组合方法有 $\binom{k}{col_0}\times \binom{k-col_0}{col_1}\times \binom{k-col_0-col_1}{col_2}$ 种。

完成上面这一步之后，相当于九宫格的每列对应的数集合是确定的。接下来遍历每一列，乘上在空缺位上的全排列数。

代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
typedef double ld;
6
typedef unsigned long ul;
7
typedef long long ll;
8
typedef unsigned long long ull;
9
typedef pair<ll, ll> pll;
10

11
const ll maxn = 2e6 + 50;
12
const ll inf = 0x3f3f3f3f3f;
13
const ll mo998 = 998244353;
14
const ll mo1e9 = 1000000007;
15

16
ll qpow(ll a, ll b) {
17
  ll ret = 1;
18
  while (b) {
19
    if (b & 1)
20
      ret = (ret * a) % mo1e9;
21
    a = a * a % mo1e9;
22
    b >>= 1;
23
  }
24
  return ret;
25
}
26
ll inv(ll x) { return qpow(x, mo1e9 - 2); }
27

28
// 逆元求组合数
29
ll fz[maxn], fm[maxn];
30
ll C(ll n, ll m) {
31
  if (n < m)
32
    return 0ll;
33
  if (n == m)
34
    return 1ll;
35
  return fz[n] * fm[m] % mo1e9 * fm[n - m] % mo1e9;
36
}
37
ll A(ll x, ll y) { return fz[x] * C(x, y) % mo1e9; }
38

39
ll maz[5][maxn];
40

41
void solve() {
42
  ll n;
43
  cin >> n;
44
  vector<string> s(4);
45
  cin >> s[1] >> s[2] >> s[3];
46

47
  // 第0,3,6...相同，i%3相同的数字组成一模一样
48
  vector<set<ll>> col(5, set<ll>()); // 第0/1/2列的数字
49
  vector<ll> q(n + 10, 0ll);         // 每列的?数量
50

51
  for (ll i = 0; i < n; i++) {
52
    set<ll> tmp;
53
    for (ll t = 1; t <= 3; t++) {
54
      char c = s[t][i];
55
      if (c != '?') {
56
        maz[t][i] = c - '0';
57
        if (tmp.count(maz[t][i])) { // 列有重复
58
          cout << "0\n";
59
          return;
60
        }
61
        tmp.insert(maz[t][i]);
62
        col[i % 3].insert(maz[t][i]);
63
        if (col[i % 3].size() > 3) { // 种数不合法
64
          cout << "0\n";
65
          return;
66
        }
67
      } else {
68
        maz[t][i] = -1;
69
        q[i]++;
70
      }
71
    }
72
  }
73

74
  set<ll> usd;
75
  for (ll i = 0; i < 3; i++) {
76
    for (auto j : col[i]) {
77
      usd.insert(j);
78
    }
79
  }
80
  vector<ll> v = {
81
      3 - (ll)col[0].size(),
82
      3 - (ll)col[1].size(),
83
      3 - (ll)col[2].size(),
84
  };
85
  ll tot = v[0] + v[1] + v[2];
86
  if (tot + usd.size() != 9) {
87
    cout << "0\n";
88
    return;
89
  }
90

91
  ll ans = 1ll * C(tot, v[0]) * C(tot - v[0], v[1]) % mo1e9;
92

93
  for (ll i = 0; i < n; i++) {
94
    ll k = q[i];
95
    ans = ans * A(k, k) % mo1e9;
96
  }
97

98
  cout << ans << '\n';
99
}
100

101
void init() {
102
  ll w = maxn - 10;
103
  fz[0] = fm[0] = 1;
104
  for (ll i = 1; i <= w; i++) {
105
    fz[i] = fz[i - 1] * i % mo1e9;
106
  }
107
  fm[w] = inv(fz[w]);
108
  for (ll i = w - 1; i >= 1; i--) {
109
    fm[i] = fm[i + 1] * (i + 1) % mo1e9;
110
  }
111
}
112

113
int main(void) {
114
  ios::sync_with_stdio(false);
115
  cin.tie(0);
116
  ll _t = 1;
117
  cin >> _t;
118
  cin.get();
119
  init();
120
  while (_t--)
121
    solve();
122

123
  return 0;
124
}