VP 记录 - 2022 CCPC 威海站

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

比赛链接

进度: 7 / 13

怎么一堆福瑞啊 🤔

难度相对较低的一场，官方题解很详细，孩子很喜欢

题目概览

题号 1标题做法
ADunai签到
*BRecruitmentBFS
CGrass计算几何
DSternhalma状压 DP
EPython Will be Faster than C++签到
*FMooncake Delivery最短路
GGrade 2签到 (找规律) / Möbius 反演
*HParty Animals平衡树
IDragon Bloodline贪心，二分
JEat, Sleep, Repeat贪心
*KI Wanna Maker
*LNovice Magician构造
*MString Master

官方题解

Sildes

视频

link

A - Dunai

解题思路

复杂度

代码参考

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
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  map<string, int> M;
  cin >> T;
  int tot = 0;
  for (int i = 1; i <= T; ++i)
    for (int j = 1; j <= 5; ++j) {
      string S;
      cin >> S;
      M[S] = 1;
    }
  int m;
  cin >> m;
  vector<int> cnt(6);
  for (int i = 1; i <= m; ++i) {
    string S;
    int opt;
    cin >> S >> opt;
    tot += M[S];
    ++cnt[opt];
  }
  int Min = cnt[1];
  for (int i = 2; i <= 5; ++i) { Min = min(Min, cnt[i]); }
  cout << min(Min, tot);
  return 0;
}

B - Recruitment

解题思路

复杂度

代码参考

Show code

C - Grass

解题思路

复杂度

代码参考

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using ll = long long;
using pii = std::pair<int, int>;
using namespace std;
constexpr bool in_same_line(pii const &u, pii const &v, pii const &w) {
  ll x1 = v.first - u.first, y1 = v.second - u.second;
  ll x2 = w.first - u.first, y2 = w.second - u.second;
  return (x1 * y2 - x2 * y1) == 0;
}
bool in_same_dir(pii const &u, pii const &v, pii const &w) {
  ll x1 = v.first - u.first, y1 = v.second - u.second;
  ll x2 = w.first - u.first, y2 = w.second - u.second;
  return in_same_line(u, v, w) && ((x1 * x2 + y1 * y2) > 0);
}
void print__(
  pii const &c, pii const &p1, pii const &p2, pii const &p3, pii const &p4) {
  cout << "YES\n";
  cout << c.first << ' ' << c.second << '\n';
  cout << p1.first << ' ' << p1.second << '\n';
  cout << p2.first << ' ' << p2.second << '\n';
  cout << p3.first << ' ' << p3.second << '\n';
  cout << p4.first << ' ' << p4.second << '\n';
}
void print(
  pii const &p0, pii const &p1, pii const &p2, pii const &p3, pii const &p4) {
  auto cond = [](pii const &x,
                 pii const &p1,
                 pii const &p2,
                 pii const &p3,
                 pii const &p4) {
    return !(in_same_dir(x, p1, p2) || in_same_dir(x, p1, p3) ||
             in_same_dir(x, p1, p4) || in_same_dir(x, p2, p3) ||
             in_same_dir(x, p2, p4) || in_same_dir(x, p3, p4));
  };
  if (cond(p0, p1, p2, p3, p4)) {
    print__(p0, p1, p2, p3, p4);
    return;
  }
  if (cond(p1, p0, p2, p3, p4)) {
    print__(p1, p0, p2, p3, p4);
    return;
  }
  if (cond(p2, p0, p1, p3, p4)) {
    print__(p2, p0, p1, p3, p4);
    return;
  }
  if (cond(p3, p0, p1, p2, p4)) {
    print__(p3, p0, p1, p2, p4);
    return;
  }
  if (cond(p4, p0, p1, p2, p3)) {
    print__(p4, p0, p1, p2, p3);
    return;
  }
}
void solve(int t_ = 0) {
  int n;
  cin >> n;
  vector<pii> v(n);
  for (auto &i : v) cin >> i.first >> i.second;
  if (n < 5) {
    cout << "NO\n";
    return;
  }
  pii p0 = v[0], p1 = v[1], p2 = v[2], p3 = v[3], p4;
  for (int i = 4; i < n; ++i) {
    p4 = v[i];
    if (!(in_same_line(p0, p1, p2) && in_same_line(p0, p1, p3) &&
          in_same_line(p0, p1, p4))) {
      print(p0, p1, p2, p3, p4);
      return;
    }
  }
  cout << "NO\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

D - Sternhalma

解题思路

复杂度

代码参考

Show code

D.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
#include <bits/stdc++.h>
using ll = long long;
#define int long long
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
using namespace std;
const int GO[19][6] = {{1, 3, 4, -1, -1, -1},
                       {4, 5, -1, -1, -1, -1},
                       {1, 5, 6, -1, -1, -1},
                       {4, 8, -1, -1, -1, -1},
                       {5, 8, 9, -1, -1, -1},
                       {4, 9, 10, -1, -1, -1},
                       {5, 10, -1, -1, -1, -1},
                       {3, 8, 12, -1, -1, -1},
                       {4, 9, 13, -1, -1, -1},
                       {4, 5, 8, 10, 13, 14},
                       {5, 9, 14, -1, -1, -1},
                       {6, 10, 15, -1, -1, -1},
                       {8, 13, -1, -1, -1, -1},
                       {8, 9, 14, -1, -1, -1},
                       {9, 10, 13, -1, -1, -1},
                       {10, 14, -1, -1, -1, -1},
                       {12, 13, 17, -1, -1, -1},
                       {13, 14, -1, -1, -1, -1},
                       {14, 15, 17, -1, -1, -1}};
const int GO2[19][6] = {{2, 7, 9, -1, -1, -1},
                        {8, 10, -1, -1, -1, -1},
                        {0, 9, 11, -1, -1, -1},
                        {5, 13, -1, -1, -1, -1},
                        {6, 12, 14, -1, -1, -1},
                        {3, 13, 15, -1, -1, -1},
                        {4, 14, -1, -1, -1, -1},
                        {0, 9, 16, -1, -1, -1},
                        {1, 10, 17, -1, -1, -1},
                        {0, 2, 7, 11, 16, 18},
                        {1, 8, 17, -1, -1, -1},
                        {2, 9, 18, -1, -1, -1},
                        {4, 14, -1, -1, -1, -1},
                        {3, 5, 15, -1, -1, -1},
                        {4, 6, 12, -1, -1, -1},
                        {5, 13, -1, -1, -1, -1},
                        {7, 9, 18, -1, -1, -1},
                        {8, 10, -1, -1, -1, -1},
                        {9, 11, 16, -1, -1, -1}};
const int N = (1 << 20) + 7;
const ll MIN = -1000000010ll;
ll Dp[N], n;
vector<int> E, A;
ll DP(int State) {
  if (Dp[State] != MIN) return Dp[State];
  Rep(i, 0, n - 1)
    if ((State >> i) & 1) {
      int to = State ^ (1 << i);
      Dp[State] = max(Dp[State], DP(to));
      Rep(j, 0, 5)
        if (~GO[i][j] && ((State >> GO[i][j]) & 1) &&
            ((State >> GO2[i][j]) & 1) == 0) {
          to = State ^ (1 << GO[i][j]) ^ (1 << GO2[i][j]) ^ (1 << i);
          Dp[State] = max(Dp[State], DP(to) + E[GO[i][j]]);
        }
    }
  return Dp[State];
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  n = 19;
  E.resize(n, 0);
  A.resize(n, 0);
  Rep(i, 0, n - 1) cin >> E[i];
  int T;
  cin >> T;
  Rep(i, 0, (1 << 20) - 1) Dp[i] = MIN;
  Dp[0] = 0;
  while (T--) {
    int State = 0;
    Rep(i, 0, n - 1) {
      char C;
      cin >> C;
      State |= (C == '#' ? 1 : 0) * (1 << i);
    }
    cout << DP(State) << '\n';
  }
  return 0;
}

E - Python Will be Faster than C++

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using i64 = int64_t;
using namespace std;
void solve(int t_ = 0) {
  int n;
  cin >> n;
  i64 t;
  cin >> t;
  i64 x, y;
  for (int i = 1; i <= n - 2; ++i) cin >> x;
  cin >> x >> y;
  if (x <= y) {
    cout << "Python will never be faster than C++\n";
    return;
  }
  i64 k = x - y;
  cout << "Python 3." << n + (y - t + k) / k << " will be faster than C++\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  solve(i_);
  return 0;
}

F - Mooncake Delivery

解题思路

复杂度

代码参考

Show code

G - Grade 2

解题思路

复杂度

代码参考

Show code

G.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
#include <bits/stdc++.h>
using ll = long long;
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int x, T;
  cin >> x >> T;
  int lim = 1 << (32 - __builtin_clz(x));
  vector<ll> f(lim + 1);
  Rep(i, 1, lim) f[i] = (gcd(((ll)i * x) ^ x, x) == 1);
  Rep(i, 2, lim) f[i] += f[i - 1];
  while (T--) {
    ll l, r;
    cin >> l >> r;
    if (x % 2 == 0) {
      cout << "0\n";
      continue;
    } else {
      auto get = [&](ll y) -> ll {
        ll shang = y / lim, yu = y % lim;
        return shang * f[lim] + f[yu];
      };
      cout << get(r) - get(l - 1) << '\n';
    }
  }
  return 0;
}

H - Party Animals

解题思路

复杂度

代码参考

Show code

I - Dragon Bloodline

解题思路

复杂度

代码参考

Show code

I.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
#include <bits/stdc++.h>
#define dec(i) (--(i))
#define int long long
using namespace std;
#define WW(i) (1 << (i))
void Solve() {
  int n, k;
  int Sum = 0, tot = 0;
  cin >> n >> k;
  vector<int> A(n), B(k);
  for (int i = 0; i < n; ++i) cin >> A[i], tot += A[i];
  for (int i = 0; i < k; ++i) cin >> B[i], Sum += B[i] * WW(i);
  int l = 0, r = Sum / tot, Mid, Ans = 0;
  while (r >= l) {
    int Mid = (r + l) >> 1;
    auto Pd = [&](int x) -> bool {
      vector<int> C(n), D(k);
      priority_queue<int> Q;
      for (int i = 0; i < n; ++i) Q.push(A[i] * x);
      D = B;
      for (int i = k - 1; ~i; --i) {
        while (!Q.empty() && D[i] && WW(i) >= Q.top()) {
          Q.pop();
          dec(D[i]);
        }
        while (!Q.empty() && D[i] && WW(i) < Q.top()) {
          int t = Q.top(), tt = t / WW(i), ttt = min(tt, D[i]);
          Q.pop();
          t -= ttt * WW(i), D[i] -= ttt;
          if (t) Q.push(t);
        }
        while (!Q.empty() && D[i] && WW(i) >= Q.top()) {
          Q.pop();
          dec(D[i]);
        }
      }
      if (Q.size()) return 0;
      return 1;
    };
    if (Pd(Mid)) Ans = Mid, l = Mid + 1;
    else r = Mid - 1;
  }
  cout << Ans << '\n';
  ;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) { Solve(); }
  return 0;
}

J - Eat, Sleep, Repeat

解题思路

复杂度

代码参考

Show code

J.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
#include <bits/stdc++.h>
using ll = long long;
using pii = std::pair<int, int>;
using namespace std;
const int N = 100010;
int a[N];
void solve(int t_ = 0) {
  int n, k;
  cin >> n >> k;
  ll ss = 0;
  for (int i = 1; i <= n; ++i) cin >> a[i], ss += a[i];
  vector<pii> cons;
  priority_queue<int, vector<int>, greater<int>> lim;
  for (int i = 1; i <= k; ++i) {
    int x, y;
    cin >> x >> y;
    if (y == 0) lim.push(x);
    else cons.emplace_back(x, y);
  }
  lim.push(1e9);
  a[n + 1] = 1e9 + 1;
  sort(a + 1, a + n + 2);
  sort(cons.begin(), cons.end());
  int now = 0, cnt = 0;
  ll sum = 0;
  while (!lim.empty() && lim.top() == now) ++now, lim.pop();
  auto it = cons.begin();
  while (!lim.empty()) {
    int nxt = upper_bound(a + 1, a + n + 2, lim.top()) - a;
    int count1 = nxt - (lower_bound(a + 1, a + n + 2, now) - a);
    while (count1 && it != cons.end() && it->first < lim.top() &&
           it->first == now) {
      sum += min(count1, it->second) * it->first;
      count1 -= min(count1, it->second);
      ++now;
      ++it;
    }
    sum += count1 * now;
    while (it != cons.end() && it->first < lim.top()) { ++it; }
    now = lim.top();
    while (!lim.empty() && lim.top() == now) ++now, lim.pop();
  }
  int count1 = n + 1 - (lower_bound(a + 1, a + n + 2, now) - a);
  while (count1 && it != cons.end() && it->first < lim.top() &&
         it->first == now) {
    sum += min(count1, it->second) * it->first;
    count1 -= min(count1, it->second);
    ++now;
    ++it;
  }
  sum += now * count1;
  if ((ss - sum) & 1) cout << "Pico\n";
  else cout << "FuuFuu\n";
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

K - I Wanna Maker

解题思路

复杂度

代码参考

Show code

L - Novice Magician

解题思路

复杂度

代码参考

Show code

M - String Master

解题思路

复杂度

代码参考

Show code

  1. 打 * 的是还没写题解的题↩︎