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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 565  

2013-03-02 10:16:43|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
嗯,抄代码的感觉真的很爽——
我不吐槽TC的题解写得有多渣了,特别是针对非英语语言国家。。。

反正1000pt的题目看题解看了蛮久,实际理解了之后还是挺好写的(写完了就可以这样说了)
算法也不难,这也是看了题解之后才能这么说的。
膜拜当场切掉的Petr和tourist
无法想象在考场上码这么多代码究竟得有多强,果然只能仰慕了

250pt的题目:水dp,害得我还调了蛮久的代码。故此略。

500pt的题目:一种游戏,每次可以将一个数变成其约数,不能操作者输。初始局面是一些连续的数。求问位于【L,R】内的区间有多少是先手必胜。(L<=10^9,R-L<=1000000)
嗯,SG函数显然就是每个数质因数分解后所有质数的指数相加。
于是任务只剩下质因数分解了——怎么将R-L区间内的所有数质因数分解?
筛法很显然,但是直接筛也是不可能的。借鉴很久以前看到的某神题的思路——只需要用小于sqrt(10^9)的质数去筛,若某个数没有被筛掉,那么剩下的数一定是个质数。
由于筛的次数就是[L,R]中所有数的质因数个数,nlogn。
接下来就是求sg值异或不等于0的个数——由于异或有前缀和性质,所以就是前缀和异或不等于0的个数,而且只有两个数相等异或才等于0,这样就很简单了吧。

1000pt的题目是道大神题:
已知一颗树上有三点,知道其余所有点与这三点的距离大小。求满足要求的树的个数。
已知只有一个点的好求吧!
为每个点选择一个父亲就可以了。其可能的父亲的个数是(sigma( [di<d[j]] )+1)。乘起来即可。
已知两个点好求吧!
假定我已经知道这两点A,B之间的距离,考虑以B为根,接下来决定每个点是在A所在的子树还是其它子树,可以由该点与B的距离+AB的距离是否等于B的距离决定(注意判掉不合法的情况)。其它子树的方案数转化为只有一个点的。而以A为子树的,那么选择离B最近的那个点作为新的根(如果有两个这样的点,不合法),于是转化为已知这个新根和A,求方案数,递归下去,直到选择的新根就是A,直接求就行了。
于是已知三个点就好求了!
三个点的位置无非就是两种情况:
1.从某个点出发的三棵子树——这种情况其实是很简单的,利用位置判定每个点属于三棵子树中的哪一个或者一个都不属于,于是分解成了四部分,不属于这三棵子树的,就是以该点为根的一颗子树,转化为已知一个点的情况,否则,转化为已知该点,和三点中某个点的情况,问题解决。
2.三个点形成了一条链——也蛮容易。设顺序为B-A-C,暴力枚举每个点,利用它可以算出所有可能AB,AC的距离。利用这个距离将问题划分为三部分:A出发不包含B,C的子树,A,B确定的子树,A,C确定的子树,问题解决。
然后就没有然后了。
代码还行(和标程没多大区别)

#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 Mod=1000000009;

struct UnknownTree
{
int work1(vector< int > D)
{
LL ans=1;
int i,j;
sort(D.begin(),D.end());
REP2(i,0,D.size())
{
int num=0;
REP2(j,0,i)
if(D[j]<D[i])
++num;
ans=ans*(num+1)%Mod;
}
return ans;
}

int work2(vector< pair<int,int> > D)
{
int i;
sort(D.begin(),D.end());
if(D.size()>1 && D[0].x==D[1].x)
return 0;
vector< pair<int,int> > B;
vector< int > A;
int b=0;
while(D[b].y!=0)
++b;
if(b==0)
{
//the root is A
REP2(i,1,D.size())
{
if(D[i].x!=D[b].x+D[i].y)
return 0;
A.pb(D[i].y);
}
return work1(A);
}
//D[0] is the root of the branch
REP2(i,1,D.size())
{
int da=D[i].x-D[0].x;
int db=D[i].y-D[0].y;
if(da==db)
A.pb(da);
else
{
if(D[i].x-D[0].x + D[i].y < D[0].y)
return 0;
B.pb(D[i]);
}
}
return (LL)work1(A)*work2(B)%Mod;
}

int Center(int a,vector<int> da,vector<int> db,vector<int> dc)
{
vector< pair<int,int> > A,B,C;
vector<int> D;
A.pb(mp(0,da[a]));
A.pb(mp(da[a],0));
B.pb(mp(0,db[a]));
B.pb(mp(db[a],0));
C.pb(mp(0,dc[a]));
C.pb(mp(dc[a],0));
int i;
REP2(i,0,da.size())
if(i!=a)
{
int pa=da[i]-da[a],pb=db[i]-db[a],pc=dc[i]-dc[a];
if(pa == pb && pb == pc && pa>0)
D.pb( pa );
else if(pa==pb && pa>0)
C.pb( mp(pa,dc[i]) );
else if(pc==pa && pc>0)
B.pb( mp(pc,db[i]) );
else if(pb==pc && pb>0)
A.pb( mp(pb,da[i]) );
else return 0;
}
LL ans=1;
ans=ans*work1(D)%Mod;
ans=ans*work2(C)%Mod;
ans=ans*work2(B)%Mod;
ans=ans*work2(A)%Mod;
return ans;
}

int calc(vector<int> da,vector<int> db,vector<int> dc,int ab,int ac)
{
if(ab<=0 || ac<=0)return 0;
int i;
vector<int> A;
vector< pair<int,int> > B,C;
B.pb(mp(0,ab));
B.pb(mp(ab,0));
C.pb(mp(0,ac));
C.pb(mp(ac,0));
REP2(i,0,da.size())
{
if(db[i]-ab==da[i] && dc[i]-ac==da[i])
A.pb(da[i]);
else if(da[i]+ac==dc[i])
B.pb(mp(da[i],db[i]));
else if(da[i]+ab==db[i])
C.pb(mp(da[i],dc[i]));
else
return 0;
}
LL ans=1;
ans=ans*work1(A)%Mod;
ans=ans*work2(B)%Mod;
ans=ans*work2(C)%Mod;
return ans;
}

int AisMid(vector<int> da,vector<int> db,vector<int> dc)
{
int m;
LL ans=0;
vector< pair<int,int> > dd;
REP2(m,0,da.size())
{
//m out_line
dd.pb(mp(db[m]-da[m],dc[m]-da[m]));
//m on AB
dd.pb(mp(da[m]+db[m],dc[m]-da[m]));
//m on AC
dd.pb(mp(db[m]-da[m],dc[m]+da[m]));
//m out AB
dd.pb(mp(da[m]-db[m],dc[m]-da[m]));
//m out AC
dd.pb(mp(db[m]-da[m],da[m]-dc[m]));
}
sort(dd.begin(),dd.end());
REP2(m,0,dd.size())
{
if(m!=0 && dd[m].x==dd[m-1].x && dd[m].y==dd[m-1].y)
continue;
ans+=calc(da,db,dc,dd[m].x,dd[m].y);
}
return ans%Mod;
}

int getCount(vector <int> dA, vector <int> dB, vector <int> dC)
{
int i;
LL ans=0;
REP2(i,0,dA.size())
ans+=Center(i,dA,dB,dC);
ans+=AisMid(dA,dB,dC);
ans+=AisMid(dB,dA,dC);
ans+=AisMid(dC,dA,dB);
return ans%Mod;
}
};



  评论这张
 
阅读(370)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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