经神牛指点。。注册了topcoder。。今天有比赛的样子。。所以先做个上次的比赛找找感觉。。
1：
直接计算。。很easy啊。。
#include<cstdio>
#include<cmath>
using namespace std;
class RecursiveFigures
{
public:
double getArea(int len,int k)
{
double ans=0;double d2=len*len,p=acos(0);
for(int i=0;i<k;i++)
{
d2/=2;
ans+=d2*p-d2;
}
ans+=d2;
return ans;
}
};
2：
扫描线。。把每个方程看成一个线段。。那么就变成了在平面上找一个点在最多的线段中了。。
然后从左往右扫描就OK了。。注意可能那个点不是整数。。转换的时候+/-个0.5就OK了。。
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
#include<sstream>
using namespace std;
typedef vector<string>::iterator it;
class Inequalities
{
struct event
{
double x;int a;
event(double _x,int _a):x(_x),a(_a){}
bool operator<(const event&o) const
{return x<o.x;}
};
vector<event> list;
typedef vector<event>::iterator lit;
void add(double l,double r)
{
list.push_back(event(l,1));
list.push_back(event(r,-1));
}
void deal(const string&a)
{
istringstream in(a,istringstream::in);string tmp;
in>>tmp;int x;in>>tmp;in>>x;
if(tmp=="<") add(-1,x);
if(tmp=="<=") add(-1,x+0.5);
if(tmp=="=") add(x,x+0.5);
if(tmp==">") add(x+0.5,1001);
if(tmp==">=") add(x,1001);
}
public:
int maximumSubset(vector<string> Is)
{
for(it i=Is.begin();i!=Is.end();i++)
{
deal(*i);
}
sort(list.begin(),list.end());int ans=0,now=0;double last=-1;
for(lit i=list.begin();i!=list.end();i++)
{
if(i->x!=last){ans=max(ans,now);last=i->x;}
now+=i->a;
}
ans=max(ans,now);
return ans;
}
};
3：还是水题。。设dp(i,k)使从i点经过k条边出去的概率。。。然后直接dp就可以了。。
这个图是无环的。。我还以为是有环的准备解方程的说。。水啊。。
那么根据条件概率公式，答案就是dp (start,k)/sum{dp(all i,k)}。。
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int maxn=50;
class ParkAmusement
{
vector<string> map;
int n;
bool e(int x){return map[x][x]==’E’;}
bool p(int x){return map[x][x]==’P’;}
bool c(int x,int y){return map[x][y]==’1′;}
double dp[maxn][maxn];
bool save[maxn][maxn];
double pro(int pos,int len)
{
double&ans=dp[pos][len];
if(save[pos][len]) return ans;
save[pos][len]=true;
if(p(pos)) return ans=0;
if(e(pos)) return ans=(len==0?1:0);
if(len==0) return ans=0;
double sum=0;int num=0;
for(int i=0;i<n;i++)
if(c(pos,i))
{
sum+=pro(i,len-1);
num++;
}
if(num==0) return ans=0;
return ans=sum/num;
}
public:
double getProbability(vector<string> land,int start,int k)
{
map=land;n=map.size();
memset(save,0,sizeof(save));double p=pro(start,k);double sum=0;
for(int i=0;i<n;i++) sum+=pro(i,k);
return p/sum;
}
};
DIV2的题目好水的说。。但是DIV的题目第一题还好说。。第二题我就吴宇森了。。。