Shen Huang's Blog
0%

2013 Asia Hangzhou Regional Contest 题解

Posted on Edited on

自己圈的一场比赛,没想到这场等于有三道搜索,A题dfs,B题bfs+dfs,I题记忆化dfs,也是醉了

A题:

不要考虑什么先把能放的放下,反而导致编码复杂度非常高,因为只有15点,直接搜,把这个点作为中心点枚举四个方向就行.一点剪枝都不需要.

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

using namespace std;
char s[220][220];
int ma[222][222];
int now[222][222];
#define maxn 101
struct Node{
    int x,y;
}p[maxn];
int pnum;
int tmpans;

void dfs(int id,int step,bool flag){
    if (id == pnum){
        for (int i = 0; i < pnum; i ++){
            if (now[p[i].x][p[i].y] == 0){
                return;
            }
        }
        tmpans = min(tmpans,step);
        return ;
    }
    int x = p[id].x, y = p[id].y;
    int t1 = now[x][y],t2 = now[x][y + 1], t3 = now[x - 1][y], t4 = now[x][y - 1],t5 = now[x + 1][y];
    if (ma[x][y] == 1 && ma[x - 1][y] != 0 && ma[x][y + 1] != 0){
        if (t1 == 1 && t2 == 1 && t3 == 1){
        }else {
            now[x][y] = 1;
            now[x][y + 1] = 1;
            now[x - 1][y] = 1;
            dfs(id + 1,step + 1, flag);
            now[x][y] = t1;
            now[x][y + 1] = t2;
            now[x - 1][y] = t3;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x - 1][y] != 0 && ma[x][y - 1] != 0){
        if (t1 == 1 && t3 == 1 && t4 == 1){
        }else {
            now[x][y] = 1;
            now[x][y - 1] = 1;
            now[x - 1][y] = 1;
            dfs(id + 1,step + 1, 1);
            now[x][y] = t1;
            now[x][y - 1] = t4;
            now[x - 1][y] = t3;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x + 1][y] != 0 && ma[x][y + 1] != 0){
        if (t1 == 1 && t5 == 1 && t2 == 1){
        }else {
            now[x][y] = 1;
            now[x][y + 1] = 1;
            now[x + 1][y] = 1;
            dfs(id + 1,step + 1, 1);
            now[x][y] = t1;
            now[x][y + 1] = t2;
            now[x + 1][y] = t5;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x + 1][y] != 0 && ma[x][y - 1] != 0){
        if (t1 == 1 && t4 == 1 && t5 == 1){
        }else {
            now[x][y] = 1;
            now[x][y - 1] = 1;
            now[x + 1][y] = 1;
            dfs(id + 1,step + 1, flag);
            now[x][y] = t1;
            now[x][y - 1] = t4;
            now[x + 1][y] = t5;

        }
    }
    dfs(id + 1,step, flag);
}

int main(){
    int n,m;
    while (~scanf("%d%d", &n, &m) && (n + m)){
        memset(ma, -1, sizeof(ma));
        memset(now, -1, sizeof(now));
        for (int i = 0; i < n; i ++){
            scanf("%s",s[i]);
            for (int  j = 0; j < m; j ++){
                if (s[i][j] == '#'){
                    ma[i + 1][j + 1] = 0;
                    now[i + 1][j + 1] = -1;
                }else {
                    ma[i + 1][j + 1] = 1;
                    now[i + 1][j + 1] = 0;
                }
            }   
        }

        pnum = 0;
        tmpans = 999999;
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= m; j ++){
                if (ma[i][j] == 1){
                    p[pnum].x = i;
                    p[pnum ++].y = j;
                }           
            }
        }
        dfs(0,0,0);
        printf("%dn",tmpans == 999999? -1 : tmpans);           
    }
    return 0;
}
B题:

先bfs找出所有的点对的距离然后存下来,然后dfs找出所有的序列.

C题:

只要找到[i][j]对应的四个点就行了.

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a[33][33],b[33][33];
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 cnt[4] = {0,0,0,0};
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                if (a[i][j] == b[i][j]) cnt[0] ++;
                if (a[i][j] == b[j][n - i - 1]) cnt[1] ++;
                if (a[i][j] == b[n - i - 1][n - j - 1]) cnt[2] ++;
                if (a[i][j] == b[n - j - 1][i]) cnt[3] ++;
            }
        }
        int ans = 0;
        for (int i = 0; i < 4; i ++){
            ans = max(ans, cnt[i]);
        }
        printf("%dn",ans);
    }
    return 0;
}
F题:

比较繁琐的模拟,就是要考虑这个点有没有气(旁边有没有空格了).要用并查集+map(set).

I题:

状态压缩DP+记忆化搜索

注意预处理所有的状态能得到的分数,A和B他们都是走最优策略可以一起考虑区别就是dp数组记录的时候的区别,要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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int num[33],bag[22][10];
int sc[1 << 21],b,g,s;
int dp[1 << 21];
void init(int maxStatus){
    //cout << g << endl;
    int tmp[20] = {0};
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < maxStatus; i ++){
        for (int j = 0; j < b; j ++){
            if (i & (1 << j)){
                for (int k = 1; k <= g; k ++){
                    tmp[k] += bag[j][k];
                }
            }
        }
        int ret = 0;
        for (int j = 1; j <= g; j ++){
        //  cout << tmp[j] << ' ' ;
            ret += tmp[j] / s;
            tmp[j] = 0;
        }
    //  cout <<g <<  i << ' ' << ret << endl;
        sc[i] = ret;

    }
}

int dfs(int stat, int remain){
    if (dp[stat] != -1) return dp[stat];
    int ntstat, cha, ret = 0;
    for (int i = 0; i < b; i ++){
        if ((stat & (1 << i)) == 0){
            ntstat = stat | (1 << i);
            cha = sc[ntstat] - sc[stat];
            if (cha){
                ret = max(ret, dfs(ntstat, remain - cha) + cha);
            }else {
                ret = max(ret, remain - dfs(ntstat, remain));
            }
        }
    }
    dp[stat] = ret;
    return ret;
}

int main(){
    while (~scanf("%d%d%d", &g, &b, &s)){
        if (g + b + s == 0) break;
        //cout << g << b << s << endl;
        memset(bag, 0, sizeof(bag));
        memset(num, 0, sizeof(num));
        memset(sc, 0, sizeof(sc));
        memset(dp, -1, sizeof(dp));
        int k,t;
        for (int i = 0; i < b; i ++){
            scanf("%d", &k);
            //cout << "k = " << k;
            for (int j = 0; j < k; j ++){
                scanf("%d", &t);
                bag[i][t] ++;
                num[t] ++;
                //cout << t ;
            }
            //cout << endl;
        }

        int sum = 0;
        for (int i = 1; i <= g; i ++){
            sum += num[i] / s;
        }
        int maxSt = 1 << b;
        //cout << "maxSt" << maxSt << endl;
        init(maxSt);
        dp[maxSt - 1] = 0;
        int ans = dfs(0, sum);
        //cout << sum << ' ' << ans << endl;
        printf("%dn", ans - (sum - ans));
    }
}