SDNU_ACM_ICPC_2019_Winter_Practice_3rd题解报告

这篇文章是关于SDNU_ACM_ICPC_2019_Winter_Practice_3rd的题解.

第三场对于当时二分不熟练，，拓扑未习得的我来说，，有点不友好啊，，好多题只能干看着，，寒假还真没多扩展几种算法，，，，刘大爷和bin佬专题也没推进多少，，再不推进来不及了啊，，先写题解系列放松一下；

题解系列续航中；

A - Replace To Make Regular Bracket Sequence

CodeForces - 612C

题意：给出包含<,>, {,}, [ , ], (,)的序列， 你能把左括号换成其他类型的左括号，把右括号换成其他的右括号，问你让这个序列中括号完全配对至少需要多少次操作；

题解：一个左括号必然和一个右括号配对，且遇到右括号就和最近的未配对左括号配对，就想到栈的结构，把遇到的左括号一个个压入栈里面，遇到右括号就放出一个，如果能配对就跳过，如果不能配对步骤就加一，当栈为空时遇到了右括号，那么必不可能配对成功

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

int main()
{
    char r = '<', b = '{', s = '[', t = '(';
    map<char, char>m;
    m['>'] = r, m['}'] = b, m[']'] = s, m[')'] = t;
    string rbs;
    cin>> rbs;
    int le = rbs.length();
    int ll = 0;
    int ans = 0;
    stack<char>ss;
    while(ll < le){
        if(rbs[ll] == r || rbs[ll] == b || rbs[ll] == s || rbs[ll] == t)
            ss.push(rbs[ll]);
        else if(!ss.empty()){
                if(ss.top() != m[rbs[ll]])++ans;
                ss.pop();
        }
        else {
            cout<< "Impossible\n";
            return 0;
        }
        ll++;
    }

    if(ss.empty())cout<< ans << '\n';
    else cout<< "Impossible\n";

    return 0;
}

B - Pearls in a Row

CodeForces - 620C

题意：给你一个有n个元素的序列，定义当序列中出现两个相同数字时为一个好序列，问你这个序列能分成多少个好序列，并输出每个好序列的头和尾的下标；

题解：用map判断输入的数字是否出现过，如果出现过就存下这个序列的尾和下个序列的头，如果没有存入就输出-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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;

int ans[300100];

int main()
{
    int n;
    while(~scanf("%d", &n)){
        map<int, int>m;
        int pos = 0;
        ans[pos++] = 1;
        for(int i = 0; i < n; i++){
            int t;
            scanf("%d", &t);
            if(m[t]){
                ans[pos++] = i + 1;
                ans[pos++] = i + 2;
                m.clear();
            }
            else m[t] = 1;
        }
        if(pos == 1)printf("-1\n");
        else printf("%d\n", (pos - 1) / 2);
        ans[pos - 2 ] = n;
        for(int i = 0; i < pos - 1; i += 2, putchar('\n')){
             printf("%d %d", ans[i], ans[i + 1]);
        }
    }


    return 0;
}

C - 排列2

HDU - 1716

题意：给你四个数，要你从小到大把能形成的四位数全部输出，千位一样在同一行

题解：模拟，输出

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

int out(int s, int er, int sa, int si)
{
    return s * 1000 + er * 100 + sa * 10 + si;
}

void sc(int s, int er, int sa, int si)
{
    if(s == 0)return;
    int sss[7];
    sss[6] = -1;
    sss[0] = out(s, er, sa, si);
    sss[1] = out(s, er, si, sa);
    sss[2] = out(s, sa, er, si);
    sss[3] = out(s, sa, si, er);
    sss[4] = out(s, si, er, sa);
    sss[5] = out(s, si, sa, er);
    sort(sss, sss + 5);
    bool scc = false;
    for(int i = 0; i < 6; i++){
        if(sss[i] != sss[i + 1]){
            if(scc)putchar(' ');
            cout<< sss[i];
            if(!scc)scc = true;
        }
    }
    if(scc)putchar('\n');
}


int main()
{
    bool chu = false;
    int num[4];
    while(~scanf("%d%d%d%d", &num[0], &num[1], &num[2], &num[3])){
        if(num[0] == 0 && num[1] == 0 && num[2] == 0 && num[3] == 0)break;
        if(chu)putchar('\n');
        sort(num, num + 4);
        sc(num[0], num[1], num[2], num[3]);
        if(num[1] != num[0])sc(num[1], num[0], num[2], num[3]);
        if(num[2] != num[1])sc(num[2], num[0], num[1], num[3]);
        if(num[3] != num[2])sc(num[3], num[0], num[1], num[2]);
        if(!chu)chu = true;
    }

    return 0;
}

D - Can you find it?

HDU - 2141

题意：分别从长度为l, n, m的序列中找一个数的和能否得到s

题解：读入三个序列后，用另外一个数组来存前两个数组和的各种可能，我第一次用map来存答案是否存在，但mle了，每次查询也会在map里面留下东西，用数组直接存答案，再排序后用lower_bound查s - c序列的数是否在a+b的序列里面，之后a了；看muyu_的博客时学到了解引用lower_bound的骚操作，是真的骚；

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

const int Ma = 550;
int L[3][Ma];
int sum[Ma * Ma];

int main()
{
    int l[3];
    int ca = 0;
    while(~scanf("%d%d%d", &l[0], &l[1], &l[2])){
    printf("Case %d:\n", ++ca);
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < l[i]; j++)
            scanf("%d", &L[i][j]);

    int q = 0;
    for(int i = 0; i < l[0]; i++)
        for(int j = 0; j < l[1]; j++)
            sum[q++] = L[0][i] + L[1][j];

    sort(sum, sum + q);

    int T;
    scanf("%d", &T);
    while(T--){
        int s;
        scanf("%d", &s);
        for(int i = 0; i < l[2]; i++)
        if(*lower_bound(sum, sum + q, s - L[2][i]) == s - L[2][i]){
                puts("YES");
                goto wh;
        }
        puts("NO");
    wh:
        ;
    }
    }

    return 0;
}

E - Legal or Not

HDU - 3342

题意：给出n个人中的m个人际关系，要求不能a是b上级，b是a上级的矛盾

题解：判断是否存在拓扑序列

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

const int N = 110;
int ru[110];
int chu[110];
vector<int>nu[110];

bool add(int a, int b)
{
    nu[a].push_back(b), chu[a]++, ru[b]++;
    return false;
}

void fin(int n)
{
    bool zg = true;
    for(int i = 0; i < n; i++){
        if(ru[i] == 0){
            zg = false;
            ru[i]--;
            for(int j = 0; j < chu[i]; j++){
                ru[ nu[i][j] ]--;
            }
        }
    }

    if(zg){
        int i;
        for(i = 0; i < n && ru[i] == -1; i++);
        if(i == n)puts("YES");
        else puts("NO");
    }
    else fin(n);
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m) && n != 0){
        memset(ru, 0, sizeof(ru));
        memset(chu, 0, sizeof(chu));
        for(int i = 0; i < 102; i++)
        nu[i].clear();
        for(int i = 0; i< m; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
        }
        fin(n);
    }

    return 0;
}

F - Ignatius and the Princess IV

HDU - 1029

题意：找到序列中出现(n + 1) / 2次的数字

题解：直接找

G - Can you solve this equation?

HDU - 2199

题意：在8x^4 + 7x^3 + 2x^2 + 3x + 6 == Y中给你y，问你能否找到x

题解：这题给了0到100，明明白白的二分

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

const double MINN = 1e-6;
double Y;

double judge(double n)
{
    return 8*n*n*n*n + 7*n*n*n + 2*n*n + 3*n + 6.0;
}

bool judje(double n)
{
    return judge(n) > Y ? true : false;
}

int main()
{
    int T;
    while(~scanf("%d", &T)){
        while(T--){
            scanf("%lf", &Y);
            if(judge(0) - Y > MINN || Y - judge(100.0) > MINN){
                printf("No solution!\n");
                continue;
            }
            double l = 0, r = 100.0;
            while(r - l > MINN){
                double mid = (l + r) / 2;
                if(judje(mid))r = mid;
                else l = mid;
            }

            printf("%.4f\n", r);

        }
    }

    return 0;
}

H - Ordering Tasks

UVA - 10305

题意：给出n件事的m个关系，先做a才能做b，要求输出做事的顺序

题解：拓扑排序，把e题的代码改改就好

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

const int N = 110;
int ru[N];
int chu[N];
bool vis[N];
vector<int>nu[110];
vector<int>ans;
vector<int>::iterator it;

bool add(int a, int b)
{
    nu[a].push_back(b), chu[a]++, ru[b]++;
    return false;
}

void fin(int n)
{
    vis[n] = false;
    for(int i = 0; i < chu[n]; i++)
        if(vis[ nu[n][i] ])fin(nu[n][i]);
    it = ans.begin();
    ans.insert(it, n);
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m) && n != 0){
        memset(ru, 0, sizeof(ru));
        memset(chu, 0, sizeof(chu));
        memset(vis, 1, sizeof(vis));
        for(int i = 0; i < 102; i++)
        nu[i].clear();
        ans.clear();
        for(int i = 0; i< m; i++){
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
        }
        for(int i = 1; i <= n; i++)
        if(vis[i])fin(i);

        for(int i : ans)
            if(i == ans[0])printf("%d", i);
            else printf(" %d", i);
        putchar('\n');
    }

    return 0;
}

I - I Can Guess the Data Structure!

UVA - 11995

题意：给你一堆输入输出数据，1表示输入数据到容器中，2表示从容器中输出数据，让你猜是哪种数据结构

题解：模拟，看输出输入的数据来判断，注意防re，在pop前一定要判断

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

int main()
{
    int n;
    while(~scanf("%d", &n)){
        queue<int>q;
        priority_queue<int>pq;
        stack<int>s;
        int a, b;
        bool qq = true, ss = true, pp = true;
        while(n--){
        scanf("%d%d", &a, &b);

        if(a == 1){
            q.push(b), pq.push(b), s.push(b);
        }
        else{
            if(q.empty())qq = false, ss = false, pp = false;
            else{
            if(q.front() != b)qq = false;
            if(s.top() != b)ss = false;
            if(pq.top() != b)pp = false;
            q.pop(), s.pop(), pq.pop();
            }
        }
        }
        int sum = qq + ss + pp;
        if(!qq && !ss && !pp)cout<< "impossible\n";
        else if(sum == 1){
            if(qq)cout<< "queue\n";
            else if(ss)cout<< "stack\n";
            else if(pp)cout<< "priority queue\n";
        }
        else cout<< "not sure\n";
    }

    return 0;
}

J - 4 Values whose Sum is 0

UVA - 1152

题意：t个测试数据，输入n个ai,bi,ci,di，问你在a, b, c, d序列中有多少个ai + bi + ci + di = 0；

题解： 和d题类似，把前两个序列作为一组看所有可能结果，后两个一组存所有结果， 再排序，用lower_bound二分查找即可，注意是判断相加是否为0， 还有可能出现cd中有好几个数都能和ab中配对的情况；

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

typedef long long ll;

const int Ma = 4200;
ll A[Ma], B[Ma], C[Ma], D[Ma];
ll ab[Ma * Ma], cd[Ma * Ma];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%lld%lld%lld%lld", &A[i], &B[i], &C[i], &D[i]);
        int tot = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                ab[tot] = A[i] + B[j], cd[tot++] = C[i] + D[j];
        sort(ab, ab + tot), sort(cd, cd + tot);
        ll ans = 0;
        ll *it;
        for(int i = 0; i < tot; i++)
            if(*(it = lower_bound(cd, cd + tot, -ab[i])) + ab[i] == 0 && it < cd + tot){
                ll tem = 1;
                while(*it == *(++it) && it != cd + tot)
                    ++tem;
                ans += tem;
            }
        printf("%lld\n", ans);
        if(T != 0)putchar('\n');
    }

    return 0;
}

Comments

⬆︎TOP