VP 记录 - 2022 CCPC 黑龙江省赛

发表于 更新于 分类于 ， ， 合著者：Foi 本文字数： 480 阅读时长 ≈ 2 分钟

比赛链接

题目概览

题号 标题 做法
A Bookshelf Filling 二分
B Lovely Fish
C Tree Division 贪心 + DP
D Collision Detector 计算几何
E Exclusive Multiplication Möbius 反演
F 342 and Xiangqi 最短路
G Chevonne's Necklace 背包
H Kanbun 模拟
I Equal Sum Arrays 签到
J JOJO's Happy Tree Friends
K Monkey Joe 树状数组 + 主席树
L Let's Swap KMP / Hash

官方题解

A - Bookshelf Filling

代码参考

Show code

A.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#define int long long
using namespace std;
int a, b, c, d, n, m, h;
int Pd(int x) { return (h - b) * ((d + m - x) / b) + c >= x ? 1 : 0; }
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int T;
  cin >> T;
  while (T--) {
    cin >> a >> b >> n >> m >> h;
    c = (h - a) * (n / b), d = n % b;
    int l = 0, r = m - 1, Ans = 0, Mid;
    while (r >= l) {
      Mid = (l + r) >> 1;
      if (Pd(Mid)) l = Mid + 1, Ans = Mid;
      else r = Mid - 1;
    }
    cout << n + m - Ans << '\n';
  }
  return 0;
}

B - Lovely Fish

代码参考

Show code

C - Tree Division

代码参考

Show code

C.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n, num, h[N], a[N], f[N][2][2];
struct node {
  int to, nxt;
} e[N << 1];
void ins(int x, int y) {
  e[++num].to = y;
  e[num].nxt = h[x];
  h[x] = num;
  e[++num].to = x;
  e[num].nxt = h[y];
  h[y] = num;
}
void dfs(int u, int father) {
  int sz = 0;
  int fa = 1, fb = 1;
  f[u][0][0] = a[u];
  f[u][0][1] = 0;
  f[u][1][0] = n + 1;
  f[u][1][1] = a[u];
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == father) continue;
    ++sz;
    dfs(v, u);
    if (f[v][1][0] <= a[u] && f[v][0][0] <= a[u]) fa = 0;
    int t = n + 1;
    if (f[v][1][0] > a[u]) { t = min(f[v][1][1], t); }
    if (f[v][0][0] > a[u]) { t = min(f[v][0][1], t); }
    f[u][0][1] = max(f[u][0][1], t);
    t = 0;
    if (f[v][0][1] >= a[u] && f[v][1][1] >= a[u]) fb = 0;
    if (f[v][0][1] < a[u]) { t = max(f[v][0][0], t); }
    if (f[v][1][1] < a[u]) { t = max(f[v][1][0], t); }
    f[u][1][0] = min(f[u][1][0], t);
  }
  if (!sz) {
    f[u][0][0] = a[u];
    f[u][0][1] = 0;
    f[u][1][0] = n + 1;
    f[u][1][1] = a[u];
  } else {
    if (!fa) {
      f[u][0][0] = 0;
      f[u][0][1] = n + 1;
    }
    if (!fb) {
      f[u][1][0] = 0;
      f[u][1][1] = n + 1;
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); }
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    ins(x, y);
  }
  memset(f, -1, sizeof(f));
  dfs(1, 0);
  if (f[1][0][0] == a[1] || f[1][1][1] == a[1]) puts("YES");
  else puts("NO");
  return 0;
}

D - Collision Detector

代码参考

Show code

D.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int a1, a2, b1, b2, c1, c2;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d%d%d", &a1, &a2, &b1, &b2, &c1, &c2);
    double BC2 = (b1 - c1) * (b1 - c1) + (b2 - c2) * (b2 - c2);
    double AB2 = (b1 - a1) * (b1 - a1) + (b2 - a2) * (b2 - a2);
    double zuo = 2.0 * (sqrt(BC2 - 4) - sqrt(AB2 - 4));
    double you = 1.0 * (b1 - a1) * (c1 - b1) + (b2 - a2) * (c2 - b2);
    puts(zuo < you ? "yes" : "no");
  }
  return 0;
}

E - Exclusive Multiplication

解题思路

不妨设 \(b_i\) 无平方因子，则所求即为

\[ \sum_{i=1}^m\sum_{j=1}^mf(i,j)\frac{ij}{(i,j)^2} \]

其中

  • \(m=\max\{b_1,...,b_n\}\)
  • \(f(i,j)=[i,j\in \{b_1,...,b_n\}]\)

然后就是经典莫反，可化为

\[ \sum_{d=1}^mF(d)(\mu*\{n^{-2}\})(d) \]

其中

\[ F(d)=\left(\sum_{i=1}^n b_i[d|b_i]\right)^2 \]

复杂度

\(O(n\log n)\)

代码参考

Show code

E.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (i64 i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const i64 MOD = 1e9 + 7, INV2 = 5e8 + 4;
constexpr i64 qpow(i64 a, i64 b = MOD - 2, const i64 &mod = MOD) {
  i64 res(1);
  a %= mod;
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
};
const int N = 2e5 + 5, P = 2e5 + 5;
bool vis[N];
i64 prime[P], cnt_prime;
i64 invp2[P], f[N];
void init_prime(const i64 &n = N - 1) {
  f[1] = 1;
  for (i64 i = 2; i <= n; ++i) {
    if (!vis[i]) {
      prime[++cnt_prime] = i;
      invp2[cnt_prime] = qpow(i * i);
      f[i] = (invp2[cnt_prime] + MOD - 1) % MOD;
    }
    for (i64 j = 1; j <= cnt_prime && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        f[i * prime[j]] = (MOD - f[i] * invp2[j] % MOD + 1) % MOD;
        break;
      }
      f[i * prime[j]] = f[i] * f[prime[j]] % MOD;
    }
  }
}
i64 a[N], g[N];
auto solve() -> void {
  i64 n;
  cin >> n;
  i64 max_num = 0;
  _for(i, 1, n, x, y, cnt) {
    cin >> x;
    y = 1;
    _for(j, 1, cnt_prime) {
      if (prime[j] > sqrt(x)) break;
      if (x % prime[j]) continue;
      cnt = 0;
      while (x % prime[j] == 0) {
        ++cnt;
        x /= prime[j];
      }
      if (cnt & 1) y *= prime[j];
    }
    chkmax(max_num, x * y);
    ++a[x * y];
  }
  _for(i, 1, max_num)
    for (i64 j = 1; i * j <= max_num; ++j)
      (g[i] += i * j % MOD * a[i * j] % MOD) %= MOD;
  _for(i, 1, max_num) g[i] = g[i] * g[i] % MOD;
  i64 ans = 0;
  _for(i, 1, max_num) (ans += f[i] * g[i] % MOD) %= MOD;
  cout << (ans + MOD - n) % MOD * INV2 % MOD;
}
int main() {
#ifdef _LOCAL_
  auto _CLOCK_ST = std::chrono::steady_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  init_prime();
#ifdef MULTI_CASES
  int _t;
  cin >> _t;
  while (_t--)
#endif
    solve();
#ifdef _LOCAL_
  std::clog << "\n---\n"
            << "Time used: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(
                 std::chrono::steady_clock::now() - _CLOCK_ST)
                 .count()
            << " ms" << std::endl;
#endif
  return 0;
}

F - 342 and Xiangqi

代码参考

Show code

F.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <iostream>
using namespace std;
const int A[8][8] = {{0, 0, 0, 0, 0, 0, 0, 0},
                     {0, 0, 1, 1, 2, 3, 3, 4},
                     {0, 1, 0, 2, 1, 2, 2, 3},
                     {0, 1, 2, 0, 1, 2, 2, 3},
                     {0, 2, 1, 1, 0, 1, 1, 2},
                     {0, 3, 2, 2, 1, 0, 2, 1},
                     {0, 3, 2, 2, 1, 2, 0, 1},
                     {0, 4, 3, 3, 2, 1, 1, 0}};
int main() {
  int T, a1, a2, b1, b2;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d%d", &a1, &a2, &b1, &b2);
    printf("%d\n", min(A[a1][b1] + A[a2][b2], A[a1][b2] + A[a2][b1]));
  }
  return 0;
}

G - Chevonne's Necklace

代码参考

Show code

G.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <iostream>
#define inc(i) (++(i))
#define dec(i) (--(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; dec(i))
using namespace std;
const int N = 2000 + 7, Mod = 998244353;
int n, A[N], Dp[N];
int main() {
  scanf("%d", &n);
  Rep(i, 1, n) scanf("%d", A + i);
  Dp[0] = 1;
  Rep(i, 1, n) if (A[i]) rep(j, n, A[i])(Dp[j] += Dp[j - A[i]]) %= Mod;
  int Ans = n;
  while (!Dp[Ans]) dec(Ans);
  printf("%d %d", Ans, Dp[Ans]);
  return 0;
}

H - Kanbun

代码参考

Show code

H.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n;
char str[N];
stack<int> q;
int main() {
  scanf("%d", &n);
  scanf("%s", str + 1);
  for (int i = 1; i <= n; ++i) {
    if (str[i] == '-') printf("%d ", i);
    else if (str[i] == '(') {
      q.push(i);
    } else {
      printf("%d ", i);
      printf("%d ", q.top());
      q.pop();
    }
  }
  return 0;
}

I - Equal Sum Arrays

代码参考

Show code

I.cppview raw
1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int main() {
  int n;
  cin >> n;
  cout << (1 << n - 1);
  return 0;
}

J - JOJO's Happy Tree Friends

代码参考

Show code

K - Monkey Joe

代码参考

Show code

L - Let's Swap

代码参考

Show code

L.cppview raw
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
#include <bits/stdc++.h>
using namespace std;
#define _run_return_void(expressions) \
  {                                   \
    expressions;                      \
    return;                           \
  }
const uint32_t OFFSET = 5;
const uint32_t N = 5e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
auto _rev = [](const string_view &s, int l) -> string {
  string _;
  for (int i = l - 1; ~i; --i) _.push_back(s[i]);
  for (int i = s.size() - 1; i >= l; --i) _.push_back(s[i]);
  return _;
};
namespace KMP {
int nxt[N];
int l;
bool kmp(const string_view &s, const string_view &t) {
  int i, j;
  int n = s.size(), m = t.size();
  for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {
    while (~j && s[j + 1] != s[i]) j = nxt[j];
    if (s[j + 1] == s[i]) ++j;
  }
  for (j = -1, i = 0; i < m; ++i) {
    while (~j && s[j + 1] != t[i]) j = nxt[j];
    if (s[j + 1] == t[i]) ++j;
    if (j == n - 1) {
      if ((i - n + 1) % l == 0) return 1;
      j = nxt[j];
    }
  }
  return 0;
}
}  // namespace KMP
using KMP::kmp;
#define MULTI_CASES
auto solve() -> void {
  string s, t;
  cin >> s >> t;
  int l1, l2;
  cin >> l1 >> l2;
  if (s == t) _run_return_void(cout << "yes\n");
  if (l1 == l2) _run_return_void(cout << (_rev(s, l1) == t ? "yes\n" : "no\n"));
  if (l1 > l2) swap(l1, l2);
  string _1 = _rev(s, l1), _2 = _rev(s, l2), _12 = _rev(_1, l2),
         _21 = _rev(_2, l1);
  t += t;
  KMP::l = gcd(l2 - l1, (int)s.size());
  cout << (kmp(_1, t) || kmp(_2, t) || kmp(_12, t) || kmp(_21, t) ? "yes\n" :
                                                                    "no\n");
}
int main() {
#ifdef _LOCAL_
  auto _CLOCK_ST = std::chrono::steady_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#ifdef MULTI_CASES
  int _t;
  cin >> _t;
  while (_t--)
#endif
    solve();
#ifdef _LOCAL_
  std::clog << "\n---\n"
            << "Time used: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(
                 std::chrono::steady_clock::now() - _CLOCK_ST)
                 .count()
            << " ms" << std::endl;
#endif
  return 0;
}