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]就是答案。
代码:
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的数量,然后在遍历一次,找到几个特殊情况进行判断。
代码:
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,进行暴力求解即可。
代码: