Atcoder arc130

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
D(树上DP,子树点乘代价合并,总代价为n方), E(细节题，不会依然不会)

D

https://atcoder.jp/contests/arc130/tasks/arc130_d

给一个树,对节点赋值1~n,两两互不相同,

限制:树上的点要么小于它直接相邻所有点的值,要么大于它直接相邻所有点的值

求方案数.

题解

显然任意选一个为根, 大于和方案和小于的方案对称性,可以只算一个然后乘2

也可以,看成二分图,但是是求满足拓扑序的赋值方案数

注意到大于和小于关系,只需要颠倒就能实现,所以这里我们只讨论 根节点大于所有直接相邻的子节点

我们考虑树上DP

状态设计为 ans[i][j] = 节点i在它和它的所有子树节点中,排序从小到大刚好为j的方案数

对于一个选定的节点,有子树T1,T2,T3,T4,…

设它们的根节点为r1,r2,r3,r4,…

设它们的节点个数为s1,s2,s3,s4,…

那么, 我们考虑维护合并这些子树.

因为 我们这里考虑的是 当前节点要大于所有子树的根节点

所以 合并的时候维护 dp[i] = 已合并的子树中,根节点最大值恰好为i的方案数

以T1和T2为例

分成两种, T1的根更大,和T2的根更大(可以对称处理)

下面讨论 T1根更大

设r1在T1 中的位置为i(1-index)

合并后的序列为(i-1个T1中的点 和 j个T2中的点) r1 ((s1-i)个T1中的点 和 (s2-j)个T2中的点)

注意在两个子树分别的内部,顺序已经固定, 所以只有交叉的顺序不定

方案为 $C((i-1)+j,i-1) \cdot C((s1-i)+(s2-j),s1-i) \cdot ans[r1][i]$

再考虑, T2中的r2的位置,因为T1根更大,所以r2只能在前j个中

$dp[i+j] += C(i+j-1,i-1) \cdot C(s1+s2-i-j,s1-i) \cdot ans[r1][i] \cdot (ans[r2][1]+\cdots +ans[r2][j])$

右边的和可以前缀和O(1),

组合数可以预处理递推O(1),

所以

我们通过 循环一遍T1的节点数,再一遍T2的节点数数,就能得到dp, 每个+= 是O(1)

这里总代价n2,而我错误估计以为n3就没写,哭了

乍看上去,所有节点处理一次,每个节点是子树之间合并,个数的乘积是n3复杂度

实际上,考虑贡献, 一次合并子树的两个子树节点个数乘积大小的代价, 相当于,两个子树之间的节点建立一个配对关系.又因为任何两个节点至多建立两次(讨论根更大)关系,所以总代价为$O(n^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
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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 998244353
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
int n;  // <=3000
vector<int> p2[3010]; // 树连接关系
// [node i][从小到大第j个] = 方案数
vector<vector<ll> > ans(3010, vector<ll>(1, 0));
 
ll qC[3010][3010]; // 预处理组合数
 
void mergeTable(const vector<ll>& arr0,
                const vector<ll>& arr1,
                vector<ll>& res) {
 
  vector<ll> presum(arr1.size(), arr1[0]);
  rep(i, 1, arr1.size()) { presum[i] = (arr1[i] + presum[i - 1]) % MOD; } // 前缀和
  // arr0 根更大 , root(arr0) > root(arr1)
  // 虽然每次代价是 子树大小之和 x arr0.size()，看起来是三次方，
  // 但实际上,从贡献角度思考 总代价n2
  rep(i, 0, arr0.size()) {
    rep(j, 0, arr1.size()) {
      // arr0: i 个 左侧， arr0.size()-i-1 个 右侧
      // arr1: j+1 个 左侧, arr1.size()-j-1 个右侧
      // res: i+j+1 个左侧, arr0.size()+arr1.size()-i-j-2 个右侧
      // presum = presumof arr1
      // 就是表达式 加上了MOD
      (res[i + j + 1] +=
       (((arr0[i] * qC[i + j + 1][i]) % MOD *
         qC[arr0.size() + arr1.size() - i - j - 2][arr0.size() - i - 1]) %
        MOD * presum[j]) %
       MOD) %= MOD;
    }
  }
}
 
void dfs(int idx, int fa/*父节点*/, int g/*大于小于关系*/) {
  vector<ll> dp = {};  // [最大的子树 根节点 位置] = 方案数
  for (auto item : p2[idx]) {
    if (item == fa)
      continue;
    dfs(item, idx, g ^ 1);
    if (g) {  // 逆向
      // 只用一次也不需要恢复了
      reverse(ans[item].begin(), ans[item].end());
    }
    if (!dp.size()) {
      dp = ans[item];
    } else {
      vector<ll> res(dp.size() + ans[item].size(), 0);
      mergeTable(dp, ans[item], res); // dp 根更大
      mergeTable(ans[item], dp, res); // ans[item] 根更大
      dp = res;
    }
  }
  ans[idx] = vector<ll>(dp.size() + 1, 0);
  if (dp.size() == 0) {
    // 叶子节点
    ans[idx][0] = 1;
  } else {
    ll cnt = 0;
    rep(i, 0, dp.size() + 1) { // 实际上也是前缀和, 当前节点 大于 所有子树根节点
      ans[idx][i] = cnt;
      (cnt += dp[i]) %= MOD;
    }
  }
  if (g) {
    reverse(ans[idx].begin(), ans[idx].end());
  }
}
 
int main() {
  rep(i, 0, 3001) {
    rep(j, 0, i + 1) {
      qC[i][j] = j == 0 ? 1 : (qC[i - 1][j] + qC[i - 1][j - 1]) % MOD;
    }
  }
 
  scanf("%d", &n);
  rep(i, 0, n - 1) {
    int u, v;
    scanf("%d %d", &u, &v);
    p2[u].push_back(v);
    p2[v].push_back(u);
  }
  dfs(1, 0, 0);
  ll res = 0;
  rep(i, 0, n) { (res += ans[1][i]) %= MOD; }
  printf("%lld\n", (2 * res) % MOD); // 大于小于对称性 乘2
  return 0;
}

submissions

官方题解

总结

  1. 可以当作知识点的: 子树全部 节点数相乘的代价,总代价是$O(n^2)$
  2. 复杂度也可以在纸上不要脑补

E

https://atcoder.jp/contests/arc130/tasks/arc130_e

一个数组，每次选最小值中的一个+1，记录下标。

形成了一个下标数组。

现在给你下标数组，求满足下标数组的字典序最小的原数组

题解

题目样例为例

1 1 4 4 2 1

如果 我们能给他们分组

1 | 1 4 | 4 2 1

那么，很容易知道合法的最小结果

1 (操作前大小为1)| 1 4 (操作前大小为2) | 4 2 1 (操作前大小为3)

我们只关心

1 | 1 4 (操作后所有为3)

所以原数组为

3-2 3-0 3-0 3-1 = 1 3 3 2

所以核心问题变成去找这个层之间的分割线

见下面代码中的注释

last(pos) = 这个位置值相同的值的上一个位置

cur[value] = 位置，辅助计算last的数组

cnt 当前层的个数

mx 上一层至少的结束的位置/当前层至少的起始位置

f(pos)= pos是有效的层级分割值，或者-1

代码

jiangly 大佬的代码 加的注释的

https://atcoder.jp/contests/arc130/submissions/27614814

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
 
// 若按照 最后一次出现的顺序排序1~n
// 最优结果的起始最小值一定是1
// 那么所有最优结果 在所有操作后 一定满足 AN-1<=A1<=A2<=A3<=...<=AN
 
int main() {
  int N, K;
  scanf("%d %d", &N, &K);
 
  vector<int> i(K);
  rep(k, 0, K) {
    scanf("%d", &i[k]);
    i[k]--;  // (0-index)
  }
 
  vector<int> last(K);  // 这个位置上同一个数上一次出现的位置 last[pos] = oldpos
  vector<int> cur(N, -1);  // 最后一次出现的位置 cur[value] = pos
  rep(k, 0, K) {
    last[k] = cur[i[k]];
    cur[i[k]] = k;
  }
 
  vector<int> f(K + 1, 0);  // 相当于找有效分割线 = 分割线的层级，从0开始
  int cnt = 0;
  int mx = -1;
  rep(k, 0, K) {
    mx = max(mx, last[k]);  // 更新最近上一组数 的最大下标
    if (last[k] == -1) {    // 当前值首次出现
      cnt++;                // 属于组的个数+1
    }
    // -1 无效值
    // 最大位置 和 当前位置之间个数小于 cnt 则 无效
    // 上一个位置无效则 无效,
    // 因为如果当前是分割线，那么当前到上一个分割线的距离一定恰好是cnt
    f[k + 1] =
        (mx >= k + 1 - cnt || f[k + 1 - cnt] == -1) ? -1 : 1 + f[k + 1 - cnt];
  }
 
  int c = -1;    // 分割最小层数
  int len = -1;  //
  rep(k, mx + 1,
      K + 1) {  // 对于最后一组分割，最后一组里各不相同，且组长度 <= cnt
    // 上一个分割线有效
    // 尚无合法的，或当前层数小于等于 上一个方案
    if (f[k] >= 0 && (c == -1 || c >= f[k])) {
      c = f[k];  // 更新层数
      len = k;   // 最后一组的起点位置
    }
  }
  // 没有有效的最后一组
  if (c == -1) {
    cout << "-1\n";
    return 0;
  }
 
  // 从最后的结果反推初始值,
  // 这里排除了最后一组，所以在最后一组之前，所有值是相等的
  vector<int> A(N, c + 1);  // 最后的结果
  rep(k, 0, len) { A[i[k]]--; }
  rep(i, 0, N) { printf("%d%c", A[i], " \n"[i == N - 1]); }
 
  return 0;
}

总结

跳表什么都会，但是能把细节分析出来，感觉是熟练度而不是什么缺失的知识点。属于这次学会了，下次可能还是不会的题。