A.

简单题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[25];
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i < n; i++) {
    if ((i & -i) == i) continue;
    if (a[i] > a[i + 1]) {
      cout << "No\n";
      return;
    }
  }
  cout << "Yes\n";
}

B.

考虑 $x$ 最后单调不增，模拟可以做到 $O(\log^2 + n)$。

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
void solve() {
  int n, q;
  cin >> n >> q;
  vi a(n);
  rep(i, n) cin >> a[i];
  vi qq;
  rep(i, q) {
    int x;
    cin >> x;
    if (qq.empty()) qq.emplace_back(x);
    else {
      if (qq.back() <= x) continue;
      qq.emplace_back(x);
    }
  }
  // debug(qq);
  ll w[31];
  memset(w, 0, sizeof w);
  for (int j = 0; j <= 30; j++) {
    w[j] = 0;
    for (int x : qq) {
      if (j >= x) {
        w[j] += 1 << x - 1;
      }
    }
  }
  rep(i, n) {
    cout << a[i] + w[__lg(a[i] & -a[i])] << " \n"[i + 1 == n];
  }
}

C.

排序之后贪心。

注意可能 $\lfloor \frac{sum}{2}\rfloor = 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

void solve() {
  int n;
  cin >> n;
  ll s = 0;
  vi a(n);
  rep(i, n) {
    cin >> a[i];
    s += a[i];
  }
  s /= 2;
  sort(all(a));
  ll ans = 0;
  for (int i = n - 1; s; i--) {
    if (s >= a[i]) {
      s -= a[i];
      a[i] = 0;
      ans += 1;
    } else {
      a[i] -= s;
      s = 0;
      ans += 1;
      break;
    }
  }
  cout << ans + accumulate(all(a), 0LL) << "\n";
}

D.

按位，二分。

复杂度 $O(T\log^2)$。

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
const int P = 1e9 + 7;
void solve() {
 
  auto solve = [&](ll l, ll r, ll x) {
    if (l > r) {
      return 0LL;
    }
    // debug(l, r, x);
    ll c = 0;
    __int128 p = 1;
    while (p * x <= l) {
      p = p * x;
      c += 1;
    }
    ll res = 0;
    for (ll i = l, j; i <= r; i = j + 1, p = p * x, c++) {
      // debug(i);
      ll L = i - 1, R = r + 1;
      while (R - L > 1) {
        // debug(L, R);
        ll M = (L + R) / 2;
        if (p <= M && M < p * x) {
          L = M;
        } else {
          R = M;
        }
      }
      j = L;
      // debug(i, j);
      res += 1ll * (j - i + 1) % P * c % P;
      if (res >= P) {
        res -= P;
      }
    }
    return res;
  };
 
  ll l, r;
  cin >> l >> r;
  ll ans = 0;
  for (int i = 0; i < 62; i++) {
    ll L = 1LL << i;
    ll R = 1LL << i + 1;
    --R;
    ans += solve(max(l, L), min(r, R), i);
    if (ans >= P) {
      ans -= P;
    }
  }
  cout << ans << "\n";
}

E.

假做法过题。

考虑 $k$ 越大答案越优秀，这是显然的。

很显然可以 dp，状态为 $dp_{i,j,k}$ 表示这是第 $i$ 个位置，用了 $j$ 次，上一个位置是不是 $0$。

然后可以在平均值附近选 $\sqrt n$ 个，如果数据随机，错误率非常的低。

记得开 ll。

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
void solve() {
  cin >> n >> k;
  rep(i, n) {
    cin >> a[i];
  }
  rep(i, 1, n) {
    rep(j, 2) {
      rep(nj, 2) {
        int x = a[i - 1];
        int y = a[i];
        if (j == 1) {
          x = 0;
        }
        if (nj == 1) {
          y = 0;
        }
        if (gcd(x, y) == 1) {
          coef[i][j][nj] = 1;
        } else {
          coef[i][j][nj] = 0;
        }
      }
    }
  }
 
  rep(c, 0, 2) rep(i, k + 1) rep(j, 2) dp[c][i][j] = inf, vis[c][i][j] = -1;
  dp[0][0][0] = 0;
  dp[0][1][1] = 0;
  vis[0][0][0] = 0;
  vis[0][1][1] = 0;
  int p = 1, q = 0;
  for (int i = 1; i < n; i++, p ^= 1, q ^= 1) {
    int l = 1ll * k * (i + 1) / n - 500;
    int r = 1ll * k * (i + 1) / n + 500;
    cmax(l, 0);
    cmin(r, k);
    rep(kk, l, r + 1) {
      dp[p][kk][0] = dp[p][kk][1] = inf;
      rep(j, 2) {
        rep(nj, 2) {
          if (kk >= nj) {
            if (vis[q][kk - nj][j] < i - 1) continue;
            cmin(dp[p][kk][nj], dp[q][kk - nj][j] + coef[i][j][nj]);
            vis[p][kk][nj] = i;
          }
        }
      }
    }
  }
 
  cout << min(dp[q][k][0], dp[q][k][1]) << "\n";
}

F.

倒着扫描线。

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
void solve() {
  int q;
  cin >> q;
  vc<vi> g(1);
  vc<vi> qq(q);
  vc<vc<pii>> ad(q);
  rep(i, q) {
    int o;
    cin >> o;
    if (o == 1) {
      int v;
      cin >> v;
      --v;
      int n = g.size();
      g[v].pb(n);
      g.pb();
      qq[i].pb(n);
    } else {
      int v, x;
      cin >> v >> x;
      --v;
      ad[i].pb(v, x);
    }
  }
  
  int n = (int)g.size();
 
  vi dfn(n);
  vi sz(n);
  int c = 0;
  auto dfs = [&](auto &self, int u) -> void {
    // debug(u, g[u]);
    sz[u] = 1;
    dfn[u] = c++;
    for (auto v : g[u]) {
      self(self, v);
      sz[u] += sz[v];
    }
  };
  dfs(dfs, 0);
 
  vc<ll> t(n * 2);
  auto add = [&](int x, int v) {
    if (x == n) {
      return;
    }
    x += n;
    while (x) {
      t[x] += v;
      x >>= 1;
    }
  };
  auto query = [&](int l, int r) {
    ll res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        res += t[l++];
      }
      if (r & 1) {
        res += t[--r];
      }
    }
    return res;
  };
 
  vc<ll> ans(n);
  for (int i = q - 1; i >= 0; i--) {
    for (auto [v, x] : ad[i]) {
      add(dfn[v], x);
      add(dfn[v] + sz[v], -x);
    }
    for (auto v : qq[i]) {
      ans[v] = query(0, dfn[v] + 1);
    }
  }
 
  ans[0] = query(0, 1);
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " \n"[i + 1 == n];
  }
}