百度之星 2016 解题报告

1002 K 个连通块
¶

题目简析
¶

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

如何求 $d p (1, s)$
¶

为方便叙述，记 $f (s) = d p (1, s)$ ， $s = 2^{j_{1}} + 2^{j_{2}} + \dots + 2^{j_{t}}$ ，故其所代表点集为 $V_{s} = {A_{j_{1}}, A_{j_{2}}, \dots, A_{j_{t}}}$ , $(0 ⩽ j_{1} < j_{2} < \dots < j_{t} ⩽ N - 1)$ . 令 $E (s)$ 表示 $V_{s}$ 中的互不相同的两点之间的边的总数；则

f (s) = 2^{E (s)} - \sum_{A_{j_{1}} \in V_{s^{'}}, V_{s^{'}} \in {V_{s}}} f (s^{'}) \times 2^{E (s - s^{'})}

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

$V_{s}$ 中的点与不在 $V_{s}$ 中的点之间不连通；因此，我们仅需考虑 $V_{s}$ 中两两之间的边，去边的总方案为 $2^{E (s)}$ .
$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^{″}}$ 中的边可以自由选择了。

如何递推
¶

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

考虑 $k = 3$ 的情况，如果 $V_{s} = {A_{1}, A_{2}, A_{3}}$ ，则 $V_{s^{'}} = {A_{1}, A_{2}}$ 与 $V_{s^{'}} = {A_{1}, A_{3}}$ 所做的贡献是完全重复的。

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

d p (k + 1, s) = \sum_{A_{j_{1}} \notin V_{s^{'}}, V_{s^{'}} \in V_{s}} d p (k, s^{'}) \times d p (1, s - s^{'})

进一步分析
¶

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

\begin{aligned} (1) & V_{s}^{'} & = V - V_{s^{'}} = {A_{p_{1}}, A_{p_{2}}, \dots, A_{p_{q}}} \\ (2) \\ (3) & d p (k + 1, s) & = \sum_{A_{j_{1}} \in V_{s^{'}}, V_{s^{'}} \in V_{s}, A_{p_{1}} \in V_{s - s^{'}}} d p (k, s^{'}) \times d p (1, s - s^{'}) \end{aligned}

上述递推式用刷表法实现即可避免 $A_{p_{1}} \in V_{s - s^{'}}$ 的判断。注意到我们要的终态是 $d p (K, 2^{N} - 1)$ ，所以，我们可以只计算满足 $A_{1} \in V_{s}$ 的状态 $d p (K, s)$ ，理由是 $A_{1} \in V_{s^{'}}$ ，即这条递推到 $d p (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 游戏
¶

题目链接

题目简析
¶

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

d p (k + 1, n) = max {min {d p (k, n - i), A_{n} \oplus A_{n - i}}}, 1 ⩽ i ⩽ L

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

算法一
¶

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

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

\begin{aligned} (4) & x & = A_{n} = b_{30} \cdot 2^{30} + b_{29} \cdot 2^{29} + \dots + b_{0} 2^{0} \\ (5) & y & = (a_{30} \oplus b_{30}) \cdot 2^{30} + (a_{29} \oplus b_{29}) \cdot 2^{29} + \dots + (a_{h} \oplus b_{h}) \cdot 2^{h} \end{aligned}

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

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

$⌊ \frac{x}{2^{h}} ⌋ \equiv 1 \mod 2$ . 也就是 $b_{h} = 1$ .
- 如果 $v a l (o_{1}) < y + 2^{h - 1}$ ，说明如果下一步选择 $o_{1}$ ，则
  $max {min {d p [k] [n - i], A [n] \oplus A [n - i]}} = v a l (o_{1})$
  所以我们 仅需选择 $o_{2}$ 求出一个最优值 $a n s_{2}$ ，最后的答案就是 $max {v a l (o_{1}), a n s_{2}}$ .
- 如果 $v a l (o_{1}) ⩾ y + 2^{h - 1}$ ，即选择 $o_{1}$ ，则最坏情况答案不小于 $y + 2^{h - 1}$ . 同时，选择 $o_{2}$ ，最好的情况不会大于 $y + 2^{h - 1}$ .
  所以我们 仅需选择 $o_{1}$ 求出一个最优值 $a n s_{1}$ ，即是最后的答案。
$⌊ \frac{x}{2^{h}} ⌋ \equiv 0 \mod 2$ . 也就是 $b_{h} = 0$ .
只有走到 $o_{2}$ 这一个选择。

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

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

程序实现
¶

时间复杂度： $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

在离散化过程中使用排序，查询使用 $l o w e r_{b} o u n d$ ，复杂度退化为 $O (M \cdot N \cdot (\log L + \log N))$ . 不过，仍然只跑了 $202 M S$ 。

算法二
¶

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

程序实现
¶

时间复杂度： $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

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

1002 K 个连通块¶

题目简析¶

如何求 dp(1,s)¶

如何递推¶

进一步分析¶

程序实现¶

1004 XOR 游戏¶

题目简析¶

算法一¶

程序实现¶

算法二¶

程序实现¶

1002 K 个连通块
¶

题目简析
¶

如何求 $d p (1, s)$
¶

如何递推
¶

进一步分析
¶

程序实现
¶

1004 XOR 游戏
¶

题目简析
¶

算法一
¶

程序实现
¶

算法二
¶

程序实现
¶