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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

Codeforces Round 124  

2012-06-16 00:03:42|  分类: CF |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       这次CF差点又悲剧了,最后时刻总算找出了B的bug交了上去,涨回了一点rating,不过离黄还是很有一段距离,继续努力!!!!

       直接从后往前贪心,只把大于等于前一个加入的字符的字符加到答案里,从前往后用队列维护也行。

       唉,此题卡了整场比赛,一开是直接复制了9次暴力BFS,没多久就被hack了,最后还5分钟的时候才想到正确的算法,改了过来,真是硬伤!如果某个点可以被访问两次,并且对应的真正坐标是不一样的,既x1%n=x2%n,y1%m=y2%m且x1!=x2或y1!=y2。那么就有解,不然无解,于是直接DFS或者是BFS就行了。

       这题比赛的时候看了一眼觉的好神,就没想了。其实解法不难想到,首先我们把x坐标最小且y坐标最小的点A取出来,剩下的n-1个点相对于A极角排序,然后我们先把节点1分配给A,假设节点1有m个子树,对应的结点个数为c1,c2,……,cm。我们就把n-1个点按极角序分成m个部分,分别和m个子树对应,然后递归到子树里去,这样可以保证子树和子树之间是没有交点的,并且最后每个点都对应一个节点。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 1600
using namespace std;
struct point{int id,x,y;}P[N];
int n,vis[N],f[N];
vector
<int> Adj[N];
int ans[N];
bool cmp(const point &a,const point &b){return 1ll*(a.x-P[0].x)*(b.y-P[0].y)>1ll*(b.x-P[0].x)*(a.y-P[0].y);}
void dfs(int rt){
f
[rt]=vis[rt]=1;
for(int i=0;i<Adj[rt].size();i++)
if(!vis[Adj[rt][i]]){
dfs
(Adj[rt][i]);
f
[rt]+=f[Adj[rt][i]];
}
}
void go(int l,int r,int rt){
vis
[rt]=1;
for(int i=l+1;i<=r;i++)
if((P[i].x<P[l].x||(P[i].x==P[l].x)&&P[i].y<P[l].y)) swap(P[l],P[i]);
P
[0]=P[l];
ans
[P[0].id]=rt;
sort
(P+l+1,P+r+1,cmp);
int v,p=l+1;
for(int i=0;i<Adj[rt].size();i++)
if(!vis[v=Adj[rt][i]]){
go
(p,p+f[v]-1,v);
p
+=f[v];
}
}
int main(){
scanf
("%d",&n);
for(int i=1;i<n;i++){
int a,b;
scanf
("%d%d",&a,&b);
Adj[a].push_back(b);
Adj[b].push_back(a);
}
for(int i=1;i<=n;i++){
scanf
("%d%d",&P[i].x,&P[i].y);
P
[i].id=i;
}
dfs
(1);
memset
(vis,0,sizeof(vis));
go
(1,n,1);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}


       字符串hash,从来没用过这么神的东西,正好趁着个机会学习了一下- -|||。给字符串S[0,n-1],进行hash:                                                                                val=sum{S[i]*P^i},0<=i<=n-1
其中P是一个大质数,貌似冲突的概率非常的低,具体就不清楚了。回到这个题来,我们先把字符串加1,这样好处理一些。要求没有长度大于等于d的回文串,其实只需要保证没有d和d+1的回文串就行了,于是我们首先从左到右的扫描,如果到某一位的时候出现了坏回文,我们就把这一位加1,直到没有坏回文为止,最多只用加两次,所以后面都是a、b或c了。怎么快速判断有没有坏回文呢?我们扫描的时候维护当前串和其反串的hash值就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#define N 400009
#define P 1000000007
using namespace std;
char s[N],r[N];
int p[N],h[N],rh[N];
int n,m;
int ok(int i,int x){
if(++i<x) return 1;
return ((rh[i]-rh[i-x]*p[x])*p[i-x])!=(h[i]-h[i-x]);
}
int go(int d,int t){
if(d==n) return puts(r),1;
for(r[d]=(t?s[d]:'a');r[d]<='z';r[d]++){
h
[d+1]=h[d]+r[d]*p[d];
rh
[d+1]=rh[d]*P+r[d];
if(ok(d,m)&&ok(d,m+1)&&go(d+1,t&&(r[d]==s[d]))) return 1;
}
return 0;
}
int main(){
scanf
("%d%s",&m,s);
int i=(n=strlen(s))-1;
for(;i>=0&&s[i]=='z';i--) s[i]='a';
if(i<0) return puts("Impossible"),0;
s
[i]++;
p
[0]=1;
for(int i=1;i<N;i++) p[i]=p[i-1]*P;
if(!go(0,1)) puts("Impossible");
return 0;
}


       要使得K个传送门都连通,只要求这K个传送门的最小生成树就行了,其中边权为两传送门之间的最短路。这和steiner树不一样,因为我们只能在传送门之间相互瞬间传送。于是这题的关键就是怎么快速的把传送门之间的边权求出来。直接全算出来总共有K*(K-1)/2条边,O(1)遍历一遍就超时了,不可行。其实我们没必要全算出来,很多边都是废边,真正有用的只有K-1条。对于每一个传送门只需要找离他最近的一个传送门连边,加到队列去就行了,但是这也不好求。我们可以用一种间接的方法,先用dijkstra算出d[i]和p[i],d[i]表示i点离最近的一个传送门p[i]的距离。对于每条边a-b,我们建一条p[a]-p[b],权为d[a]+w[a,b]+d[b]边的加到队列中,最后所有的m条边里并然包含了我们想要的K-1条边。因为假设x,y是两个离的最近的传送门,那么在x->y的路径上,p[i]必然只变一次,并且是从x变到y,于是m条边中必然包含了我们想要的所有的边,这个题就搞出来了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define N 100009
#define ll long long
using namespace std;

struct edge{int v,w;edge *nxt;}E[N<<1],*Adj[N],*cur;
struct edge2{int u,v;ll w;}EE[N<<1];
struct state{int v;ll c;};
struct cmp{bool operator ()(const state &a,const state &b){return a.c>b.c;}};

int n,m,K;
int pot[N],anc[N],f[N];
ll d
[N];

bool cmp2(const edge2 &a,const edge2 &b){return a.w<b.w;}
void addedge(int u,int v,int w){cur->v=v,cur->w=w,cur->nxt=Adj[u],Adj[u]=cur++;}
int find(int a){return a==anc[a]?a:anc[a]=find(anc[a]);}
void init_anc(){for(int i=0;i<=n;i++) anc[i]=i;}
bool union_set(int a,int b){a=find(a),b=find(b);if(a==b) return false;anc[a]=b;return true;}

void dij(){
state p
,t;
priority_queue
<state,vector<state>,cmp> Q;
memset
(d,-1,sizeof(d));
for(int i=1;i<=n;i++)
if(pot[i])
p
.v=f[i]=i,p.c=d[i]=0,Q.push(p);
while(!Q.empty()){
p
=Q.top();
Q
.pop();
if(p.c!=d[p.v]) continue;
for(edge *i=Adj[p.v];i;i=i->nxt)
if(d[i->v]==-1||p.c+i->w<d[i->v]){
f
[t.v=i->v]=f[p.v];
t
.c=d[i->v]=p.c+i->w;
Q
.push(t);
}
}
}

int main(){
cur
=E;
scanf
("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf
("%d%d%d",&a,&b,&c);
addedge
(a,b,c);
addedge
(b,a,c);
}
scanf
("%d",&K);
for(int i=1,t;i<=K;i++) scanf("%d",&t),pot[t]=1;
dij
();
int cnt=0;
for(int i=1;i<=n;i++)
for(edge *j=Adj[i];j;j=j->nxt)
if(f[i]!=f[j->v])
EE
[cnt].u=f[i],EE[cnt].v=f[j->v],EE[cnt++].w=d[i]+d[j->v]+j->w;
sort
(EE,EE+cnt,cmp2);
ll ans
=d[1];
init_anc
();
for(int i=0,c=K-1;c&&i<cnt;i++)
if(union_set(EE[i].u,EE[i].v))
c
--,ans+=EE[i].w;
cout
<<ans<<endl;
return 0;
}


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

历史上的今天

评论

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

页脚

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