11.22：保持更新状态：主要发一些相关的题目和个人理解
（P.S.如果觉得简单，可以直接看后面的题目）
upd 11.30 更完了
【NO.1】
一道比较坑的题目,多给了一个没用的条件...其实就是利用线性关系，取一个平均值就OK了。
把最优情况和最差情况算出来，取一个算数平均值算出期望就OK了，应该是最简单的一道题了，关键是要想得到
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int n,d,p,i=;
double ans=;
int main(){
while(n=read(),d=read(),n||d){
++i;ans=;int k=;
while(n--){
int x=read(),y=read(),z=read();
k+=y;
ans+=2.0*y/z;
}ans+=d-k;
printf("Case %d: %.3lf\n\n",i,ans);
}
return ;
}
【NO.2】
SP1026 FAVDICE - Favorite Dice
其实这是一道赠券收集问题，这个看懂了之后，其实就很简单了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int n;
int main(){
n=read();
while(n--){
int x=read();
double ans=;
for(int i=;i<=x;i++){
ans+=x*1.0/(x-i+);
}
printf("%.2lf\n",ans);
}
return ;
}
中间小结：我们发现一个特性，代码很短，然而需要一定脑回路，想通了肯能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）的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int n,m;
double dp[],ans;
int main(){
n=read(),m=read();
dp[]=;
for(int i=;i<=m;i++)
dp[i]=dp[i-]*(-dp[i-])+dp[i-]*(dp[i-]-1.0/n),ans+=dp[i];
printf("%.5lf",ans+);
return ;
} 啦啦啦~~
感觉有点写不下去了...难受，关键是找不到一些题目...
【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.注意向下取整！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline double read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f*1.0;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int n,m;
double dp[];
int a[],b[];
const double t=(sqrt(5.0)+1.0)/2.0;
double dfs(int sum){
if(dp[sum]>) return dp[sum];
for(int i=;i<=n;i++){
if(sum>a[i])
dp[sum]+=(double)b[i]/n;
else dp[sum]+=(dfs(sum+a[i])+1.0)/n;
}
return dp[sum];
}
int main(){
while(~scanf("%d%d",&n,&m)){
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)cin>>a[i],b[i]=a[i]*a[i]*t;
double ans=dfs(m);
printf("%.3lf\n",ans);
}
return ;
}
后面的题目会偏难一点噢.
upd:11.29
好吧，其实也不是很难。。。暴力枚举状态然后转移就好了
前面的题目看懂的话，这道题可以直接上代码了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
double f[][][][];
int T,n,a1,a2,a3;
double solve(){
double ans=;
f[][a1][a2][a3]=;
for(int i=;i<n;i++)
for(int a=;a<=;a++)
for(int b=;b<=;b++)
for(int c=;c<=;c++){
if(a+b+c>) continue;
if(a>)f[i+][a-][b][c]+=(double)f[i][a][b][c]*(double)a/(double)(a+b+c+);
if(b>&&a+b+c==)f[i+][a+][b-][c]+=f[i][a][b][c]*(double)b/(double)(a+b+c+);
if(b>&&a+b+c<) f[i+][a+][b-][c+]+=f[i][a][b][c]*(double)b/(double)(a+b+c+);
if(c>&&a+b+c==) f[i+][a][b+][c-]+=f[i][a][b][c]*(double)c/(double)(a+b+c+);
if(c>&&a+b+c<) f[i+][a][b+][c]+=f[i][a][b][c]*(double)c/(double)(a+b+c+);
f[i+][a][b][c]+=f[i][a][b][c]/(double)(a+b+c+);
ans+=f[i][a][b][c]/(double)(a+b+c+);
}printf("%.2lf\n",ans);
} int main(){
T=read();
while(T--){memset(f,,sizeof(f));
n=read(),a1=read(),a2=read(),a3=read();solve();
}
return ;
}
最后一道
刷表法就好了，有个技巧就是可以先排序一下，然后就能保证所有背包先被处理（因为与顺序无关，上面的“依次”是骗人的）
f[i][j][k] 表示第i个挑战，赢了j次，背包容量为k，还是暴力枚举状态枚举
具体可以见代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
char chr=getchar(); int f=,ans=;
while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<) putchar('-'),x=-x;
if(x>) write(x/);
putchar(x%+'');
}
int n,l,k;
struct P{double p;int a;}a[];//概率 属性
double f[][][];
bool cmp(const P &x,const P &b){return x.a>b.a;}
int main(){
n=read(),l=read(),k=read();
for(int i=;i<=n;i++) cin>>a[i].p,a[i].p/=100.0;
for(int i=;i<=n;i++) cin>>a[i].a;
sort(a+,a+n+,cmp);
f[][][min(,k)]=;
for(int i=;i<n;i++)
for(int j=;j<=i;j++)
for(int k=;k<=n;k++){
f[i+][j][k]+=f[i][j][k]*(1.0-a[i+].p);//失败
int v=k+a[i+].a;
if(v<) continue;v=min(n,v);
f[i+][j+][v]+=f[i][j][k]*a[i+].p;//成功
}
double ans=;
for(int i=l;i<=n;i++)
for(int j=;j<=n;j++)
ans+=f[n][i][j];
printf("%.6lf",ans);
return ;
}