Celery's Blog

0%

挑战程序设计竞赛-day5

发表于 更新于 Valine：

精度保留

setprecision()

头文件：#include <iomanip>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double a = 3.1415926;
    cout << setprecision(3) << a << endl;           // 3.14
    cout << setprecision(9) << a << endl;           // 3.1415926
    cout << fixed << setprecision(3) << a << endl;  // 3.142
    cout << fixed << setprecision(9) << a << endl;  // 3.141592600

    /**
     * 结论：
     * cout << fixed << setprecision(n) << a << endl;   是保留a的n位小数
     * cout << setprecision(n) << a << endl;            是保留a的n位数
     */
}

POJ 3040： Allowance

http://poj.org/problem?id=3040

题目大意：

作为创纪录的牛奶生产的奖励，农场主约翰决定开始给Bessie奶牛一个小的每周津贴。FJ有一套硬币N种（1≤N≤20）不同的面额，每枚硬币是所有比他小的硬币面值的倍数，例如1美分硬币、5美分硬币、10美分硬币和50美分硬币。使用这些硬币，FJ每周至少给Bessie C（1 <= C <=100000000）美分。请你计算他最多能给Bessie几周

思路：

这里所做的贪心选择就是：

  • 先从大到小取，如果能刚好凑满，则支付
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
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
typedef pair<int, int> P;
P coin[25];
int coin_use[25];   // coin_use[25] 数组表示当前的硬币最多能取几个

int main() {
    int n, c, sum = 0;
    cin >> n >> c;
    for(int i = 0; i < n; i++) {
        cin >> coin[i].first >> coin[i].second;
        // 大于c的直接取
        if(coin[i].first >= c) {
            sum += coin[i].second;
            coin[i].second = 0;
        }
    }
    sort(coin, coin + n, greater<P>()); // 从大到小排列
    while(true) {
        int cost = c;
        int flag = 0;
        memset(coin_use, 0, sizeof(coin_use));
        // 从大到小
        for(int i = 0; i < n; i++) {
            if(coin[i].second) {
                // 计算为了达到金额，每种硬币需要多少个
                coin_use[i] = min(coin[i].second, cost / coin[i].first);
                cost -= coin_use[i] * coin[i].first;
                // 如果能刚好凑满
                if(cost == 0) {
                    flag = 1;
                    break;
                }
            }
        }
        // 如果不能刚好的话，就按照从小到大的顺序，进行补贴
        if(cost > 0) {
            for(int i = n - 1; i >= 0; i--) {
                while(coin[i].second > coin_use[i]) {
                    cost -= coin[i].first;
                    coin_use[i]++;
                    if(cost <= 0) {
                        flag = 1;
                        break;
                    }
                }
                if(flag) {
                    break;
                }
            }
        }
        if(!flag) {
            break;
        }
        // maxn根据需要用的每一种类的硬币然后求解最多能支付多少天
        int maxn = INT_MAX;
        for(int i = 0; i < n; i++) {
            if(coin_use[i]) {
                maxn = min(coin[i].second / coin_use[i], maxn);
            }
        }
        sum += maxn;
        // 更新所有现有的硬币数目
        for(int i = 0; i < n; i++) {
            if(coin_use[i]) {
                coin[i].second -= maxn * coin_use[i];
            }
        }
    }
    cout << sum << endl;
}

POJ 2229 Sumsets

http://poj.org/problem?id=2229

大意：求把一个整数分解为2的幂的和共有几种方案

设dp[i]表示将i拆分成2的幂的和的方案数

当i为奇数时，他只能是在dp[i - 1]即偶数的情况下再加1

当i为偶数的情况下，可以从前一个奇数的情况下再加一个1得到，也可以从i / 2的情况下推导出来

dp[i] = dp[i - 1] + dp[i >> 1], i is oven

dp[i] = dp[i - 1], i is odd

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 <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 1000010;
int n;
ll sumset[N];
void solve() {

}

int main() {
    int maxN = 0;
    sumset[0] = 1;
    while(scanf("%d", &n) != EOF) {
        if(n <= maxN) {
            printf("%lld\n", sumset[n]);
            continue;
        }
        for(int i = maxN + 1; i <= n; i++) {
            if(i & 1) {
                sumset[i] = sumset[i - 1];
            } else {
                sumset[i] = (sumset[i - 1] + sumset[i >> 1]) % 1000000000;
            }
        }
        maxN = n;
        printf("%lld\n", sumset[n]);
    }
}

POJ 2385 Apple Catching

http://poj.org/problem?id=2385

大意：

两棵苹果树每一分会有树落下苹果，有人去接，但是来回两个树之间的次数是一定的，所以求出在最大次数时最多能接到多少苹果。

设dp[i][j]表示第i分钟移动次数为j时，获得的最多的苹果,a[i]表示第i分钟，苹果落在a[i]棵树下。

因为只有两颗苹果树，由于起始位置为苹果树1，所以经过j次之后，到达j % 2 + 1棵数下

所以dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + (j % 2 + 1 == a[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
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_T = 1001, MAX_W = 31;
int T, W;
int dp[MAX_W];
int cnt(int t, int j) {
    return t == (j % 2 + 1) ? 1 : 0; 
}
// dp[i][j] 表示前i个苹果，走j次的最大获得值。可以压缩空间用一位数组即可
// dp[i + 1][j] = max(dp[i][j], dp[i][j - 1]) + (t == (j % 2 + 1) ? 1 : 0)
int main() {
    while(scanf("%d%d", &T, &W) != EOF) {
        for(int i = 0; i < T; i++) {
            int t;
            scanf("%d", &t);
            for(int j = W; j >= 0; j--) {
                if(j == 0) {
                    dp[j] += cnt(t, j);
                } else {
                    dp[j] = max(dp[j - 1], dp[j]) + cnt(t, j);
                }
            }
            int Max = -1;
            for(int j = 0; j <= W; j++) {
                Max = max(Max, dp[j]);
            }
            printf("%d\n", Max);
        }
    }
}

这题是npy教的，😄