寒假训练3解题报告 CodeForces #148

CodeForces 148B

一道简单模拟，判断龙能够抓到公主几次，如果公主和龙同时到达公主的城堡，不算龙抓住她，因为路程除以速度可能会产生浮点数，所以这里考虑一下精度问题

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iomanip>
 5 #include <algorithm>
 6 using namespace std;
 7 #define eps 1e-19
 8 
 9 int ok(int x)
10 {
11     if(abs(x)<=eps) return 0;
12     else return x>0?1:-1;
13 }
14 
15 int main()
16 {
17    // freopen("a.in" , "r", stdin);
18     double vp , vd , t , f , c;
19     while(~scanf("%lf%lf%lf%lf%lf", &vp , &vd , &t , &f , &c))
20     {
21         if(ok(vp-vd) >= 0){
22             puts("0");
23             continue;
24         }
25         double  del = t*vp;
26         double cur = del;
27         int ans = 0;
28         double t1 , t2;//t1princess从dragon在cave时到达目的地要的时间，t2表示dragon从cave追上princess要的时间
29         t1 = (c-cur)/vp , t2 = (del)/(vd-vp);
30         while(ok(t1-t2) > 0){
31             cur += t2*vp;
32             cur = cur+(cur/vd+f)*vp;
33             del = cur;
34             t1 = (c-cur)/vp , t2 = (del)/(vd-vp);
35             ans++;
36         }
37         printf("%d
" , ans);
38     }
39     return 0;
40 }

CodeForces 148C

得到a个数，这些数都比先前的数大但不能比前面所有数的和大，得到b个数这些数都比前面的所有数大

这道题自己写的有点坑，太长了，但其实没那么麻烦

那个Wow成立，说明当前数大于前面所有数的和，我们为了使数尽可能小，所以总是将Wow成立的数放前面，Oh成立的数方面，最后多余的数都和前一个数一样即可

当 a+b+1 = n b=0,a>0时是不成立的，因为第二个数开始就必须比前一个数大，那么第二个数比前面的大，也就是大于前面的总和，必然得到的是Wow，与b=0矛盾

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int num[105];
 6 
 7 int main()
 8 {
 9    // freopen("a.in" , "r", stdin);
10     int n,a,b,sum;
11     while(~scanf("%d%d%d" , &n , &a , &b))
12     {
13         int flag = 1;
14 
15         if(a+b+1 == n){
16             num[1] = 1 , sum = 1;
17             if(b == 0 && a>0) flag = 0;
18             for(int i=2 ; i<=1+b ; i++)
19             {
20                 num[i] = sum+1 , sum += num[i];
21                 if(num[i]>=50000){
22                     flag=0;
23                     break;
24                 }
25             }
26             for(int i=2+b ; i<=n ; i++){
27                 num[i] = num[i-1]+1 , sum += num[i];
28                 if(num[i]>=50000){
29                     flag=0;
30                     break;
31                 }
32             }
33 
34         }
35         else{
36             sum = 0;
37             num[1] = 1 , sum = 1;
38             if(b>0){
39                 for(int i=2 ; i<=1+b ; i++)
40                 {
41                     num[i] = sum+1 , sum+=num[i];
42                     if(num[i]>=50000){
43                         flag=0;
44                         break;
45                     }
46                 }
47                 for(int i=2+b ; i<=1+a+b ; i++)
48                 {
49                     num[i] = num[i-1]+1;
50                     if(num[i]>=50000){
51                         flag=0;
52                         break;
53                     }
54                 }
55                 for(int i=2+a+b ; i<=n ; i++)
56                     num[i] = num[i-1];
57             }
58             else{
59                 for(int i=1 ; i<=n-a ; i++)
60                     num[i] = 1;
61                 for(int i=n-a+1 ; i<=n ; i++)
62                     num[i] = num[i-1]+1;
63             }
64         }
65         if(!flag){
66             puts("-1");
67             continue;
68         }
69         for(int i=1 ; i<=n ; i++){
70             if(i==1) printf("%d" , num[i]);
71             else printf(" %d" , num[i]);
72         }
73         puts("");
74     }
75     return 0;
76 }

Codeforces 148D

简单的概率dp过程

用dp[0][w][b]表示后取完后游戏还未结束得到w只老鼠，b只黑鼠的概率

用dp[1][w][b]表示龙取完后游戏还未结束得到w只白鼠，b只黑鼠的概率

最后答案就是所有龙取完后游戏未结束的局面*一个后取到白鼠的概率

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 1005;
 6 double dp[2][N][N];
 7 
 8 int main()
 9 {
10    // freopen("a.in" , "r", stdin);
11     int w , b;
12     while(~scanf("%d%d" , &w , &b))
13     {
14         memset(dp , 0 , sizeof(dp));
15         dp[1][w][b] = 1.0;
16         for(int i=w ; i>=1 ; i--){
17             for(int j=b ; j>=0 ; j--){
18                 dp[0][i][j] += dp[1][i][j+1]*(j+1)/(i+j+1);
19                 dp[1][i][j] += dp[0][i][j+2]*(j+2)/(i+j+2)*(j+1)/(i+j+1) + dp[0][i+1][j+1]*(j+1)/(i+j+2)*(i+1)/(i+j+1);
20             }
21         }
22         double ans = 0;
23         for(int i=1 ; i<=w ; i++)
24             for(int j=0 ; j<=b ; j++){
25                 ans += dp[1][i][j]*i/(i+j);
26             }
27         printf("%.10f
" , ans);
28     }
29     return 0;
30 }

codeforces 148E
每行书都是跟其他行没有直接关系的，求出每行书取得的个数达到的最大值

然后将n行结合在一起当成背包问题看

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int N = 105;
 6 int dp[N][N][N] , val[N][N] , sum[N][N];
 7 int maxn[N][N] , cnt[N];
 8 int bag[N][N*N];
 9 
10 int main()
11 {
12   //  freopen("a.in" , "r" , stdin);
13     int n,m;
14     while(scanf("%d%d" , &n , &m) != EOF)
15     {
16         memset(dp , 0 , sizeof(dp));
17         memset(maxn , 0 , sizeof(maxn));
18         memset(sum , 0 , sizeof(sum));
19         for(int i=1 ; i<=n ;i++){
20             scanf("%d" , &cnt[i]);
21             for(int j=1 ; j<=cnt[i] ; j++){
22                 scanf("%d" , &val[i][j]);
23                 sum[i][j] = sum[i][j-1]+val[i][j];
24                 for(int k=1 ; k<=cnt[i] ; k++){
25                     for(int l=1 ; l<=k+1 ; l++){
26                         maxn[i][k] = max(maxn[i][k] , sum[i][cnt[i]]-sum[i][l+cnt[i]-k-1] + sum[i][l-1]);
27                     }
28                 }
29             }
30         }
31         memset(bag , 0 , sizeof(bag));
32         for(int i=1 ; i<=n ; i++){
33             for(int k=0 ; k<=cnt[i] ; k++){
34                 for(int j=0 ; j<=m ; j++){
35                     bag[i][j] = max(bag[i][j] , bag[i-1][j]);
36                     if(j>=k)
37                         bag[i][j] = max(bag[i][j] , bag[i-1][j-k]+maxn[i][k]);
38                 }
39             }
40         }
41         printf("%d
" , bag[n][m]);
42     }
43     return 0;
44 }