The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

TC SRM 475 DIV2

第一题 水题 秒掉
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

int f(vector <string> names,string s)
{

    
int n=names.size();
    
for(int i=0;i<n;i++)
    
{
        
if(names[i]==s)
            
return i;
    }

    
return -1;
}


int istie(int v[],int n)
{

    
int i;
    
int ans=-1;
    
int ma=-1;
    
for(i=0;i<n;i++)
    
{

        
if(v[i]>ans)
        
{
            ans
=v[i];
            ma
=i;
        }


    }

    
for(i=0;i<n;i++)
    
{

        
if(v[i]==ans&&i!=ma)
        
{
            
return -1;
        }


    }

    
return ma;
}



class RabbitVoting
{
public:
    
string getWinner(vector <string> names, vector <string> votes)
    
{
        
int n=names.size();
        
int i;
        
int v[100];
        memset(v,
0,sizeof(v));
        
for(i=0;i<n;i++)
        
{

            
if(names[i]!=votes[i])
            
{
                v[f(names,votes[i])]
++;
            }

        }

        
int ans=istie(v,n);
        
if(ans==-1)
            
return names[ans];
        
else
            
return names[ans];
    }

}
;


第二题 模拟题 没写完。。。本来认为做模拟题是最没用的,后来才发现原来模拟题能快的话 证明你编码能力是很强的。。。
#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;

}

posted on 2010-07-07 01:33 abilitytao 阅读(1020) 评论(2)  编辑 收藏 引用

评论

# re: TC SRM 475 DIV2 2010-07-07 15:10 吴冬亮

有教程吗?怎么进去SRM,TC账号有 登陆出错 抓狂 求解……  回复  更多评论   

# re: TC SRM 475 DIV2 2010-07-07 15:20 tt

@吴冬亮
网上有教程的吧。我记得我就是看教程学的  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理