0%

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

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

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

4

Problem A 白学姐选妃I

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

int main() {
    int n, k;
    cin >> n >> k;
    int x, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x > k)ans++;
    }
    cout << ans << endl;
    return 0;
}

Problem B 白学姐选妃II

从小到大排序，优先选取分数低的

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

const int N = 100 + 10;
int a[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);
    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (sum <= k)cnt++;
        else break;
    }
    cout << cnt << endl;
    return 0;
}

Problem C 白学姐选妃III

dfs搜索出所有可能的和，插入一个unordered_set中，自动去重，最后答案为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
#include<bits/stdc++.h>
using namespace std;

const int N = 20 + 5;
int n, a[N];
unordered_set<int> s;

void dfs(int i, int sum) {
    if (i == n) {
        s.insert(sum);
        return;
    }
    dfs(i + 1, sum);
    dfs(i + 1, sum + a[i]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dfs(0, 0);
    cout << s.size() << endl;
    return 0;
}

Problem D 白学姐选妃IV

奇数由奇数个奇数和任意个偶数组成，统计奇数和偶数个数，答案为从所有奇数中选取奇数个数的方案数乘从所有偶数中选取任意个数的方案数，化简得到2的n-1次方，需要用快速幂。还要特判奇数个数为0时答案为0

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;

typedef long long LL;
const LL mod = 1000000007;

LL mod_pow(LL x, LL n) {
    LL res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    int n, m, x;
    bool f = false;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x;
        if (x & 1)f = true;
    }
    cout << (f ? mod_pow(2, n - 1) : 0) << endl;
    return 0;
}

5

Problem A 友好的阶乘

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

int main() {

    int n;
    cin >> n;
    int res = 1;
    for(int i = 2; i <= n; i++) res *= i;
    cout << res << endl;

    return 0;
}

Problem B 白学姐的烦恼

用一个桶标记出现的字符即可，塞进一个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
#include <bits/stdc++.h>
using namespace std;

char s[1005];
bool book[26];
int res;

int main() {

    cin >> s;
    for(int i = 0; i < strlen(s); i++) book[s[i] - 'a'] = true;
    for(int i = 0; i < 26; i++) res += book[i];
    cout << res << endl;

    return 0;
} 

#include <bits/stdc++.h>
using namespace std;

int main() {

    set<char> a;
    char c;
    while(cin >> c) a.insert(c);
    cout << a.size() << endl;
    return 0;
}

Problem C 青年歌手大赛

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

int a[100], n;
double res;

int main() {

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        res += a[i]; 
    } 
    res -= *max_element(a, a + n) + *min_element(a, a + n);
    printf("%.2f\n", res / (n - 2));

    return 0;
}

Problem D 相同后三位

p的所有幂指数打表，二重循环直接判断后三位是否相等即可。如果会快速幂的话就不用打表，直接暴力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000;
int a[10005], p;

int main() {

    cin >> p;
    a[1] = p % mod;
    for (int i = 2, t; ; i++) {
        a[i] = a[i - 1] * p % mod;
        t = i;
        while (--t) {
            if (a[t] == a[i]) {
                cout << i << " " << t << endl;
                return 0;
            }
        }
    }

    return 0;
}
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
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000;
int p;

int mod_pow(int x, int n) {

    int res = 1;
    while(n) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
int main() {

    cin >> p;
    for(int i = 2; ; i++)
        for(int j = 1; j < i; j++) {
            if(mod_pow(p,i) == mod_pow(p,j)) {
                cout << i << ' ' << j << endl;
                return 0;
            }
        }

    return 0;
}

6

Problem A 可爱的白学姐

输出 n^2 遍 "Bai is a lovely girl."，即可

1
2
3
4
5
6
7
8
#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n); n = n * n;
    while (n--) {
        puts("Bai is a lovely girl.");
    }
}

Problem B 善良的白学姐

利用C++ STL 中的 set 可以直接判断出结果。

也可以使用一个数组作为桶记录出现过的数字，然后统计一下总个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
const int maxn = int(1e4);
set<int> S;
int a[maxn]; 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        S.insert(a[i]);
    }
    cout << S.size() << endl;
}

Problem C 优秀的白学姐

能够得到一个递推式：

基础条件：dp(1) = 1

如果 i 是奇数：dp(i) = dp(i-1)

如果 i 是偶数：dp(i) = dp(i-1) + dp(i/2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int mod = int(1e8);
const int maxn = int(1e3) + 5;
int dp[maxn];
int main() {
    int n;
    scanf("%d", &n);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i-1] + 
            (i % 2 == 0 ? dp[i/2] : 0)) % mod;
    }
    cout << dp[n] << endl;
    return 0;
}

Problem D 美丽的白学姐

如果在第 i 个房间，那么编号一定大于前 i-1 个房间的人数总和，并且小于 前 i 个房间的人数总和。 求一下前 n 项的和，sum[i] 一定单调递增，可以利用二分查找找到符合条件的房间号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = int32_t(2e5);
int a[maxn], b[maxn], sum[maxn];
int32_t main() {
    int n, m, c;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum[i+1] = a[i] + sum[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> c;
        auto p = lower_bound(sum, sum + n + 1, c) - 1;
        auto id = p - sum + 1;
        cout << id << " " << (c - *p) << endl;
    }
}