【题解】 —算法竞赛入门经典第二版 【第五章习题】【6/16】

发表于 | 更新于 | 分类于

UVa 1593 Alignment of Code【模拟】【vector】

题目大意：

给出若干行代码，要求对齐。对齐规则为按照每列中长度最长的那个字符串为最大长度左对齐，相邻字符串间用一个空格分割。

解题思路：

直接做。

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
#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 cnt, cou;
int mlen[MAX];
string t, s;
vector<string> yy[MAX];
int main()
{
    cnt = 0;
    memset(mlen, 0, sizeof(mlen));
    while(getline(cin, t))
    {
        cou = 0;
        stringstream ss (t);
        while(ss >> s)
        {
            yy[cnt].push_back(s);
            mlen[cou] = max(mlen[cou], (int)s.size());
            ++cou;
        }
        ++cnt;
    }
    for(int i = 0; i < cnt; ++i)
    {
        int j;
        for(j = 0; j < yy[i].size()-1; ++j)
        {
            int k;
            for(k = 0; k < yy[i][j].size(); ++k)
                cout << yy[i][j][k];
            for(; k <= mlen[j]; ++k)
                cout << " ";
        }
        cout << yy[i][j];
        puts("");
    }
    return 0;
}

UVa 1594 Ducci Sequence【模拟】

题目大意：

按照规则进行操作，看1000步内能否使这个组的所有元素全变成0。

解题思路：

直接做。

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

int a[MAX];
int main()
{
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
            scanf("%d",&a[i]);

        int tem, k;
        bool flag = false;
        for(int i = 0; i < 1000; ++i)
        {
            tem = a[0];
            for(int j = 0; j < n-1; ++j)
            {
                a[j] = abs(a[j]-a[j+1]);
            }
            a[n-1] = abs(a[n-1]-tem);

            /*cout << "tem=" <<tem << endl;
            for(int tt = 0; tt < n; ++tt)
            {
                cout << a[tt] << " ";
            }
            puts("");*/

            for(k = 0; k < n; ++k)
            {
                if(a[k] != 0) break;
            }
            if(k == n)
            {
                flag = true;
                break;
            }
        }

        if(flag)
            puts("ZERO");
        else
            puts("LOOP");
    }
    return 0;
}

UVa 10935 Throwing cards away I【模拟】【vector】

题目大意：

按照规则模拟这个过程。

解题思路：

直接做。

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 = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

struct node
{
    int num;
    bool flag;
};
int main()
{
    int n, xx, tot, now, pos;
    while(scanf("%d",&n) && n)
    {
        if(n==1)
        {
            printf("Discarded cards:\n");
            printf("Remaining card: 1\n");
            continue;
        }

        node a[55];
        vector<int> ans;
        for(int i = 0; i < n; ++i)
        {
            a[i].num = i;
            a[i].flag = true;
        }
        a[0].num = n;

        ans.push_back(1);
        a[1].flag = false;

        tot = 1;
        pos = 2;
        while(tot < n-1)
        {
            xx = 0;
            now = pos;
            for(int i = 0; i < n; ++i)
            {
                if(a[(now+i)%n].flag)
                {
                    xx++;
                    pos = (now+i)%n;
                    if(xx == 2)
                    {
                        a[(now+i)%n].flag = false;
                        tot++;
                        ans.push_back(a[(now+i)%n].num);
                        break;
                    }
                }
            }
        }

        printf("Discarded cards: ");
        for(int i = 0; i < ans.size(); ++i)
        {
            if(i) cout << ", ";
            cout << ans[i];
        }
        puts("");
        printf("Remaining card: ");
        for(int i = 0; i < n; ++i)
        {
            if(a[i].flag) cout << a[i].num;
        }
        puts("");
    }
    return 0;
}

UVa 10763 Foreign Exchange【模拟】【map】

题目大意：

给出$n$组数，每组包含两个数A、B，判断是否所有的A、B都有对应的B、A组相对应。

解题思路：

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

int main()
{
    int n;
    int a, b;
    while(scanf("%d",&n) && n)
    {
        map<pair<int,int>, int> ss;
        bool flag = true;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d",&a,&b);
            ++ss[make_pair(a, b)];
        }

        for(auto it = ss.begin(); it != ss.end(); ++it)
        {
            if(ss[make_pair(it->first.second, it->first.first)] != it->second)
            {
                flag = false;
                break;
            }
        }

        if(flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

UVa 10391 Compound Words【模拟】【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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 120005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int main()
{
    string s;
    string ss[MAX];
    map<string, bool> mp;
    int tot = 0;
    while(cin >> s)
    {
        ss[tot++] = s;
        mp[s] = true;
    }

    string a, b;
    for(int i = 0; i < tot; ++i)
    {
        for(int j = 0; j < ss[i].size()-1; ++j)
        {
            a = ss[i].substr(0, j+1);
            if(!mp[a]) continue;
            b = ss[i].substr(j+1);
            if(!mp[b]) continue;
            cout << ss[i] << endl;
            break;
        }
    }
    return 0;
}

UVa 1595 Symmetry【模拟】【map】

题目大意：

给出$n$个点，问是否可以找到一条竖线，使得所有的点左右对称。

解题思路：

因为是竖线，所以如果对称轴存在，那么它一定为$x = \frac{max + min}{2}$，因此我们只要找出$x$坐标的最大值和最小值就可以求出“疑似对称轴”的竖线了，然后对于每个点挨个进行验证就好了——看它对称轴另一边是否存在对应的点。

小技巧：

因为/2可能会出现小数的情况，造成运算的不便，因此我们可以通过将所有横坐标 × 2的操作避免小数的出现。为什么都×2对最终结果无影响呢？因为我们看的只是他们的相对大小。

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
#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 n, t;
int x[MAX], y[MAX];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        map<pair<int,int>, bool> mapa;
        scanf("%d",&n);
        int mi = INF;
        int ma = -INF;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d",&x[i],&y[i]);
            x[i] <<= 1;
            mi = min(mi, x[i]);
            ma = max(ma, x[i]);
            mapa[make_pair(x[i], y[i])] = 1;
        }
        int xx = (mi + ma) / 2;
//        cout << xx << endl;
        bool f = true;
        for(int i = 0; i < n; ++i)
        {
            if(!mapa[make_pair(2*xx - x[i], y[i])])
            {
                f = false;
                break;
            }
        }
        if(f)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

UVa 12100 Printer Queue

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


UVa

题目大意：

解题思路：

MyCode：

1
2


Donate comment here
0%