跃迁引擎启动

The 2018 ICPC Asia Regional Contest 选做

发表于 更新于 分类于 阅读次数：

徐州 D Rikka with Subsequences

UpSolved by XLor.

求每种本质不同好子序列的出现次数立方和。

令 $f(a)$ 表示子序列 $a$ 的出现次数，立方和展开一下，$\sum_{i=1}^{f(a)} \sum_{j=1}^{f(a)} \sum_{k=1}^{f(a)} 1$。观察上式的实际意义，等价于将序列复制三份，求公共好子序列的个数。举例来说，假如 $a$ 作为子序列出现了 $2$ 次，分别出现在位置序列 $a_1,a_2$，那么有公共子序列 $(a_1,a_1,a_1)$ 一直到 $(a_2,a_2,a_2)$ 共 $8$ 种对应。

记 $dp(i,j,k)$ 表示在第一个串以 $i$ 结尾，第二个 $j$ 结尾，第三个 $k$ 结尾的方案数。$dp(i,j,k)$ 有值当且仅当 $a_i=a_j=a_k$。

$$
dp(i,j,k)=[ a_i=a_j=a_k ]( \sum_{i’=1}^{i-1} \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} dp(i’,j’,k’) [M(a_{j’},a_i)] )
$$

转移过程相当于同时从 $(i’,j’,k’)$ 走到 $(i,j,k)$，我们将这个过程拆开变成 $3$ 个阶段，钦定先走 $i$，再走 $k$，最后走 $j$。也就是说最后一步的 $j’$ 和 $i$ 两个之间必须可以走。

枚举 $i$，令 $f(i,j,k) = \sum_{i’=1}^{i=1} dp(i’,j,k)$, $g(i,j,k) = f(i,j,k) [M(a_j, a_i)]$。

$$
dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} \sum_{i’=1}^{i=1} dp(i’,j’,k’) [M(a_{j’}, a_i)]) \
dp(i,j,k)=[ a_i=a_j=a_k ] ( \sum_{j’=1}^{j-1} \sum_{k’=1}^{k-1} g(i,j’,k’)) \
$$

因此，$dp$ 的转移，只需要对 $g$ 数组做一次二维前缀和即可。

徐州 F Rikka with Nice Counting Striking Back

UpSolved by XLor

求母串的本质不同子串个数，且子串 $T$ 满足，对于任意非空串 $P$，若 $TP=PT$，那么 $TP$ 不是 $S$ 的子串。

观察一下，对于子串 $T$，当存在 $TT$，$T$ 不合法，存在 $TTT$，$TT$ 不合法，也就是对于这样的一组串只会算一次。

上述等价于，减去多算的 $TT,TTT,TTTT,\dots$，暴力枚举每个 Runs 内部的每个右端点的周期串，哈希去重。

徐州 G Rikka with Intersections of Paths

UpSolved by XLor

给定树上 $q$ 条路径，求选出 $k$ 条有公共点的路径的方案数。

对于一种选择方案，公共点数减去公共边数等于 $1$。

对于所有点和边，分别求其出现在多少条路径上，相减即为答案。

青岛 I Soldier Game

UpSolved by XLor.

给定一个序列，将序列划分为长度为 $1$ 或 $2$ 的子串，最小化每个子串和的极差。

显然，枚举最小值，dp 出可能的最小的最大值。

令 $\infty$ 表示情况不存在，$-\infty$ 表示任意。

记 $dp(i,0/1)$ 表示 $i$ 位置是否被用过的最小最大值，当前下界为 $D$。

$$
dp(i,0)=dp(i-1,1) \
dp(i,1)=\min(\max(a_i+a_{i-1}, dp(i-1,0)), \max(a_i, dp(i-1,1)))
$$

上式中的 $a_i,a_i+a_{i-1}$ 均会在 $< D$ 时，被换成 $\infty$。最终最小的最大值为 $dp(n,1)$。

上面的 $dp$ 状态改成可以线段树动态维护的，允许区间合并的状态。

令 $dp(l,r,0/1,0/1)$ 表示：

  • 00：$[l,r]$ 都被用上；

  • 01：$l$ 和 $l-1$ 配对；

  • 10：$r$ 没有被用上；

  • 11：$l$ 和 $l-1$ 配对，且 $r$ 没有被用上。

合并时，只需要枚举中间两个位置的情况即可。

代码

青岛 I Soldier Game

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
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <cmath>
#include <functional>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const ll inf = 1ll << 60;
const int maxn = 100000 + 5;

int n, a[maxn]; ll mn;

struct Info {
  ll val[2][2];
  Info() {
    val[0][0] = val[0][1] = val[1][0] = val[1][1] = inf;
  }
  Info(int i) {
    if (a[i] >= mn) { // 两端点不匹配
      val[0][0] = a[i];
    } else {
      val[0][0] = inf;
    }
    if (a[i] + a[i - 1] >= mn) { // 左端点匹配
      val[1][0] = a[i] + a[i - 1];
    } else {
      val[1][0] = inf;
    }
    val[0][1] = -inf; // 右端点匹配
    val[1][1] = inf; // 两端均匹配，不存在
  }
  ll* operator [] (int x) { return val[x]; }
  const ll* operator [] (int x) const { return val[x]; }
  Info operator+(const Info& b) {
    Info r;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        ll x = max(val[i][0], b[0][j]);
        ll y = max(val[i][1], b[1][j]);
        r[i][j] = min(x, y);
      }
    }
    return r;
  }
} t[maxn << 2];

void build(int l = 1, int r = n, int rt = 1) {
  if (l == r) {
    t[rt] = Info(l); return ;
  }
  int m = (l + r) / 2;
  build(lson); build(rson);
  t[rt] = t[rt << 1] + t[rt << 1 | 1];
}
void update(int i, int l = 1, int r = n, int rt = 1) {
  if (l == r) {
    t[rt] = Info(l); return ;
  }
  int m = (l + r) / 2;
  if (i <= m) update(i, lson);
  else update(i, rson);
  t[rt] = t[rt << 1] + t[rt << 1 | 1];
}

ll cal(int mn) {
  vector<ll> f(n + 1, -inf), g(n + 1, -inf);
  for (int i = 1; i <= n; i++) {
    // f[i] = min(f[i - 1], g[i - 1]);
    f[i] = g[i - 1];
    ll one = a[i];
    ll two = a[i] + a[i - 1];
    if (one < mn) one = inf;
    if (two < mn) two = inf;
    g[i] = min(max(one, g[i - 1]), max(two, f[i - 1]));
  }
  return g[n];
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    vector<tuple<int,int,int> > teams;
    for (int i = 1; i <= n; i++) {
      scanf("%d", a + i);
      teams.emplace_back(a[i], i, 1);
      if (i > 1) {
        teams.emplace_back(a[i - 1] + a[i], i, 2);
      }
    }
    sort(begin(teams), end(teams));
    mn = get<0>(teams[0]);
    build(); 
    ll ans = inf;
    for (int i = 0, j; i < n + n - 1; i = j) {
      ans = min(ans, min(t[1][0][0], t[1][1][0]) - mn);
      j = i;
      while (j < n + n - 1 && get<0>(teams[i]) == get<0>(teams[j])) j++;
      if (j == n + n - 1) break;
      mn = get<0>(teams[j]);
      for (int k = i; k < j; k++) update(get<1>(teams[k]));
    }
    printf("%lld\n", ans);
  }
  return 0;
}