山东省第一届ACM大学生程序设计竞赛解题报告【7/10】

发表于 | 更新于 | 分类于
－－－－－－－－－－－山东省第一届ACM大学生程序设计竞赛解题报告－－－－－－－－－－ －

A.Phone Number【签到】【string】

直接做。

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

int n;
string s[N];
int main()
{
    while(scanf("%d", &n) && n)
    {
        bool flag = false;
        for(int i = 0; i < n; ++i)
            cin >> s[i];
        sort(s, s + n);
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i == j)  continue;
                if(s[i].find(s[j]) == 0)
                {
                    flag = true;
                    break;
                }
            }
        }
        puts(flag ? "NO" : "YES");
    }
    return 0;
}

B.Balloons【DFS】

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

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

int n, res1, res2;
char map1[N][N], map2[N][N];
void DFS1(int x, int y)
{
    map1[x][y] = '0';
    for(int i = 0; i < 4; ++i)
    {
        int xx = x + dir1[i][0];
        int yy = y + dir1[i][1];
        if(xx < 1 || xx > n || yy < 1 || yy > n)    continue;
        if(map1[xx][yy] == '1')
            DFS1(xx, yy);
    }
}
void DFS2(int x, int y)
{
    map2[x][y] = '0';
    for(int i = 0; i < 8; ++i)
    {
        int xx = x + dir2[i][0];
        int yy = y + dir2[i][1];
        if(xx < 1 || xx > n || yy < 1 || yy > n)    continue;
        if(map2[xx][yy] == '1')
            DFS2(xx, yy);
    }
}
int main()
{
    for(int cas = 1; scanf("%d", &n) && n; ++cas)
    {
        res1 = res2 = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%s", map1[i] + 1);
            for(int j = 1; j <= n; ++j)
            {
                map2[i][j] = map1[i][j];
            }
        }

//        for(int i = 1; i <= n; ++i, puts(""))
//            for(int j = 1; j <= n; ++j)
//                printf("%c", map1[i][j]);
//
//        for(int i = 1; i <= n; ++i, puts(""))
//            for(int j = 1; j <= n; ++j)
//                printf("%c", map2[i][j]);

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(map1[i][j] == '1')
                {
                    DFS1(i, j);
                    ++res1;
                }
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(map2[i][j] == '1')
                {
                    DFS2(i, j);
                    ++res2;
                }
            }
        }
        printf("Case %d: %d %d\n\n", cas, res1, res2);
    }
    return 0;
}

C.Clockwise

D.Shopping【签到】

找出最大值最小值做差就完了。

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

int n;
ll t, maxx, minn;
int main()
{
    while(scanf("%d", &n) && n)
    {
        scanf("%lld", &t);
        maxx = minn = t;
        for(int i = 1; i < n; ++i)
        {
            scanf("%lld", &t);
            maxx = max(maxx, t);
            minn = min(minn, t);
        }
        printf("%lld\n", (maxx - minn) * 2);
    }
    return 0;
}

E.Emergency【最短路】

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf = 0x3f3f3f3f;
int vis[305],dis[305][305];
int m,n,q,te=1;
void init(){
    for(int i=0;i<n;i++){
        vis[i]=0;
        for(int j=0;j<n;j++){
            dis[i][j]=inf;
        }
        dis[i][i]=0;
    }
}
void go(int x){
    //0->n-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dis[i][j]=min(dis[i][j],dis[i][x]+dis[x][j]);
        }
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&q)&&n&&m&&q){
        printf("Case %d:\n",te++);
        init();
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            dis[a][b]=min(dis[a][b],c);
        }
        while(q--){
            int ask,a,b;
            scanf("%d",&ask);
            if(ask==1){
                scanf("%d%d",&a,&b);
                if(vis[a]==0||vis[b]==0){
                    printf("City %d or %d is not available.\n",a,b);
                }
                else{
                    if(dis[a][b]==inf){
                        printf("No such path.\n");
                    }
                    else
                        printf("%d\n",dis[a][b]);
                }
            }
            else{
                scanf("%d",&a);
                if(vis[a]==1){
                    printf("City %d is already recaptured.\n",a);
                }
                else {
                    vis[a]=1;
                    go(a);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

F.Fairy tale

G.Greatest Number【二分】

题意：从n个数中选4个数，它们的和在不超过M的前提下，最大是多少。

思路：将n个数的两两之和保存下来，排序后对每一个b[i]，查找出最接近M - b[i]的数，不断枚举并更新。

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

typedef long long ll;
const int maxn = 1e3+5;

int n, m, cnt;
int ar[maxn];
int br[maxn*maxn];

int main()
{
    int cas = 0;
    while (scanf("%d %d", &n, &m) != EOF && n+m) {
        cnt = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &ar[i]);
        }
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                br[++cnt] = ar[i]+ar[j];
            }
        }
        sort(br+1, br+1+cnt);
        br[cnt+1] = 2e9;
        int ans = 0;
        for (int i = 1; i <= cnt; ++i) {
            int pos = upper_bound(br+1, br+1+cnt, m-br[i])-br;
            if (br[i]+br[pos-1] <= m) {
                ans = max(ans, br[i]+br[pos-1]);
            }
        }
        printf("Case %d: %d\n\n", ++cas, ans);
    }
    return 0;
}

H.Hello World!【结构体排序】

给出n个点，对这n个点的每一个点，找出横纵坐标都比它大的点中的横纵坐标最小的点，没有的话输出-1 -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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

struct node
{
    int aa, bb;
};
bool cmp(node a, node b)
{
    if(a.aa == b.aa) return a.bb < b.bb;
    return a.aa < b.aa;
}
int main()
{
    int n;
    bool flag;
    int cou = 0;
    while(scanf("%d",&n) && n)
    {
        if(cou) puts("");
        printf("Case %d:\n",++cou);
        node p[MAX], q[MAX];
        for(int k = 0; k < n; ++k)
        {
            scanf("%d%d",&p[k].aa,&p[k].bb);
            q[k].aa = p[k].aa;
            q[k].bb = p[k].bb;
        }
        sort(q, q+n, cmp);
        for(int k = 0; k < n; ++k)
        {
            flag = true;
            for(int i = 0; i < n; ++i)
            {
                if(q[i].aa > p[k].aa && q[i].bb > p[k].bb)
                {
                    printf("%d %d\n",q[i].aa,q[i].bb);
                    flag = false;
                    break;
                }
            }
            if(flag) printf("-1 -1\n");
        }
    }
    return 0;
}

I.Ivan comes again!【set】

上一题的加强版。这里将所有点存到一个容器中，通过二分查到第一个横坐标大于他的点，再遍历纵坐标。

如果这题极限数据的话算了下复杂度这样写应该是过不了的，搜了一下有通过线段树维护最大值什么的，有空再学(咕咕咕)。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#define pii pair<int, int>
using namespace std;

char s[11];
int n, x, y, cas;
int main()
{
    while(scanf("%d",&n) && n)
    {
        printf("Case %d:\n", ++cas);
        set<pii> S;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s%d%d", s, &x,&y);
            if(s[0] == 'a')
                S.insert({x, y});
            else if(s[0] == 'r')
                S.erase({x, y});
            else
            {
                auto it = S.upper_bound({x, y});
                while(1)
                {
                    if(it == S.end())
                    {
                        puts("-1");
                        break;
                    }
                    if(it -> first > x && it -> second > y)
                    {
                       printf("%d %d\n", it -> first, it -> second);
                       break;
                    }
                    ++it;
                }
            }
        }
        puts("");
    }
    return 0;
}

J.Jerry Mouse

不可做题。。。

Donate comment here
0%