【题解】 —算法竞赛入门经典第二版 【第八章例题】【10/19】

发表于 | 更新于 | 分类于

UVa 120 Stacks of Flapjacks【构造】

题目大意：

一叠煎饼等待翻转，每个煎饼上有一个编号代表其大小，每次翻转是选择一个数$k$，将从锅底数第$k$张上面的煎饼全部翻过来，即原来的煎饼现在到了下面。请设计一种方法使得所有煎饼按照从小到大的顺序排列，即最上边的最小。

解题思路：

每次查找不满足要求的位置，将它翻转到顶端后再翻转到自己应该在的位置。为了满足无后效性，我们每次都找最大的元素。

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

string s;
int tot, a[35];
void filp(int t)
{
    int i, j;
    for(i = 1, j = t; i <= j; ++i, --j)
    {
        swap(a[i], a[j]);
    }
    cout << tot - t << " ";
}
int main()
{
    while(getline(cin, s))
    {
        tot = 1;
        cout << s << endl;
        stringstream ss(s);
        while(ss >> a[tot])
        {
            ++tot;
        }
        for(int i = tot-1; i >= 1; --i)
        {
            int t = max_element(a + 1, a + i + 1) - a;
            if(t == i)  continue;
            if(t > 1)   filp(t);    //将它翻到顶端
            filp(i);                //翻到该在位置
        }
        cout << 0 << endl;
    }
    return 0;
}

UVa 1605 Building for UN【构造】

题目大意：

设计一个包含若干层的大楼，每层都是一个等大的网格，要求给每个格子分配一个字母，使得任意两个不同的字母都有一对相邻的格子。要求设计的大楼不超过$1000000$个格子。

解题思路：

因为层数、行数、列数都可以自己选，那我可以直接选择两层，每层都是$n \times n$的，第一层的第$i$行全是国家$i$，第二层的第$j$列全是国家$j$。

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

int n;
void country(int i)
{
    if(i <= 26)
        cout << char('A' + i - 1);
    else
        cout << char('a' + i - 26 - 1);
}
int main()
{
    while(cin >> n)
    {
        printf("2 %d %d\n", n, n);
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                country(i);
            }
            cout << endl;
        }
        cout << endl;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                country(j);
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

UVa 1152 4 Values whose Sum is 0【二分】

题目大意：

给定$4$个$n$元素的集合$A$、$B$、$C$、$D$，要求分别从里面选出一个元素$a$、$b$、$c$、$d$，使得$a + b + c + d = 0$，问有多少种选法。

解题思路：

将$A$、$B$合并，$C$、$D$合并，分别排序然后对其中一个数组的元素进行遍历$x_i$，从另一个数组中找是否存在$y = -x_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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 4005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int a[MAX], b[MAX], c[MAX], d[MAX];
int A[MAX * MAX], B[MAX * MAX];
int main()
{
    int t, n, tot;
    scanf("%d", & t);
    while(t--)
    {
        tot = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
            {
                A[i*n + j] = a[i] + b[j];
                B[i*n + j] = c[i] + d[j];
            }
        sort(A, A + n*n);
        sort(B, B + n*n);
        int tt = n*n - 1;
        for(int i = 0; i < n*n; ++i)
        {
            while(A[i] + B[tt] > 0 && tt >= 0) --tt;
            if(tt < 0)  break;
            int tem = tt;
            while(A[i] + B[tem] == 0 && tem >= 0)
            {
                ++tot;
                --tem;
            }
        }
        printf("%d\n", tot);
        if(t)   puts("");
    }
    return 0;
}

UVa 11134 Fabled Rooks【问题分解】【贪心】

题目大意：

在一个$n \times n$的棋盘上放置$n$枚棋子，使得任意两者之间既不同行也不同列，并且每个棋子都在规定的范围$(xl_i, yl_i) - (xr_i, yr_i)$内。

解题思路：

互相攻击的条件为在同一行或者同一列，则不互相攻击的情况就是既不在同一行也不在同一列，又因为行和列是无关的，那我们就可以把这个问题分解为两个一维的问题来解决了。

对于$x$坐标来说，我们要做的就是在将$n$个点分配完毕后，每个区间都至少包含一个点。而分配是采用贪心的策略——即对所有可分配的区间找到右边界最小的区间进行分配。$y$坐标同理。

MyCode(参考LRJ’s 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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;

int n, xl[N], yl[N], xr[N], yr[N], x[N], y[N];
bool solve(int *l, int *r, int *res)
{
    fill(res, res + n, -1);
    for(int col = 1; col <= n; ++col)
    {
        int idx = -1, minr = n + 1;
        for(int i = 0; i < n; ++i)
            if(res[i] < 0 && r[i] < minr && col >= l[i])
            {
                idx = i;
                minr = r[i];
            }
        if(idx < 0 || col > minr)   return false;
        res[idx] = col;
    }
    return true;
}

int main()
{
    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d%d", &xl[i], &yl[i], &xr[i], &yr[i]);

        if(solve(xl, xr, x) && solve(yl, yr, y))
            for(int i = 0; i < n; ++i)
                printf("%d %d\n", x[i], y[i]);
        else
            puts("IMPOSSIBLE");

    }
    return 0;
}

UVa 11054 Wine trading in Gergovia【等价转换】

题目大意：

直线上有$n$个村庄，每个村庄要么买酒要么卖酒，设第$i$个村庄的需求为$a_i$，$\sum_{i = 1}^{i = n} a_i = 0$。

把$k$个单位的酒从村庄运到相邻村庄需要$k$个单位的劳动力，计算最少需要多少劳动力可以满足所有村庄的需求。

解题思路：

因为最终供需平衡，所以不管你这个酒是从哪来的最终一定会全部抵消。为了使花费的劳动力最小，就是不得不运的时候才运。我们直接从最左边的村庄开始向右边遍历，如果可以卖那就卖掉，无法卖掉就带着继续走。当买的时候也一样，当前需要再买多少先记着，等碰到可以买的村庄时再一块买了，花费的劳动力等同于从这里的酒卖到目的村庄。

感想：

这个等价转换的思想让我想起了有道蚂蚁的题目，两者碰到后掉头，可以转化为直接穿了过去。

MyCode：

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

LL ans;
int t, tem, last;
int main()
{
    while(cin >> t && t){
        ans = 0;
        last = 0;
        for(int i = 0; i < t; ++i){
            cin >> tem;
            ans += abs(last);
            last += tem;
        }
        cout << ans << endl;
    }
    return 0;
}

UVa 1606 Amphiphilic Carbon Molecules【极角排序+扫描】【贪心】

题目大意：

平面上有$n$个点，每个点不是黑的就是白的，现在要放一个隔板，把它们分成两部分，使得一侧的白点数加上另一侧的黑点数最多。隔板上的点可以看做任意一侧。

解题思路：

首先假设直线经过两个点，否则可以移动直线使其经过两个点，并且总数不会减少。

最简单的想法就是枚举两个点，然后输出两侧的黑白点的个数。

跟进一步的做法是先找一个基准点，让隔板绕该点旋转。每当隔板扫过一个点就动态修改两侧的点数。在此之前，需对所有点相对于基准点（即将基准点看做(0,0))进行极角排序。

小技巧：

如果将所有的黑点以基点为中心做一个中心对称，则符合要求的点的个数就变成了直线一侧的点的个数。

LRJ’s 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
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
// UVa1606 Amphiphilic Carbon Molecules
// Rujia Liu
// To make life a bit easier, we change each color 1 point into color 0.
// Then we only need to find an angle interval with most points. See code for details.
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1000 + 5;

struct Point
{
    int x, y;
    double rad; // with respect to current point
    bool operator<(const Point &rhs) const
    {
        return rad < rhs.rad;
    }
} op[maxn], p[maxn];

int n, color[maxn];

// from O-A to O-B, is it a left turn?
bool Left(Point A, Point B)
{
    return A.x * B.y - A.y * B.x >= 0;
}

int solve()
{
    if(n <= 2)
        return 2;
    int ans = 0;

    // pivot point
    for(int i = 0; i < n; i++)
    {
        int k = 0;

        // the list of other point, sorted in increasing order of rad
        for(int j = 0; j < n; j++)
            if(j != i)
            {
                p[k].x = op[j].x - op[i].x;
                p[k].y = op[j].y - op[i].y;
                if(color[j])
                {
                    p[k].x = -p[k].x;
                    p[k].y = -p[k].y;
                }
                p[k].rad = atan2(p[k].y, p[k].x);
                k++;
            }
        sort(p, p+k);

        // sweeping. cnt is the number of points whose rad is between p[L] and p[R]
        int L = 0, R = 0, cnt = 2;
        while(L < k)
        {
            if(R == L)
            {
                R = (R+1)%k;    // empty interval
                cnt++;
            }
            while(R != L && Left(p[L], p[R]))
            {
                R = (R+1)%k;    // stop when [L,R] spans across > 180 degrees
                cnt++;
            }
            cnt--;
            L++;
            ans = max(ans, cnt);
        }
    }
    return ans;
}

int main()
{
    while(scanf("%d", &n) == 1 && n)
    {
        for(int i = 0; i < n; i++)
            scanf("%d%d%d", &op[i].x, &op[i].y, &color[i]);
        printf("%d\n", solve());
    }
    return 0;
}

UVa 11572 Unique Snowflakes【滑动窗口】

题目大意：

输入一个长度为$n$的序列，找一个尽量长的连续子序列，使得该序列中没有相同的元素。

解题思路：

对元素下标进行存储，向前延伸的过程中更新答案。

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

int t, n, ans, l, r;
int a[MAX];
int main()
{
    cin >> t;
    while(t--)
    {
        ans = -1;
        l = r = 1;
        cin >> n;
        for(int i = 1; i <= n; ++i)
            cin >> a[i];
        map<int, int> idx;
        idx[a[1]] = 1;
        for(int i = 2; i <= n; ++i)
        {
            if(idx.count(a[i]))
            {
                ans = max(ans, r - l);
                l = max(l, idx[a[i]] + 1);
            }
            r = i;
            idx[a[i]] = i;
        }
        ans = max(ans, r-l);
        cout << ans + 1 << endl;
    }
    return 0;
}

UVa 1471 Defense Lines【】

题目大意：

解题思路：

MyCode：

1
2


UVa 1451

题目大意：

解题思路：

MyCode：

1
2


UVa 714 Copying Books【二分】【最小化最大值】

题目大意：

将包含$m$个整数的序列划分为$k$段，使得每段的数的和最小。

解题思路：

将最优化问题转化为判定性问题，求出最小的区间和之后，按照格式输出。

要求的格式比较恶心，如果有多解要求前面的区间和尽量小。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 555;

bool ok[N];
int t, n, k, a[N];
bool judge(ll m)
{
    ll tem = 0;
    int tot =1;
    for(int i = 1; i <= n; ++i)
    {
        tem += a[i];
        if(tem > m)
        {
            ++tot;
            tem = a[i];
        }
    }
    return tot <= k;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n,&k);
        ll tot = 0; int maxx = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            tot += a[i];
            maxx = max(maxx, a[i]);
        }

        ll l = maxx, r = tot, res = maxx, m;
        while(l <= r)
        {
            m = (l + r) / 2;
            if(judge(m))
            {
                r = m - 1;
                res = m;
            }
            else
                l = m + 1;
        }

        ll tem = 0; int remain = k;
        memset(ok, 0, sizeof(ok));
        for(int i = n; i >= 1; --i)
        {
            if(tem + a[i] > res || remain > i)
            {
                tem = a[i];
                ok[i] = 1;
                remain--;
            }
            else
                tem += a[i];
        }
        for(int i = 1; i <= n; ++i)
        {
            printf("%d%c", a[i], i == n ? '\n' : ' ');
            if(ok[i])   printf("/ ");
        }
     }
    return 0;
}

UVa 10954 Add All【贪心】【Huffman编码】

题目大意：

给定一个包含$n$个数的集合，每次从中删除两个数并将其和放回集合，直到剩下一个数。每次的代价为两个数的和，求最小代价。

解题思路：

这就是Huffman编码的建立过程，数据范围较小，利用priority_queue可轻松解决。

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
#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 n, t, ans;
int main()
{
    while(cin >> n && n)
    {
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < n; ++i)
        {
            cin >> t;
            q.push(t);
        }
        ans = 0;
        for(int i = 0; i < n-1; ++i)
        {
            int x = q.top();    q.pop();
            int y = q.top();    q.pop();
            ans += x+y;
            q.push(x+y);
        }
        cout << ans << endl;
    }
    return 0;
}

UVa 12627 Erratic Expansion【】

题目大意：

有一个红气球，每小时后会变成三个红气球 + 一个蓝气球，一个蓝气球每小时会变成4个蓝气球，分布情况如题中图片所示。

问经过$k$小时后，第$a$ ~ $b$行有多少个红气球。

解题思路：

MyCode：

1
2


UVa 11093 Just Finish it up【枚举】

题目大意：

环形跑道上有$n$个加油站，第$i$个加油站可以加$p_i$单位的汽油，从第i个到下一个加油站需要消耗$q_i$单位的汽油。油桶初始为空，假设油桶无限大，问你能否选择一个加油站作为起始位置，使得汽车可以走完一圈回到起始位置。

解题思路：

枚举起始位置就可以。如果当前枚举的位置到达某一个点$x$时汽油不够无法继续前行，则他之前的位置都不可以作为起始位置。根据这个我们可以在$O(n)$时间内解决问题。

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

bool flag;
int t, n, res;
int a[MAX], b[MAX];
int main()
{
    scanf("%d",&t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d",&n);
        flag = false;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&a[i]);
            a[i+n] = a[i];
        }
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&b[i]);
            b[i+n] = b[i];
        }

        int i, j, idx;
        int now;
        for(i = 0; i < n; i += idx)  //start point
        {
            idx = 1;
            now = 0;
            for(j = i; j < i+n; ++j)
            {
                now += a[j];
                now -= b[j];
                if(now < 0) break;
                ++idx;
            }
            if(j == i+n)
            {
                res = i;
                break;
            }
        }
        if(i >= n)
            flag = true;

        if(flag)
            printf("Case %d: Not possible\n", cas);
        else
            printf("Case %d: Possible from station %d\n", cas, res+1);
    }
    return 0;
}

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%