2018 Autumn 清北学堂普及刷题班 Day4 题解

十月 04, 2018 8288

没人AC的题目和没人得分的题目

T1. 牛奶

没AC的退役吧

问题描述

为了增加营养，你决定每天喝牛奶，牛奶的营养含量十分固定，下表示牛奶上写的营养成分表。

项目 每100mL
能量 284kJ
蛋白质 3.2g
脂肪 4.0g
碳水化合物 4.8g
钠 62mg
钙 100mg
这天你喝了N mL的牛奶，那么你摄入的营养成分分别为多少呢？

输入格式

一个整数N

输出格式

6个用空格隔开的数字，分别表示6项营养成分的数值，单位和表上单位相同，四舍五入保留一位小数。

输入样例

1
100

输出样例

1
284.0 3.2 4.0 4.8 62.0 100.0

数据范围

对于30%的数据，N是100的倍数。

对于50%的数据，N<=1000。

对于100%的数据，1<=N<=10000。

解析

没什么好说的，浮点数运算而已

这题唯一也是最毒瘤的的坑点就是浮点数运算

代码实现

毒瘤代码

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace Solution {
	const double energy100 = (double) 284; // kJ
	const double protein100 = (double) 3.2; // g
	const double fats100 = (double) 4.0; // g
	const double carbohydrate100 = (double) 4.8; // g
	const double sodium100 = (double) 62; // mg
	const double calcium100 = (double) 100; // mg
}

int main(int argc, char *const argv[]) {
    #ifndef HANDWER_FILE
    freopen("milk.in", "r", stdin);
    freopen("milk.out", "w", stdout);
    #endif
    using namespace Solution;
	double n = 1.0;
	scanf("%lf", &n);
	n *= 1.0;
	double anse = (double) n * (double) energy100 * 1.0;
	double ansp = (double) n * (double) protein100 * 1.0;
	double ansf = (double) n * (double) fats100 * 1.0;
	double ansc = (double) n * (double) carbohydrate100 * 1.0;
	double anss = (double) n * (double) sodium100 * 1.0;
	double ansl = (double) n * (double) calcium100 * 1.0;
	printf("%0.1lf %0.1lf %0.1lf %0.1lf %0.1lf %0.1lf\n", 
	    anse / 100.0, 
		ansp / 100.0, 
		ansf / 100.0, 
		ansc / 100.0, 
		anss / 100.0, 
		ansl / 100.0
	);
	return 0;
}

T2. 上课

问题描述

这天，学校正上着课，学校有n个教室，每个教室坐着 a_i 个人正在上课。

突然来了m个人也要上课，每个人都可以选择n个教室中的任意一个教室上课，由于学校需要提供教室的座位，学校想知道这m个人来之后，最多人的那个教室人数的最小值和最大值分别为多少。

输入格式

第一行两个数n和m，用空格隔开。

第二行n个数字用空格隔开，表示 a_i 。

输出格式

两个用空格隔开的数字，分别表示最小值和最大值

输入样例

1
2
4 6
1 1 1 1

输出样例

1
3 7

数据范围

对于30%的数据，n=1。

对于50%的数据，m<=10000。

对于100%的数据，1<=n,ai<=100,1<=m<=10^9。

解析

我们随便想一想就能想出贪心策略

首先最大值是人最多的班级的人数+m 这没什么好说的

最小值也很好求

既然是最小值，那么就要保证m的平均分配

那么我们排个序，从最小的数字依次 O(n) 扫

对于每个数字 a_i ，计算它和最大值的差，记为 d

当 d\ge m 时，直接输出 d （因为将 m 全部安排到这个班里去也不能让这个班的人数比最大值大，所以答案即是最大值）

否则让 m 减去 d ，将 a_i 赋值为最大值（把这个班的人数变成最大值）

扫完一遍之后，如果 m 变成0了，就直接输出最大值（m个人被正好安排完了）

否则就再把剩下的人一个一个地分别安排到每个班中（可能有一个班分配多人的情况），最后取个max值即可

这里有个小技巧，就是我们把m整除n的结果记为place，然后把整个序列都加上place，表示每个班都还要分配place个人

再把m模n的结果记为 lm，循环把这最后lm个人分别分配到每个班中，最后取max即可

讲起来还是挺麻烦的

代码实现

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
	const int MAXN = 100;
	
	int n, m;
	int seq[MAXN];
	
	bool stlCmp(int x, int y) { return x > y; }
	
	void PrintAnswer(int maxAns, int minAns) {
		FastIO::putint(minAns, ' ');
		FastIO::putint(maxAns, '\n');
	} 
}

int main(int argc, char *const argv[]) {
	// Wrong Algorithm
    #ifndef HANDWER_FILE
    freopen("class.in", "r", stdin);
    freopen("class.out", "w", stdout);
    #endif
    using namespace Solution;
	using namespace FastIO;
	n = getint(), m = getint();
	int maxSiz = -233333;
	For (i, 1, n) {
		seq[i] = getint();
		maxSiz = std::max(seq[i], maxSiz);
	}
	
	sort(seq + 1, seq + 1 + n);
	int maxAns = m + seq[n];
	
	For (i, 1, n) {
		int differ = maxSiz - seq[i];
		if (differ >= m) {
			PrintAnswer(maxAns, maxSiz);
			return 0;
		}
		seq[i] = maxSiz;
		m -= differ;
	}
	if (m == 0) {
		PrintAnswer(maxAns, maxSiz);
		return 0;
	}
	/*/
	sort(seq + 1, seq + 1 + n, stlCmp);
	long long int maxAns = m + seq[n];
	long long int minAns = 0;
	/*/
	/*/
	int j = n;
	For (i, 1, m) {
		++seq[j--];
		if (j == 0) j = n;
	}
	/*/
	
	int place = m / n;
	For (i, 1, n) seq[i] += place;
	int mod = m % n;
	int i = n;
	while (mod --> 0) {
		++seq[i--];
	}
	
	int minAns = *(max_element(seq + 1, seq + 1 + n));
	PrintAnswer(maxAns, minAns);
	return 0;
}


T3. 维生素

问题描述

商店里卖着n种果汁，每种果汁都有它的价格ci，每种果汁有一些维生素，维生素有三种类型，维生素A，维生素B，维生素C，每种果汁可以含有其中一种或多种维生素。

你需要3种维生素来保持身体健康，那么你最少需要购买多少价格的果汁才能保证购买的这些果汁包含3种维生素呢？

输入格式

第一行包含一个整数n。

接下来n行，每行包含一个整数ci和一个字符串si，si表示其中蕴含的维生素种类，只包含字母ABC且每个字母最多出现一次。

输出格式

输出最小能满足条件的价格，如果不能满足，输出-1。

输入样例

1
2
3
4
5
4
5 C
6 B
16 BAC
4 A

输出样例

1
15

数据范围

对于30%的数据，1<=n<=20。

对于另外20%的数据，所有果汁只包含单种维生素。

对于100%的数据，1<=n<=1000, 1<=ci<=100000。

解析

DP

我们设 f_{i,j} 表示前i种果汁状态为j时的价格，其中

j 的值 代表意思
1 含有维生素A
2 含有维生素B
3 含有维生素C
4 含有维生素AB
5 含有维生素BC
6 含有维生素AC
7 含有维生素ABC

转移方程：

`a[i|w] = min(a[i|w], a[i] + c[i])`
`w = w | (1 左移 (str[i] - 'A'))`，其中`1 ≤ i ≤ str.length()`
## 代码实现 
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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>
using namespace std;

/*  Constants Start  */

/*  Constants End  */

/*  Variants Start  */

/*  Variants End  */

namespace FastIO {
	void DEBUG(char comment[], int x) {
		cerr << comment << x << endl;
	}

	inline int getint() {
		int s = 0, x = 1;
		char ch = getchar();
		while (!isdigit(ch)) {
			if (ch == '-') x = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			s = s * 10 + ch - '0';
			ch = getchar();
		}
		return s * x;
	}
	inline void __basic_putint(int x) {
		if (x < 0) {
			x = -x;
			putchar('-');
		}
		if (x >= 10) __basic_putint(x / 10);
		putchar(x % 10 + '0');
	}

	inline void putint(int x, char external) {
		__basic_putint(x);
		putchar(external);
	}
}

int main(int argc, char *const argv[]) {
	#ifndef HANDWER_FILE
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
	#endif
	int n;
	cin >> n;
	int t[8 + 2];
	for (int i = 0; i <= 8; ++i) t[i] = 60;
	t[0] = 0;
	string s;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		cin >> s;
		int len = s.length();
		int v = 0;
		for (int j = 1; j <= len; ++j) v |= (1 << s[j-1] - 'A');
		for (int j = 0; j < 8; ++j) t[j | v] = std::min(t[j | v], t[j] + x);
	} 
	if (t[7] > 1e8) puts("-1");
	else cout << t[7] << endl;
	return 0;
}

# T4. 队列 ~~挖坑待填~~