11.22：保持更新状态：主要发一些相关的题目和个人理解

（P.S.如果觉得简单，可以直接看后面的题目）

upd 11.30 更完了

 

【NO.1】

UVA12230 Crossing Rivers 

一道比较坑的题目,多给了一个没用的条件...其实就是利用线性关系，取一个平均值就OK了。

把最优情况和最差情况算出来，取一个算数平均值算出期望就OK了，应该是最简单的一道题了，关键是要想得到

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }
12 void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }
17 int n,d,p,i=0;
18 double ans=0;
19 int main(){
20     while(n=read(),d=read(),n||d){
21         ++i;ans=0;int k=0;
22         while(n--){
23             int x=read(),y=read(),z=read();
24             k+=y;
25             ans+=2.0*y/z;
26         }ans+=d-k;
27         printf("Case %d: %.3lf\n\n",i,ans);
28     }
29     return 0;
30 }

 

 

【NO.2】

SP1026 FAVDICE - Favorite Dice 

其实这是一道赠券收集问题，这个看懂了之后，其实就很简单了

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }
12 void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }
17 int n;
18 int main(){
19     n=read();
20     while(n--){
21         int x=read();
22         double ans=0;
23         for(int i=1;i<=x;i++){
24             ans+=x*1.0/(x-i+1);
25         }
26         printf("%.2lf\n",ans);
27     }
28     return 0;
29 }

 

 

 

中间小结：我们发现一个特性，代码很短，然而需要一定脑回路，想通了肯能5min就解决了，否则可能会想的很复杂（比如有一次码一百多行，后来发现可以O（1）时间一行直接输出...）

 

 

 upd:11.26

【NO.3】

KIDS AND PRIZES

P.S.　额...这道题找不到来源，具体是SGU495，但是SGU消失了，Vjudge又不能提交，如果有读者知道怎么提交的话，可以在下面回复一下，谢谢

【题目描述】

n个盒子里装有礼物，m个人随机选择礼物，选完之后空盒子放回
问选中的礼物数的期望。

【思路】

有log(m)的做法（快速幂），在这里先介绍O（m）的做法

令dp[i]表示第i个人去箱子时的得到礼物的概率，那么有方程：

dp[1]=1,dp[i(i>1)]=dp[i-1]*(1-dp[i-1])+dp[i-1]*(dp[i-1]-1.0/n);

关于优化：

对上式进行化简，则有

　dp[i]=dp[i-1]*(1-1.0/n)

不难发现1.0/n是一个常数 然后用数列的知识一顿瞎搞->dp[n]=(1-1.0/n)^m-1;

ans=∑dp[i]=n-n*((n-1)/n)^m

然后快速幂就好了

下面代码是O（m）的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }
12 void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }
17 int n,m;
18 double dp[1000005],ans;
19 int main(){ 
20     n=read(),m=read();
21     dp[1]=1;
22     for(int i=2;i<=m;i++)
23         dp[i]=dp[i-1]*(1-dp[i-1])+dp[i-1]*(dp[i-1]-1.0/n),ans+=dp[i];
24     printf("%.5lf",ans+1);
25     return 0;
26 }
27 
28 啦啦啦~~

 

 

 感觉有点写不下去了...难受，关键是找不到一些题目...

 

 

【NO.4】

ZOJ3640 help me escape

题目描述

英语不太好，翻译不来，用机翻吧...这里就不给出了（懒..）

【思路】

记忆化搜索是个好东西，其实用记忆化搜索做这种题有时候更方便呢...

如果i>c[j]           dp[i]+=(int)(p*c[j]*c[j])/n;
如果i<=c[j]      dp[i]+=(dfs(i+c[j])+1)/n;

P.S.注意向下取整！！！

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 inline double read(){
 8     char chr=getchar();    int f=1,ans=0;
 9     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
11     return ans*f*1.0;
12 }
13 void write(int x){
14     if(x<0) putchar('-'),x=-x;
15     if(x>9) write(x/10);
16     putchar(x%10+'0');
17 }
18 int n,m;
19 double dp[1000005];
20 int a[1000005],b[1000005];
21 const double t=(sqrt(5.0)+1.0)/2.0;
22 double dfs(int sum){
23     if(dp[sum]>0) return dp[sum];
24     for(int i=1;i<=n;i++){
25         if(sum>a[i])
26             dp[sum]+=(double)b[i]/n;
27         else dp[sum]+=(dfs(sum+a[i])+1.0)/n;
28     }
29     return dp[sum];
30 }
31 int main(){
32     while(~scanf("%d%d",&n,&m)){
33         memset(dp,0,sizeof(dp));
34         for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]*a[i]*t;
35         double ans=dfs(m);
36         printf("%.3lf\n",ans);
37     }
38     return 0;
39 }

 

 

 

　　后面的题目会偏难一点噢.

upd:11.29

HYSBZ - 4832 抵制克苏恩

　　好吧，其实也不是很难。。。暴力枚举状态然后转移就好了

前面的题目看懂的话，这道题可以直接上代码了

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }
12 void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }
17 double f[60][10][10][10];
18 int T,n,a1,a2,a3;
19 double solve(){
20     double ans=0;
21     f[0][a1][a2][a3]=1;
22     for(int i=0;i<n;i++)
23         for(int a=0;a<=7;a++)
24             for(int b=0;b<=7;b++)
25                 for(int c=0;c<=7;c++){
26                     if(a+b+c>7) continue;
27                     if(a>0)f[i+1][a-1][b][c]+=(double)f[i][a][b][c]*(double)a/(double)(a+b+c+1);
28                     if(b>0&&a+b+c==7)f[i+1][a+1][b-1][c]+=f[i][a][b][c]*(double)b/(double)(a+b+c+1);
29                     if(b>0&&a+b+c<7) f[i+1][a+1][b-1][c+1]+=f[i][a][b][c]*(double)b/(double)(a+b+c+1);
30                     if(c>0&&a+b+c==7) f[i+1][a][b+1][c-1]+=f[i][a][b][c]*(double)c/(double)(a+b+c+1);
31                     if(c>0&&a+b+c<7) f[i+1][a][b+1][c]+=f[i][a][b][c]*(double)c/(double)(a+b+c+1);
32                     f[i+1][a][b][c]+=f[i][a][b][c]/(double)(a+b+c+1);
33                     ans+=f[i][a][b][c]/(double)(a+b+c+1);
34                 }printf("%.2lf\n",ans);
35 }
36 
37 int main(){
38     T=read();
39     while(T--){memset(f,0,sizeof(f));
40         n=read(),a1=read(),a2=read(),a3=read();solve();
41     }
42     return 0;
43 }

 

 

 

 

 

最后一道 

tyvj-1864 守卫者的挑战

　　刷表法就好了，有个技巧就是可以先排序一下，然后就能保证所有背包先被处理（因为与顺序无关，上面的“依次”是骗人的）

　　f[i][j][k] 表示第i个挑战，赢了j次，背包容量为k，还是暴力枚举状态枚举

　　具体可以见代码

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 inline int read(){
 7     char chr=getchar();    int f=1,ans=0;
 8     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
10     return ans*f;
11 }
12 void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }
17 int n,l,k;
18 struct P{double p;int a;}a[100005];//概率  属性
19 double f[205][205][205];
20 bool cmp(const P &x,const P &b){return x.a>b.a;}
21 int main(){
22     n=read(),l=read(),k=read();
23     for(int i=1;i<=n;i++) cin>>a[i].p,a[i].p/=100.0;
24     for(int i=1;i<=n;i++) cin>>a[i].a;
25     sort(a+1,a+n+1,cmp);
26     f[0][0][min(200,k)]=1;
27     for(int i=0;i<n;i++)
28         for(int j=0;j<=i;j++)
29             for(int k=0;k<=n;k++){
30                 f[i+1][j][k]+=f[i][j][k]*(1.0-a[i+1].p);//失败 
31                 int v=k+a[i+1].a;
32                 if(v<0) continue;v=min(n,v);
33                 f[i+1][j+1][v]+=f[i][j][k]*a[i+1].p;//成功 
34             }
35     double ans=0;
36     for(int i=l;i<=n;i++)
37         for(int j=0;j<=n;j++)
38             ans+=f[n][i][j];
39     printf("%.6lf",ans);
40     return 0;
41 }