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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1562][NOI2009]变换序列  

2014-12-01 20:11:55|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1562: [NOI2009]变换序列

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1192  Solved: 621
[Submit][Status]

Description

[BZOJ1562][NOI2009]变换序列 - Trinkle - n+e

Input

[BZOJ1562][NOI2009]变换序列 - Trinkle - n+e

Output

[BZOJ1562][NOI2009]变换序列 - Trinkle - n+e

Sample Input

5
1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。

Solution

直接二分图匹配。

注意题目中要求字典序最小的答案,所以扫描出边的时候按从小到大的顺序,最外层for的时候从大到小,就能保证字典序最小

Code

/**************************************************************
    Problem: 1562
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:1820 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 20010
int n,et=1,la[N],vis[N],a[N],x,y,i,j,k,tim=1,fa[N],ans[N];
struct E{int to,nxt;}e[N<<2];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
int dfs(int x){
    for(int i=la[x];i;i=e[i].nxt)
    if(vis[e[i].to]!=tim){
        vis[e[i].to]=tim;
        if(fa[e[i].to]==-1|(fa[e[i].to]!=-1&&dfs(fa[e[i].to])))
        return fa[e[i].to]=x,1;
    }
    return 0;
}
int main(){
    memset(ans,-1,sizeof(ans));
    memset(fa,-1,sizeof(fa));
    for(n=F(),i=0;i<n;i++)
    {
        if((k=F())>n/2)return puts("No Answer"),0;
        x=(i+k)%n,y=(i+n-k)%n,x<y?j=x,x=y,y=j:1,add(i,x+n),add(i,y+n);
    }
    for(i=n-1;~i;i--)
    {
        if(tim++,dfs(i)==0)return puts("No Answer"),0;
    }
    for(i=0;i<n;i++)ans[fa[i+n]]=i;
    for(i=0;i<n;i++)if(ans[i]==-1)return puts("No Answer"),0;
    for(i=0;i<n-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[n-1]);
}
  评论这张
 
阅读(73)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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