算法竞赛入门经典第四章习题(10/10)

终于刷完第四章了，，第四章习题耗时良久，，记录下，

Xiangqi

UVA - 1589

题意：判断黑方是否被将死

题解：模拟象棋动作，判断将走前后左右是否能不被将死

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
#include<bits/stdc++.h>
using namespace std;

char dead[11][10];
int n, xq, yq;
int xz[] = {-1, 1, 0, 0}, yz[] = {0, 0, -1, 1};
int mx[] = {-2, -2, 2, 2, 1, -1, 1, -1}, my[] = {1, -1, 1, -1, -2, -2, 2, 2};
int mxx[] = {-1, -1, 1, 1, 1, -1, 1, -1}, myy[] = {1, -1, 1, -1, -1, -1, 1, 1};

bool check(int x, int y){
    return (x >= 1 && x <=10 && y >= 1 && y <= 9);
}

bool judge(int x, int y){
    if(x < 1 || x > 3 || y < 4 || y > 6)return true;
    for(int i = 0; i < 4; i++){
        int tx = x, ty = y, cnt = 0;
        while(check(tx += xz[i], ty += yz[i])){
//            if(cnt == 0 && dead[tx][ty] == 'G' && (tx == xq || ty == yq))return false;
            if(cnt == 0 && (dead[tx][ty] == 'G' || dead[tx][ty] == 'R'))return true;
            if(cnt == 1 && dead[tx][ty] == 'C')return true;
            if(dead[tx][ty] != 0)cnt++;
        }
    }
    for(int i = 0; i < 8; i++)
        if(check(x + mx[i], y + my[i]) && dead[x + mx[i]][y + my[i]] == 'H' && dead[x + (mxx[i])][y + (myy[i])] == 0){
                return true;
        }
    return false;
}


int main(){
    while(~scanf("%d%d%d", &n, &xq, &yq) && n){
        memset(dead, 0, sizeof(dead));
        for(int i = 0; i < n; i++){
        char aim;
        int xx, yy;
        cin.ignore();
        cin>> aim >> xx >> yy;
        dead[xx][yy] = aim;
        }
        bool ans = 1;
        for(int i = 0; i < 4; i++){
            ans &= judge(xq + xz[i], yq + yz[i]);
        }
        puts(ans ? "YES" : "NO");
    }

    return 0;
}

Squares

UVA - 201

题意：给你一个网，和连上的边，问你有几个正方形;

题解：根据边长遍历,一下下搜，判断能否形成正方形 

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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 11;
bool kj[2][Ma][Ma][Ma];
int n;

int fidn(int x){
    int sl = 0;
    for(int i = 1; i <= n - x; i++){
        for(int j = 1; j <= n - x; j++){
            int u;
            for(u = 0; u < 4; u++){
                int ii;
                for(ii = 0; ii < x; ii++){
                    if(u % 2 == 0 && !kj[0][i + x * (u / 2)][j + ii][j + ii + 1])break;
                    else if(!kj[1][j + x * (u / 3)][i + ii][i + ii + 1])break;
                }
                if(ii != x)break;
            }
            if(u == 4)sl++;
        }
    }
    return sl;
}

int main(){
    int tot = 0, m;
    while(~scanf("%d%d", &n, &m)){
        if(tot)puts("\n**********************************\n");
        printf("Problem #%d\n\n", ++tot);
        memset(kj, 0, sizeof(kj));
        while(m--){
            char c[2];
            int x, y;
            scanf("%s%d%d", c, &x, &y);
            if(x <= n && y < n)
                    kj[c[0] == 'H' ? 0 : 1][x][y][y + 1] = true;
        }
        bool chu = false;
        for(int i = 1; i < n; i++){
            int sl = fidn(i);
            if(sl != 0)chu = true, printf("%d square (s) of size %d\n", sl, i);
        }
        if(!chu)puts("No completed squares can be found.");
    }

    return 0;
}

Othello

UVA - 220

题意：模拟黑白棋，两枚黑棋夹住的白棋会变黑;

题解：题有些坑点，，默认一个棋手走完下一个棋手走，输出黑白棋时输出两位数，不满加空格，，在这里pe好多次，，(可能是我题没读仔细，，)

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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 10;
char qp[Ma][Ma];

bool judge(int x, int y){
    return x >= 0 && x < 8 && y >= 0 && y < 8;
}

bool zou(char wh, int r, int c, bool ms){
    if(!judge(r, c) || qp[r][c] != '-')return false;
    int zx[] = {1, -1, 0, 0, -1, 1, -1, 1};
    int zy[] = {0, 0, 1, -1, -1, 1, 1, -1};
    for(int i = 0; i < 8; i++){
        int x = r, y = c, cnt = 0;
        while(judge(x += zx[i], y += zy[i])){
//            cout<< i << " = " << x <<' ' << y << qp[x][y] <<endl;
            if(qp[x][y] == '-')break;
            if(ms && qp[x][y] == wh){
                if(cnt == 0)break;
                else return true;
            }
            if(!ms && qp[x][y] == wh){
                while(x -= zx[i], y -= zy[i], x != r || y != c){
//                    cout<<i <<" = " <<x << ' ' << y << endl;
                    qp[x][y] = wh;
                }
                break;
            }
            cnt++;
        }
//        if(r ==2 && c == 3){
//            for(int i = 0; i < 8; i++)
//            printf("%s\n", qp[i]);
//        }
    }
    return false;
}

void zh(char wh){
    int gs = 0;
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            if(zou(wh, i, j, 1))printf(gs ? " (%d,%d)": "(%d,%d)", i + 1, j + 1), gs++;
        }
    }
    if(gs == 0)puts("No legal move.");
    else putchar('\n');
}

void chu(char wh, int r, int c){
    --r, --c;
    zou(wh, r, c, 0);
    qp[r][c] = wh;
    int gs = 0, qt = 0;
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++)
        if(qp[i][j] == wh)gs++;
        else if(qp[i][j] != '-')qt++;
    if(wh == 'W')printf("Black - %2d White - %2d\n", qt, gs);
    else printf("Black - %2d White - %2d\n", gs, qt);
}

int main(){
    int T;
    scanf("%d", &T);
    bool q = false;
    while(T--){
        if(q)putchar('\n');
        else q = true;
        memset(qp, 0, sizeof(qp));
        for(int i = 0; i < 8; i++)
            scanf("%s", qp[i]);
        char aim[2];
        scanf("%s", aim);
        char ml[5];
        do{
            scanf("%s", ml);
            if(ml[0] == 'L')zh(aim[0]);
            else if(ml[0] == 'M'){
                if(zou(aim[0], int(ml[1] - '0') - 1, int(ml[2] - '0') - 1, 1))chu(aim[0], int(ml[1] - '0'), int(ml[2] - '0'));
                else chu((aim[0] = aim[0] == 'W' ? 'B': 'W'), int(ml[1] - '0'), int(ml[2] - '0'));
                aim[0] = aim[0] == 'W' ? 'B': 'W';
            }
        }while(ml[0] != 'Q');
        for(int i = 0; i < 8; i++)
            printf("%s\n", qp[i]);
    }

    return 0;
}

Cube painting

UVA - 253

题意：判断两枚骰子是否相同;

题解：易证明骰子一样的话对面一定是同一对，根据这个进行判断;

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
#include<bits/stdc++.h>
using namespace std;
//rgbgrb grgrbb
int main(){
    string tem;
    while(cin>> tem){
        bool ss[13];
        memset(ss, 1, sizeof(ss));
        for(int i = 0; i < 3; i++){
            ss[i] = ss[5 - i] = false;
            for(int j = 6; j < 12; j++){
                if(tem[j] == tem[i] && ss[j]){
                    if(tem[12 - j + 5] == tem[5 - i]){
                        ss[j] = ss[12 - j + 5] = false;
                        break;
                    }
                }
            }
        }
        int cnt = 0;
        for(int i = 0; i < 12; i++)
            if(ss[i])cnt++;
        if(cnt == 0)puts("TRUE");
        else puts("FALSE");
    }

    return 0;
}

IP Networks

UVA - 1590

题意：给你几个ip地址，让你输出最小的能包含他们的ip和子网掩码

题解：读入ip凭接在一起，不断求当前掩码，将这些数据当成二进制来计算，算是位运算的运用,当当前掩码和当前ip能包含输入ip时不进行运算;

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<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll getIp(ll a, ll b, ll c, ll d){
    return (a << 24) | (b << 16) | (c << 8) | d;
}

ll getMark(ll a, ll b){
    ll mark = ~0;
    ll x = a ^ b;
    while(x){
        x >>= 1;
        mark <<= 1;
    }
    return mark;
}

int main(){
    int n;
    while(~scanf("%d", &n)){
    n--;
    ll ip, a, b, c, d, mark = ~0;
    scanf("%lld.%lld.%lld.%lld", &a, &b, &c, &d);
    ip = getIp(a, b, c, d);
    while(n--){
        scanf("%lld.%lld.%lld.%lld", &a, &b, &c, &d);
        ll tip = getIp(a, b, c, d);
        if(ip ^ (tip & mark))
        mark = getMark(ip, tip), ip &= mark;
    }
    printf("%lld.%lld.%lld.%lld\n", (ip >> 24) & 255, (ip >> 16) & 255, (ip >> 8) & 255, ip & 255);
    printf("%lld.%lld.%lld.%lld\n", (mark >> 24) & 255, (mark >> 16) & 255, (mark >> 8) & 255, mark & 255);
    }
    return 0;
}

Morse Mismatches

UVA - 508

题意：给你morse编码和一个字典，让你根据这些输出密文，有多个时输出单词最短的并加上！，当不能完美匹配时输出删减或增加密文后能匹配的，并输出？，

题解：根据具题意模拟，

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
#include<bits/stdc++.h>
using namespace std;

map<char, string>zd;

struct ms{
    string s, ss;
    ms(string a){
        int le = a.length();
        s = a;
        for(int i = 0; i < le; i++){
            ss += zd[a[i]];
        }
    }
    bool operator < (ms b) const {
        return s.length() < b.s.length();
    }
};

int main(){
    vector<ms>v;
    string aim, ans;
    while(cin>> aim && aim != "*"){
        cin>> ans;
        zd[aim[0]] = ans;
    }
    while(cin>> aim && aim != "*"){
        v.push_back(ms(aim));
    }//建立字典
    sort(v.begin(), v.end());
    while(cin>> aim && aim != "*"){
        int cnt = 0;
        int t = 0;
        int ma = aim.length();
        int le = v.size();
        while(1){
        for(int i = 0; i < le; i++)
            if(v[i].ss == aim.substr(0, ma - t)){
                if(!cnt)cout<< v[i].s;
                cnt++;
            }
            else if(v[i].ss.substr(0, v[i].ss.size() - t) == aim){
                if(!cnt)cout<< v[i].s;
                cnt++;
            }
        if(cnt)break;
        t++;
        }
        if(t)cout<< '?';
        else if(cnt > 1)cout<< '!';
        putchar('\n');
    }


    return 0;
}

RAID!

UVA - 509

题意：这题真的是题意读一年，，，，给n个磁盘让你判断能否恢复，若能输出恢复后的数据，

题解：输入是按磁盘来输入的，判断时得往下一列列判断，校验块有b块，d块出现一次;

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int Ma = 100000;
char ck[7][Ma];

void solve(string ans){
    int le = ans.length();
    while(le % 4)
        ans += '0', le++;

    for(int i = 0; i < le; i += 4){
        int t = 0;
        for(int j = 0; j < 4; j++)
            if(ans[i + j] == '1')t += (1 << (3 - j));
        if(t < 10)printf("%d", t);
        else printf("%c", 'A' + t - 10);
    }

    return ;
}

int main(){
    int d;
    int tot = 0;
    while(~scanf("%d", &d) && d != 0){
        int s, b;
        scanf("%d%d", &s, &b);
        getchar();
        char c;
        c = getchar();
        int aim = (c == 'E' ? 0 : 1);
        for(int i = 0; i < d; i++)
            scanf("%s", ck[i]);
        bool can = true;
        for(int i = 0; can && i < s * b; i++){
            int x = 0, t = 0, dis;
            for(int j = 0; j < d; j++){
                if(ck[j][i] != 'x')t ^= int(ck[j][i] - '0');
                else x++, dis = j;
                if(x > 1)can = false;
            }
            if(!can)break;
            if(x)ck[dis][i] = (t == aim ? '0' : '1');
            else if(t != aim)can = false;
        }
        if(!can)printf("Disk set %d is invalid.\n", ++tot);
        else {
            printf("Disk set %d is valid, contents are: ", ++tot);
            string ans = "";
            int tot = 0;
            for(int i = 0; i < b; i++){
                int j = i % d;
                ck[j][tot++ * s] = '*';
            }
            for(int i = 0; i < s * b; i += s){
                for(int j = 0; j < d; j++){
                if(ck[j][i] == '*')continue;
                for(int ii = i; ii < i + s; ii++){
                    ans += ck[j][ii];
                    if(ans.length() % 4 == 0)solve(ans), ans.clear();
                }
                }
            }
            solve(ans);
            putchar('\n');
        }
    }

    return 0;
}

Extraordinarily Tired Students

UVA - 12108

题意：每个学生有一个清醒周期和一个睡眠周期，当睡觉人数严格大于一半的人才能睡，不然就坚持一个清醒周期;

题解：直接模拟上课进程，当每个同学的状态和初始状态相同时进入循环，退出模拟，输出-1

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<bits/stdc++.h>
using namespace std;

bool wek, hav;
int n;
int first[12];
int cnt;
struct Stu{
    int a, b, c;
    bool wk;
    void init(int k){
        if(k)c %= (a + b);
        if(k && c == a && cnt >= n - cnt)
            c = 0;
        c += k;
        if(c > a)wk = false;
        else wk = true;
    }
}stu[12];

bool check(){
    int qi = 0;
    cnt = 0;
    for(int i = 0; i < n; i++){
        if(stu[i].wk)cnt++;
        if(hav && stu[i].c == first[i])qi++;
        else hav = true;
    }
    if(cnt == n){
            wek = true;
            return false;
    }
    else if(qi == n)return false;
    return true;
}

void go(){
    for(int i = 0; i < n; i++){
        stu[i].init(1);
    }
}

int main(){
    int tot = 0;
    while(~scanf("%d", &n) && n){
        cnt = 0;
        wek = false;hav = false;
        printf("Case %d: ", ++tot);
        for(int i = 0; i < n; i++){
            scanf("%d%d%d", &stu[i].a, &stu[i].b, &stu[i].c);
            first[i] = stu[i].c;
            stu[i].init(0);
        }
        int tim = 1;
        while(check())
            go(), tim++;
        if(wek)printf("%d\n", tim);
        else puts("-1");
    }

    return 0;
}

Data Mining

UVA - 1591

题意：这题题意是真的恐怖，，半天读不明白，，为了精简除法的速度，tuple发现了一种用位运算来精简计算q的偏移值的公式，让你求公式中的A和B;

题解：直接枚举a和b，按常识来设定a和b的范围，计算q的总大小由一个q大小的位置加上有最后一个p地址计算出的偏移值的大小，根据算出来的值不能比原来的小的基础上尽量小来更新a和b;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long llu;

int main(){
    llu n, p, q;
    while(~scanf("%llu%llu%llu", &n, &p, &q)){
        llu k = n * q << 30, a, b;//k尽量大
        llu pof = p * (n - 1);
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < 32; j++){
                llu tem = ((pof + (pof << i)) >> j) + q;
                if(tem >= n * q && tem < k){
                    a = i, b = j, k = tem;
                }
            }
        }
        printf("%llu %llu %llu\n", k, a, b);
    }

    return 0;
}

Flooded!

UVA - 815

题意：给你一个网格及其各个海拔，每个网格是10米的正方形，和网格内总的水量，外面是无限高的墙，问你水平面有多高， 和多少面积有水;

题解：将总的水量除以100，得到高度，将网格按海拔排序，水当前高度比下一块地高的话就淹没它，加上他的高度，每次用水除以已淹网格数的平均高度进行比较，最后输出总高度除以淹没网格数的海拔，以及已淹网格除以总网格数的淹没百分比;总的水量得用浮点存储，不然精度的丢失会导致与下个网格的比较出现问题;(我单词没拼对wa了好多发，，，下次一定用复制的，，，)

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
#include<bits/stdc++.h>
using namespace std;

const int Ma = 32;
const int inf = 0x3f3f3f3f;
int ge[Ma * Ma];

int main(){
	int n, m;
	int tot = 0;
 	while(~scanf("%d%d", &n, &m) && n){
		printf("Region %d\n", ++tot);
		for(int i = 0; i < n * m; i ++){
			scanf("%d", &ge[i]);
		}
		double all;
		int ma = n * m;
		scanf("%lf", &all);
		all /= 100.0;
		sort(ge, ge + m * n);
		ge[ma] = inf;
		int i;
		for(i = 0; i < ma; i++){
			all += ge[i];
			if(all / (i + 1) <= ge[i + 1])
				break;
		}

		printf("Water level is %.2f meters.\n", 1.0 * all / (i + 1));
		printf("%.2f percent of the region is under water.\n\n", 1.0 * (i + 1) / ma * 100);
	}
    return 0;
}

Comments

⬆︎TOP