2019 HZNU Winter Training Day 13 Comprehensive Training

A.Jongmah   CodeForces-1110D

  题意:你在玩一个数字游戏,有一堆写在瓦片上的数字,希望你能组成最多的三元组(三个数字相同,或顺子)。

  这题用到的方法是动态规划.f[i][j][k]表示为i的数字中,属于组成三个连续数字三元组的开头的有k 个,属于组成三个连续数字的三元组的中间的有j个,由于连续三个的数字组成三元组的数量不会大于等于三个,如果大于等于的话就是不会更优的,那么转移方程为:

    f[i+1][j][k]=max(f[i+1][j][k],f[i][k][l]+l+(a[i]−(j+k+l))/3)

  a[i] 表示i 这个数字的出现次数,最后f[m][0][0]就是答案。

  代码:

2019 HZNU Winter Training Day 13 Comprehensive Training
 1 /*
 2  I have a dream!A AC deram!!
 3  orz orz orz orz orz orz orz orz orz orz orz
 4  orz orz orz orz orz orz orz orz orz orz orz
 5  orz orz orz orz orz orz orz orz orz orz orz
 6 
 7  */
 8 
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cstring>
13 #include<cmath>
14 #include<string>
15 #include<algorithm>
16 #include<vector>
17 #include<queue>
18 #include<set>
19 #include<stack>
20 #include<map>
21 using namespace std;
22 typedef long long ll;
23 const int maxn = 1e6 + 5;
24 const int N = 105;
25 ll f[maxn][3][3], a[maxn];
26 inline int read() 
27 {
28     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar())if (ch == '-')f = -1;
29     for (; isdigit(ch); ch = getchar())x = x * 10 + ch - '0'; return x * f;
30 }
31 
32 int main() 
33 {
34     int n=read(), m=read();
35     for (int i = 1; i <= n; i++)
36         a[read()]++;
37     memset(f, -0x3f, sizeof(f));
38     f[0][0][0] = 0;
39     for (int i = 1; i <= m; i++)
40         for (int x = 0; x < 3; x++)
41             for(int y = 0; y<3; y++)
42                 for (int z = 0; z < 3; z++)
43                 {
44                     if (a[i] < x + y + z)
45                         continue;
46                     f[i][x][y] = max(f[i][x][y], f[i - 1][z][x] + (a[i] - x - y - z) / 3 + z);
47                 }
48     printf("%lld\n", f[m][0][0]);
49     //system("pause");
50     return 0;
51 }
View Code

 

B.Ball   CodeForces-12D

  题意:一群女士来到国王的宫殿参加聚会,每位女士都拥有三个属性值:美貌,财富和智慧。当出现一位A女士的每个属性值严格大于另一位B女士的时候,B女士就会跳窗,即满足如下等式:Bi < Bj, Ii < Ij, Ri < Rj  。

  方法:线段树降维。

  代码:

 

C.Robot   Gym-101915G

  题意:机器人在树上进行比赛,一棵树拥有n个结点和n-1条边,每条边拥有权重Wi。每个机器人有一个能力值Xi,只有当Xi>Wi的时候,机器人才能通过这条路径。

     当然,如果出现几条路径都可以通过的时候,机器人会选择较大的一条路径。

        最后求的是每个机器人最后到达的结点的和。

  方法:贪心。

  代码:

 

D.String of CCPC ZOJ-3985

  题意:在一串字符串中数有几个CCPC,一个CCPC具有一个价值,你也可以购买C和P,第i次购买会花费i-1个价值。所以最好的情况就是只够买一次。

  方法:先遍历一遍字符串,记录CCPC的数量,然后在遍历一次,找到几个特殊情况进行判断。

  代码:

  

2019 HZNU Winter Training Day 13 Comprehensive Training
 1 /*
 2  I have a dream!A AC deram!!
 3  orz orz orz orz orz orz orz orz orz orz orz
 4  orz orz orz orz orz orz orz orz orz orz orz
 5  orz orz orz orz orz orz orz orz orz orz orz
 6 
 7  */
 8 
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cstring>
13 #include<cmath>
14 #include<string>
15 #include<algorithm>
16 #include<vector>
17 #include<queue>
18 #include<set>
19 #include<stack>
20 #include<map>
21 using namespace std;
22 typedef long long ll;
23 const int maxn = 1e5 + 5;
24 const int N = 105;
25 char s[250000];
26 int main() 
27 {
28     int T;
29     scanf("%d", &T);
30     while(T--)
31     {
32         int len,flag,ans=0;
33         scanf("%d", &len);
34         scanf("%s", s);
35         for (int i = 0; i < len; i++)
36         {
37             if (s[i] == 'C'&&s[i + 1] == 'C'&&s[i + 2] == 'P'&&s[i + 3] == 'C')
38                 ans++;
39         }
40         for (int i = 0; i < len; i++)
41         {
42             flag = 0;
43             if (s[i] == 'C'&&s[i + 1] == 'P'&&s[i + 2] == 'C')
44             {
45                 if (i - 1 < 0 || s[i - 1] != 'C')
46                     flag++;
47             }
48             else if (s[i] == 'C'&&s[i + 1] == 'C'&&s[i + 2] == 'P'&&s[i + 3] != 'C')
49                 flag++;
50             else if (s[i] == 'C'&&s[i + 1] == 'C'&&s[i + 2] == 'C')
51             {
52                 if (s[i + 3] == 'P'&&s[i + 4] == 'C')
53                     flag--;
54                 flag++;
55             }
56             if (flag > 0)
57             {
58                 ans++;
59                 break;
60             }
61         }
62         printf("%d\n", ans);
63     }
64     return 0;
65 }
View Code

 

E.Drazil and Tiles   CodeForces-516B

  题意:给你一块n*m的格子,希望你用1*2的砖块铺满。瓷砖拥有的形态是“<>”和“^v”,图上“.”表示格子为空,需要被铺上瓷砖,“*”表示已经被铺上,不需要再铺。如果拥有独一无二的铺满的方法就画出铺上瓷砖的格子,如果不存在铺满的情况或者有多种情况出现,就输出“Not unique”。

  方法:先统计每个空格子旁边有几个空格子,用二维数组d[][]记录(即有几种方法填满)。然后开一个队列,将只有一种方法铺满的格子扔进去,更新邻近的点,更新d[][]。最后如果仍有“.”,即说明不满足题目要求。

  代码:

 

F.How can I satisfy thee? Let me count the ways... ZOJ - 3025 

  题意:输入一个式子,里面具有变量,常量和运算符号,变量P,Q,R取值为0,1,2这三个常量,然后有-,*,+三个运算规则。最后问让一个式子最后答案为2的方法有多少种(即让变量取不同的值)。

  方法:暴力。先把式子转成后缀表达式。然后总共的可能就是3*3*3,进行暴力求解即可。

  代码:

上一篇:HZNU ACM一日游 2019.3.17


下一篇:2019 HZNU Winter Training Day 14 Comprehensive Training