VP 记录 - 2019 ICPC 亚洲区域赛 (银川)

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

比赛链接

进度: 6 / 14

题目概览

题号 1标题 2做法
*AGirls Band PartyDP
BSo Easy双指针，单调队列 / 二维差分
*CImage Processing双指针，单调队列优化 DP
DEasy ProblemMöbius 反演
*EXOR Tree长链剖分，DP
FFunction!推式子
GPot!!线段树
*HDelivery Route最短路
IBase62签到
*JToad’s Travel
*KLargest Common Submatrix单调栈 / 悬线法
*LXian Xiang状压 DP
*MCrazy Cake生成函数，DP
NFibonacci Sequence签到

官方题解

A - Girls Band Party

解题思路

复杂度

代码参考

Show code

B - So Easy

解题思路

复杂度

代码参考

Show code

B.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
#include <bits/stdc++.h>
using namespace std;
int n, m, posx, posy, a[1010][1010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> a[i][j];
      if (a[i][j] == -1) posx = i, posy = j;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (i == posx) continue;
    int mn = 0x3f3f3f3f;
    for (int j = 1; j <= n; ++j) { mn = min(mn, a[i][j]); }
    for (int j = 1; j <= n; ++j) a[i][j] -= mn;
  }
  for (int i = 1; i <= n; ++i) {
    if (i == posy) continue;
    int mn = 0x3f3f3f3f;
    for (int j = 1; j <= n; ++j) { mn = min(mn, a[j][i]); }
    for (int j = 1; j <= n; ++j) a[j][i] -= mn;
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[posx][i] != -1) {
      ans += a[posx][i];
      break;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i][posy] != -1) {
      ans += a[i][posy];
      break;
    }
  }
  cout << ans << "\n";
  return 0;
}

C - Image Processing

解题思路

复杂度

代码参考

Show code

D - Easy Problem

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
template <class Tp>
using vc = std::vector<Tp>;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
using namespace std;
const int N = 1e5 + 5;
int prime[N], cnt_prime;
bool vis[N];
int mu[N];
void init_prime(int n = N - 1) {
  mu[1] = 1;
  for_(i, 2, n) {
    if (!vis[i]) {
      prime[++cnt_prime] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cnt_prime && i * prime[j] <= n; ++j) {
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) continue;
      mu[i * prime[j]] = -mu[i];
    }
  }
}
const int MOD = 59964251, PHI = 642 * 93256;
constexpr i64 qpow(i64 a, i64 b, i64 mod) {
  i64 res = 1;
  a %= MOD;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) res = res * a % MOD;
  return res;
}
void solve(int t_ = 0) {
  int n = 0, m, d, k;
  string s;
  cin >> s;
  for (char ch : s) ((n *= 10) += ch - '0') %= PHI;
  cin >> m >> d >> k;
  i64 mm = m / d, nk = (i64)n * k % PHI;
  vc<i64> smue(mm + 1);
  for_(i, 1, mm)
    smue[i] =
      (smue[i - 1] + ((mu[i] * qpow(i, nk, MOD) % MOD) + MOD) % MOD) % MOD;
  vc<i64> si(mm + 1);
  for_(i, 1, mm) si[i] = (si[i - 1] + qpow(i, k, MOD)) % MOD;
  i64 ans = 0;
  for (i64 l = 1, r; l <= mm; l = r + 1) {
    r = mm / (mm / l);
    i64 __ = qpow(si[mm / l], n, MOD);
    (ans += (smue[r] + MOD - smue[l - 1]) % MOD * __ % MOD) %= MOD;
  }
  (ans *= qpow(d, nk, MOD)) %= MOD;
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cerr << std::fixed << std::setprecision(6);
  int i_ = 0;
  init_prime();
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

E - XOR Tree

解题思路

复杂度

代码参考

Show code

F - Function!

解题思路

复杂度

代码参考

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using ll = long long;
using i64 = ll;
#define for_(i, l, r, v...) for (ll i = (l), i##e = (r), ##v; i <= i##e; ++i)
using namespace std;
const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2, INV3 = (MOD + 1) / 3;
void solve(int t_ = 0) {
  i64 n;
  cin >> n;
  auto calc = [](i64 a, i64 n) -> i64 {
    i64 ans = 0;
    for (i64 l = a, r, cnt = 1; l <= n; l = r + 1, ++cnt) {
      r = min(l * a - 1, n);
      (ans += cnt * ((r - l + 1) % MOD) % MOD) %= MOD;
    }
    return ans * a % MOD;
  };
  auto f = [&](i64 x) {
    x %= MOD;
    return x * (x + 1) % MOD * INV2 % MOD * ((n * 3 + 2 - 2 * x) % MOD) % MOD *
           INV3 % MOD;
  };
  i64 ans = 0;
  for_(i, 2, sqrtl(n)) (ans += calc(i, n)) %= MOD;
  cout << (ans + (f(n) + MOD - f((i64)floor(sqrtl(n))))) % MOD << '\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;
}

G - Pot!!

解题思路

复杂度

代码参考

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
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
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int t[N << 2][4], tag[N << 2][4];
void update(int v) {
  for (int i = 0; i < 4; ++i) {
    t[v][i] = max(t[v][i], max(t[v << 1][i], t[v << 1 | 1][i]));
  }
}
void pushdown(int v) {
  for (int i = 0; i < 4; ++i) {
    if (tag[v][i]) {
      t[v << 1][i] += tag[v][i];
      t[v << 1 | 1][i] += tag[v][i];
      tag[v << 1][i] += tag[v][i];
      tag[v << 1 | 1][i] += tag[v][i];
      tag[v][i] = 0;
    }
  }
}
void add(int v, int l, int r, int x, int y, int a2, int a3, int a5, int a7) {
  if (x <= l && r <= y) {
    if (a2) {
      tag[v][0] += a2;
      t[v][0] += a2;
    }
    if (a3) {
      tag[v][1] += a3;
      t[v][1] += a3;
    }
    if (a5) {
      tag[v][2] += a5;
      t[v][2] += a5;
    }
    if (a7) {
      tag[v][3] += a7;
      t[v][3] += a7;
    }
    return;
  }
  int mid = l + r >> 1;
  pushdown(v);
  if (x <= mid) add(v << 1, l, mid, x, y, a2, a3, a5, a7);
  if (mid < y) add(v << 1 | 1, mid + 1, r, x, y, a2, a3, a5, a7);
  update(v);
  return;
}
int query(int v, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    int mx = 0;
    for (int i = 0; i < 4; ++i) { mx = max(mx, t[v][i]); }
    return mx;
  }
  int mid = l + r >> 1, res = 0;
  pushdown(v);
  if (x <= mid) res = max(res, query(v << 1, l, mid, x, y));
  if (mid < y) res = max(res, query(v << 1 | 1, mid + 1, r, x, y));
  update(v);
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    string op;
    int l, r, x;
    cin >> op >> l >> r;
    if (op == "MULTIPLY") {
      cin >> x;
      if (x == 2) {
        add(1, 1, n, l, r, 1, 0, 0, 0);
      } else if (x == 3) {
        add(1, 1, n, l, r, 0, 1, 0, 0);
      } else if (x == 4) {
        add(1, 1, n, l, r, 2, 0, 0, 0);
      } else if (x == 5) {
        add(1, 1, n, l, r, 0, 0, 1, 0);
      } else if (x == 6) {
        add(1, 1, n, l, r, 1, 1, 0, 0);
      } else if (x == 7) {
        add(1, 1, n, l, r, 0, 0, 0, 1);
      } else if (x == 8) {
        add(1, 1, n, l, r, 3, 0, 0, 0);
      } else if (x == 9) {
        add(1, 1, n, l, r, 0, 2, 0, 0);
      } else if (x == 10) {
        add(1, 1, n, l, r, 1, 0, 1, 0);
      }
    } else {
      cout << "ANSWER " << query(1, 1, n, l, r) << "\n";
    }
  }
  return 0;
}

H - Delivery Route

解题思路

复杂度

代码参考

Show code

I - Base62

解题思路

复杂度

代码参考

Show code

J - Toad’s Travel

解题思路

复杂度

代码参考

Show code

K - Largest Common Submatrix

解题思路

复杂度

代码参考

Show code

L - Xian Xiang

解题思路

复杂度

代码参考

Show code

M - Crazy Cake

解题思路

复杂度

代码参考

Show code

N - Fibonacci Sequence

解题思路

复杂度

代码参考

Show code

N.phpview raw
1
1 1 2 3 5

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

  2. 带超链接的是找到了原题或原型↩︎