注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 561  

2013-03-05 15:12:49|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这套题目的完成就标志着我TC补完计划暂时告一段落了
虽然我还是打算继续做TC的,不过已经不是填坑性质了,而是开始了正式的刷题。。。
561题目都是挺好的(好像我每次都会说这句话来着???),1000pt的题目是rng_58大神出的神题,对于解决概率问题是很有启发性质的。重要思路,数学期望的计算是线性的,所以我们可以将一个很困难的东西划分成不相关的几个部分分别计算期望然后相加。

从1000pt的开始吧,毕竟题目比较重要:
给定一颗树,上面有些点是checkpoint,如果你随机选择K个点,将会有一条最短的路径是从某点出发然后遍历了这K个点。求出这条最短路径的期望长度。点数<=300。
是不是很有NOI2012既是感——不过这个问题稍稍难一些:
如果给定树上K个点,怎么计算最短的路径?
答案很显然就是这K个点所在的生成树的长度*2-生成树的直径。这部分很容易想到,但是对于解题有什么好处呢?
注意期望的计算是线性的,所以我们可以分别求解生成树的期望长度和直径的期望长度!
直径很好求,暴力枚举作为直径的两个点,那么剩下的K-2的点的要求就是与这两点的距离不超过K,同时保证枚举的这两个点字典序最小,接下来就是计算在所有点中选择出满足要求的K-2个点的概率。(这个条件是充分必要的,联系树的直径的求法)
最小生成树会麻烦一些,但是有个经典的思路:考虑每条边在生成树中的概率,将每条边的期望贡献计算出来算进答案。不过这个东西也会比较纠结,不如反过来,计算其不在生成树的概率——这个是很简单,概率就是选择的K个点全部在其一边的情况数/总情况数。
在计算概率的过程中我们会碰到求一种值C(j,k)/C(i,k)。如果直接算组合数会挂得很惨的。。。所以建议用公式直接递推,当然是预处理的事情。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=2500+10;
const int NUM=300+10;

int walk[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int dist[MAX][MAX];
ld f2[NUM][NUM],f[NUM][NUM];

struct Orienteering
{
vector<int> ne[MAX];
vector<int> checkpoint;
vector<string> g;
int root,K;

void preCalc()
{
//(j+1)!*(n-x)!/(n!*(j+1-x)!) => j!*(n-x)!/(n!*(j-x)!)
int N=checkpoint.size();
int j,k;
REP(j,0,N)
f[N][j]=1;
for(j=N-1;j>=0;--j)
REP(k,0,j)
f[j][k]=f[j+1][k]/(j+1)*(j+1-k);
REP(j,0,N-2)
f2[N-2][j]=1;
for(j=N-2-1;j>=0;--j)
REP(k,0,j)
f2[j][k]=f2[j+1][k]/(j+1)*(j+1-k);
}

void dfs(int u,int S,int Dist)
{
dist[S][u]=Dist;
int i,v;
REP2(i,0,ne[u].size())
{
v=ne[u][i];
if(dist[S][v]==-1)
dfs(v,S,Dist+1);
}
}

ld expectedDiameter()
{
int N=checkpoint.size();
int i,j,k;
REP2(i,0,N)
{
int a=checkpoint[i];
memset(dist[a],-1,sizeof dist[a]);
dfs(a,a,0);
}
ld ans=0;
ld tot=0;
REP2(i,0,N)
REP2(j,i+1,N)
{
int cnt=0;
int a=checkpoint[i];
int b=checkpoint[j];
int max_dist=dist[a][b];
REP2(k,0,N)
{
int c=checkpoint[k];
if(c==a || c==b)
continue;
if( (dist[a][c]<max_dist && dist[b][c]<max_dist)
|| (dist[a][c]==max_dist && c>b && dist[b][c]<max_dist)
|| (dist[c][b]==max_dist && c>a && dist[a][c]<max_dist)
)
++cnt;
if( dist[a][c]==max_dist && dist[b][c]==max_dist && c>b)
++cnt;
}
ans+=max_dist*f2[cnt][K-2];
tot+=f2[cnt][K-2];
}
return ans/tot;
}

pair<ld,int> get(int u,int fa)
{
size_t i;
int v;
int size=(g[u/g[0].size()][u%g[0].size()]=='*');
int N=checkpoint.size();
ld ans=0;
REP2(i,0,ne[u].size())
{
v=ne[u][i];
if(v==fa)
continue;
pair<ld,int> tmp=get(v,u);
size+=tmp.y;
ans+=tmp.x;
ans+=1.0-f[tmp.y][K]-f[N-tmp.y][K];
}
return mp(ans,size);
}

ld expectedSpanningTree()
{
return get(root,-1).x;
}

ld expectedLength(vector<string> field,int initK)
{
g=field;
K=initK;
int i,j;
int n=g.size();
int m=g[0].size();
root=-1;
REP2(i,0,n)
REP2(j,0,m)
{
if(g[i][j]=='#')
continue;
if(g[i][j]=='*')
checkpoint.pb(i*m+j);
if(root==-1)
root=i*m+j;
int dir=0;
REP2(dir,0,4)
{
int x=i+walk[dir][0];
int y=j+walk[dir][1];
if(x<0 || x>=n || y<0 || y>=m || g[x][y]=='#')
continue;
ne[i*m+j].pb(x*m+y);
}
}
preCalc();
sort(checkpoint.begin(),checkpoint.end());
return expectedSpanningTree()*2-expectedDiameter();
}
};



500pt的题目:
cot3的无法再弱化版本,就略掉了
写法很暴力,大概是n^3次方的,可能会更大

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int NUM=100+10;

struct Circle
{
LL x,y,r;
}cir[NUM];

int n;

LL sqr(LL a)
{
return a*a;
}

LL dist(const Circle& a,const Circle& b)
{
return sqr(a.x-b.x)+sqr(a.y-b.y);
}

int operator < (const Circle& a,const Circle& b)
{
return a.r>b.r;
}

vector<int> ne[NUM];
int dp[NUM],fa[NUM],hash[NUM][NUM],can[NUM],in[NUM];

void operator += (vector<int>& a,vector<int> b)
{
size_t i;
REP2(i,0,b.size())
a.pb(b[i]);
}

int get(int u)
{
if(!can[u])
return dp[u];
int ans=0,i;
REP2(i,0,ne[u].size())
ans^=get(ne[u][i]);
return ans;
}

vector<int> dfs(int u)
{
int i;
int v;
vector<int> son;
REP2(i,0,ne[u].size())
{
v=ne[u][i];
fa[v]=u;
son+=dfs(v);
}
son.pb(u);
REP2(i,0,son.size())
{
memset(can,0,sizeof can);
int v=son[i];
while(1)
{
can[v]=1;
if(v==u)
break;
v=fa[v];
}
hash[u][get(u)]=1;
}
REP2(i,0,NUM)
if(!hash[u][i])
{
dp[u]=i;
break;
}
return son;
}

struct CirclesGame
{
string whoCanWin(vector<int> x,vector<int> y,vector<int> r)
{
int i,j;
n=x.size();
REP2(i,0,n)
{
cir[i].x=x[i];
cir[i].y=y[i];
cir[i].r=r[i];
}
sort(cir,cir+n);
REP2(j,0,n)
for(i=j-1;i>=0;--i)
if(cir[i].r>cir[j].r)
{
LL d=dist(cir[i],cir[j]);
if(sqr(cir[i].r-cir[j].r)>d)
{
ne[i].pb(j);
++in[j];
break;
}
}
int ans=0;
REP2(i,0,n)
if(!in[i])
{
dfs(i);
ans^=dp[i];
}
if(ans)
return "Alice";
else return "Bob";
}
};



250略
  评论这张
 
阅读(433)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017