SCUACM 2016集训 7.11【7/11】

ACM_集训

集训期间完成6道，补题1道。
比赛链接：http://vjudge.net/contest/121496#overview

A - Lights Against Dudely(状压+暴力)

题意：

给定$n*m$的矩阵，其中$k(0 \le k \le 15)$个地方可以放灯，每个灯只能照到右边和上边的两个方格，有一种特殊的灯，可以旋转。灯只能照到有灯的地方，问最少需要多少盏灯？

分析：

注意审题！最多只有$15$个灯，和一盏特殊的灯，吃果果的状压枚举，然后就没了。
注意$vis$数组初始化用$memset$会T啊，我真是T了几百年，改了就A了，可能也跟我代码写的很挫有关。。
罗大神说可以用一种类似时间戳的方式，这样不必每次都初始化，只要判断并不断更新他的时间戳即可。

代码：

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define sal(n) scanf("%I64d", &(n))
#define sa(n) scanf("%d", &(n))
typedef long long ll;
const double eps = 1e-8;
const int maxn = 200 + 5, maxc = 60 + 5, maxr = 60 + 5, inf = 0x3f3f3f3f;
bool vis[maxn][maxn];
char t[maxn];
int mat[maxn][maxn];
bool tmp[maxn][maxn];
int dx[4][2] = {{-1, 0},{0, 1}, {1, 0}, {0, -1} };
int dy[4][2] = {{0, 1},{1, 0}, {0, -1}, {-1, 0}};
typedef pair<int, int>p;
p v[maxn];
int cnt;
int n, m;
int temp;
int judge(int d, int b, int x, int y)
{
    if(x + dx[d][b]< 0 || x + dx[d][b] >= n || y + dy[d][b] < 0 || y + dy[d][b] >= m) return 0;
    else if(!mat[x + dx[d][b]][y + dy[d][b]]) return -1;
    if(!vis[x + dx[d][b]][y + dy[d][b]]) temp++;
    vis[x + dx[d][b]][y + dy[d][b]] = true;
    return 1;
}
int main (void)
{
    while(~scanf("%d%d", &n, &m) && (n + m)){
        cnt = 0;
        memset(mat, 0, sizeof(mat));
        for(int i = 0; i < n; i++){
            scanf("%s", t);
            for(int j = 0; j < m; j++){
                if(t[j] == '.'){
                    mat[i][j] = 1;
                    v[cnt++] = p(i, j);
                }
            }
        }
        int ans = 0x3f3f3f3f, res = 0;
        bool flag = false;
        bool ok;
        if(cnt == 0){
            puts("0");
            continue;
        }
        for(int i = 0; i < (1 << cnt); i++){//2^15
            for(int k = 0; k < cnt; k++){//special
                if((i >> k & 1) == 0) continue;
                res = 0;
                ok = true;
                temp = 0;
               for(int a = 0; a < cnt; a++){
                    vis[v[a].first][v[a].second] = false;
               }
               for(int j = 0; j < cnt; j++){//deng
                   if(i >> j & 1){
                        if(j == k) continue;
                        res++;
                        int x = v[j].first, y = v[j].second;
                        if(!vis[x][y]) temp++;
                        vis[x][y] = true;
                        int a = judge(0, 0, x, y);
                        if(a == -1){ok = false; break;}
                        a = judge(0, 1, x, y);
                        if(a == -1){ok = false; break;}
                   }
               }
               if(!ok) continue;
               int x = v[k].first, y = v[k].second;
               if(!vis[x][y]) temp++;
               vis[x][y] = true;
                for(int a = -1; a <= 1; a++){
                        for(int b = -1; b <= 1; b++){
                           if(x + a < 0 || x + a >= n || y + b < 0 || y + b >= m) continue;
                            tmp[x + a][y + b] = vis[x + a][y + b];
                    }
                }
               int ttemp = temp;
               bool found = false;
               for(int d = 0; d < 4; d++){
                     for(int a = -1; a <= 1; a++){
                        for(int b = -1; b <= 1; b++){
                           if(x + a < 0 || x + a >= n || y + b < 0 || y + b >= m) continue;
                            vis[x + a][y + b] = tmp[x + a][y + b];
                        }
                    }
                    temp = ttemp;
                    ok = true;
                    int a = judge(d, 0, x, y);
                    if(a == -1) continue;
                    a = judge(d, 1, x, y);
                    if(a == -1) continue;
                    if(ok && temp == cnt) {found = true; break;}
                }
                if(found){
                        ans = min(ans, res + 1);
                }
            }
        }
        if(ans ==  0x3f3f3f3f) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

B - Stealing Harry Potter’s Precious(BFS + DFS)

题意：

给定一个$n*m$的地图，及$k(k \le 4)$个点，问从起点开始全部经过这$k$个点的最小步数。

分析：

与正常$bfs$不同的是这题要求必须走$k$个点，而$k \le 4$，那么我们可以先$bfs$求出任意两点之间的最短距离，再枚举这$4$个点的走的顺序，把距离加起来即可。
最初我的做法是，先$bfs$找到$k$个点与出发点以及$k$个点之间的最短路，然后$dfs$找到最短的一条路，将最短路连接在一起。

代码：

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e2 + 5, oo = 0x3f3f3f3f;
int a[maxn][maxn];
int head[maxn];
bool vis[maxn][maxn];
bool use[maxn];
char t[maxn];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
struct p{int x, y, dist;};
int n, m, k;
int aa[maxn], ab[maxn];
int dist[maxn][maxn];
struct EDGE{int to; int next; int val;};
EDGE edge[maxn];
int bfs(int sx, int sy, int ex, int ey)
{
    queue<p>q;
    q.push((p){sx, sy, 0});
    memset(vis, false, sizeof(vis));
    vis[sx][sy] = true;
    while(!q.empty()){
        p t = q.front();q.pop();
        int x = t.x, y = t.y;
        if(x == ex && y == ey) return t.dist;
        for(int k = 0; k < 4; k++){
            int xx = x + dx[k];
            int yy = y + dy[k];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || vis[xx][yy]) continue;
            if(a[xx][yy]) continue;
            vis[xx][yy] = true;
            q.push((p){xx, yy, t.dist + 1});
        }
    }
    return -1;
}
int tot = 0;
void addedge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].val = dist[u][v];
    head[u] = tot++;
}
int cnt = 0;
int ans;
void dfs(int id, int cnt, int val)
{
    if(cnt == k) {
        ans = min(ans, val);
        return;
    }
    for(int i = head[id]; i != -1; i = edge[i].next){
        if(use[edge[i].to]) continue;
        use[edge[i].to] = true;
        dfs(edge[i].to, cnt + 1, val + edge[i].val);
        use[edge[i].to] = false;
    }
}
int main (void)
{
    while(~scanf("%d%d", &n, &m) && (n + m)){
        int stai, staj;
        tot = 0;
        for(int i = 0; i < n; i++){
            scanf("%s", t);
            for(int j = 0; j < m; j++){
                a[i][j] = (t[j] == '#')?1:0;
                if(t[j] == '@'){stai = i;staj = j;}
            }
        }
        scanf("%d",&k);
        aa[0] = stai + 1;
        ab[0] = staj + 1;
        for(int i = 1; i <= k; i++){
            scanf("%d%d", &aa[i],& ab[i]);
        }
        memset(head, -1, sizeof(head));
        for(int i = 0; i <= k; i++){
            for(int j = 0; j <= k; j++){
                dist[i][j] = bfs(aa[i] - 1, ab[i] - 1, aa[j] - 1, ab[j] - 1);
                if(dist[i][j] != -1) addedge(i, j);
            }
        }
        memset(use, false, sizeof(use));
        use[0] = true;
        ans = oo;
        dfs(0, 0, 0);
        if(ans == oo) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

状压

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int, int>p;
const int maxn = 100 + 5, oo = 0x3f3f3f3f;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
int a[maxn][maxn];
int d[maxn * maxn];
int dist[maxn * maxn][maxn * maxn];
int n, m, k;
int t[maxn];
bool vis[maxn][maxn];
p b[maxn];
inline int gid(p pi)
{
    return pi.first * m + pi.second;
}
int bfs(p aa, p b)
{
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    d[gid(aa)] = 0;
    queue<p> q;
    q.push(aa);
    while(!q.empty()) {
        p t = q.front(); q.pop();
        if(t == b) return d[gid(t)];
        int x = t.first, y = t.second;
        for (int dir = 0; dir < 4; dir++) {
            int xx = x + dx[dir], yy = y + dy[dir];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if(!a[xx][yy] && !vis[xx][yy] ) {
                d[xx * m + yy] = d[x * m + y] + 1;
                q.push(p(xx, yy));
                vis[xx][yy]  = true;
            }
        }
    }
    return d[gid(b)];
}
int main(void)
{
    while(~scanf("%d%d", &n, &m) && (n + m)) {
        char tt[maxn];
        int stai, staj;
         for(int i = 0; i < n; i++){
            scanf("%s", tt);
            for(int j = 0; j < m; j++){
                a[i][j] = (tt[j] == '#')?1:0;
                if(tt[j] == '@'){stai = i;staj = j;}
            }
        }
        b[0] = p(stai, staj);
        int k;scanf("%d",&k);
        int x, y;
        for (int i = 1; i <= k; i++) {
            scanf("%d%d", &x, &y);
            b[i] = p(x - 1, y - 1);
        }
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                dist[gid(b[i])][gid(b[j])] = bfs(b[i], b[j]);
            }
        }
        for(int i = 0; i <= k; i++){
            t[i] = i;
        }
        int ans = oo;
        do {
            int cnt = 0;
            for (int i = 0; i < k; i++) {
                cnt += dist[gid(b[t[i]])][gid(b[t[i + 1]])];
            }
            ans = min(ans, cnt);
        } while(next_permutation(t + 1, t + k + 1));
        if(ans == oo) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

C - Zhuge Liang’s Password(模拟)

题意：

给定两个$n*n$的矩阵，矩阵可以进行$90，180，270$的旋转，问两个矩阵完全重合的时候最多有几个数是相同的。

分析：

这场最水的一道题了。。暴力模拟一下即可。

代码：

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 30 + 5;
int a[maxn][maxn], b[maxn][maxn], tmp[maxn][maxn];
int main()
{
    int n;
    while(~scanf("%d", &n) && n){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                scanf("%d", &a[i][j]);
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                scanf("%d", &b[i][j]);
            }
        }
        int ans = 0;
        int cnt;
        for(int i = 0; i < 4; i++){
            cnt = 0;
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(a[j][k] == b[j][k]) cnt++;
                }
            }
            ans = max(ans, cnt);
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                   tmp[j][k] = a[n - 1 - k][j];
                }
            }
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                   a[j][k] = tmp[j][k];
                }
            }
        }
        printf("%d\n", ans);
    }
}

F - Infinite Go(并查集，模拟)

题意：

两个人下围棋，问最后黑白棋子各剩多少。

分析：

模拟，第一反应连通块可以用并查集搞，然后就顺着题意一直在纠结怎么判断联通块内部的空白区域的大小，其实转换个角度，我们可以看一个连通块周围是否有空白区域，如果一个连通块四周被相反颜色的包围，没有剩余空白区域，那么整个连通块都要被移走。这样我们只要维护连通块周围的空白部分即可。删除的时候dfs遇到颜色相同的就删除，否则该块所在连通块的空白区域加一。
然后就狂T不止，因为$map$常数太大，每次找颜色都访问一次$map$的话，太耗时，直接作为参数传进$Delete()$中

代码：

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
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
#define sa(n) scanf("%d", &n)
typedef pair<int, int>p;
const int maxn = 1e4 + 5;
int pa[maxn], sz[maxn];
int ans[2];
map<p, int>id;
map<p, int>::iterator mi;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1,1, 0};
int _find(int a)
{
    if(pa[a] == a) return a;
    return pa[a] = _find(pa[a]);
}
void Delete(p a, int c)
{
    id.erase(a);
    int x = a.first, y = a.second;
    for(int j = 0; j < 4; j++){
        int xx = x + dx[j], yy = y + dy[j];
        if(xx < 1 || yy < 1) continue;
        p t = p(xx, yy);
        if(id.find(t) == id.end()) continue;
        if((id[t] & 1) == c) Delete(t, c);
        else sz[_find(id[t])]++;
    }
}
int tmp;
p a, t;
int main (void)
{
    int T;sa(T);
    while(T--){
        int n;sa(n);
        int x, y;
        id.clear();
        for(int i = 1; i <= n; i++){
                pa[i] = i;sz[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            sa(x);sa(y);
            a = p(x, y);
            id[a] = i;
            for(int j = 0; j < 4; j++){
                int xx = x + dx[j], yy = y + dy[j];
                if(xx < 1|| yy < 1) continue;
                t = p(xx, yy);
                if(id.find(t) == id.end()) sz[i]++;
                else if((id[t] & 1) == (i & 1)){
                    tmp = _find(id[t]);
                    sz[tmp]--;
                    pa[tmp] = i;
                    sz[i] += sz[tmp];
                }
            }
             for(int j = 0; j < 4; j++){
                int xx = x + dx[j], yy = y + dy[j];
                if(xx < 1|| yy < 1) continue;
                t = p(xx, yy);
                if(id.find(t) == id.end()) continue;
                tmp = _find(id[t]);
                if((id[t] & 1) != (i & 1)){//different
                    sz[tmp]--;
                    if(!sz[tmp]) Delete(t, id[t] & 1);
                }
            }
            if(!sz[i]) Delete(a, i & 1);
        }
        ans[0] = ans[1] = 0;
        for(mi = id.begin(); mi != id.end(); mi++){
            if(mi->second != 0){
                ans[mi->second & 1]++;
            }
        }
        printf("%d %d\n", ans[1], ans[0]);
    }
    return 0;
}

G - Ants(01Trie树)

题意：

$n$个点组成一棵树，给定树边长度，定义任意两个不同点之间的距离为两点之间边的异或值(考虑顺序)，$m$个询问，求所有距离中第$k$大距离为多少。

分析：

首先利用异或的性质，我们可以随便找一点作为根节点，然后$dfs$求出每个点到该点之间边的异或值，那么求两点之间的距离就将两点的$dist$数组异或一下即可~
这样我们就可以将$dist$数组插入$01Trie$树中，那么对于单独的一个点，问题就可以转化为经典的求异或值第$k$大的问题了。
但是如何处理所有点的第$k$大呢？这里就开始想不清楚了。。。。
======= 我是智障的分界线 =====
我们将询问离线处理。。
直接得到第$k$大不好算，可以从第1大开始，依次计算。
首先将所有点的第$1$大进行比较，选出最大，然后将选出的最大值删除，并将其对应的点的第$2$大值，加进去再与那些第$1$大们进行比较选出第$2$大值。。。依次类推。。这样是可以保证我们每次取到的点时全局最大，第$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
/*************************************************************************
    > File Name: 4776.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/8 14:41:18
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, int>pl;
const int maxn = 1e5 + 5, maxm = 6200005;
struct Trie {
    int a[2];
    int sz;
} f[maxm];
int cnt,  tot;
int head[maxn], _rank[maxn];
ll ans[maxn << 1];
void init(int n)
{
    cnt = 1;
    tot = 0;
    memset(ans, -1, sizeof(ans));
    memset(f, 0, sizeof(Trie) * maxm);
    for(int i = 1; i <= n; i++){
        _rank[i] = 1;
        head[i] = -1;
    }
}
void insert(ll x, int u, int num) 
{
	int k;
    for (int i = num; i >= 0; i--) {
        f[u].sz++;
        k = (x >> i) & 1;
        if (!f[u].a[k])  f[u].a[k] = ++cnt;
        u = f[u].a[k];
    }
    f[u].sz++;
}
ll query(ll x, int u, int num, int K) 
{
	int k;
    ll ans = 0;
    for (int i = num; i >= 0; i--) {
        k = (x >> i) & 1;
        ans <<= 1;
        if (f[u].a[k^1] && f[f[u].a[k^1]].sz >= K){
            u = f[u].a[k^1];
            ans |= k^1;
        }else{
            if(f[u].a[k^1]) K -= f[f[u].a[k^1]].sz;  
            u = f[u].a[k];
            ans |= k;
        }
    }
    ans ^= x;
    return ans;
}
struct EDGE{
    int to, next;
    ll val;
}edge[maxn << 1];
void addedge(int u, int v, ll val)
{
    edge[tot].to = v;
    edge[tot].val = val;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int q[maxn];
ll dist[maxn];
void dfs(int u, int fa)
{
    for(int i = head[u]; i != -1; i = edge[i].next){
        int v = edge[i].to;
        if(v == fa) continue;
        dist[v] = dist[u] ^ edge[i].val;
        dfs(v, u);
    }
}
int main(void)
{
    int n;
    while(~scanf("%d", &n) && n){
        int root;
		priority_queue<pl>que;
        init(n);
        int x, y;
        ll z;
        for(int i = 0; i < n - 1; ++i){
            scanf("%d%d%I64d", &x, &y, &z);
            addedge(x, y, z); addedge(y, x, z);
        }
        dist[1] = 0;
        dfs(1, 1);
        for(int i = 1; i <= n; ++i){
            insert(dist[i], 1, 60);
        }
        for(int i = 1; i <= n; ++i){
            que.push(pl(query(dist[i], 1, 60, 1), i));
        }
        int maxq = 0;
        int m;scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            scanf("%d", &q[i]);
            maxq = max(maxq, q[i]);
        }
        maxq = min((ll)maxq, n * 1ll * (n - 1));
        for(int i = 1; i <= maxq; ++i){
            if(que.empty()) break;
            pl t = que.top(); que.pop();
            ans[i] = t.first;
            if(_rank[t.second] >= n) continue;
            _rank[t.second]++;
            que.push(pl(query(dist[t.second], 1, 60, _rank[t.second]), t.second));
        }
        for(int i = 0; i < m; ++i){
            printf("%I64d\n", ans[q[i]]);
        }
    }
    return 0;
}

H - Rabbit Kingdom(树状数组)

题意：

给定序列，若干询问，求给定询问区间中互质的数的个数。

分析：

智商太低理解了好久好久，最后还是看别人代码明白的。
设$l[i]$为位置为$i$的元素左边第一个与$w[i]$不互质的数，$r[i]$为右边第一个与$w[i]$不互质的数，那么$(l[i], r[i])$区间内的所有数均与$w[i]$互质。
假设我们从头开始扫，为了防止重复计算，我们不管$i$左边的数，那么每遇到$i$，就把$i$的贡献加到后面相应的区间$[i,r[i])$里，实现起来我们就可以用树状数组(或线段树)维护区间互质数的对数和，每遇到$i$，就$add(i,1),add(r[i],-1)$。
下面处理询问，首先对所有询问根据区间左端点进行排序，然后我们从头开始扫，设头指针$pp=1$，每次遇到$l[i]=pp$时，说明对于左端点在$pp$之后的询问他是有贡献的，就把他的贡献加到相应的区间中，即$[i, r[i])$，指针扫过时再进行还原。我们可以用$vector$保存每个$l[i]=pp$的元素位置$i$，然后每次访问到一个位置直接遍历相应的$vector$即可。
关键是

  1. 区间问题，前缀和不可搞，就用两个数组标记头和尾
  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
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 200000 + 5, oo = 0x3f3f3f3f;
vector<int>prime[maxn];
vector<int>loc[maxn];
int l[maxn], r[maxn];
int w[maxn];
int pos[maxn];
int bit[maxn];
int ans[maxn];
bool isprime[maxn];
int n, q;
struct Q{
    int lq; int rq;int num;
    bool operator < (const Q &a) const{
        return lq < a.lq;
    }
};
Q query[maxn];
int h[maxn];
void initprime()
{
    int tot = 0;
    memset(isprime, false, sizeof(isprime));
    memset(h, 0, sizeof(h));
    for(int i = 2; i < maxn; i++){
        if(!isprime[i]){
            h[tot++] = i;
            for(int j = 2 * i; j < maxn; j += i){
                isprime[j] = true;
            }
        }
   }
   for(int i = 0; i < tot; i++){
        for(int j = h[i]; j < maxn; j += h[i]){
            prime[j].push_back(h[i]);
        }
   }
}
void add(int i, int x)
{
    while(i <= n){
        bit[i] += x;
        i += i & (-i);
    }
}
int sum(int i)
{
    int ans = 0;
    while(i){
        ans += bit[i];
        i -= i & (-i);
    }
    return ans;
}
int main (void)
{
    initprime();
    while(scanf("%d%d", &n, &q) && (n + q)){
        for(int i = 1; i <= maxn; i++){
            loc[i].clear();
        }
        for(int i = 1; i <= n; i++){
            scanf("%d", &w[i]);
        }
        memset(pos, 0, sizeof(pos));
        int a;
        for(int i = 1; i <= n; i++){
            a = 0;
            for(int j = 0; j < prime[w[i]].size(); j++){
                a = max(a, pos[prime[w[i]][j]]);
                pos[prime[w[i]][j]] = i;
            }
            l[i] = a;
            loc[a].push_back(i);
        }
        a = oo;
        memset(pos, 0x3f, sizeof(pos));
        for(int i = n; i >= 1; i--){
            a = oo;
            for(int j = 0; j <  prime[w[i]].size(); j++){
                a = min(a, pos[prime[w[i]][j]]);
                pos[prime[w[i]][j]] = i;
            }
            r[i] = a;
        }
        //for(int i = 1; i <= n; i++)cout<<i<<' '<<l[i]<<' '<<r[i]<<endl;
       int tl, tr;
       for(int i = 0; i < q; i++){
            scanf("%d%d", &query[i].lq, &query[i].rq);
            query[i].num = i;
       }
       sort(query, query + q);
       memset(bit, 0, sizeof(bit));
       for(int i = 1; i <= n; i++){
            if(!l[i]){
                add(i, 1);
                if(r[i] <= n) add(r[i], -1);
            }
       }
       int pp = 1;
       for(int i = 0; i < q; i++){
            while(pp < query[i].lq){
                add(pp, -1);
                if(r[pp] <= n) add(r[pp], 1);
                for(int j = 0; j < loc[pp].size(); j++){
                    add(loc[pp][j], 1);
                    if(r[loc[pp][j]] <= n) add(r[loc[pp][j]], -1);
                }
                pp++;
            }
            ans[query[i].num] = sum(query[i].rq) - sum(query[i].lq - 1);
        }
        for(int i = 0; i < q; i++){
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

I - Gems Fight!(博弈+DP)

题意：

有$B(0\le B \le 21)$个背包，有$G(0 \le G \le 8)$种颜色的宝石，这两个人轮流选择某一个背包，把这个背包包里的宝石放到一个共享的地方里，当这里某一种颜色的宝石等于$S$，那么就可以产生一个魔法石，这个人得到这个魔法石并且还能得到一个额外的拿包的机会，两个人都用最佳策略，问最后两个人能获得的魔法石的差。

分析：

  1. 首先可以明确，背包最多只有$21$个， 所以我们可以用状态压缩来表示拿背包的情况。
  2. 对于不同局势，先手后手均采取最优策略，所以二者均采取同样的方式拿包。
  3. 另外一个重要性质就是两个人拿到魔法石的总数总是确定的

那么我们就可以得出：
设$dp[i] :=面对背包状态为i时可以获得的最大的魔法宝石数$
状态转移方程：
如果拿某个包产生了新的魔法石，则可以继续下一轮，那么dp[i] = max (dp[i], dp[i|(1<<j)] + ccnt);
否则，换手，那么$dp[i|(1<<j)]$就是下一手的了，根据总和我们就可以求出当前手对应的值
dp[i] = max (dp[i], res - dp[i|(1<<j)]);
当所有背包都被取即$i == 1 << n - 1$时，此时获得的最大魔法石数为$0$，那么我们倒着推一遍，先手获得的最大值即为$dp[0]$。
然后位运算少加个括号就成功调试了一个小时。

代码：

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
#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 22, oo = 0x3f3f3f3f;
int dp[1<<maxn], cnt[maxn][10],num[maxn];
int main ()
{
    int G, B, S;
    while (scanf ("%d %d %d", &G, &B, &S) && (G + B + S)){
        int m, x;
        memset (cnt, 0, sizeof(cnt));
        for (int i = 0; i < B; i++){
            scanf ("%d", &m);
            for (int j = 0; j < m; j++){
                scanf ("%d", &x);
                cnt[i][x] ++;
            }
            for(int j = 1; j <= G; j++){
                num[j] += cnt[i][j];
            }
        }
        int sum = 0;
        for(int i = 1; i <= G; i++){
            sum += num[i] / S;
        }
        memset(dp, 0, sizeof(dp));
        int n = 1 << B;
        for(int i = n - 2; i >= 0; i--){
            memset(num, 0, sizeof(num));
            for(int j = 0; j < B; j++){
                if(i & (1 << j)){
                    for(int k = 1; k <=G; k++){
                        num[k] += cnt[j][k];
                    }
                }
            }
            int now = 0;
            for(int j = 1; j <= G; j++){
                now += num[j] / S;
                num[j] %= S;
            }
            int res = sum - now;
            for (int j = 0; j < B; j++){
                if ((i & (1<< j)) == 0){
                    int ccnt = 0;
                    for (int k = 1; k <= G; k++)
                        ccnt += (num[k] + cnt[j][k]) / S;
                    if (ccnt > 0)
                        dp[i] = max (dp[i],  dp[i|(1<<j)] + ccnt);
                    else
                        dp[i] = max (dp[i], res - dp[i|(1<<j)]);
                }
            }
        }
        printf ("%d\n", 2 * dp[0] - sum);
    }
    return 0;
}
文章目录
  1. 1. A - Lights Against Dudely(状压+暴力)
    1. 1.1. 题意：
    2. 1.2. 分析：
    3. 1.3. 代码：
  2. 2. B - Stealing Harry Potter’s Precious(BFS + DFS)
    1. 2.1. 题意：
    2. 2.2. 分析：
    3. 2.3. 代码：
  3. 3. C - Zhuge Liang’s Password(模拟)
    1. 3.1. 题意：
    2. 3.2. 分析：
    3. 3.3. 代码：
  4. 4. F - Infinite Go(并查集，模拟)
    1. 4.1. 题意：
    2. 4.2. 分析：
    3. 4.3. 代码：
  5. 5. G - Ants(01Trie树)
    1. 5.1. 题意：
    2. 5.2. 分析：
    3. 5.3. 代码：
  6. 6. H - Rabbit Kingdom(树状数组)
    1. 6.1. 题意：
    2. 6.2. 分析：
    3. 6.3. 代码：
  7. 7. I - Gems Fight!(博弈+DP)
    1. 7.1. 题意：
    2. 7.2. 分析：
    3. 7.3. 代码：