🔖 acm递推状态压缩动态规划字典树解题报告

1002 K 个连通块

题目链接

题目简析

假入 $N$ 个点依次为：$\displaystyle V=\left\lbrace A_0,A_1,\cdots,A_{N-1} \right\rbrace$. 不难想到状态压缩。令 $dp(k, s)$ 表示点集 $\displaystyle V_s= \left\lbrace A_i \;\Bigg|\; \left\lfloor \frac{s}{2^i} \right\rfloor \equiv 1 \mod 2 \right\rbrace$ 恰好构成 $k$ 个连通块的方案数。要注意的是，点对 $\displaystyle \big\lbrace (u,v) \;\big|\; u \in V, v\in V_s \big\rbrace$ 之间的连边都要抹去，因为 $V_s$ 中的点首先要和不在 $V_s$ 中的断开“联系”，才能得到独立的 $k$ 连通块，这样才能正确递推。

如何求 $dp(1,s)$

为方便叙述，记 $f(s) = dp(1,s)$， $\displaystyle s=2^{j_1}+2^{j_2}+\cdots+2^{j_t}$，故其所代表点集为 $\displaystyle V_s=\big\lbrace A_{j_1},A_{j_2},\cdots,A_{j_t} \big\rbrace$, $(0\leqslant j_1 < j_2 < \cdots < j_t \leqslant N-1)$. 令 $E(s)$ 表示 $V_s$ 中的互不相同的两点之间的边的总数；则

$$f(s) = 2^{E(s)} - \sum_{A_{j_1} \in V_{s'},~V_{s'} \in \lbrace V_s \rbrace} f(s') \times 2^{E(s-s')}$$

证明并不难，为使 $V_s$ 为一个独立的连通块，则需要考虑两个部分：

  1. $V_s$ 中的点与不在 $V_s$ 中的点之间不连通；因此，我们仅需考虑 $V_s$ 中两两之间的边，去边的总方案为 $2^{E(s)}$.

  2. $V_s$ 内部的点两两连通；可以反过来考虑，减去所有使得内部不连通的情况。将点集 $V_s$ 分成 $V_{s'}$ 和 $V_{s''}$ 两部分，其中 $V_{s'}+V_{s''}=V_s$ 且 $A_{j_1} \in V_{s'}$，且 $V_{s'}$ 构成一个独立的连通块。对于这一划分方案，共有 $f(s') \times 2^{E(s-s')}$ 种方案使得 $V_{s'}$ 和 $V_{s''}$ 之间不连通。因为 $V_{s'}$ 是一个独立的连通块，所以 $V_{s'}$ 和 $V_{s''}$ 之间的边必须全断，则 $V_{s''}$ 中的边可以自由选择了。

如何递推

不难想到递推方程 $\displaystyle dp(k+1,s) = \sum_{V_{s'} \in V_s} dp(k,s') \times dp(1, s-s')$. 但是很遗憾，它是错的：

考虑 $k=3$ 的情况，如果 $V_s=\big\lbrace A_1, A_2,A_3 \big\rbrace$，则 $V_{s'}=\big\lbrace A_1,A_2 \big\rbrace$ 与 $V_{s'}=\big\lbrace A_1, A_3 \big\rbrace$ 所做的贡献是完全重复的。

去掉重复的贡献，我们得到新的递推式

$$dp(k+1, s) = \sum_{A_{j_1} \notin V_{s'},~V_{s'} \in V_s} dp(k, s') \times dp(1, s-s')$$

进一步分析

上述分析足以通过此题，我跑了 858MS。但还有改进的余地。先改造一下递推式，记 。

$$\begin{align} V'_s&=V-V_{s'}=\big\lbrace A_{p_1},A_{p_2},\cdots,A_{p_q} \big\rbrace\\\\ dp(k+1, s) &= \sum_{A_{j_1} \in V_{s'},~V_{s'} \in V_s,~A_{p_1} \in V_{s-s'}} dp(k, s') \times dp(1, s-s') \end{align}$$

上述递推式用刷表法实现即可避免 $A_{p_1} \in V_{s-s'}$ 的判断。注意到我们要的终态是 $dp(K, 2^N-1)$，所以，我们可以只计算满足 $A_1 \in V_s$ 的状态 $dp(K, s)$，理由是 $A_1 \in V_{s'}$，即这条递推到 $dp(K, s)$ 的递推链都可以被计算到。当然，也可以采取记忆化搜索。跑了 124MS 左右。

程序实现

  • 空间复杂度 $O(2^N)$
  • 时间复杂度 $O(N^2 \cdot 2^N+K \cdot 3^N)$
1002.cpp  | 112 lines.
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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;


typedef long long LL;
const int MAXN = 15;
const int MOD = 1000000000 + 9;


int G[MAXN][MAXN];
int p2[MAXN * MAXN];
int l2[1 << MAXN];
int dp[2][1 << MAXN];
int f[1 << MAXN];
int c[1 << MAXN];


inline int lowbit(int& x) {
  return x & -x;
}


inline void add(int& x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}


inline void sub(int& x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}


int calc(int N, int K) {
  const int all = (1 << N) - 1;
  int now = 0, last = 1;


  for (int s = 0; s <= all; s += 2) dp[0][s] = 0;
  for (int s = 1; s <= all; s += 2) dp[0][s] = f[s];
  for (int k = 1; k < K; ++k) {
    swap(now, last);
    memset(dp[now], 0, sizeof dp[now]);
    for (int s = 1; s <= all; ++s) {
      if (!dp[last][s]) continue;
      int r = all ^ s;
      int x = lowbit(r);
      r ^= x;


      for (int t = r; t; t = (t - 1) & r)
        add(dp[now][s | x | t], (LL)dp[last][s] * f[t | x] % MOD);
      add(dp[now][s | x], (LL)dp[last][s] * f[x] % MOD);
    }
  }
  return dp[now][all];
}


void solve(int N, int K, int e) {
  const int all = (1 << N) - 1;
  static int vi[20];
  int siz, cnt;


  for (int s = 1; s <= all; ++s) {
    siz = cnt = 0;
    for (int u = s, v; u; u ^= v) vi[siz++] = l2[v = lowbit(u)];
    for (int u = 0; u < siz; ++u)
      for (int v = u + 1; v < siz; ++v) cnt += G[vi[u]][vi[v]];
    c[s] = p2[cnt];
  }


  memcpy(f, c, sizeof f);


  for (int s = 1; s <= all; ++s) {
    int ls = lowbit(s);
    if (ls == s) continue;
    int r = s ^ ls;
    for (int t = (r - 1) & r; t; t = (t - 1) & r)
      sub(f[s], (LL)f[t | ls] * c[r ^ t] % MOD);
    sub(f[s], (LL)f[ls] * c[r] % MOD);
  }


  int ans = (LL)calc(N, K) * p2[e] % MOD;
  printf("%d\n", ans);
}


void work() {
  p2[0] = 1;
  for (int i = 1; i < MAXN * MAXN; ++i) p2[i] = p2[i - 1] * 2 % MOD;
  for (int i = 0; i < MAXN; ++i) l2[1 << i] = i;


  int T_T, N, M, K, e, u, v;
  scanf("%d", &T_T);
  for (int kase = 1; kase <= T_T; ++kase) {
    printf("Case #%d:\n", kase);
    memset(G, 0, sizeof G);
    e = 0;


    scanf("%d%d%d", &N, &M, &K);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &u, &v);
      if (u > v) swap(u, v);
      if (u != v)
        ++G[u - 1][v - 1];
      else
        ++e;
    }


    solve(N, K, e);
  }
}


int main() {
  work();
  return 0;
}

1004 XOR 游戏

题目链接

题目简析

设 $dp(k, n)$ 表示将前 $n$ 个数划分成 $k$ 组的合法方案的分组异或和最小值的最大值；并设 $A_n$ 表示前 $n$ 个数的异或和。不难得到递推方程：

$$dp(k+1, n) = \max \Big\lbrace \min \big\lbrace dp(k, n-i), A_n \oplus A_{n-i} \big\rbrace \Big\rbrace, 1\leqslant i\leqslant L$$

很可惜，这个方程的时间复杂度是 $O(M\cdot N\cdot L)$ 的，难以承受。如何在更短的时间内求出 $dp(k+1, n)$ 呢？

算法一

先假设 $\big\lbrace A_{n-L},A_{n-L+1},\cdots,A_{n-1} \big\rbrace$ 两两不相等；并将其二进制表示插入字典树中。字典树中表示 $A_i$ 的链，其叶子节点的权值为 $dp(k, i)$，非叶子节点权值为所有子孙节点权值最大值。那么，计算 $dp(k+1, n)$ 时，仅需在用字典树贪心求 $A_n$ 最大异或和的基础上，将节点的权值作为选择贪心策略的依据。具体地：

设当前在字典树中第 $h$ 层(考虑到题目的数据范围，从 $31$ 开始递减计数，所有叶子节点都在第 $0$ 层)：记在前面 $31-h$ 层中，选择的边边权依次为：$a_{30},a_{29},\cdots,a_{h}$. 并记：

$$\begin{align} x&=A_n=b_{30}\cdot 2^{30}+b_{29}\cdot 2^{29}+\cdots+b_0 2^{0}\\ y&=(a_{30} \oplus b_{30})\cdot 2^{30}+(a_{29} \oplus b_{29})\cdot 2^{29}+\cdots+(a_{h} \oplus b_{h})\cdot 2^h \end{align}$$

接下来考虑下一层往哪走，即 $a_{h-1}$ 的取值。

记与当前节点相连且边权为 $a_{h-1} = b_{h-1} \oplus 1$ 的子节点为 $o_1$；另一子节点为 $o_2$。其权值依次为 $val(o_1), \; val(o_2)$.

  1. $\displaystyle \left\lfloor \frac{x}{2^h} \right\rfloor \equiv 1\hskip -1em \mod 2$. 也就是 $b_h=1$.

    • 如果 $val(o_1) < y+2^{h-1}$，说明如果下一步选择 $o_1$，则

      $$\max \Big\lbrace \min \big\lbrace dp[k][n-i], A[n] \oplus A[n-i] \big\rbrace \Big\rbrace = val(o_1)$$

      所以我们 仅需选择 $o_2$ 求出一个最优值 $ans_2$，最后的答案就是 $\max \big\lbrace val(o_1),ans_2 \big\rbrace$.

    • 如果 $val(o_1) \geqslant y+2^{h-1}$，即选择 $o_1$，则最坏情况答案不小于 $y+2^{h-1}$. 同时，选择 $o_2$，最好的情况不会大于 $y+2^{h-1}$.

      所以我们 仅需选择 $o_1$ 求出一个最优值 $ans_1$，即是最后的答案。

  2. $\displaystyle \left\lfloor \frac{x}{2^h} \right\rfloor \equiv 0\hskip -1em \mod 2$. 也就是 $b_h=0$.

    只有走到 $o_2$ 这一个选择。

根据上面的分析，不难发现，查询操作时间复杂度为 $O(1)$。如果存在一对 $(i,j)$ 使得 $A_i=A_j$ 呢？

事实上，只要保证字典树中的表示 $A_i$ 的链的叶子节点权值为 $\max \big\lbrace dp[k][n-i],dp[k][n-j] \big\rbrace$ 就好了。可以先将 $A$ 离散化，开 $N$ 棵 $multiset$。那么，在删除 $dp(k, n-L-1)$ 时，只要将 $A_{n-L-1}$ 对应的 $multiset$ 中最大权值更新到字典树中即可。

程序实现

  • 时间复杂度：$O(M\cdot N\cdot \log L)$
  • 空间复杂度：$O(N)$
1004.cpp  | 124 lines.
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
119
120
121
122
123
124
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;


static const int MAXN = 10000 + 10;


struct node {
  node* ch[2];
  int val;
  void Maintain() {
    val = 0;
    if (ch[0]) val = ch[0]->val;
    if (ch[1]) val = std::max(val, ch[1]->val);
  }
};


node nodepool[MAXN << 5];
node* nodetop;
node* root;


inline node* newnode() {
  nodetop->ch[0] = nodetop->ch[1] = NULL;
  nodetop->val = 0;
  return nodetop++;
}


void Update(node*& o, int x, int v, int d = 30) {
  if (o == NULL) o = newnode();
  if (d == -1)
    o->val = v;
  else {
    int c = (x >> d) & 1;
    Update(o->ch[c], x, v, d - 1);
    o->Maintain();
  }
}


int Query(node*& o, int x, int ans = 0, int d = 30) {
  if (o == NULL) return 0;
  if (d == -1) return min(o->val, ans);
  int c = (x >> d) & 1;
  if (o->ch[c ^ 1]) {
    if (o->ch[c ^ 1]->val < (ans ^ (1 << d)))
      return max(o->ch[c ^ 1]->val, Query(o->ch[c], x, ans, d - 1));
    return Query(o->ch[c ^ 1], x, ans ^ (1 << d), d - 1);
  }
  return Query(o->ch[c], x, ans, d - 1);
}


inline int read() {
  int s = 0;
  char c = getchar();
  bool positive = true;
  for (; !isdigit(c); c = getchar())
    if (c == '-') positive = false;
  for (; isdigit(c); c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}


multiset<int> ms[MAXN];
int A[MAXN];
int B[MAXN], bsiz;
int dp[2][MAXN];


inline void add(int x, int v) {
  int id = lower_bound(B, B + bsiz, x) - B;
  if (ms[id].upper_bound(v) == ms[id].end()) Update(root, B[id], v);
  ms[id].insert(v);
}


inline void sub(int x, int v) {
  int id = lower_bound(B, B + bsiz, x) - B;
  multiset<int>::iterator it;
  it = ms[id].find(v);
  ms[id].erase(it);
  int vv = 0;
  if (!ms[id].empty()) {
    it = ms[id].end();
    vv = *(--it);
  }
  if (vv < v) Update(root, B[id], vv);
}


void work() {
  int N = read();
  int K = read();
  int L = read();
  for (int i = 1; i <= N; ++i) A[i] = A[i - 1] ^ read();


  memcpy(B, A + 1, sizeof(int) * N);
  sort(B, B + N);
  bsiz = std::unique(B, B + N) - B;


  memset(dp[0], 0, sizeof dp[0]);
  for (int i = 1; i <= L; ++i) dp[0][i] = A[i];


  int now = 0, last = 1;
  for (int k = 2; k <= K; ++k) {
    nodetop = nodepool;
    root = newnode();
    for (int i = 0; i < bsiz; ++i) ms[i].clear();


    swap(now, last);
    for (int n = 1; n <= N; ++n) {
      if (n > L + 1) sub(A[n - L - 1], dp[last][n - L - 1]);
      dp[now][n] = Query(root, A[n]);
      add(A[n], dp[last][n]);
    }
  }
  printf("%d\n", dp[now][N]);
}


int main() {
  int T_T = read();
  for (int kase = 1; kase <= T_T; ++kase) {
    printf("Case #%d:\n", kase);
    work();
  }
  return 0;
}
HINT

在离散化过程中使用排序，查询使用 $lower_bound$，复杂度退化为 $O(M\cdot N\cdot(\log L+\log N))$. 不过，仍然只跑了 $202MS$。

算法二

重新定义 $dp(k, n)$。给定一个下界 $val$，定义 $dp(k, n)$ 为能否将前 $n$ 个数分成 $k$ 份，使得合法方案的分组异或和最小值的最大值大于等于 $val$. 那么，我们仅需将 $1\leqslant i\leqslant L$ 中满足 $dp(k, n-i)=true$ 的 $A_{n-i}$ 丢进字典树中，则仅需判断字典树中的数与 $A_n$ 最大异或值是否大于等于 $val$ 即可。然后，仅需二分 $val$ 即可。

程序实现

  • 时间复杂度：$O(M\cdot N\cdot \log N)$
  • 空间复杂度：$O(N)$
1004_2.cpp  | 108 lines.
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
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;


const int MAXN = 10000;


struct node {
  node* ch[2];
  int val;
  node(int val = 0) : val(val) {
    ch[0] = ch[1] = NULL;
  }
};


node* root;
node* nodetop;
node nodepool[MAXN << 5];
bool dp[12][MAXN];
int A[MAXN];
int N, K, L;


inline node* newnode() {
  nodetop->ch[0] = nodetop->ch[1] = NULL;
  nodetop->val = 0;
  return nodetop++;
}


inline void Insert(int x, int d) {
  node* u = root;
  for (int i = 30; i >= 0; --i) {
    int c = (x >> i) & 1;
    if (!u->ch[c]) u->ch[c] = newnode();
    u = u->ch[c];
    u->val += d;
  }
}


inline int Search(int x) {
  node* u = root;
  int ans = 0;
  for (int i = 30; i >= 0; --i) {
    int c = (x >> i) & 1;
    if (u->ch[c ^ 1] && u->ch[c ^ 1]->val > 0) {
      ans ^= 1 << i;
      u = u->ch[c ^ 1];
    } else if (u->ch[c])
      u = u->ch[c];
  }
  return ans;
}


inline int read() {
  int s = 0;
  char c = getchar();
  bool positive = true;
  for (; !isdigit(c); c = getchar())
    if (c == '-') positive = false;
  for (; isdigit(c); c = getchar()) s = s * 10 + c - '0';
  return positive ? s : -s;
}


bool check(int val) {
  memset(dp[1], 0, sizeof dp[1]);
  for (int n = 1; n <= L; ++n) dp[1][n] = A[n] >= val ? true : false;


  for (int k = 2; k <= K; ++k) {
    nodetop = nodepool;
    root = newnode();
    for (int n = 1; n <= N; ++n) {
      if (n > L + 1 && dp[k - 1][n - L - 1]) Insert(A[n - L - 1], -1);


      dp[k][n] = Search(A[n]) >= val ? true : false;


      if (dp[k - 1][n]) Insert(A[n], 1);
    }
  }
  return dp[K][N];
}


void work() {
  N = read();
  K = read();
  L = read();
  for (int i = 1; i <= N; ++i) A[i] = A[i - 1] ^ read();


  int lft = 0, rht = (1 << 30) | 1;
  while (lft < rht) {
    int mid = (lft + rht) >> 1;
    if (check(mid))
      lft = mid + 1;
    else
      rht = mid;
  }


  printf("%d\n", lft - 1);
}


int main() {
  int T_T = read();
  for (int kase = 1; kase <= T_T; ++kase) {
    printf("Case #%d:\n", kase);
    work();
  }
  return 0;
}
HINT

算法二思路简单，实现难度小，效率还不错，跑了 $1092MS$。

© 2017-2025 光和尘有花满渚、有酒盈瓯

Comments