【题解】 —算法竞赛入门经典第二版 【第四章习题】【10/10】

发表于 | 更新于 | 分类于

UVa 1589 Xiangqi【模拟】

题目大意：

给出一个象棋残局，按照象棋规则，此时红方已被“将军”，判断红方是否已被“将死”。

解题思路：

模拟黑方所有棋子下一步可能走的位置，将这些位置进行标记。之后枚举红方的帥能走的每一个位置，看是否有一个没被标记的位置。

Mycode：

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

int dir[][2] = {0,1,1,0,-1,0,0,-1};

struct node
{
    char ch;
    int x, y;
};

bool check(char ch)   //没棋子是真
{
    if(ch == 'G') return false;
    if(ch == 'H') return false;
    if(ch == 'R') return false;
    if(ch == 'C') return false;
    return true;
}

char mapa[25][25];
bool mmpa[25][25];

int main()
{
    //int cas = 0;
    int t, n, m;
    bool flag;
    while(cin >> t >> n >> m && (t||n||m))
    {
        //cout << "case:" << cas++ << endl;
        node ss[10];
        bool flag = false;
        memset(mapa, 0, sizeof(mapa));
        memset(mmpa, 0, sizeof(mmpa));
        for(int i = 0; i < t; ++i)
        {
            cin >> ss[i].ch >> ss[i].x >> ss[i].y;
            mapa[ss[i].x][ss[i].y] = ss[i].ch;
        }


        for(int ii = 0; ii < t; ++ii)  //标记棋盘将不能到达的位置
        {
            //cout << ss[ii].ch << endl;
            if(ss[ii].ch == 'R')//车
            {
                for(int i = ss[ii].x-1; i > 0; --i) //Up
                {
                    mmpa[i][ss[ii].y] = true;
                    if(!check(mapa[i][ss[ii].y])) break;
                }
                for(int i = ss[ii].x+1; i < 11; ++i) //Down
                {
                    mmpa[i][ss[ii].y] = true;
                    if(!check(mapa[i][ss[ii].y])) break;
                }
                for(int i = ss[ii].y-1; i > 0; --i) //Left
                {
                    mmpa[ss[ii].x][i] = true;
                    if(!check(mapa[ss[ii].x][i])) break;
                }
                for(int i = ss[ii].y+1; i < 11; ++i) //Right
                {
                    mmpa[ss[ii].x][i] = true;
                    if(!check(mapa[ss[ii].x][i])) break;
                }
            }


            if(ss[ii].ch == 'C') //炮
            {
                flag = false;
                for(int i = ss[ii].x-1; i > 0; --i) //Up
                {
                    if(!check(mapa[i][ss[ii].y]))
                    {
                        if(flag) break;//{mmpa[i][ss[ii].y] = true;break;}
                        flag = true;
                    }
                    if(flag)
                        mmpa[i-1][ss[ii].y] = true;
                        //mmpa[i][ss[ii].y] = true;
                }

                flag = false;
                for(int i = ss[ii].x+1; i < 11; ++i) //Down
                {
                    if(!check(mapa[i][ss[ii].y]))
                    {
                        if(flag) break;//{mmpa[i][ss[ii].y] = true;break;}
                        flag = true;
                    }
                    if(flag)
                        mmpa[i+1][ss[ii].y] = true;
                        //mmpa[i][ss[ii].y] = true;
                }

                flag = false;
                for(int i = ss[ii].y-1; i > 0; --i) //Left
                {
                    if(!check(mapa[ss[ii].x][i]))
                    {
                        if(flag) break;//{ mmpa[ss[ii].x][i] = true;break;}
                        flag = true;
                    }
                    if(flag)
                        mmpa[ss[ii].x][i-1] = true;
                        //mmpa[ss[ii].x][i] = true;
                }

                flag = false;
                for(int i = ss[ii].y+1; i < 10; ++i) //Right
                {
                    if(!check(mapa[ss[ii].x][i]))
                    {
                        if(flag) break;//{mmpa[ss[ii].x][i] = true;break;}
                        flag = true;
                    }
                    if(flag)
                        mmpa[ss[ii].x][i+1] = true;
                        //mmpa[ss[ii].x][i] = true;
                }
            }

            if(ss[ii].ch == 'H') //马
            {
                if(check(mapa[ss[ii].x-1][ss[ii].y]))
                {
//                    mmpa[ss[ii].x-1][ss[ii].y+2] = true;
//                    mmpa[ss[ii].x-1][ss[ii].y-2] = true;
                    if(ss[ii].x-2 > 0)
                    {
                        if(ss[ii].y-1 > 0)
                            mmpa[ss[ii].x-2][ss[ii].y-1] = true;
                        mmpa[ss[ii].x-2][ss[ii].y+1] = true;
                    }
                }
                if(check(mapa[ss[ii].x+1][ss[ii].y]))
                {
//                    mmpa[ss[ii].x+1][ss[ii].y+2] = true;
//                    mmpa[ss[ii].x+1][ss[ii].y-2] = true;
                    if(ss[ii].y-1 > 0)
                        mmpa[ss[ii].x+2][ss[ii].y-1] = true;
                    mmpa[ss[ii].x+2][ss[ii].y+1] = true;
                }
                if(check(mapa[ss[ii].x][ss[ii].y+1]))
                {
//                    mmpa[ss[ii].x-2][ss[ii].y+1] = true;
//                    mmpa[ss[ii].x+2][ss[ii].y+1] = true;
                    if(ss[ii].x-1 > 0)
                        mmpa[ss[ii].x-1][ss[ii].y+2] = true;
                    mmpa[ss[ii].x+1][ss[ii].y+2] = true;
                }
                if(check(mapa[ss[ii].x][ss[ii].y-1]))
                {
//                    mmpa[ss[ii].x-2][ss[ii].y-1] = true;
//                    mmpa[ss[ii].x+2][ss[ii].y-1] = true;
                    if(ss[ii].y-2 > 0)
                    {
                        if(ss[ii].x-1 > 0)
                            mmpa[ss[ii].x-1][ss[ii].y-2] = true;
                        mmpa[ss[ii].x+1][ss[ii].y-2] = true;
                    }
                }
            }

            if(ss[ii].ch == 'G') //帅
            {
                //cout << ss[ii].x << "---" << ss[ii].y << endl;
                for(int i = ss[ii].x-1; i > 0; --i) //上
                {
                    mmpa[i][ss[ii].y] = true;
                    if(!check(mapa[i][ss[ii].y]))
                        break;
                    //cout << i << "--" << ss[ii].y << endl;
                }
            }
            //cout << ss[ii].ch << endl;
        }

        bool ans = false;
        //将可以到达的位置
        for(int i = 0; i < 4; ++i)
        {
            int xx = n + dir[i][0];
            int yy = m + dir[i][1];

            if(xx < 1 || xx > 3 || yy < 4 || yy > 6) continue;  //越界continue
//            if(!check(mapa[xx][yy])) continue;                  //有棋子continue
            if(!mmpa[xx][yy]) ans = true;
        }
        if(!mmpa[n][m]) ans = true;

        /*puts("");
        puts("棋盘");
        for(int q = 1; q < 10; ++q)
        {
            for(int w = 1; w < 12; ++w)
            {
                cout << mmpa[q][w] << " ";
            }
            puts("");
        }*/

        if(!ans)
            puts("YES");
        else
            puts("NO");
        //puts("");
    }
    return 0;
}

对拍Code：

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    srand(time(NULL));
    int maxn = 6, cou = 0;
    int dir[11][10];
    const char s0[] = "RRCCHH";
    //for(int s = 3; s >= 1; --s)
    for(int s = (1<<maxn) - 1; s >= 1; --s)
    {
        for(int num = 1; num; num--)
        {
            memset(dir, 0, sizeof(dir));
            int n = 0, is = 0;
            int r0 = 1 + rand()%3, c0 = 4+rand()%3;
            dir[r0][r0] = 1;
            int r1 = 8 + rand()%3, c1 = 4 + rand()%3;
            while(c0 == c1)
                c1 = 4 + rand()%3;
            dir[r1][c1] = 1;
            for(int i = 0; i < maxn; ++i)
                if(s & (1<<i))
                    n++;
            printf("\n%d %d %d\nG %d %d\n",n+1,r0,c0,r1,c1);
            cou++;
            for(int i = 0; i < maxn; ++i)
                if(s & (1<<i))
                {
                    int r = 1+rand()%10, c = 1+rand()%9;
                    if(is == 0 && s0[i] != 'C')
                    {
                        if(s0[i] != 'H')
                        {
                            r = r0 +1;
                            c = c0;
                        }
                        else
                        {
                            r = r0+2;
                            c = c0+1;
                        }
                        is = 1;
                    }
                    else
                    {
                        while(dir[r][c])
                        {
                            r = 1+rand()%10;
                            c = 1+rand()%9;
                        }
                    }
                    dir[r][c] = 1;
                    printf("%c %d %d\n",s0[i], r, c);
                }
        }
    }
    printf("0 0 0\n");
    return 0;
}

UVa 201 Squares【模拟】

题目大意：

在n行n列的小黑点中，用m条线段将这些黑点进行连接，按照边长统计这些线段构成了多少个正方形。

解题思路：

因为数据范围很小，我直接用四维数组存下了任意两点之间是否有线段将其连接。最后遍历每个顶点，记录以当前顶点为正方形的左上角边长为k的正方形是否存在。

PS：其实完全可以用二维数组做出来的。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

map<int,int> a;
bool xx[10][10][10][10];
bool yy[10][10][10][10];

int main()
{
    int n, _;
    char op;
    int x, y, cas = 0;
    while(cin >> n >> _)
    {
        if(cas)
            puts("\n**********************************\n");
        a.clear();
        memset(xx, false, sizeof(xx));
        memset(yy, false, sizeof(yy));
        while(_--)
        {
            cin >> op >> x >> y;
            if(op == 'H')
                xx[x][y][x][y+1] = true;
            else
                yy[y][x][y+1][x] = true;
        }

        /*for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                cout << xx[i][j] << " ";
            puts("");
        }
        puts("");

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                cout << yy[i][j] << " ";
            puts("");
        }
        puts("");*/

        for(int i = 1; i < n; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                for(int k = 1; k <= n; ++k)
                {
                    if(k + j > n) break;
                    if(k + i > n) break;
                    int q;
                    for(q = i; q < i+k; ++q)
                    {
                        if(yy[q][j][q+1][j] == 0 || yy[q][j+k][q+1][j+k] == 0) break;
//                        if(xx[q][j] == 0 || yy[q][j] == 0) break;
//                        if(xx[q][j+k] == 0 || yy[q][j+k] == 0) break;
                    }
                    if(q < i+k) continue;;

                    for(q = j; q < j+k; ++q)
                    {
                        if(xx[i][q][i][q+1] == 0 || xx[i+k][q][i+k][q+1] == 0) break;
//                        if(xx[i][q] == 0 || yy[i][q] == 0) break;
//                        if(xx[i+k][q] == 0 || yy[i+k][q] == 0) break;
                    }
                    if(q < j+k) continue;;

                    //printf("i=%d j=%d k=%d\n",i,j,k);
                    //cout << k << endl;
                    if(!a.count(k)) a[k] = 0;
                    ++a[k];
                }
            }
        }

        //cout << "a.size=" << a.size() << endl;
        printf("Problem #%d\n\n",++cas);
        if(a.size())
        {
            for(auto it = a.begin(); it != a.end(); ++it)
                printf("%d square (s) of size %d\n", it->second,it->first);
        }
        else
            puts("No completed squares can be found.");
    }
    return 0;
}

UVa 220 Othello【模拟】

题目大意：

模拟黑白棋的游戏进程。

PS：这里紫书上有点错误，就是给出的例子白旗有8个合法操作，书上少了(3,6)和(7,5)这两个位置(网站上的题面是正确的)。

解题思路：

模块化一下程序，直接模拟就好了。

这里比较重要的模块是判断某个点放置某个棋子时是否合法，用变量为0和1来控制棋子的颜色，写完这个模块，其他的都很轻松了。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

string tem;
int t, p, x, y; //p为1是W-白，0是B-黑
char mapa[10][10];
int dir[][2] = {1,0,-1,0,1,1,1,-1,-1,1,-1,-1,0,1,0,-1};

bool judge(int x, int y, int p)
{
    bool f1, f2;
    int xx, yy, dx, dy;
    char now = p ? 'W' : 'B';
    char nex = p ? 'B' : 'W';
    for(int i = 0; i < 8; ++i)
    {
        f1 = f2 = false;
        xx = x, yy = y;
        dx = dir[i][0], dy = dir[i][1];
        while(1)
        {
            xx += dx, yy += dy;
            if(mapa[xx][yy] == nex)
                f1 = true;
            else if(mapa[xx][yy] == now)
            {
                f2 = true;
                break;
            }
            else
                break;
        }
        if(f1 && f2)
            return true;
    }
    return false;
}

void legal(int p)
{
    int cnt = 0;
    for(int i = 1; i <= 8; ++i)
    {
        for(int j = 1; j <= 8; ++j)
        {
            if(mapa[i][j] != '-')   continue;
            if(judge(i, j, p))
            {
                if(cnt) printf(" ");
                printf("(%d,%d)", i, j);
                ++cnt;
            }
        }
    }
    if(cnt)
        puts("");
    else
        puts("No legal move.");
}

void update(int x, int y, int p)
{
    bool f1, f2;
    int xx, yy, dx, dy;
    char now = p ? 'W' : 'B';
    char nex = p ? 'B' : 'W';
    mapa[x][y] = now;
    for(int i = 0; i < 8; ++i)
    {
        f1 = f2 = false;
        xx = x, yy = y;
        dx = dir[i][0], dy = dir[i][1];
        while(1)
        {
            xx += dx, yy += dy;
            if(mapa[xx][yy] == nex)
                f1 = true;
            else if(mapa[xx][yy] == now)
            {
                f2 = true;
                break;
            }
            else
                break;
        }
        if(f1 && f2)
        {
            for(int q = x + dx, w = y + dy; (q != xx || w != yy); q += dx, w += dy)
                    mapa[q][w] = now;
        }
    }
}

void out()
{
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= 8; ++i)
    {
        for(int j = 1; j <= 8; ++j)
        {
            if(mapa[i][j] == 'B')   cnt1++;
            if(mapa[i][j] == 'W')   cnt2++;
        }
    }
    printf("Black - %2d White - %2d\n", cnt1, cnt2);
}

int main()
{
    cin >> t;
    for(int cas = 1; cas <= t; ++cas)
    {
        if(cas > 1)  puts("");
        for(int i = 1; i <= 8; ++i)
            scanf("%s",mapa[i]+1);
        cin >> tem;
        p = (tem == "W");
        while(cin >> tem && tem != "Q")
        {
            if(tem == "L")  //L
                legal(p);
            else            //Mxy
            {
                x = tem[1] - '0';
                y = tem[2] - '0';
                if(!judge(x, y, p))
                    p ^= 1;
                update(x, y, p);
                out();
                p ^= 1;
            }
        }
        for(int i = 1; i <= 8; ++i)
            puts(mapa[i]+1);
    }
    return 0;
}

Uva 253 Cube painting【模拟】

题目大意：

给两个骰子，问他们是否等价。

解题思路：

我直接找了个魔方标记了一下然后把所有情况都找出来了。太暴力了，我好菜啊。

PS：这样做的话要注意所有的if都是并列的，就是只要满足任意一种情况，答案就是TRUE。

MyCode：

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

int main()
{
    string s, a, b;
    while(cin >> s)
    {
        a = b = " ";
        for(int i = 0; i < 6; ++i)
            a += s[i];
        for(int i = 6; i < 12; ++i)
            b += s[i];

        bool flag = false;
        char ch = b[3];
        char ca = b[4];
        //cout << ch << "--" << b[3] << "--" << a[6] << endl;
        //cout << ca << "--" << b[4] << "--" << a[1] << endl;

        if(ch==a[1] && ca==a[6])
        {
            if(b[1]==a[4] && b[2]==a[2] && b[5]==a[5] && b[6]==a[3])
                flag = true;
            if(b[1]==a[2] && b[2]==a[3] && b[5]==a[4] && b[6]==a[5])
                flag = true;
            if(b[1]==a[3] && b[2]==a[5] && b[5]==a[2] && b[6]==a[4])
                flag = true;
            if(b[1]==a[5] && b[2]==a[4] && b[5]==a[3] && b[6]==a[2])
                flag = true;
        }
        if(ch==a[2] && ca==a[5])
        {
            if(b[1]==a[1] && b[2]==a[4] && b[5]==a[3] && b[6]==a[6])
                flag = true;
            if(b[1]==a[3] && b[2]==a[1] && b[5]==a[6] && b[6]==a[4])
                flag = true;
            if(b[1]==a[4] && b[2]==a[6] && b[5]==a[1] && b[6]==a[3])
                flag = true;
            if(b[1]==a[6] && b[2]==a[3] && b[5]==a[4] && b[6]==a[1])
                flag = true;
        }
        if(ch==a[3] && ca==a[4])
        {
            if(b[1]==a[1] && b[2]==a[2] && b[5]==a[5] && b[6]==a[6])
                flag = true;
            if(b[1]==a[2] && b[2]==a[6] && b[5]==a[1] && b[6]==a[5])
                flag = true;
            if(b[1]==a[6] && b[2]==a[5] && b[5]==a[2] && b[6]==a[1])
                flag = true;
            if(b[1]==a[5] && b[2]==a[1] && b[5]==a[6] && b[6]==a[2])
                flag = true;
        }
        if(ch==a[4] && ca==a[3])
        {
            if(b[1]==a[1] && b[2]==a[5] && b[5]==a[2] && b[6]==a[6])
                flag = true;
            if(b[1]==a[5] && b[2]==a[6] && b[5]==a[1] && b[6]==a[2])
                flag = true;
            if(b[1]==a[6] && b[2]==a[2] && b[5]==a[5] && b[6]==a[1])
                flag = true;
            if(b[1]==a[2] && b[2]==a[1] && b[5]==a[6] && b[6]==a[5])
                flag = true;
        }
        if(ch==a[5] && ca==a[2])
        {
            if(b[1]==a[1] && b[2]==a[3] && b[5]==a[4] && b[6]==a[6])
                flag = true;
            if(b[1]==a[3] && b[2]==a[6] && b[5]==a[1] && b[6]==a[4])
                flag = true;
            if(b[1]==a[6] && b[2]==a[4] && b[5]==a[3] && b[6]==a[1])
                flag = true;
            if(b[1]==a[4] && b[2]==a[1] && b[5]==a[6] && b[6]==a[3])
                flag = true;
        }
        if(ch==a[6] && ca==a[1])
        {
            if(b[1]==a[2] && b[2]==a[4] && b[5]==a[3] && b[6]==a[5])
                flag = true;
            if(b[1]==a[4] && b[2]==a[5] && b[5]==a[2] && b[6]==a[3])
                flag = true;
            if(b[1]==a[5] && b[2]==a[3] && b[5]==a[4] && b[6]==a[2])
                flag = true;
            if(b[1]==a[3] && b[2]==a[2] && b[5]==a[5] && b[6]==a[4])
                flag = true;
        }
        //cout << a << "---" << b << endl;
        if(flag)
            puts("TRUE");
        else
            puts("FALSE");
    }
    return 0;
}

UVa 1590 IP Networks【模拟】【位运算】

题目大意：

给出n个IP地址，求最小的网络包含所有的输入地址。

解题思路：

因题目背景需要计算机网络的知识，所以理解起来可能比较难。但读懂题意后就是二进制和十进制的转换。

翻译一下就是将给出的点分十进制形式的IP地址转化为32位的二进制形式，找出他们前n项的二进制表示是一样的“公共前缀”，最小IP地址就是这前缀之后的二进制全改为0然后写成点分十进制的结果，子网掩码就是将这些前缀二进制表示全改成1后转化为点分十进制的结果。(表述能力有限，可自己查阅《计算机网络》这本书或者当♂面问我)

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int t;
string ans, ipp;
struct node
{
    int yi[5];
    string yy[5];
};
string trans(int a)
{
    string aft = "";
    while(a)
    {
        if(a & 1)
            aft = '1' + aft;
        else
            aft = '0' + aft;
        a >>= 1;
    }
    while(aft.size() < 8)
        aft = '0' + aft;
    return aft;
}
void solve()
{
    int tem;
    for(int i = 0; i < 4; ++i)
    {
        tem = 0;
        for(int j = 0; j < 8; ++j)
        {
            tem += (1 << (8-j-1)) * (ipp[i*8+j] - '0');
        }
        printf("%d", tem);
        printf("%c", i < 3 ? '.' : '\n');
    }

    for(int i = 0; i < 4; ++i)
    {
        tem = 0;
        for(int j = 0; j < 8; ++j)
        {
            tem += (1 << (8-j-1)) * (ans[i*8+j] - '0');
        }
        printf("%d", tem);
        printf("%c", i < 3 ? '.' : '\n');
    }
}
int main()
{
    while(cin >> t)
    {
        node s[MAX];
        for(int i = 0; i < t; ++i)
        {
            scanf("%d.%d.%d.%d",&s[i].yi[0], &s[i].yi[1], &s[i].yi[2], &s[i].yi[3]);
            for(int j = 0; j < 4; ++j)
                s[i].yy[j] = trans(s[i].yi[j]);
            //cout << s[i].yy << "   " << s[i].ee << "   " << s[i].aa << "   " << s[i].ii << endl;
        }
        int pos = 32;
        for(int i = 0; i < t; ++i)
        {
            for(int j = i+1; j < t; ++j)
            {
                bool flag = true;
                for(int k = 0; k < 4 && flag; ++k)
                {
                    for(int q = 0; q < 8; ++q)
                    {
                        if(s[i].yy[k][q] != s[j].yy[k][q])
                        {
                            pos = min(pos, k*8 + q);
                            flag = false;
                            break;
                        }
                    }
                }
            }
        }
        ans = ipp = "";
//        string ipp = "";
        bool flag = true;
        for(int i = 0; i < 4 && flag; ++i)
        {
            for(int j = 0; j < 8; ++j)
            {
                if(i*8 + j >= pos)
                {
                    flag = false;
                    break;
                }
                ipp += s[0].yy[i][j];
            }
        }

//        cout << ipp << endl;
//        string ans = "";
        for(int i = 0; i < pos; ++i)
            ans += '1';
        for(int i = pos+1; i <= 32; ++i)
        {
            ans += '0';
            ipp += '0';
        }

//        cout << ans.size() << endl;
//        cout << ipp << "-----" << ans << endl;
        solve();
    }
    return 0;
}

UVa 508 Morse Mismatches【模拟】【map】

题目大意：

给出加密方式、待加密文本和加密文本，要你根据前两项内容输出加密文本代表的什么。如果精准匹配则直接输出；如果多个匹配则输出字典序最小的那个后加上!；如果无法匹配则选一个字典序最小的可能匹配的单词输出并在最后加个?，其中可能匹配指的是可以在编码尾部加上或删去若干字符。

(紫书上表述有误，多个单词精准匹配时输出字典序最小的，非精准匹配时也要输出字典序最小的可能匹配的单词)

解题思路：

因为不同文本加密后可能是相同的密文，所以根据密文直接模拟找明文是无法实现的。因为我们已经知道了待加密文本，所以我们可以直接将待加密文本和它加密后的密文存起来，直接拿着这些密文和要求的密文作对比并记录。

因为map自动按照字典序排列了，所以前两种情况很容易实现。对于第三种情况直接拿map中的文本和要匹配的文本进行子序列判断也可以很容易实现。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

char a;
string s;
map<char, string> morse;
map<string, string> context;

void read_morse()
{
    while(1)
    {
        cin >> a;
        if(a == '*') return ;
        cin >> s;
        morse[a] = s;
    }
}

string trans(string before)
{
    string after = "";
    for(int i = 0; i < before.size(); ++i)
        after += morse[before[i]];
    return after;
}

void read_context()
{
    while(1)
    {
        cin >> s;
        if(s == "*") return ;
        context[s] = trans(s);
    }
}

void solve()
{
    string yy, tt;
    while(1)
    {
        cin >> s;
        if(s == "*") return ;
        yy = "";
        int flag = 0;

        for(auto it = context.begin(); it != context.end(); ++it)
        {
            tt = it -> second;
            if(tt == s)
            {
                if(flag == 0)
                    yy = it -> first;
                ++flag;
            }
        }

        if(flag == 1)           //精确匹配
            cout << yy << endl;
        else if(flag > 1)       //!
            cout << yy << "!" << endl;
        else                    //?
        {
            int hh = INF;
            bool ok = false;
            bool is_first = true;

            for(auto it = context.begin(); it != context.end(); ++it)
            {
                if(is_first) yy = it -> first;
                is_first = false;
                tt = it -> second;
                if(tt.size() > s.size())
                {
                    if(tt.find(s) == 0)
                    {
                        if(tt.size() - s.size() < hh)
                        {
                            hh = tt.size() - s.size();
                            yy = it -> first;
                            ok = true;
                        }
                    }
                }
                else if(tt.size() < s.size())
                {
                    if(s.find(tt) == 0)
                    {
                        if(s.size() - tt.size() < hh)
                        {
                            hh = s.size() - tt.size();
                            yy = it -> first;
                            ok = true;
                        }
                    }
                }
            }
            cout << yy << "?" <<endl;
        }
    }
}

int main()
{
    read_morse();
    read_context();
    solve();
    return 0;
}

UVa 509 RAID!【模拟】【位运算】

题目大意：

给出了一种磁盘保护技术，要你根据规则检验一下磁盘存储数据是否正确及能否恢复，如果可以输出存储的数据。

解题思路：

先检验是否合法，如果大于1个x，一定不合法；若恰好一个x，则可以根据规则将这个x恢复出来；若没有x则直接将这些位进行异或操作看最终结果。确定合法后再讲二进制转化为16进制输出就可以了。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

char op;
int jiou;
int d, s, b;
char mapa[10][MAX];
char hexa[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
string trans(string zz)
{
    int tot = 0;
    tot += (zz[0] - '0') * 8;
    tot += (zz[1] - '0') * 4;
    tot += (zz[2] - '0') * 2;
    tot += (zz[3] - '0') * 1;
    string ans = "";
    ans += hexa[tot];
    return ans;
}
int main()
{
    int cas = 0;
    while(cin >> d && d)
    {
        cin >> s >> b;
        cin >> op;
        //1是奇校验，0是偶校验。
        jiou = (op == 'O' ? 1 : 0);
        for(int i = 1; i <= d; ++i)
        {
            scanf("%s",mapa[i]+1);
        }

        bool flag = true;
        for(int i = 1; i <= s*b; ++i)
        {
            int t = 0;
            int x = 0;
            int idx = 0;
            for(int j = 1; j <= d; ++j)
            {
                if(mapa[j][i] == 'x')
                {
                    ++x;
                    idx = j;
                    continue;
                }
                t ^= (mapa[j][i] - '0');
            }
            if(x > 1)
            {
                flag = false;
                break;
            }
            if(x == 1)
            {
                if(t == jiou)
                    mapa[idx][i] = '0';
                else
                    mapa[idx][i] = '1';
            }
            else        //x==0
            {
                if(t != jiou)
                {
                    flag = false;
                    break;
                }
            }
        }

        if(!flag)
            printf("Disk set %d is invalid.\n", ++cas);
        else
        {
            int temp = 0;
            for(int i = 1; i <= b; ++i)
            {
                int ii = i % d;
                if(ii == 0)  ii = d;
                for(int j = 1; j <= s; ++j)
                {
                    mapa[ii][j+temp] = '2';
                }
                temp += s;
            }

            //d、s、b
            string stem = "", ans = "";
            for(int i = 1; i <= b*s; i += s)
            {
                for(int j = 1; j <= d; ++j)
                {
                    for(int k = 0; k < s; ++k)
                    {
                        if(mapa[j][k+i] == '2')   continue;
                        stem += mapa[j][k+i];
                        if(stem.size() == 4)
                        {
                            ans += trans(stem);
                            stem = "";
                        }
                    }
                }
            }
            //不足位补0
            if(stem.size())
            {
                int goal = 4 - stem.size();
                while(goal--)
                    stem += '0';
                ans += trans(stem);
            }

            printf("Disk set %d is valid, contents are: ", ++cas);
            cout << ans << endl;
        }
    }
    return 0;
}

UVa 12108 Extraordinarily Tired Students【模拟】

题目大意：

给出n个学生的清醒-睡眠周期以及初始时他们所处的周期的哪个时间，当课堂上睡觉人数大于清醒人数时他就会睡觉，否则再听课A_i分钟后再观察一下。问经过多次时间后全班同学都处于清醒状态，或者不存在这种情况。

解题思路：

直接模拟睡觉的过程。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 505;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, tot;
bool slp[15];
int a[15], b[15], c[15], pri[15];
int main()
{
    int cas = 0;
    while(cin >> n && n)
    {
        for(int i = 0; i < n; ++i)
        {
            cin >> a[i] >> b[i] >> c[i];
            pri[i] = a[i] + b[i];
            slp[i] = (c[i] > a[i]);
        }
        int t = 1;
        bool f = false;
        while(t < MAX)
        {
            int awake = 0;
            int sleep = 0;
            for(int i = 0; i < n; ++i)
            {
                if(slp[i])
                    sleep++;
                else
                    awake++;
            }
            if(awake == n)
            {
                f = true;
                break;
            }
            for(int i = 0; i < n; ++i)
            {
                if(c[i] == a[i])            //判断是否要入睡
                {
                    if(sleep <= awake)      //坚持听课a_i分钟再说
                    {
                        slp[i] = false;
                        c[i] = 1;
                    }
                    else                    //睡吧
                    {
                        slp[i] = true;
                        c[i]++;
                    }
                }
                else if(c[i] == pri[i])     //恰好一个周期结束
                {
                    c[i] = 1;
                    slp[i] = false;
                }
                else                        //还在睡中
                    c[i]++;
            }
            t++;
        }
        if(f)
            printf("Case %d: %d\n", ++cas, t);
        else
            printf("Case %d: -1\n", ++cas);
    }
    return 0;
}

UVa 1591 Data Mining【模拟】

题目大意：

？？？

解题思路：

直接枚举AB的取值即可。

MyCode：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

LL n, Sp, Sq, K, A, B, Pofs, tem;
int main()
{
    while(cin >> n >> Sp >> Sq)
    {
        K = Sq * n << 10;
        Pofs = (n-1) * Sp;
        for(int a = 0; a < 32; ++a)
            for(int b = 0; b < 32; ++b)
            {
                tem = ((Pofs + (Pofs << a)) >> b) + Sq;
                if(tem >= n * Sq && tem < K)
                {
                    K = tem;
                    A = a;
                    B = b;
                }
            }
        cout << K << " " << A << " " << B << endl;
    }
    return 0;
}

UVa 815 Flooded!【模拟】【二分】

题目大意：

输入一个n x m的网格及每个格子的高度，每个格子都是边长为10m的正方形，网格四周是无限大的墙壁。给你网格内雨水的总体积，输出水位的海拔及多少百分比的区域有水。

解题思路：

雨水分布只与网格高度有关，和其位置分布无关，因此我们可以将网格按照高度从小到大排序后，看雨水能淹没到哪里。当无法全部淹没时找到恰好无法淹没的那个位置，根据它的高度来二分枚举最终水位的高度。

MyCode：

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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;

double a[MAX];
int main()
{
    int n, m;
    int cas = 0, tot, num;
    double wat, res, tem, ans;
    while(cin >> n >> m && m)
    {
        tot = 0;
        n *= m;
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a+n);
        cin >> wat;
        wat /= 100;

        num = -1;
        tem = 0;
        for(int i = 1; i < n; ++i)
        {
            tem += (a[i] - a[i-1])*i;
            //cout <<tem << endl;
            if(tem >= wat)
            {
                //cout << tem << endl;
                num = i;
                break;
            }
        }

        if(num == -1) //全部淹没
        {
            ans = a[n-1] + (wat - tem)/n;
            tot = n;
            //cout << ans <<endl;
        }
        else
        {
            tem -= (a[num]-a[num-1])*num;

            double l = a[num-1], r = a[num];
            double hh = l;
            while(r-l > eps)
            {
                double mid = (r+l)/2;
                //cout << mid << "==" << tem + (mid-hh)*num << endl;

                if(tem + (mid-hh)*num > wat)
                    r = mid;
                else
                    l = mid;
                //cout << r << "--" << l << endl;
            }
            ans = l;
            for(int i = 0; i < n; ++i)
            {
                if(a[i] < ans) tot++;
            }
        }
        res = 100.0 * tot / n;
        printf("Region %d\n",++cas);
        printf("Water level is %.2f meters.\n",ans);
        printf("%.2f percent of the region is under water.\n",res);
        puts("");
    }
    return 0;
}
Donate comment here
0%