首页 > 代码库 > Codeforces 448(#256 (Div. 2) ) 解题报告
Codeforces 448(#256 (Div. 2) ) 解题报告
A:
1 // File Name: a.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月17日 星期四 21时44分03秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 int a[10];27 int b[10];28 int main(){29 int suma = 0 ; 30 int sumb = 0 ; 31 for (int i = 1;i <= 3;i ++)32 {33 scanf("%d",&a[i]);34 suma += a[i];35 }36 for(int i =1 ;i<= 3;i ++)37 {38 scanf("%d",&b[i]);39 sumb += b[i] ;40 }41 int n; 42 scanf("%d",&n);43 int ta;44 int tb;45 if(suma % 5 == 0)46 {47 ta = suma/5;48 }else {49 ta = suma/5 + 1 ;50 }51 if(sumb % 10 == 0)52 {53 tb = sumb/10;54 }else {55 tb = sumb/10 + 1 ;56 }57 if(ta + tb <= n)58 printf("YES\n");59 else printf("NO\n");60 return 0;61 }
B:三种情况,其中一种需要最长上升子序列
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月17日 星期四 22时12分12秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 char str[110];27 char str1[110];28 int dp[102][102];29 int hs[30];30 int hs1[30];31 int len;32 int len1;33 int ok1 = 0 ;34 int is()35 {36 memset(dp,0,sizeof(dp));37 for(int i = 1;i <= len;i++)38 {39 for(int j = 1;j <= len1 ;j ++)40 {41 if(str[i-1] == str1[j-1])42 dp[i][j] = dp[i-1][j-1] + 1;43 else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);44 }45 }46 /* for(int i = 1;i <= len;i++)47 {48 for(int j = 1;j <= len1 ;j ++)49 {50 printf("%d ",dp[i][j]);51 }52 printf("\n");53 }*/54 //printf("%d\n",dp[len][len1]);55 if(dp[len][len1] == len1)56 return 1; 57 return 0 ;58 }59 int main(){60 scanf("%s",str);61 scanf("%s",str1);62 len = strlen(str);63 len1 = strlen(str1);64 if(len < len1)65 {66 printf("need tree\n");67 return 0;68 }69 memset(hs,0,sizeof(hs));70 memset(hs1,0,sizeof(hs1));71 for(int i = 0 ;i < len;i ++)72 { 73 hs[str[i] -‘a‘] ++;74 }75 for(int i = 0 ;i < len1;i ++)76 { 77 hs1[str1[i] -‘a‘] ++;78 }79 for(int i = 0 ;i <= 26;i ++)80 {81 if(hs[i] < hs1[i])82 {83 printf("need tree\n");84 return 0; 85 }86 }87 if(is())88 {89 printf("automaton\n");90 }else {91 // printf("%d %d\n",len,len1);92 if(len == len1)93 printf("array\n");94 else printf("both\n");95 }96 return 0;97 }
C:
D:
很巧妙的一个二分思想的题目
这里我们需要找到 大于等于K 且数最小的那个数(这样才满足 i*j 的条件,我这里也是想了好久),这里也要用到二分的一些技巧
1 // File Name: d1.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月18日 星期五 10时38分20秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 long long n , m , k ; 27 long long solve(long long t)28 {29 long long sum = 0 ; 30 for(int i = 1;i <= n;i ++)31 {32 sum += min(m,t/i);33 }34 return sum ; 35 }36 int main(){37 38 scanf("%lld %lld %lld",&n,&m,&k);39 long long l = 1,r = n*m,mid,ans;40 while(l <= r )41 {42 // printf("%lld %lld\n",l,r);43 long long mid = (l+r) >> 1;44 if(solve(mid) >= k )45 {46 r = mid - 1; 47 }else 48 l = mid + 1;49 }50 printf("%lld\n",l);51 return 0;52 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。