训练

2019 ICPC Asia Xuzhou Regional

A B C D E F G H I J K M
O x O x O O x Ø x Ø x O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • x 没有尝试

A. Cat

询问$[L, R]$的最大子区间，满足其异或和不超过$S$。

通过打表 可以发现 \[4k \oplus (4k+1) \oplus (4k+2) \oplus (4k+3) = 0\] 所以可以暴力枚举两个端点，复杂度$O(16)$。

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
  static auto gao = [&](ll x) {
    ll y = x, res = 0;
    while (y % 4 != 3 && y > 0) --y;
    for (++y; y <= x; ++y) res ^= y;
    return res;
  };
  ll ans = -1, l, r, s;
  cin >> l >> r >> s;
  ll il = l - 1, ir = min(r - 1, l + 4);
  ll jl = max(l, r - 4), jr = r;
  for (ll i = il; i <= ir; ++i)
    for (ll j = jl; j <= jr; ++j) {
      if (i >= j) continue;
      if ((gao(i) ^ gao(j)) <= s) ans = max(ans, j - i);
    }
  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int o_o;
  for (cin >> o_o; o_o; --o_o) solve();
  return 0;
}

C. < 3 numbers

询问一个区间内素数和$1$的占比是否小于$\frac{1}{3}$。

训练时写的做法是随机化，在区间内做随机取样。

后来根据素数密度为$\frac{1}{\log n}$，如果区间足够大，那么一定为 Yes。小区间暴力即可。

随机化

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int STEPS = 5e3;

inline int mmul(int a, int b, int mod) { return 1ll * a * b % mod; }

inline int mpow(int a, int b, int mod) {
  int res = 1;
  for (; b; b >>= 1, a = mmul(a, a, mod)) (b & 1) && (res = mmul(res, a, mod));
  return res;
}

inline bool check(int x, int p) {
  if (!(x % p) || (mpow(p % x, x - 1, x) ^ 1)) return false;
  int k = x - 1, t;
  while (~k & 1) {
    if (((t = mpow(p % x, k >>= 1, x)) ^ 1) && (t ^ (x - 1))) return false;
    if (!(t ^ (x - 1))) return true;
  }
  return true;
}

inline bool Miller_Rabin(int x) {
  if (x < 2) return true;
  static const int p[12] = {2, 3, 5, 7, 11, 13, 17, 19, 61, 2333, 4567, 24251};
  for (int i = 0; i < 12; ++i) {
    if (!(x ^ p[i])) return true;
    if (!check(x, p[i])) return false;
  }
  return true;
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int T, l, r;
  for (cin >> T; T; --T) {
    cin >> l >> r;
    int len = r - l + 1, cnt = 0;
    if (len <= STEPS) {
      for (int i = l; i <= r; ++i) cnt += Miller_Rabin(i);
      cout << (3 * cnt < len ? "Yes\n" : "No\n");
    } else {
      static mt19937 rnd(
          chrono::high_resolution_clock::now().time_since_epoch().count());
      for (int i = 0; i < STEPS; ++i) {
        int x = rnd() % (len + 1) + l;
        cnt += Miller_Rabin(x);
      }
      cout << (3 * cnt < STEPS ? "Yes\n" : "No\n");
    }
  }

  return 0;
}

素数密度

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int LIMIT = 60;

inline int mmul(int a, int b, int mod) { return 1ll * a * b % mod; }

inline int mpow(int a, int b, int mod) {
  int res = 1;
  for (; b; b >>= 1, a = mmul(a, a, mod)) (b & 1) && (res = mmul(res, a, mod));
  return res;
}

inline bool check(int x, int p) {
  if (!(x % p) || (mpow(p % x, x - 1, x) ^ 1)) return false;
  int k = x - 1, t;
  while (~k & 1) {
    if (((t = mpow(p % x, k >>= 1, x)) ^ 1) && (t ^ (x - 1))) return false;
    if (!(t ^ (x - 1))) return true;
  }
  return true;
}

inline bool Miller_Rabin(int x) {
  if (x < 2) return true;
  static const int p[12] = {2, 3, 5, 7, 11, 13, 17, 19, 61, 2333, 4567, 24251};
  for (int i = 0; i < 12; ++i) {
    if (!(x ^ p[i])) return true;
    if (!check(x, p[i])) return false;
  }
  return true;
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int T, l, r;
  for (cin >> T; T; --T) {
    cin >> l >> r;
    int len = r - l + 1, cnt = 0;
    if (len <= LIMIT) {
      for (int i = l; i <= r; ++i) cnt += Miller_Rabin(i);
      cout << (cnt * 3 < len ? "Yes\n" : "No\n");
    } else {
      cout << "Yes\n";
    }
  }

  return 0;
}

E. Multiply

给定$X, Y$和$Z = a_1! × a_2! × a_3! \ldots a_n!$。令$b_i = Z × X^i$，求最大的$i$满足$b_i | Y!$。

实际上是求最大的\(i\) 满足 $X^i | \frac{Y!}{Z}$，对$X$因数分解，然后求出对应的指数即可。

  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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll mmul(ll a, ll b, ll mod) {
  ll k = (ll)((1.0L * a * b) / (1.0L * mod)), t = a * b - k * mod;
  for (t -= mod; t < 0; t += mod) {}
  return t;
}

inline ll mpow(ll a, ll b, ll mod) {
  ll res = 1;
  for (; b; b >>= 1, a = mmul(a, a, mod)) (b & 1) && (res = mmul(res, a, mod));
  return res;
}

inline bool check(ll x, ll p) {
  if (!(x % p) || (mpow(p % x, x - 1, x) ^ 1)) return false;
  ll k = x - 1, t;
  while (~k & 1) {
    if (((t = mpow(p % x, k >>= 1, x)) ^ 1) && (t ^ (x - 1))) return false;
    if (!(t ^ (x - 1))) return true;
  }
  return true;
}

inline bool Miller_Rabin(ll x) {
  if (x < 2) return true;
  static const int p[12] = {2, 3, 5, 7, 11, 13, 17, 19, 61, 2333, 4567, 24251};
  for (int i = 0; i < 12; ++i) {
    if (!(x ^ p[i])) return true;
    if (!check(x, p[i])) return false;
  }
  return true;
}

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

inline ll rand64(ll x) { return rnd() % (x - 1) + 1; }

inline ll Pollard_rho(ll x, int y) {
  ll v0 = rand64(x), v = v0, d, s = 1;
  for (int t = 0, k = 1;;) {
    if (v = (mmul(v, v, x) + y) % x, s = mmul(s, abs(v - v0), x),
        !(v ^ v0) || !s)
      return x;
    if (++t == k) {
      if ((d = __gcd(s, x)) ^ 1) return d;
      v0 = v, k <<= 1;
    }
  }
}

vector<ll> factor;
void find_factor(ll n) {
  if (Miller_Rabin(n)) {
    factor.push_back(n);
    return;
  }
  ll p = n;
  while (p >= n) p = Pollard_rho(p, rand64(n));
  find_factor(p), find_factor(n / p);
}

const int MAX_FACTOR = 100;
ll ex[MAX_FACTOR], ey[MAX_FACTOR], ez[MAX_FACTOR];

void gao(ll x, ll *e) {
  for (int i = 0; i < static_cast<int>(factor.size()); ++i) {
    for (ll x_ = x, f = factor[i]; x_; x_ /= f) e[i] += x_ / f;
  }
}

void solve() {
  int n;
  ll x, y, a;
  cin >> n >> x >> y;
  memset(ex, 0, sizeof(ex));
  memset(ey, 0, sizeof(ey));
  memset(ez, 0, sizeof(ez));
  factor.clear();
  find_factor(x);
  sort(factor.begin(), factor.end());
  factor.erase(unique(factor.begin(), factor.end()), factor.end());

  for (int i = 0; i < static_cast<int>(factor.size()); ++i) {
    for (ll x_ = x, f = factor[i]; x_ % f == 0; x_ /= f) ++ex[i];
  }

  gao(y, ey);
  for (int i = 0; i < n; ++i) {
    cin >> a;
    gao(a, ez);
  }

  ll ans = LLONG_MAX;
  for (int i = 0; i < static_cast<int>(factor.size()); ++i)
    ans = min(ans, (ey[i] - ez[i]) / ex[i]);

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int T;
  for (cin >> T; T; --T) solve();

  return 0;
}

F. The Answer to the Ultimate Question of Life, The Universe, and Everything.

每次询问$a, b, c$，满足 $a^3 + b^3 + c^3 = x(|{a}, |{b}, |{c} ≤ 5000, 0 ≤ x ≤ 200)$。

由于$x$很小，本地打表即可。

H. Yuuki and a problem

给定一个序列${a_i}$，指出以下两种操作：

  • 将$a_i$修改为$y$；
  • 询问一个区间内不能凑出的最小的正整数。

此题的重点是第二种的操作。假设我们当前已经可以表示出了区间$[1, x]$内的所有数，那么如果我们有 \(x + 1\) ，那么可以再凑出 \([x + 2, 2x + 1]\) 的所有数。另一个结论是如果我们可以凑出区间 \([1, x]\) 内的所有数，那么我们进一步可以凑出 \(\sum_{1 \le y \le x} y\) 以内的所有数。使用上面两个结论均可以完成此题，且都可以在 \(O(\log max\_value)\) 步内完成。

所以我们现在需要实现一个支持修改的区间权值范围内求和。这可以使用树状数组套线段树实现。

  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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 3;

struct Node {
  ll sum;
  Node *left, *right;
} * nil, node_pool[MAXN * 100], *pool_ptr = node_pool, *root[MAXN];

inline Node *new_node(int sum = 0) {
  *pool_ptr = {sum, nil, nil};
  return pool_ptr++;
}

void update(Node *(&u), int l, int r, int pos, int delta) {
  if (u == nil) {
    u = new_node(delta);
  } else {
    u->sum += delta;
  }
  if (l == r) return;
  int mid = (l + r) / 2;
  if (pos <= mid) {
    update(u->left, l, mid, pos, delta);
  } else {
    update(u->right, mid + 1, r, pos, delta);
  }
}

int n, q;

void update(int pos, int value, int delta) {
  for (int i = pos; i <= n; i += i & -i) update(root[i], 1, MAXN, value, delta);
}

ll query(int pos, int upper) {
  if (pos <= 0) return 0;

  static Node *rts[25];
  ll sum = 0, cnt = 0;
  for (int i = pos; i > 0; i &= i - 1) rts[cnt++] = root[i];
  for (int l = 1, r = MAXN;;) {
    int mid = (l + r) / 2;
    if (upper > mid) {
      l = mid + 1;
      for (int i = 0; i < cnt; ++i) {
        sum += rts[i]->left->sum;
        rts[i] = rts[i]->right;
      }
    } else if (upper < mid) {
      r = mid;
      for (int i = 0; i < cnt; ++i) rts[i] = rts[i]->left;
    } else {
      for (int i = 0; i < cnt; ++i) sum += rts[i]->left->sum;
      break;
    }
  }
  return sum;
}

int a[MAXN];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  nil = new_node();
  nil->left = nil->right = nil;

  cin >> n >> q;
  fill(root + 1, root + n + 1, nil);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    update(i, a[i], a[i]);
  }
  for (int op, x, y; q; --q) {
    cin >> op >> x >> y;
    if (op == 1) {
      update(x, a[x], -a[x]);
      update(x, y, y);
      a[x] = y;
    } else if (op == 2) {
      int mx;
      ll sum = 0, temp;
      do {
        temp = sum + 1;
        mx = temp <= MAXN ? temp : MAXN;
        sum = query(y, mx) - query(x - 1, mx);
      } while (sum >= temp);
      cout << sum + 1 << "\n";
    } else {
      assert(0);
    }
  }
  return 0;
}

J. Loli, Yen-Jen, and a graph problem

给定一个完全图，将其拆分为$n - 1$条边交集为空路径，且第$i$条路径长度为$i$。

构造题，完全不会，赛后看的别人代码。

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 3;

bitset<MAXN> used[MAXN];
int n, ans[MAXN][MAXN], mx[MAXN];

void gao1() {
  fill(mx + 1, mx + n + 1, 1);
  for (int i = 1; i <= n; ++i) used[i].set(i);
  for (int len = n - 1; len; --len) {
    ans[len][0] = n;
    int sz = 1, pre = n;
    while (sz <= len) {
      int &cur = mx[pre];
      while (used[pre][cur]) ++cur;
      ans[len][sz++] = cur;
      used[cur][pre] = used[pre][cur] = 1;
      pre = cur;
    }
  }
}

int cur_len;

void push(int x) {
  ans[cur_len][mx[cur_len]++] = x;
  if (cur_len + 1 == mx[cur_len]) {
    --cur_len;
    if (~cur_len & 1) ans[cur_len][mx[cur_len]++] = x;
  }
}

void gao2() {
  cur_len = n - 1;
  for (int i = 2; i <= n; i += 2) {
    push(i);
    for (int x = 1, y = i + 1;; ++x, ++y) {
      push(x);
      if (y > n) break;
      push(y);
    }
  }
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  cin >> n;

  (n & 1) ? (gao1(), 0) : (gao2(), 0);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= i; ++j) cout << ans[i][j] << " \n"[j == i];
  }

  return 0;
}

M. Kill the tree

给定一棵有根树，求每个子树内到其他点距离和最小的点。

一棵树内距离和最小的点就是重心，重心至多为两个。所以我们现在需要求所有子树的重心。当我们合并两棵树时，新的重心必定在旧重心的路径上。所以合并子树时只要让每个子树的重心依次往上爬即可。

 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

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

vector<int> adj[MAXN];
int sz[MAXN], fa[MAXN], ans[MAXN], ans2[MAXN];

void dfs(int u, int from) {
  sz[u] = 1;
  queue<int> q;
  for (int v : adj[u]) {
    if (v == from) continue;
    fa[v] = u;
    dfs(v, u);
    q.push(ans[v]);
    sz[u] += sz[v];
  }

  int &point = ans[u] = u, val = sz[u];
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    while (sz[u] > sz[v] << 1) v = fa[v];
    if (v == u) continue;
    int val_ = max(sz[v], sz[u] - sz[v]);
    if (val_ < val) point = v, val = val_;
  }
  if (sz[u] == sz[point] << 1) ans2[u] = fa[point];
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  int n;
  cin >> n;
  for (int u, v, i = 1; i < n; ++i) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(1, 1);
  for (int i = 1; i <= n; ++i) {
    if (ans2[i]) {
      cout << min(ans[i], ans2[i]) << " " << max(ans[i], ans2[i]) << "\n";
    } else {
      cout << ans[i] << "\n";
    }
  }

  return 0;
}
comments powered by Disqus