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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 562  

2013-03-04 22:19:18|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目很难的一次。。。
当时考场上ACrush怒虐rank1。
仅仅是500分的题目就卡了我两个小时的。。。其实我250分的题目也想了好久,看了样例才想出来。
废话少说:

250pt:
每次将n*m的矩形中指定颜色的格子染成指定颜色。该矩形左上角位置依次为(1,1),(2,2),(3,3),...,(T,T)。要求每种颜色有多少格子染成了它。
开始纠结了好久。每个斜行是独立的,所以分开搞。然后发现对于一个格子,其可能覆盖的范围是个区间。每个格子对应一个区间。于是就转化成了区间统计问题,很简单的。

#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;

int id(char a)
{
if(a=='R')return 0;
if(a=='G')return 1;
if(a=='B')return 2;
return 3;
}

struct PastingPaintingDivOne
{
vector<LL> countColors(vector <string> g,int T)
{
int n=g.size();
int m=g[0].size();
int i,j;
vector<LL> ans(3,0);
REP(i,-m,n)
{
vector<int> hash;
REP2(j,0,m)
{
int y=i+j;
if(y>=0 && y<n && g[y][j]!='.')
hash.pb(j);
}
int last=-1000000;
REP2(j,0,hash.size())
{
int y=hash[j];
ans[id(g[i+y][y])]+=max(0,y+T-1-max(last,y-1));
last=y+T-1;
}
}
return ans;
}
};



500pt的题目:n个白点和m个黑点(n,m<=220)。判断是否有个凸多边形,使得其边界是黑白交错的。
这道题我也纠结了好久的说。。。
暴力枚举一个黑点和一个白点,并将白点作为x坐标正方向。那么接下来对于所有在1,2象限的白点,判断是否出现如图的情况:
SRM 562 - hzaskywalker - Yavin(某沙茶的代码库)
如果在白点之间和白点与黑点的三条连线中存在黑点的话,那么就一定有凸多边形满足题意。
我们发现,如果固定一个点,另外一个白点经可能的右偏——其实就是对白点求个凸壳,如果有黑点在凸壳内,那么就找到解了,否则就一定无解。
求出凸壳,暴力判断每个黑点是否在凸壳内部即可,方法用二分。
注意排序对于每个黑点只要排一遍,否则TLE会很爽的(叉积运算是很耗时间的)

#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=10000;

struct point
{
LL x,y;
point(){}
point(LL a,LL b)
{
x=a;
y=b;
}
point operator = (const point& c)
{
x=c.x;
y=c.y;
return *this;
}
}O,st[MAX];
int top;

inline LL chaji(const point& s,const point& a,const point& b)
{
return (a.x-s.x)*(b.y-s.y)-(a.y-s.y)*(b.x-s.x);
}

inline int operator < (const point& a,const point& b)
{
return chaji(O,a,b)>0;
}

inline int sign(LL a)
{
return a>0?1:(a==0?0:-1);
}

inline int cross(point a,point b,point c,point d)
{
return sign(chaji(a,c,b))*sign(chaji(a,b,d))>0 && sign(chaji(c,a,d))*sign(chaji(c,d,b))>0;
}

struct CheckerFreeness
{
vector<int> concatenate(vector<string> c)
{
size_t i;
string a;
REP2(i,0,c.size())
a+=c[i];
vector<int> ans;
for(i=0;i<a.size();++i)
{
int now=0;
for(;i<a.size() && a[i]<='9' && a[i]>='0';++i)
now=now*10+a[i]-'0';
ans.pb(now);
}
return ans;
}

string isFree(vector <string> wX, vector <string> wY, vector <string> bX, vector <string> bY)
{
vector<int> x1,y1,x2,y2;
x1=concatenate(wX);
y1=concatenate(wY);
x2=concatenate(bX);
y2=concatenate(bY);
size_t i,j,k;
vector<point> a,b;
REP2(i,0,x1.size())
a.pb(point(x1[i],y1[i]));
REP2(i,0,x2.size())
b.pb(point(x2[i],y2[i]));
REP2(i,0,a.size())
{
O=a[i];
sort(b.begin(),b.end());
REP2(j,0,b.size())
{
vector<point> c;
REP2(k,0,b.size())
if(chaji(a[i],b[j],b[k])>=0)
c.pb(b[k]);
top=0;
REP2(k,0,c.size())
{
while(top>1 && chaji(st[top-1],st[top],c[k])>0)
--top;
st[++top]=c[k];
}
REP2(k,0,a.size())
{
if(chaji(O,a[k],st[1])>0)continue;
if(chaji(O,st[top],a[k])>0)continue;
int left=1,right=top-1;
while(left<right)
{
int mid=(left+right+1)/2;
if(chaji(O,st[mid],a[k])>0)left=mid;
else right=mid-1;
}
if(cross(a[i],a[k],st[left],st[left+1]))
return "NO";
}
}
}
return "YES";
}
};



1000pt的题目是一道大神题,Petr考场上似乎犯了小错误而导致没有AK(真心膜拜了)
题意:给定一棵数和k,求出重标号的方案数,使得任意连续k个点的导出子图是联通的。。。
真心神爆了。。。
核心思想是,若给定一颗子树,要求其[i,n],的每个区间是联通的怎么办?
那么就是每个点的标号必须小于其父亲的标号,这是充分必要的。
接下来分情况讨论:
若2*k<n,那么最终答案一定是中间连续的一条链和两端。
若2*k>n,那么答案一定是一个联通的子图,旁边伸出一些分支。
可以自己画一下,有了这些结论就不难了。

#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=50+1;

int dp[MAX][MAX][MAX][MAX];//i,j a,b
bool hash[MAX][MAX];

struct InducedSubgraphs
{
const static int Mod=1000000009;

int n,K;
vector<int> ne[MAX];
int C[MAX][MAX],fac[MAX];
map< pair<int,int>,pair<int,int> > f;

void preComb()
{
int i,j;
C[0][0]=1;
REP2(i,0,MAX)
{
C[i][0]=1;
REP(j,1,i)
{
C[i][j]=C[i-1][j-1]+C[i-1][j];
if(C[i][j]>=Mod)
C[i][j]-=Mod;
}
}
fac[0]=1;
REP2(i,1,MAX)
fac[i]=(LL)fac[i-1]*i%Mod;
}

pair<int,int> get(int u,int fa)
{
if(f[mp(u,fa)].x)
return f[mp(u,fa)];
size_t i;
int size=1;
int ans=1;
REP2(i,0,ne[u].size())
{
int v=ne[u][i];
if(v==fa)
continue;
pair<int,int> now=get(v,u);
size+=now.x;
now.y=(LL)now.y*C[size-1][now.x]%Mod;
ans=(LL)ans*now.y%Mod;
}
f[mp(u,fa)]=mp(size,ans);
return mp(size,ans);
}

pair<int,int> findAnother(int u,int fa)
{
if(f[mp(u,fa)].x==K)return mp(u,fa);
int i,v,sum=0;
pair<int,int> ans(-1,-1);
REP2(i,0,ne[u].size())
{
v=ne[u][i];
if(v==fa)
continue;
pair<int,int> temp=findAnother(v,u);
if(temp.x!=-1)
ans=temp;
++sum;
}
if(sum!=1 || ans.x==-1)
return mp(-1,-1);
return ans;
}

int solveEasy()
{
map< pair<int,int>,pair<int,int> >::iterator it;
pair<int,int> findu(-1,-1),findv;
REP2(it,f.begin(),f.end())
if(it->y.x==K)
{
findu=it->x;
break;
}
if(findu.x!=-1)
{
findv=findAnother(findu.y,findu.x);
if(findv.x==-1)
return 0;
return (LL)f[findu].y*f[findv].y%Mod*2%Mod;
}
return 0;
}

void update(int& a,int b)
{
a+=b;
if(a>Mod)
a-=Mod;
}

void dpit(int u,int fa)
{
if(hash[u][fa])
return;
hash[u][fa]=1;
int size=f[mp(u,fa)].x;
int F[MAX][MAX],G[MAX][MAX];
int i,v,j,k,l,o;
memset(F,0,sizeof F);
F[0][0]=1;
REP2(i,0,ne[u].size())
{
v=ne[u][i];
if(v==fa)
continue;
memset(G,0,sizeof G);
F[0][0]=1;
dpit(v,u);
REP(j,0,size)
REP(k,0,size-j)
if(F[j][k])
{
int vsize=f[mp(v,u)].x;
REP(l,0,vsize)
REP(o,0,vsize-l)
if(dp[v][u][l][o])
{
LL p=dp[v][u][l][o];
p=p*F[j][k]%Mod;
p=p*C[j+l][l]%Mod;
p=p*C[k+o][o]%Mod;
update(G[j+l][k+o],p);
}
}
memcpy(F,G,sizeof G);
}
memcpy(dp[u][fa],F,sizeof F);
update(dp[u][fa][size][0],f[mp(u,fa)].y);
update(dp[u][fa][0][size],f[mp(u,fa)].y);
}

int solveHard()
{
memset(dp,0,sizeof dp);
memset(hash,0,sizeof hash);
int u;
LL ans=0;
int d=(n-(2*K-n))/2;
REP2(u,0,n)
{
dpit(u,n);
ans+=dp[u][n][d][d];
}
ans%=Mod;
return ans*fac[2*K-n-1]%Mod;
}

int getCount(vector <int> edge1,vector <int> edge2,int k)
{
int i,j;
K=k;
n=edge1.size()+1;
REP2(i,0,n-1)
{
ne[edge1[i]].pb(edge2[i]);
ne[edge2[i]].pb(edge1[i]);
}
preComb();
if(K==1 || n==K)
return fac[n];
REP2(i,0,n)
{
REP2(j,0,ne[i].size())
get(ne[i][j],i);
get(i,n);
}
if(2*K<=n)
return solveEasy();
return solveHard();
}
};



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

历史上的今天

评论

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

页脚

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