暑假集训-合训第三场

 　　A

　　　　题意：有C类课程，每类课程有T个班，不同的班在不同位置，上不同的班有不同的花费，初始位置是0，末位置L，求最小花费。

　　　　比较简单的递推，f[i][j]表示上i类课的j个班所需的最小花费。最后求f[c]中的最小值就可以了。

　　　　

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 //#define OPEN_FILE
18 using namespace std;
19 int T, c, t, L;
20 struct Node{
21     int pos, v;
22 }p[30][1005];
23 int f[30][1005];
24 int main()
25 {
26 #ifdef OPEN_FILE
27     freopen("in.txt", "r", stdin);
28     //freopen("out.txt", "w", stdout);
29 #endif // OPEN_FILE
30     scanf("%d", &T);
31     for (int cas = 1; cas <= T; cas++){
32         scanf("%d%d%d", &c, &t, &L);
33         for (int i = 1; i <= c; i++){
34             for (int j = 1; j <= t; j++){
35                 scanf("%d%d", &p[i][j].pos, &p[i][j].v);
36             }
37         }
38         memset(f, INF, sizeof(f));
39         for (int i = 1; i <= t; i++){
40             f[1][i] = p[1][i].pos + p[1][i].v;
41         }
42         for (int i = 2; i <= c; i++){
43             for (int j = 1; j <= t; j++){
44                 for (int k = 1; k <= t; k++){
45                     int dis = abs(p[i - 1][k].pos - p[i][j].pos);
46                     f[i][j] = min(f[i][j], f[i - 1][k] + dis + p[i][j].v);
47                 }
48             }
49         }
50         int ans = INF;
51         for (int i = 1; i <= t; i++){
52             int dis = abs(p[c][i].pos - L);
53             ans = min(ans, f[c][i] + dis);
54         }
55         printf("%d
", ans);
56     }
57 }
View Code

　　B

　　　　题意:给你一个长度为n的数列，循环起来相当于n个数列，求这n个数列里所有前缀和都非负的有多少

　　　　单调队列。

　　　　

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 //#define OPEN_FILE
18 #define MAXN 2000005
19 using namespace std;
20 int n;
21 int a[MAXN], Q[MAXN];
22 LL sum[MAXN];
23 int main()
24 {
25 #ifdef OPEN_FILE
26     freopen("in.txt", "r", stdin);
27     //freopen("out.txt", "w", stdout);
28 #endif // OPEN_FILE
29     while (~scanf("%d", &n)){    
30         if (n == 0) break;
31         memset(a, 0, sizeof(a));
32         memset(sum, 0, sizeof(sum));
33         for (int i = 1; i <= n; i++){
34             scanf("%d", &a[i]);
35             a[i + n] = a[i];
36         }
37         for (int i = 1; i <= 2 * n; i++){
38             sum[i] = sum[i - 1] + a[i];
39         }
40         int head = 0, tail = 0;
41         int ans = 0;
42         for (int i = 1; i <= 2 * n; i++){
43             //keep queue's order
44             while (head < tail && sum[Q[tail - 1]] >= sum[i]){
45                 tail--;
46             }
47             Q[tail++] = i;
48             if (i > n && sum[Q[head]] - sum[i - n] >= 0) {
49                 ans++;
50             }
51             //keep n numbers in queue
52             while (head < tail && i - Q[head] >= n){
53                 head++;
54             }
55         }
56         printf("%d
", ans);
57     }
58 }
View Code

　　C

　　　　题意：coming soon

　　D

　　　　题意：给你一个坐标表示你的初始位置，再给你一些直线，问沿着这些线最远能离初始位置多远。

　　E

　　　　题意：给你一棵树，边的权值在[0,L]中随机，求使树的总权值不超过S的概率

　　F

　　　　题意：coming soon

　　G

　　　　题意：给你n表示置换循环的长度，K表示1在这个循环置换中的对应最大值，问形成这种置换的排列数。

　　H

　　　　题意：给你一棵树，边由两个公司组成，问使的正好有K条A公司的边的最小生成树的花费。

　　I

　　　　题意：袋子里有N个球，每个球是蓝色或者是红色，取出来P个球里面有Q个红球，问再拿出一个球来是红球的概率

　　J

　　　　题意：A有N张牌，B有M张牌，一张牌能盖住另一张牌的条件是height和width都不比另一张牌小，为A最多能盖住B多少张牌。

　　K

　　　　题意：从小到大给你汉诺塔中盘子位于哪个柱子，问全部移到B柱上要多少步。

　　　　work（a,b,t)表示把第t个盘从a移到b，如果t-1号盘在a，那就只要把这t-1个盘移到另外一个盘，再把t移到b，再把t-1个放好的盘移到b，后面的这个过程是标准的汉娜塔就直接可以得到步数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define OPEN_FILE
18 using namespace std;
19 const char CH[3] = { 'A', 'B', 'C' };
20 LL ans;
21 char s[70];
22 LL POW(int p){
23     LL res = 1;
24     for (int i = 1; i <= p; i++){
25         res *= 2;
26     }
27     return res;
28 }
29 void work(char a, char b, LL m){
30     if (m == 0){
31         return;
32     }
33     int i;
34     for (i = 0; i < 3; i++){
35         if (a != CH[i] && b != CH[i]) break;
36     }
37     if (s[m - 1] == a){
38         ans += POW(m - 1);
39         work(a, CH[i], m - 1);
40     }
41     else if (s[m - 1] == b){
42         work(CH[i], b, m - 1);
43     }
44     else{
45         ans += POW(m - 1);
46         work(CH[i], a, m - 1);
47     }
48 }
49 
50 int main()
51 {
52 #ifdef OPEN_FILE
53     //freopen("in.txt", "r", stdin);
54     //freopen("out.txt", "w", stdout);
55 #endif // OPEN_FILE
56     while (~scanf("%s", s)){
57         if (s[0] == 'X') break;
58         ans = 0;
59         work('A', 'B', strlen(s));
60         printf("%I64d
", ans);
61     }
62 
63 }
View Code

　　L

　　　　题意：有M升水到倒给2N个人，N个男生，N个女生，男生杯子里的水必须是女生的两倍，男生之间和女生之间的水必须一样，问最多倒出多少升。

　　　　比较简单的贪心。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define OPEN_FILE
18 using namespace std;
19 int n;
20 double w;
21 double a[200005];
22 int main()
23 {
24 #ifdef OPEN_FILE
25     //freopen("in.txt", "r", stdin);
26 //    freopen("out.txt", "w", stdout);
27 #endif // OPEN_FILE
28     scanf("%d%lf", &n, &w);
29     for (int i = 1; i <= 2 * n; i++){
30         scanf("%lf", &a[i]);
31     }
32     sort(a + 1, a + 2 * n + 1);
33     double ans = 0;
34     if (a[n + 1] > a[1] * 2){
35         if (a[1] * n * 3 <= w){
36             ans = a[1] * n * 3;
37         }
38         else{
39             ans = w;
40         }
41     }
42     else{
43         if (a[n + 1] * n * 1.5 <= w){
44             ans = a[n + 1] * n * 1.5;
45         }
46         else{
47             ans = w;
48         }
49     }
50     printf("%.6lf
", ans);
51 
52 }
View Code

　　　　

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/macinchang/p/4678259.html