A1.

  • 考虑将所有数字变成大于零的，可以前缀和。

  • 考虑将所有数字变成小于零的，可以后缀和。

A2.

按照 A1 的策略，倍增，分类讨论。

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
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);
  vector<pair<int, int>> ans;
  rep (i, 0, n) cin >> a[i];
  int pos = 0, neg = 0;
  rep (i, 0, n) if (a[i] > 0) pos += 1;
  rep (i, 0, n) if (a[i] < 0) neg += 1;
  auto print = [&]() {
    cout << sz(ans) << "\n";
    for (auto [x, y] : ans) {
      cout << x + 1 << " " << y + 1 << "\n";
    }
    return;
  };
  if (*min_element(a.begin(), a.end()) >= 0) {
    rep (i, 1, n) ans.emplace_back(i, i - 1);
    return print();
  }
  if (*max_element(a.begin(), a.end()) <= 0) {
    for (int i = n - 1; i >= 1; i--) ans.emplace_back(i - 1, i);
    return print();
  }
  if (neg && pos <= 7) {
    int p = -1;
    rep (i, 0, n) if (a[i] < 0) {
      p = i;
      break;
    }
    rep (i, 0, 5) a[p] *= 2, ans.emplace_back(p, p);
    rep (i, 0, n) if (a[i] > 0) {
      a[i] += a[p];
      ans.emplace_back(i, p);
    }
    for (int i = n - 1; i >= 1; i--) ans.emplace_back(i - 1, i);
    return print();
  }
  if (pos && neg <= 7) { // neg <= 7
    int p = -1;
    rep (i, 0, n) if (a[i] > 0) {
      p = i;
      break;
    }
    rep (i, 0, 5) a[p] *= 2, ans.emplace_back(p, p);
    rep (i, 0, n) if (a[i] < 0) {
      a[i] += a[p];
      ans.emplace_back(i, p);
    }
    rep (i, 1, n) ans.emplace_back(i, i - 1);
    return print();
  }
  // 8 <= pos <= 12 && 8 <= neg <= 12
  int p = 0;
  rep (i, 0, n) if (abs(a[i]) > abs(a[p])) p = i;
  if (a[p] > 0) {
    rep (i, 0, n) if (a[i] < 0) ans.emplace_back(i, p); // 12
    rep (i, 1, n) ans.emplace_back(i, i - 1); // 19
  } else {
    rep (i, 0, n) if (a[i] > 0) ans.emplace_back(i, p); // 12
    for (int i = n - 1; i >= 1; i--) { // 19
      ans.emplace_back(i - 1, i);
    }
  }
  return print();
}

B.

有一个长度为 $n$ 的牌，每个牌上面的数字为 $a_i$，初始只有一张牌。每次可以用一张牌进行两种操作。

  • 往下摸 $a_i$ 张牌，直到摸完。
  • 获得 $a_i$ 的分数，并丢弃。

如果知道哪些前缀可以恰好被解锁，就可以用 $\sum_{j=1}^{i} a_j - (i - 1)$，因为需要 $i-1$ 的代价来解锁前缀。

从左往右递推，如果最长可以被解锁的前缀 $p$ 小于当前的位置，则 $i$ 一定无法被解锁，退出。

否则对于解锁了 $i$ 的方案，可以再解锁 $a_i$ 张。

用 bitset 优化即可。

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
const int N = 1e5 + 5;
bitset<N * 2> f;
void solve() {
  int n;
  cin >> n;
  f[1] = 1;
  vc<ll> s(n + 1);
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if (s[i - 1] < i - 1) {
      cout << ans << "\n";
      return;
    }
    s[i] = s[i - 1] + x;
    f |= f << x;
    if (f[i]) {
      cmax(ans, s[i] - (i - 1));
      f[i] = 0;
    }
  }
  for (int i = n + 1; i <= n * 2; i++) {
    if (f[i]) {
      cmax(ans, s[n] - (i - 1));
    }
  }
  cout << ans << "\n";
}

C.

给定集合 $S$，每个数在 $1 \sim m$ 之间，每一秒进行一个操作。

  • 从 $S$ 中等概率选择一个数字 $x$
  • 将 $x$ 从 $S$ 里面删去。
  • 若 $x+1\leq m$，且 $x+1 \notin S$，把 $x+1$ 加入 $S$。

求 $S$ 变成空集的期望时间对 $1e9+7$ 取模。

$n, m\leq 500$。

先考虑 $S$ 是一个可重集，那么每次操作会让 $\sum S$ 恰好增加 1，答案上界是 $\sum m + 1 - S_i$。但是里面有算重的部分。

考虑怎么去掉算重的部分：考虑相邻两个元素的差，每次操作会将至多一个差值变为 0。如果变为 0 的相邻两个元素为 $t$，则答案会减少 $m+1-t$。

根据期望的线性性，将答案摊到每相邻两个元素上。根据 $S_{i+1} \leq t < m$。求出过程中 $S_{i +1}$ 是 $S_i = t$ 的概率，则将答案减去 $P \times (m + 1- t)$。

这等价于求出 $S_i = S_{i + 1} = t$ 的概率 $P$。

设 $f_{x, y}$ 表示 $S_i = x$ 且 $S_j = y$ 的概率。初始化 $f_{S_i,S_{i+1}} = 1$。

  • 对于 $(x, y), x < y$，以 $1/2$ 的概率转移到 $f_{x+1,y}$ 和 $f_{x, y+1}$ 上，我们不关心别的元素被选中。

复杂度 $O(n+m^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
const int P = 1e9 + 7;
const int iv2 = (P + 1) / 2;

void md(int &x) {
  if (x >= P) {
    x -= P;
  }
}

void solve() {
  int N, M;
  cin >> N >> M;
  int ans = 0;
  vi a(N);
  rep(i, N) cin >> a[i], --a[i], ans += M - a[i];
  vc<vi> dp(M, vi(M));
  rep(i, N - 1) dp[a[i]][a[i + 1]] = 1;
  rep(i, M) {
    rep(j, i + 1, M) {
      int x = dp[i][j];
      x = 1ll * x * iv2 % P;
      if (j + 1 < M)
        md(dp[i][j + 1] += x);
      if (i + 1 < M)
        md(dp[i + 1][j] += x);
    }
  }
  rep(i, M) md(ans += P - 1ll * dp[i][i] * (M - i) % P);
  cout << ans << "\n";
}

E.

设 $F$ 为背包数组，$F_{60}$ 为构造出 $60$ 的不同方案数，要求给出一组使得 $F_{60} = m$ 的方案。

考虑可以先随机加入 $\leq 6$ 的数字，取到 $F_{60} \leq m$ 的最大的 $F_{60}$。

然后每次找到使得 $F_{60}$ 增幅最大的一个，迭代这个操作，就可以得到一组合法解了。

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
void f(vector<long long> &F, int v) {
  for (int i = 60; i >= v; i--) F[i] += F[i - v];
}
void solve() {
  long long m;
  cin >> m;
  while (true) {
    vector<int> ans;
    vector<long long> F(61, 0); F[0] = 1;
    while (true) {
      int x = rng() % 6 + 1;
      auto NF = F;
      f(NF, x);
      if (NF[60] > m) {
        break;
      }
      ans.emplace_back(x);
      f(F, x);
    }
    while (F[60] < m) {
      int p = 0;
      rep (i, 0, 60)
        if (F[60] + F[i] <= m)
          if (F[i] > F[p])
            p = i;
      ans.emplace_back(60 - p);
      f(F, 60 - p);
    }
    if (sz(ans) <= 60) {
      debug(F[60]);
      cout << sz(ans) << "\n";
      for (int x : ans) {
        cout << x << " ";
      }
      cout << "\n";
      break;
    }
  }
}