百度之星 2016 解题报告

目录
  1. 1. 1002 K 个连通块
    1. 1.1. 题目简析
    2. 1.2. 进一步分析
    3. 1.3. 复杂度分析
    4. 1.4. 程序实现
  2. 2. 1004 XOR 游戏
    1. 2.1. 题目简析
    2. 2.2. 算法一
      1. 2.2.1. 复杂度分析
      2. 2.2.2. 程序实现
      3. 2.2.3. Hint
    3. 2.3. 算法二
      1. 2.3.1. 复杂度分析
      2. 2.3.2. 程序实现
      3. 2.3.3. Hint

1002 K 个连通块

题目链接

题目简析

假入 $N$ 个点依次为：$\displaystyle V=\left\lbrace A_0,A_1,\cdots,A_{N-1} \right\rbrace$。
不难想到状态压缩。
令 $dp[k][s]$ 表示点集 $\displaystyle V_s=\big\lbrace A_i ~~ \big| ~~\left\lfloor \frac{s}{2^i} \right\rfloor \equiv 1\hskip -1em\mod 2 \text{（即 $s&2^i=1$）} \big\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$ 中的互不相同的两点之间的边的总数；则
\begin{align}
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’)}
\end{align}
证明并不难：
为使 $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$ 所做的贡献是完全重复的。为了避免重复，我们得到新的递推式
\begin{align}
dp[k+1][s]=\sum_{A_{j_1} \notin V_{s’},~V_{s’} \in V_s} dp[k][s’] \times dp[1][s-s’]
\end{align}
不难验证其正确性。

进一步分析

上述分析足以通过此题，我跑了 858MS。但还有改进的余地。
先改造一下递推式，记 $V’_s=V-V_{s’}=\big\lbrace A_{p_1},A_{p_2},\cdots,A_{p_q} \big\rbrace$。
\begin{align}
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)$

程序实现

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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] = \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$ 呢？

算法一

先假设 $\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}$。
记 $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$。
接下来考虑下一层往哪走，即 $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$，即是最后的答案。

  1. $\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)$

程序实现

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
125
126
127
128
129
#include <set>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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

在离散化过程中使用排序，查询使用 $lowerbound$，复杂度退化为 $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)$

程序实现

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
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
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$。