首页 > 代码库 > 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 }
View Code

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 }
View Code

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 }
View Code