0%

CCZU ACM 算法设计课 期末考试 1 参考答案

发表于 更新于 分类于 Disqus：
CCZU ACM 算法设计课 期末考试 1 参考答案

CCZU ACM 算法设计课 期末考试 1 参考答案

1卷

出题人觉得用python可以更优雅地表现算法

A

1
2
3
4
5
6
7
8
9
n, m = map(int, input().split())

ans = list(map(int, input().split()))

st = set(map(int, input().split()))

for i in ans:
    if i in st:
        print(i, end=' ')

B

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
from collections import defaultdict
import heapq

def find(x):
    return x[0]

n, m = map(int, input().split())
ans = defaultdict(int)
heap = []

power = list(map(int, input().split()))
coins = list(map(int, input().split()))
num = list(i for i in range(n+1))

knt = list(zip(power, coins, num))

knt.sort(key=find)

Sum = 0

for i in knt:
    ans[i[2]] = i[1] + Sum
    heapq.heappush(heap, i[1])
    Sum += i[1]
    if len(heap) > m:
        Sum -= heapq.heappop(heap)

for i in range(n):
    print(ans[i], end=' ')

C

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

set<string> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n;
    string a;

    cin >> n;
    int book[26] = {};
    while(n --) {
        string tmp = "";
        memset(book, 0, sizeof(book));

        cin >> a;
        for(auto& i: a) book[i-'a'] = 1;
        for(int i = 0; i < 26; i++)
            tmp += to_string(book[i]);
        s.insert(tmp);
    }

    cout << s.size() << endl;
    return 0;
}

D

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;

int main() {
    int n, w;
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> w;
    vector<int> v;
    v.resize(n);

    for(int i = 0; i < n; i++) cin >> v[i];

    int cnt = 0;
    int Max = -w-1;
    int Min = w+1;
    for(auto& i: v) {
        cnt += i;
        if(cnt < -w or cnt > w) {
            cout << 0 << endl;
            return 0;
        }

        Max = max(Max, cnt);
        Min = min(Min, cnt);
    }
//    cout << Max << " " << Min << endl;
    int r = (Max) > 0 ? (w - Max) : w;
    int l = (Min) < 0 ? abs(Min) : 0;

    if(l > r) cout << 0 << endl;
    else cout << r - l + 1 << endl;

    return 0;
}

2卷

A

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int s = n % 60;
    int m = (n / 60) % 60;
    int h = n / 3600;
    printf("%d:%d:%d\n", h, m, s);
}

B

原样输出，不要被浮点数迷惑了

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    cout << s;
}

C

先找到较小的那个质数因子，然后就能直接求出较大的那个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

inline bool isprime(int n) {
    int sq = sqrt(n);
    for (int i = 2; i <= sq; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 2; i < n; i++)
        if (n % i == 0 && isprime(i)) {
            cout << n / i << endl;
            return 0;
        }
}

D

对于每一个重复的数字，用它和序列中的最大值求和，保留新求出的和，删掉那个重复数字。因为是和最大值求和，一定不会于序列中已有的元素重复，并且这个新求出来的和将成为下次操作用到的最大值。因此每个重复的数字都能用一次操作去掉，还不会产生副作用，题目就是求有多少重复数字。

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    cout << a.end() - unique(a.begin(), a.end()) << endl;
}

3卷

A

数据范围只有无符号64位整数才能放下

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned long long t,maxn=0;
    while (cin >> t)
        maxn=max(maxn,t);
    cout << maxn << endl;
}

B

两数之积除以最大公约数即可 最大公约数用辗转相除法或者调用内置函数求解

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a / __gcd(a, b) * b << endl;
}

C

手动逐个字符检查计数也可以，没什么技术含量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

const char delim[] = " ~!@#$%^&*()_+`-=[]\\{}';':\",./<>?\n";

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    char *p = strtok(s, delim);
    int cnt = 0;
    while (p) {
        cnt++;
        cout << p << endl;
        p = strtok(0, delim);
    }
    cout << cnt << endl;
}

D

化简成ax=b的形式 遇到非数字就提交刚才的数字到a或者b上

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

int main() {
    string eq;
    getline(cin, eq);
    // ax=b
    double a = 0, b = 0;
    int sign = 1, sign2 = 1;
    string buf;
    char unknown;
    for (auto p = eq.begin(); p <= eq.end(); ++p) {
        if (!isdigit(*p)) {
            int cmt = atoi(buf.c_str());
            if (buf.size() == 0 && isalpha(*p)) cmt = 1;
            cmt *= sign * sign2;
            buf.clear();

            if (isalpha(*p)) {
                unknown = *p;
                a += cmt;
            } else {
                b -= cmt;
                if (*p == '+') sign = 1;
                else if (*p == '-') sign = -1;
                else if (*p == '=') sign = 1, sign2 = -1;
            }
        } else {
            buf.push_back(*p);
        }
    }
    double res = b / a;
    if (res == 0) res = 0;
    printf("%c=%.3f\n", unknown, res);
}