VP 记录 - 2021 ICPC 亚洲区域赛 (上海)

发表于 更新于 分类于 ， ， 本文字数： 478 阅读时长 ≈ 2 分钟

比赛链接

进度: 8 / 13

题目概览

题号标题做法
*AStrange Functions
*BStrange Permutations
*CStrange Matrices
DStrange Fractions
EStrange Integers
*FKaiji!
GEdge Groups
HLife is a Game
ISteadily Growing Steam
JTwo Binary Strings Problem
KCircle of Life
*LThree,Three,Three
MHarmony in Harmony

官方题解

A - Strange Functions

解题思路

复杂度

代码参考

Show code

B - Strange Permutations

解题思路

复杂度

代码参考

Show code

C - Strange Matrices

解题思路

复杂度

代码参考

Show code

D - Strange Fractions

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
using namespace std;

int main() {
  int _t;
  cin >> _t;
  while (_t--) {
    int64_t p, q;
    cin >> p >> q;
    int64_t __ = p * p - 4 * q * q;
    if (int64_t _ = int64_t(sqrt(__)); _ * _ != __) {
      cout << "0 0\n";
      continue;
    }
    __ = sqrt(__);
    int64_t a = p + __, b = 2 * q;
    int64_t g = __gcd(a, b);
    a /= g;
    b /= g;
    if (a > 1e9 || b > 1e9) {
      cout << "0 0\n";
      continue;
    }
    cout << a << ' ' << b << '\n';
  }
}

E - Strange Integers

解题思路

复杂度

代码参考

Show code

E.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + n + 1);
  int ans = 1, l = a[1];
  for (int i = 2; i <= n; i++) {
    if (a[i] - l >= k) {
      ans++;
      l = a[i];
    }
  }
  cout << ans;
}

F - Kaiji!

解题思路

复杂度

代码参考

Show code

G - Edge Groups

解题思路

复杂度

代码参考

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#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 = 100000 + 7, Mod = 998244353;
int n, Dp[N], M[N], Sign[N], Cnt[N], Fac[N], Fac1[N], Sz[N];
vector<int> E[N];
int Mul(int A, int B) { return 1ll * A * B % Mod; }
void Add(int u, int v) { E[u].push_back(v), E[v].push_back(u); }
int KSM(int x, int p) {
  int Ret = 1;
  while (p) {
    if (p & 1) Ret = Mul(Ret, x);
    p >>= 1, x = Mul(x, x);
  }
  return Ret;
}

void dp(int u, int fa) {
  int v, cnt = 0, S0 = 1, S1 = 1;
  Sz[u] = 1;
  Rep(i, 0, E[u].size() - 1)
    if ((v = E[u][i]) != fa) dp(v, u), Sz[u] += Sz[v];
  Rep(i, 0, E[u].size() - 1)
    if ((v = E[u][i]) != fa) {
      inc(Cnt[u]);
      if (Sz[v] % 2 == 1) S0 = Mul(S0, Dp[v]), inc(cnt);
      if (Sz[v] % 2 == 0) S1 = Mul(S1, Dp[v]);
    }
  Dp[u] = Mul(Mul(Mul(Mul(S0, S1), Fac[cnt]), M[cnt / 2]), Fac1[cnt / 2]);
}

int main() {
  scanf("%d", &n);
  int u, v;
  Rep(i, 1, n - 1) scanf("%d%d", &u, &v), Add(u, v);
  M[0] = Fac[0] = Fac[1] = 1;
  Rep(i, 2, n) Fac[i] = Mul(Fac[i - 1], i);
  Rep(i, 0, n) Fac1[i] = KSM(Fac[i], Mod - 2);
  Rep(i, 1, n) M[i] = Mul(M[i - 1], 2);
  Rep(i, 1, n) M[i] = KSM(M[i], Mod - 2);
  dp(1, 0);
  printf("%d", Dp[1]);
  return 0;
}

H - Life is a Game

解题思路

复杂度

代码参考

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
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include <bits/stdc++.h>

using i32 = int32_t;

using u32 = uint32_t;
using u64 = uint64_t;
using usz = size_t;

template <class T>
using ptt = std::pair<T, T>;

template <class T>
using vec = std::vector<T>;
template <class T>
using vvec = vec<vec<T>>;

namespace tifa_libs::ds {
template <bool RANK_ = false>
class dsu_basic {
  vec<i32> p;

public:
  explicit dsu_basic(usz sz): p(sz, -1) {}

  i32 find(u32 x) { return p[x] < 0 ? (i32)x : p[x] = find((u32)p[x]); }
  u32 size(u32 x) { return (u32)-p[(u32)find(x)]; }
  bool same(u32 x, u32 y) { return find(x) == find(y); }
  bool merge(u32 x, u32 y) {
    if ((x = (u32)find(x)) == (y = (u32)find(y))) return false;
    if (RANK_ && p[x] > p[y]) std::swap(x, y);
    p[x] += p[y];
    p[y] = (i32)x;
    return true;
  }
};

}  // namespace tifa_libs::ds

namespace tifa_libs::graph {

namespace adjlist_impl_ {

template <class T, bool isv = std::is_void_v<T>>
struct E;
template <class T>
struct E<T, false> {
  u32 to;
  T w;
  E() {}
  E(u32 v, T const &w): to(v), w(w) {}
};
template <class T>
struct E<T, true> {
  u32 to;
  E() {}
  explicit E(u32 v): to(v) {}
};

template <class T = void>
class adjlist {
protected:
  u32 m;
  vvec<E<T>> g;

public:
  //! vertex ID: [0, n)
  explicit adjlist(u32 n = 0): m(0), g(n) {}
  void reset_v_size(u32 n) { g.resize(n); }
  void clear() { g.clear(); }
  void shrink() { g.shrink_to_fit(); }

  template <class... Ts>
  E<T> &add_arc(u32 u, Ts &&...args) {
    ++m;
    g[u].emplace_back(args...);
    return g[u].back();
  }
  template <class... Ts>
  ptt<E<T> &> add_edge(u32 u, u32 v, Ts &&...args) {
    return {add_arc(u, v, args...), add_arc(v, u, args...)};
  }

  auto &operator[](u32 u) { return g[u]; }
  auto operator[](u32 u) const { return g[u]; }

  u32 v_size() const { return (u32)g.size(); }
  u32 arc_size() const { return m; }
};

}  // namespace adjlist_impl_

using adjlist_impl_::adjlist;

}  // namespace tifa_libs::graph

namespace tifa_libs::graph {

enum state_tdfs {
  s_dfn = 1,
  s_sz = 2,
  s_fa = 4,
  s_dep = 8,
  s_maxson = 16,
  s_go = 32,
  s_sum_node_w = 64
};

template <class T = void>
struct tree: public adjlist<T> {
  u32 rt;
  vec<u32> node_w, dfn, sz, fa, dep, maxson, top;
  vec<u64> sum_node_w;
  vec<vec<u32>> go;

  explicit tree(u32 n, vec<u32> NODE_W = vec<u32>(), u32 root = 0)
    : adjlist<T>(n), rt(root), node_w(NODE_W) {}

  void clear(u32 u = 0, u32 fa = 0) {
    for (auto v : this->g[u])
      if (v.to != fa) clear(v.to, u);
    this->g[u].clear();
  }

  template <int state>
  inline void reset_dfs_info() {
    u32 n = (u32)this->v_size();
    if constexpr (state & s_dfn) dfn = vec<u32>(n);
    if constexpr (state & (s_sz | s_maxson)) sz = vec<u32>(n);
    if constexpr (state & s_fa) fa = vec<u32>(n);
    if constexpr (state & s_dep) dep = vec<u32>(n);
    if constexpr (state & s_maxson) maxson = vec<u32>(n, n);
    if constexpr (state & s_go) go = vec<vec<u32>>(n, vec<u32>(21u, n));
    if constexpr (state & s_sum_node_w) sum_node_w = vec<u64>(n);

    u32 cnt = 0;
    auto before = [&](u32 u, u32 f) {
      if constexpr (state & s_dfn) dfn[u] = cnt++;
      if constexpr (state & (s_sz | s_maxson)) sz[u] = 1;
      if constexpr (state & s_fa) fa[u] = f;
      if constexpr (state & s_go) {
        go[u][0] = f;
        for (u32 i = 1; i <= 20u && go[u][i - 1] < n; i++)
          go[u][i] = go[go[u][i - 1]][i - 1];
      }
      if constexpr (state & s_sum_node_w) sum_node_w[u] = node_w[u];
    };
    auto pre_dfs = [&](auto const &ev, u32 u) {
      if constexpr (state & s_dep) dep[ev.to] = dep[u] + 1;
    };
    auto post_dfs = [&](auto const &ev, u32 u) {
      if constexpr (state & (s_sz | s_maxson)) sz[u] += sz[ev.to];
      if constexpr (state & s_maxson)
        if (maxson[u] == n || sz[ev.to] > sz[maxson[u]]) maxson[u] = ev.to;
      if constexpr (state & s_sum_node_w) sum_node_w[u] += sum_node_w[ev.to];
    };

    dfs_(rt, n, before, pre_dfs, post_dfs);
  }

  template <bool need_dfn = false>
  void reset_top() {
    u32 n = (u32)this->v_size();
    if (maxson.empty()) reset_dfs_info<s_maxson>();
    if constexpr (need_dfn) dfn = vec<u32>(n);
    top = vec<u32>(n, n);

    u32 cnt = 0;
    auto before = [&](u32 u, u32 top_) {
      if constexpr (need_dfn) dfn[u] = cnt++;
      top[u] = top_;
    };
    dfs_top_(rt, rt, before);
  }

private:
  template <class Fb, class Fp, class Fs>
  void dfs_(u32 u, u32 fa, Fb before, Fp pre_dfs, Fs post_dfs) {
    before(u, fa);
    for (auto v : this->g[u])
      if (v.to != fa) {
        pre_dfs(v, u);
        dfs_(v.to, u, before, pre_dfs, post_dfs);
        post_dfs(v, u);
      }
  }

  template <class F>
  void dfs_top_(u32 u, u32 top_, F before) {
    before(u, top_);
    if (maxson[u] == this->v_size()) return;
    dfs_top_(maxson[u], top_, before);
    for (auto v : this->g[u])
      if (top[v.to] == this->v_size()) dfs_top_(v.to, v.to, before);
  }
};

}  // namespace tifa_libs::graph

namespace tifa_libs::graph {

//!! edge: w u v
template <class T>
inline std::pair<tree<void>, vec<T>> kruskal_re_tree(
  vec<std::tuple<T, u32, u32>> a, u32 n, vec<u32> node_w = vec<u32>()) {
  std::sort(a.begin(), a.end());
  if (node_w.size()) node_w.resize(2 * n - 1);
  tree<void> tr(2 * n - 1, node_w);
  vec<T> w_(2 * n - 1);
  ds::dsu_basic dsu(2 * n - 1);
  u32 m = n - 1, cnt = n;
  for (auto [w, u, v] : a) {
    u = dsu.find(u), v = dsu.find(v);
    if (u != v) {
      u32 t = cnt++;
      w_[t] = w;
      tr.add_arc(t, u), tr.add_arc(t, v);
      dsu.merge(t, u), dsu.merge(t, v);
      --m;
    }
    if (m == 0) break;
  }
  tr.rt = cnt - 1;
  return {tr, w_};
}

}  // namespace tifa_libs::graph

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  u32 n, m, q;
  std::cin >> n >> m >> q;
  vec<u32> nw(n);
  for (auto &x : nw) std::cin >> x;
  vec<std::tuple<u32, u32, u32>> e(m);
  for (auto &[w, u, v] : e) std::cin >> u >> v >> w, --u, --v;
  auto [tr, ew] = tifa_libs::graph::kruskal_re_tree(e, n, nw);
  n = tr.v_size();
  tr.reset_dfs_info<tifa_libs::graph::s_go | tifa_libs::graph::s_sum_node_w>();
  while (q--) {
    u32 x, k;
    std::cin >> x >> k;
    --x;
    u64 ans = k + tr.sum_node_w[x];
    while (x != tr.rt) {
      u32 tem = x;
      for (i32 i = 20; i >= 0; i--) {
        if (tr.go[x][i] < n && ew[tr.go[x][i]] <= ans) x = tr.go[x][i];
      }
      if (x == tem) break;
      ans = k + tr.sum_node_w[x];
    }
    std::cout << ans << '\n';
  }
  return 0;
}

I - Steadily Growing Steam

解题思路

复杂度

代码参考

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
#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 = 100 + 7, M = 1300 * 2 + 4;
int n, k, m;
ll Dp[N][N][M];
int v[N], W[N];

int main() {
  scanf("%d%d", &n, &k), m = n * 13;
  Rep(i, 1, n) scanf("%d%d", v + i, W + i);
  Rep(l, 0, n)
    Rep(i, 0, k)
      Rep(j, 0, 2 * m) Dp[l][i][j] = -100000000007;
  Dp[0][0][m] = 0;
  Rep(i, 1, n)
    Rep(j, 0, min(i, k))
      Rep(l, 0, 2 * m)
        if (Dp[i - 1][j][l] != -100000000007) {
          Dp[i][j][l] = max(Dp[i][j][l], Dp[i - 1][j][l]);
          if (l + W[i] <= 2 * m)
            Dp[i][j][l + W[i]] =
              max(Dp[i][j][l + W[i]], Dp[i - 1][j][l] + v[i]);
          if (l - W[i] >= 0)
            Dp[i][j][l - W[i]] =
              max(Dp[i][j][l - W[i]], Dp[i - 1][j][l] + v[i]);
          if (j != min(i, k)) {
            if (l + 2 * W[i] <= 2 * m)
              Dp[i][j + 1][l + 2 * W[i]] =
                max(Dp[i][j + 1][l + 2 * W[i]], Dp[i - 1][j][l] + v[i]);
            if (l - 2 * W[i] >= 0)
              Dp[i][j + 1][l - 2 * W[i]] =
                max(Dp[i][j + 1][l - 2 * W[i]], Dp[i - 1][j][l] + v[i]);
          }
        }
  ll Ans = -100000000007;
  Rep(j, 0, k) Ans = max(Ans, Dp[n][j][m]);
  printf("%lld", Ans);
  return 0;
}

J - Two Binary Strings Problem

解题思路

复杂度

代码参考

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
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; --i)
#define debug cout << __LINE__ << "RE" << endl
using namespace std;
using i64 = long long;
using u32 = uint32_t;

const int N = 50000 + 7;
void solve(int t_ = 0) {
  int n;
  string a, b;
  cin >> n >> a >> b;
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    if (i) s[i] = s[i - 1];
    s[i] += a[i] == '1' ? 1 : -1;
  }
  bitset<N * 2> ans, les, gre;
  ans.set();
  vector<int> id(n);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&](int a, int b) { return s[a] < s[b]; });
  gre.set();
  for (int i = 0, j = 0, flag = 1; i < n; i = j + 1) {
    while (j + 1 < n && s[id[j + 1]] == s[id[i]]) ++j;
    if (flag && s[id[i]] > 0) {
      for (int k = n; k <= n + n; ++k) les[k] = 1, gre[k] = 0;
      flag = 0;
    }
    for (int k = i; k <= j; ++k)
      if (b[id[k]] == '1') ans &= les >> (n - 1 - id[k]);
      else ans &= gre >> (n - 1 - id[k]);
    for (int k = i; k <= j; ++k) les[n - 1 - id[k]] = 1, gre[n - 1 - id[k]] = 0;
  }
  for (int i = 1; i <= n; ++i) cout << ans[i];
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) solve(t);
  return 0;
}

K - Circle of Life

解题思路

复杂度

代码参考

Show code

K.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
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; ++i)
#define rep(i, a, b) for (int i = (a), i##Limit = (b); i >= i##Limit; --i)

using namespace std;
using i64 = long long;
using u32 = uint32_t;

template <class... Ts>
void print(Ts const &...p) {
  ((cout << p << ' '), ...);
}
#define debug(var)

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  if (n == 3) cout << "Unlucky", exit(0);
  if (n % 2 == 0) {
    while (n > 2) {
      n -= 4;
      cout << "1001";
    }
    if (n) cout << "10";
    exit(0);
  }
  if (n % 4 == 1) {
    while (n > 5) {
      n -= 4;
      cout << "1001";
    }
    if (n) cout << "10001";
    exit(0);
  }
  if (n % 4 == 3) {
    while (n > 3) {
      n -= 4;
      cout << "1001";
    }
    if (n) cout << "010";
    exit(0);
  }
  return 0;
}

L - Three,Three,Three

解题思路

复杂度

代码参考

Show code

M - Harmony in Harmony

解题思路

复杂度

代码参考

Show code

M.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  cout << fixed << setprecision(9) << 1. / n / ((n + 1) / 2) / (n / 2 + 1)
       << '\n';
  return 0;
}