HNOI2012解题报告

发表于 | 分类于

HNOI2012解题报告

Author: Pengyihao

Day1 T1 双十字

思路

因为矩阵总的大小不超过 \(1000000\)，所以我们可以预处理往左最多能延续多少，往右、往上、往下……

然后我们考虑枚举双十字中间线所在的列。

枚举下面这根横线所在的行。

然后对于这根横线形成的双十字的数量有影响的行，一定在其之上并且长度短于它。

于是对于每段连续的 \(1\)，我们维护一个 \(splay\)。

\(splay\) 的关键字键值为左右延伸的长度，然后记录每个点往上扩展的长度以及自身的长度能够给予的贡献。

这个贡献可以求一下子树的和。

那么每次计算下面这根横线的贡献的时候，直接找到它在 \(splay\) 中的位置，把它左边、右边的区间提取出来，计算贡献即可。

注意必须在第 \(i\) 行的时候插入第 \(i-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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (LL i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (LL i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
using std::vector;
const LL MAXN = 10010, MOD = 1000000009;
vector<LL>line[MAXN];
vector<LL>lr[MAXN], tp[MAXN], co[MAXN];
LL r, c, n;
struct Node {
    Node *ch[2], *fa;
    LL data1, data2, sum1, sum2, sum3, sz;
    void clear();
    void update();
    void rotate();
    void insert(LL, LL);
    LL get_rnk(LL);
    void splay(Node*);
    Node *find_key(LL);
} *treap;
void Node::rotate()
{
    Node *pa = fa;
    fa = pa -> fa; pa -> fa = this;
    if (fa != NULL) {
        bool t = (fa -> ch[0] == pa ? 0 : 1);
        fa -> ch[t] = this;
    }
    bool t = (pa -> ch[0] == this ? 0 : 1);
    Node *chd = ch[t ^ 1];
    ch[t ^ 1] = pa; pa -> ch[t] = chd;
    if (chd != NULL) chd -> fa = pa;
    pa -> update(); update();
}
void Node::splay(Node *top)
{
    while (fa != top) {
        if (fa -> fa != top) {
            bool t = (fa -> fa -> ch[0] == fa ? 0 : 1);
            if (fa -> ch[t] == this) fa -> rotate(), rotate();
            else rotate(), rotate();
        }
        else rotate();
    }
    if (top == NULL) treap = this;
}
LL Node::get_rnk(LL now)
{
    Node *x = this;
    LL ret = 0;
    
    while (true) {
        if (x -> data1 == now) {
            return (x -> ch[0] == NULL ? 1 : x -> ch[0] -> sz + 1) + ret;
        }
        if (x -> data1 > now) {
            if (x -> ch[0] == NULL) return ret;
            x = x -> ch[0];
        }
        else {
            if (x -> ch[1] == NULL) return x -> sz + ret;
            ret += (x -> ch[0] == NULL ? 1 : x -> ch[0] -> sz + 1);
            x = x -> ch[1];
        }
    }
}
Node* Node::find_key(LL rnk)
{
    Node *x = this;
    while (true) {
        if ((x -> ch[0] == NULL ? 1 : x -> ch[0] -> sz + 1) == rnk) return x;
        else if ((x -> ch[0] == NULL ? 1 : x -> ch[0] -> sz + 1) < rnk) {
            rnk -= (x -> ch[0] == NULL ? 1 : x -> ch[0] -> sz + 1);
            x = x -> ch[1];
        }
        else x = x -> ch[0];
    }
}
void Node::insert(LL now, LL now2)
{
    if (treap == NULL) {
        Node *hr = new Node;
        hr -> ch[0] = hr -> ch[1] = hr -> fa = NULL;
        hr -> data1 = now; hr -> data2 = now2; treap = hr; treap -> update();
        return;
    }
    LL rnk = treap -> get_rnk(now);
    if (rnk == 0) {
        Node *hr = new Node;
        hr -> ch[0] = hr -> fa = NULL;
        hr -> ch[1] = treap; hr -> data1 = now; hr -> data2 = now2;
        treap -> fa = hr; hr -> update();
        treap = hr;
    }
    else if (rnk == treap -> sz) {
        Node *hr = new Node;
        hr -> ch[1] = hr -> fa = NULL;
        hr -> ch[0] = treap; hr -> data1 = now; hr -> data2 = now2;
        treap -> fa = hr; hr -> update();
        treap = hr; 
    }
    else {
        Node *hr = new Node;
        treap -> find_key(rnk) -> splay(NULL);
        treap -> find_key(rnk + 1) -> splay(treap);
        hr -> data1 = now;
        hr -> data2 = now2;
        hr -> ch[0] = NULL;
        hr -> ch[1] = treap -> ch[1];
        hr -> fa = treap; treap -> ch[1] = hr;
        hr -> ch[1] -> fa = hr; hr -> update(); treap -> update();
    }
}
void Node::clear()
{
    if (ch[0] != NULL) ch[0] -> clear();
    if (ch[1] != NULL) ch[1] -> clear();
    delete this;
}
void Node::update()
{
    sz = 1;
    sum1 = data1 * data2 % MOD;
    sum2 = (data1 * (data1 + 1) / 2) * data2 % MOD;
    sum3 = data2;
    if (ch[0] != NULL) {
        sz += ch[0] -> sz;
        sum1 = (sum1 + ch[0] -> sum1) % MOD;
        sum2 = (sum2 + ch[0] -> sum2) % MOD;
        sum3 = (sum3 + ch[0] -> sum3) % MOD;
    }
    if (ch[1] != NULL) {
        sz += ch[1] -> sz;
        sum1 = (sum1 + ch[1] -> sum1) % MOD;
        sum2 = (sum2 + ch[1] -> sum2) % MOD;
        sum3 = (sum3 + ch[1] -> sum3) % MOD;
    }
}
int main()
{
    freopen("cross.in", "r", stdin);
    freopen("cross.out", "w", stdout);
    
    in(r); in(c); in(n);
    FOR(i, 0, r + 1) {
        lr[i].resize(c + 2);
        tp[i].resize(c + 2);
        co[i].resize(c + 2);
        line[i].resize(c + 2);
    }
    FOR(i, 1, r) FOR(j, 1, c) line[i][j] = 1;
    
    FOR(i, 1, n) {
        LL x, y;
        in(x); in(y);
        line[x][y] = 0;
    }
    FOR(i, 1, r) {
        FOR(j, 1, c) {
            if (line[i][j] == 0) continue;
            if (j == 1 || line[i][j - 1] == 0) lr[i][j] = 0;
            else lr[i][j] = lr[i][j - 1] + 1;
        }
        DNF(j, c, 1) {
            if (line[i][j] == 0) continue;
            if (j == c || line[i][j + 1] == 0) lr[i][j] = 0;
            else chkmin(lr[i][j], lr[i][j + 1] + 1);
        }
        FOR(j, 1, c) if (line[i][j]) {
            if (i == 1 || !line[i - 1][j]) tp[i][j] = 0;
            else tp[i][j] = tp[i - 1][j] + 1;
        }
    }
    DNF(i, r, 1) {
        FOR(j, 1, c) if (line[i][j]) {
            if (i == r || !line[i + 1][j]) co[i][j] = 0;
            else co[i][j] = co[i + 1][j] + 1;
        }
    }
    treap = NULL;
    bool is_cleared = true;
    LL ans = 0;
    
    FOR(j, 1, c) {
        if (!is_cleared) {
            treap -> clear();
            treap = NULL;
            is_cleared = true;
        }
        FOR(i, 1, r) {
            if (i > 2) {
                if (lr[i - 2][j] != 0 && line[i - 1][j]) {
                    treap -> insert(lr[i - 2][j], tp[i - 2][j]);
                    is_cleared = false;
                }
            }
            
            if (!line[i][j]) {
                if (!is_cleared) {
                    treap -> clear();
                    treap = NULL;
                    is_cleared = true;
                }
                continue;
            }
            LL now = lr[i][j];
            
            if (now && treap != NULL) {
                LL rnk = treap -> get_rnk(now);
                if (rnk != 0) {
                    Node *hr;
                    if (rnk != treap -> sz) {
                        treap -> find_key(rnk + 1) -> splay(NULL);
                        treap -> find_key(rnk) -> splay(treap);
                        hr = treap -> ch[0];
                    }
                    else {
                        treap -> find_key(rnk) -> splay(NULL);
                        hr = treap;
                    }
                    LL fst = hr -> sum1 * now % MOD * co[i][j] % MOD;
                    LL sec = hr -> sum2 * co[i][j] % MOD;
                    ans = (ans + fst - sec) % MOD;
                }
                if (rnk != treap -> sz) {
                    Node *hr;
                    if (rnk != 0) {
                        treap -> find_key(rnk) -> splay(NULL);
                        treap -> find_key(rnk + 1) -> splay(treap);
                        hr = treap -> ch[1];
                    }
                    else {
                        treap -> find_key(rnk + 1) -> splay(NULL);
                        hr = treap;
                    }
                    LL valu =
                        (now * now - now * (now + 1) / 2) * co[i][j] % MOD;
                    ans = (ans + hr -> sum3 * valu % MOD) % MOD;
                }
            }
        }
    }
    printf("%lld\n", ans);
        
    return 0;
}

Day1 T2 与非

思路

首先可以发现一个性质——NAND操作可以构成所有的位运算，这个手玩一下就出来了。

然后对于二进制的某两位，我们发现如果对于每一个操作数，他们的这两位都相同，那么不论怎么运算最后肯定还是相同的。

除了这种限制之外，就没有其它限制了。

意思是说，如果在必定相同的两位之间连一条边，那么会形成一个个联通块。联通块与联通块之间两两对于答案的贡献是独立的。

联通块可以用并查集维护。

于是就可以答案进行数位DP辣！！

对于答案的第 \(i\) 位，它的取值会影响一个联通块的取值。

我们从高到低地做，如果边界的该位上为 \(1\)，那么我们取 \(0\) 的话答案就要加上 \(2^p\)，其中 \(p\) 是尚未确定的联通块个数。

其余的类似。

代码

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
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(), f = 1; x = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
const LL MAXN = 1010;
LL n, k, l, r, tot, A[MAXN], fa[MAXN];
LL find(LL x)
{
    LL tmp = x, pre;
    while (tmp != fa[tmp]) tmp = fa[tmp];
    while (x != tmp) pre = fa[x], fa[x] = tmp, x = pre;
    return tmp;
}
void merge(LL x, LL y)
{
    LL fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}
LL query(LL x)
{
    if (x < 0) return 0;
    LL ret = 0, tmp = tot;
    static bool chose[100];
    static bool how_chose[100];
    memset(chose, false, sizeof chose);
    if (x > (1ll << (k)) - 1) return (1ll << tmp);
    
    DNF(i, k, 1) {
        if (!(x & (1ll << (i - 1)))) {
            LL fx = find(i);
            if (chose[fx]) {
                if (how_chose[fx] == 1) return ret;
            }
            else {
                chose[fx] = true;
                how_chose[fx] = 0;
                tmp--;
                continue;
            }
        }
        else {
            LL fx = find(i);
            if (chose[fx]) {
                if (how_chose[fx] == 1) continue;
                else {
                    ret += (1ll << tmp);
                    return ret;
                }
            }
            else {
                chose[fx] = true;
                how_chose[fx] = 1;
                tmp--;
                ret += (1ll << tmp);
                continue;
            }
        }
    }
    return ret + 1;
}
int main()
{
    freopen("nand.in", "r", stdin);
    freopen("nand.out", "w", stdout);
    
    in(n); in(k); in(l); in(r);
    FOR(i, 1, n) in(A[i]);
    FOR(i, 1, k) fa[i] = i;
    
    FOR(i, 1, k) {
        LL tmp = (1ll << (k)) - 1;
        FOR(j, 1, n) {
            if (A[j] & (1ll << (i - 1))) {
                tmp &= A[j];
            }
            else tmp &= (A[j] ^ ((1ll << k) - 1));
        }
        if (!(tmp & (1ll << (i - 1)))) {
            puts("WA");
        }
        FOR(j, 1, k) if (j != i) {
            if (bool(tmp & (1ll << (j - 1))) == bool(tmp & (1ll << (i - 1))))
                merge(i, j);
        }
    }
    FOR(i, 1, k) if (fa[i] == i) tot++;
    printf("%lld\n", query(r) - query(l - 1));
    return 0;
}

Day1 T3 排队

思路

首先放男同学，有 \(n!\)。

然后放老师，可以放到一起或分开放，方案分别为 \(n!\times P_{n+1}^2\times P_{n+3}^m\)，和 \(n!\times2(n+1)\)。

最后放女同学。如果老师放在一起了，那么就要放一个女同学在老师中间；否则把老师看作男同学。

总方案为

\[n!\times(P_{n+1}^n\times P_{n+3}^m + 2(n+1)\times P_{n+2}^{m-1}\times m)\]

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define Max(x,y) ((x)>(y)?(x):(y))
#define LL long long
#define MOD 100000000
using namespace std;
struct bign{
    int len;
    LL s[10000];
    bign(){
        len=1;
        memset(s,0,sizeof s); 
        s[1]=1;
    }
    
    bign operator = (const LL &num){
        len=1;
        s[1]=num;
        return *this;
    }
    bign operator + (const bign&num){
        bign c;c.s[1]=0;c.len=Max(num.len,len);
        for(int i=1;i<=c.len;i++){
            c.s[i+1]=(c.s[i]+s[i]+num.s[i])/MOD;
            c.s[i]=(c.s[i]+s[i]+num.s[i])%MOD;
        }
        if(c.s[c.len+1])c.len++;
        return c;
    }
    
    bign operator - (const bign&num){
        bign c;c.s[1]=0;c.len=len;
        int x=0;
        for(int i=1;i<=c.len;i++){
            c.s[i]=s[i]-num.s[i]+x;
            x=0;
            if(c.s[i]<0){
                c.s[i]+=MOD;
                x=-1;
            }
        }
        while(!c.s[c.len]&&c.len>1)c.len--;
        return c;
    }
    
    bign operator * (const LL&num){
        bign c;c.s[1]=0;c.len=len;
        for(int i=1;i<=c.len;i++){
            c.s[i+1]=(c.s[i]+s[i]*num)/MOD;
            c.s[i]=(c.s[i]+s[i]*num)%MOD;
        }
        if(c.s[c.len+1])c.len++;
        return c; 
    }
    
    bign operator * (const bign&num){
        bign c;c.s[1]=0;c.len=len+num.len+1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=num.len;j++){
                c.s[i+j]+=(c.s[i+j-1]+s[i]*num.s[j])/MOD;
                c.s[i+j-1]=(c.s[i+j-1]+s[i]*num.s[j])%MOD;
            }
        while(!c.s[c.len]&&c.len>1)c.len--;
        return c;
    }
    
    void out(){
        for(int i=len;i>=1;i--){
            if(i==len)printf("%lld",s[i]);
            else printf("%08lld",s[i]);
        }
    }
};
LL n,m,tmp,tmp2;
bign ans1,ans2;
int main(){
    freopen("queue.in", "r", stdin);
    freopen("queue.out", "w", stdout);
    
    scanf("%lld%lld",&n,&m);tmp=n+4;tmp2=n+3;
    for(LL i=1;i<=n;i++){
        ans1=ans1*i;
        ans2=ans2*i;
    }
    ans1=ans1*(n+1)*n;
    for(LL i=1;i<=m&&tmp>=0;i++){
        tmp--;
        ans1=ans1*tmp;
    }
    for(LL i=1;i<=m-1&&tmp2>=0;i++){
        tmp2--;
        ans2=ans2*tmp2; 
    }
    ans2=ans2*2*m*(n+1);
    (ans1+ans2).out(); 
    
    return 0;
}

Day1 T4 矿场搭建

思路

首先双联通缩点，然后对于每个联通块，只需要每个叶子节点放一个出口就行了（不能放割点）。

方案个数的话乘法原理就好了。

注意只有一个双联通分量的情况要特判！！

代码

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
#include <bits/stdc++.h>
 
const int MAXN = 1010, MAXM = 510;
 
bool is[MAXN];
int belong[MAXN];
int dfn[MAXN], low[MAXN], INDEX, dot[MAXN], all, sz[MAXN];
int n, cnt, head[MAXN], nxt[MAXM << 1], data[MAXM << 1], du[MAXN];
 
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch != EOF && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == EOF) exit(0);
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
 
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
 
void add(int x, int y) {
    nxt[cnt] = head[x]; data[cnt] = y; head[x] = cnt++;
    nxt[cnt] = head[y]; data[cnt] = x; head[y] = cnt++;
}
 
void dfs(int now, int rot, int fa) {
    int size = 0; bool flag = false;
    dfn[now] = low[now] = ++INDEX;
    for (int i = head[now]; i != -1; i = nxt[i]) 
        if (!dfn[data[i]]) {
            size++;
            dfs(data[i], rot, now);
            low[now] = Min(low[now], low[data[i]]);
            if (low[data[i]] >= dfn[now]) flag = true;
        }
        else if (data[i] != fa) {
            low[now] = Min(low[now], dfn[data[i]]);
        }
    if (flag && (now != rot || size >= 2)) {
        dot[++dot[0]] = now;
        is[now] = true;
    }
}
 
void dfs2(int now) {
    dfn[now] = 1;
    for (int i = head[now]; i != -1; i = nxt[i])
        if (!is[data[i]] && !dfn[data[i]]) {
            dfs2(data[i]);
            sz[all]++;
            belong[data[i]] = all;
        }
}
 
int TTT;
 
int main() {
    freopen("mining.in", "r", stdin);
    freopen("mining.out", "w", stdout);
    
    while (true) {
        in(n);
        int dian = -1;
        if (!n) return 0;
        cnt = 0; all = 0;
        memset(du, 0, sizeof du);
        memset(is, 0, sizeof is);
        memset(dot, 0, sizeof dot);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(head, -1, sizeof head);
        memset(belong, 0, sizeof belong);
        for (int i = 1; i <= n; i++) {
            int s, t;
            in(s); in(t); add(s, t);
            dian = std::max(dian, std::max(s, t));
        }
        for (int i = 1; i <= dian; i++)
            if (!dfn[i]) dfs(i, i, -1);
        memset(dfn, 0, sizeof dfn);
        for (int i = 1; i <= dian; i++)
            if (!dfn[i] && !is[i]) {
                belong[i] = ++all;
                sz[all] = 1;
                dfs2(i);
            }
        if (all == 1) {
            printf("Case %d: %d %d\n", ++TTT, 2, dian * (dian - 1) / 2);
            continue;
        }
        for (int i = 1; i <= dian; i++)
            if (is[i]) {
                for (int j = head[i]; j != -1; j = nxt[j])
                    dfn[belong[data[j]]] = 0;
                for (int j = head[i]; j != -1; j = nxt[j])
                    if (!dfn[belong[data[j]]]) {
                        dfn[belong[data[j]]] = true;
                        du[belong[data[j]]]++;
                    }
            }
        int tot = 0;
        long long fang = 1;
        for (int i = 1; i <= all; i++) {
            if (du[i] == 1) {
                tot++;
                if (sz[i] > 1)
                    fang = fang * (sz[i]);
            }
        }
        printf("Case %d: %d %lld\n", ++TTT, tot, fang);
    }
    return 0;
}

Day2 T1

这是一道计算几何的题目。

因为我还没有进行这个专题，所以我跳过了这道题目。

Day2 T2

这是一道计算几何的题目。

因为我还没有进行这个专题，所以我跳过了这道题目。

Day2 T3

思路

这个题目是一道 \(splay\) 的启发式合并的模板题。

只需要从小的合并到大的中间就可以了。

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MAXN = 100010;
char command[10];
int n, m, rnk[MAXN], fa[MAXN];
struct Node {
    int data, sz, id;
    Node *ch[2], *fa;
    void update();
    void splay(Node*);
    void rotate();
    Node *find_key(int);
    void insert(Node*);
} *to[MAXN];
void Node::rotate()
{
    Node *pa = fa;
    fa = pa -> fa;
    if (fa != NULL) {
        bool t = fa -> ch[0] == pa ? 0 : 1;
        fa -> ch[t] = this;
    }
    pa -> fa = this;
    bool t = pa -> ch[0] == this ? 0 : 1;
    Node *chd = ch[t ^ 1];
    pa -> ch[t] = chd;
    if (chd != NULL) chd -> fa = pa;
    ch[t ^ 1] = pa;
    pa -> update(); update();
}
void Node::splay(Node *top)
{
    while (fa != top) {
        if (fa -> fa != top) {
            bool t = (fa -> ch[0] == this ? 0 : 1);
            if (fa -> fa -> ch[t] == fa) {
                fa -> rotate(); rotate();
            }
            else rotate(), rotate();
        }
        else rotate();
    }
}
Node* Node::find_key(int rnk)
{
    Node *hr = this;
    while (true) {
        int nowrnk;
        nowrnk = (hr -> ch[0] == NULL ? 1 : hr -> ch[0] -> sz + 1);
        if (nowrnk == rnk) return hr;
        if (nowrnk <  rnk) {
            rnk -= nowrnk;
            hr = hr -> ch[1];
        }
        else hr = hr -> ch[0];
    }
}
void Node::update()
{
    sz = 1;
    if (ch[0] != NULL) sz += ch[0] -> sz;
    if (ch[1] != NULL) sz += ch[1] -> sz;
}
void Node::insert(Node *x)
{
    bool t;
    Node *pos = this, *pa = NULL;
    while (pos != NULL) {
        pa = pos;
        if (x -> data > pos -> data) pos = pos -> ch[1], t = 1;
        else pos = pos -> ch[0], t = 0;
    }
    x -> fa = pa;
    if (pa != NULL) pa -> ch[t] = x;
    x -> ch[0] = x -> ch[1] = NULL;
    while (x != NULL) {
        x -> update();
        x = x -> fa;
    }
}
void Ins(Node* now, Node* to)
{
    if (now == NULL) return;
    Ins(now -> ch[0], to); Ins(now -> ch[1], to);
    to -> splay(NULL); to -> insert(now); now -> splay(NULL);
}
int find(int x)
{
    int tmp = x, pre;
    while (tmp != fa[tmp]) tmp = fa[tmp];
    while (x != tmp) pre = fa[x], fa[x] = tmp, x = pre;
    return tmp;
}
bool merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    return fx == fy ? false : fa[fx] = fy, true;
}
int main()
{
    freopen("neverland.in", "r", stdin);
    freopen("neverland.out", "w", stdout);
    
    in(n); in(m);
    FOR(i, 1, n) fa[i] = i;
    FOR(i, 1, n) in(rnk[i]);
    FOR(i, 1, n) {
        to[i] = new Node;
        to[i] -> data = rnk[i];
        to[i] -> sz = 1; to[i] -> id = i;
        to[i] -> fa = to[i] -> ch[0] = to[i] -> ch[1] = NULL;
    }
    FOR(i, 1, m) {
        int x, y; in(x); in(y);
        if (merge(x, y)) {
            if (to[x] == NULL) printf("%d\n", x);
            to[x] -> splay(NULL);
            to[y] -> splay(NULL);
            if (to[x] -> sz < to[y] -> sz) {
                Ins(to[x], to[y]);
            }
            else Ins(to[y], to[x]);
        }
    }
    int q; in(q);
    while (q--) {
        scanf("%s", command);
        if (command[0] == 'Q') {
            int x, k;
            in(x); in(k);
            to[x] -> splay(NULL);
            if (to[x] -> sz < k) printf("-1\n");
            else {
                printf("%d\n", to[x] -> find_key(k) -> id);
            }
        }
        else {
            int x, y;
            in(x); in(y);
            if (merge(x, y)) {
                to[x] -> splay(NULL);
                to[y] -> splay(NULL);
                if (to[x] -> sz < to[y] -> sz) {
                    Ins(to[x], to[y]);
                }
                else Ins(to[y], to[x]);
            }
        }
    }
    
    return 0;
}

Day2 T4 集合选数

思路

考虑一张表，将 \(1\) 在左下角。

满足一个性质：对于一个格子，它的右边的格子里的数字是它的 \(3\) 倍，上面的格子里的数字是它的 \(2\) 倍。

于是问题转化为在格子中选不相邻的数的方案数。

表的长宽不会很大，是 \(log\) 级别的。

可能有很多张不相交的表。

状压dp就好了。

代码

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
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i, a, b) for (register int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (register int i = (a), i##_END_ = (b); i >= i##_END_; i--)
template <typename Tp> void in(Tp &x) {
    char ch = getchar(); x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <typename Tp> Tp Min(Tp x, Tp y) {return x < y ? x : y;}
template <typename Tp> Tp Max(Tp x, Tp y) {return x > y ? x : y;}
template <typename Tp> Tp chkmax(Tp &x, Tp y) {return x > y ? x : x=y;}
template <typename Tp> Tp chkmin(Tp &x, Tp y) {return x < y ? x : x=y;}
const int MOD = 1000000001;
const int MAXN = 100010;
bool vis[MAXN];
int n, ans = 1;
int map[18][18], end[18], f[2][MAXN << 1];
void solve(int now)
{
    int ret = 0;
    FOR(i, 1, 100000) {
        if (i == 1) map[1][i] = now;
        else map[1][i] = map[1][i - 1] * 2;
        if (map[1][i] > n) {
            //map[1][i] = -1;
            break;
        }
        vis[map[1][i]] = true;
        FOR(j, 2, 100000) {
            map[j][i] = map[j - 1][i] * 3;
            if (map[j][i] > n) {
                //map[j][i] = -1;
                break;
            }
            vis[map[j][i]] = true;
        }
    }
    end[0] = 0;
    bool t = 0;
    int all = 1;
    f[t ^ 1][0] = 1;
    bool first = true;
    
    FOR(i, 1, 100000) {
        if (map[i][1] <= n) {
            FOR(j, 1, 100000) if (map[i][j] > n) {end[i] = j - 1; break;}
            int limits1 = (1 << end[i]) - 1, limits2 = (1 << end[i - 1]) - 1;
            FOR(j, 0, limits1) {
                f[t][j] = 0;
                bool flag = true;
                if (!first && !f[t ^ 1][j]) continue;
                FOR(l, 2, end[i]) if ((j & (1 << (l - 1))) && (((j) & (1 << (l - 2))))) {
                    flag = false;
                    break;
                }
                if (!flag) continue;
                FOR(k, 0, limits2) {
                    bool flag = true;
                    if (!f[t ^ 1][k]) continue;
                    FOR(l, 1, end[i]) {
                        if ((j & (1 << (l - 1))) && (k & (1 << (l - 1)))) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) f[t][j] = (f[t][j] + f[t ^ 1][k]) % MOD;
                }
            }
        }
        else {
            all = i - 1;
            break;
        }
        first = false;
        t ^= 1;
    }
    FOR(i, 0, (1 << (end[all] - 1))) ret = (ret + f[t ^ 1][i]) % MOD;
    
    ans = 1ll * ans * ret % MOD;
}
int main()
{
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    
    in(n);
    FOR(i, 1, n) {
        if (!vis[i]) solve(i);
    }
    printf("%d\n", ans);
    return 0;
}