第一题 水题 秒掉
第二题 模拟题 没写完。。。本来认为做模拟题是最没用的,后来才发现原来模拟题能快的话 证明你编码能力是很强的。。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
int fieldkind[100];//0是w,1是B,2是R
int field[100];//记录有没有兔子
int last[100];
int n,r;
int nsize;
double p;
double C(int n,int r)
{
int i,j;
double ans=1;
for(i=n;i>=n-r+1;i--)
ans*=i;
for(i=r;i>=1;i--)
ans/=i;
return ans;
}
void copy(int t[],int s[])
{
int i;
for(i=0;i<nsize;i++)
{
t[i]=s[i];
}
}
void onestep()
{
int field2[100];
copy(field2,field);
for(int i=1;i<n-2;i++)
{
if(fieldkind[i]==2)
{
if(last[i]==-1&&field[i]>=1)
{
field2[i]--;
field2[i-1]++;
last[i-1]=i;
}
else if(field[i]>=1)
{
field2[i]--;
field2[last[i]]++;
last[last[i]]=i;
}
}
}
if(field[0]>=1)
{
field2[1]++;
field2[0]--;
last[1]=0;
}
if(field[n-1]>=1)
{
field2[n-2]++;
field2[n-1]--;
last[n-2]=n-1;
}
if(field[n-2]>=1)
{
field2[n-3]++;
field2[n-2]--;
last[n-3]=n-2;
}
for(int i=1;i<n-2;i++)
{
if(fieldkind[i]==0&&field[i]>=1)
{
field2[i]--;
field2[i-1]++;
last[i-1]=i;
}
else if(fieldkind[i]==1&&field[i]>=1)
{
field2[i]--;
field2[i+1]++;
last[i+1]=i;
}
}
for(int i=0;i<n;i++)
{
if(field2[i]>=2)
field2[i]=0;
}
n--;
copy(field,field2);
}
bool check(int num)
{
int i;
int ans=0;
for(i=0;i<nsize;i++)
{
if((1<<i)&num)
ans++;
}
if(ans==r)
return true;
else
return false;
}
void distru(int num)
{
memset(field,0,sizeof(field));
for(int i=0;i<nsize;i++)
{
if((1<<i)&(num))
field[i]=1;
}
}
class RabbitStepping
{
public:
double getExpected(string f, int rr)
{
n=f.size();
p=C(n,rr);
p=1/p;
r=rr;
nsize=n;
double res=0;
for(int i=0;i<n;i++)
{
if(f[i]=='W')
fieldkind[i]=0;
else if(f[i]=='B')
fieldkind[i]=1;
else
fieldkind[i]=2;
}
for(int i=0;i<(1<<nsize);i++)
{
memset(last,-1,sizeof(last));
n=nsize;
if(!check(i))
continue;
distru(i);
for(int j=nsize;j>2;j--)
{
onestep();
}
int tem=0;
for(int j=0;j<2;j++)
{
if(field[j]==1)
tem++;
}
res+=p*tem;
}
return res;
}
};
int main()
{
RabbitStepping t;
string f;
f="WRBRW";
int r=4;
double ans=t.getExpected(f,4);
return 0;
}