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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

tyvj P1865  

2012-08-17 08:55:47|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
其实本题很水

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
using namespace std;

typedef long long LL;
const int MAX=10000+10;
const int MAXN=10;
const int MAXL=20;

int n,k,num[MAXN],all;
pair<LL,LL> val[MAX];
int map[MAXN][MAXN],hash[MAXN],c,ans[MAXN][MAXN];
LL p10[MAXL];

int check(LL a)
{
int left=1,right=n,mid;
while(left<right)
{
mid=(left+right+1)>>1;
if(a<val[mid].first)right=mid-1;
else left=mid;
}
return val[left].first<=a && a<=val[right].second;
}

void dfs(int u)
{
int i,j,k;
if(u==10)
{
for(i=1;i<=9;++i)
for(j=1;j<=9;++j)
if(hash[i]==hash[j] && map[i][j])
return;
int flag=1;
for(i=1;i<=all;++i)
for(j=1;j<=9;++j)
{
if(hash[j]!=all)
{
for(k=1;k<=9 && flag;++k)
if(hash[k]==all && map[j][k])
flag=0;
}
if(flag)return;
}
/*
for(i=1;i<=9;++i)
for(j=1;j<=9;++j)
if(hash[i]==hash[j])
cout<<map[i][j]<<endl;
*/
for(i=1;i<=all;++i)
{
//cout<<i<<endl;
for(j=1;j<=9;++j)
if(hash[j]==i)
cout<<j;
cout<<endl;
}
exit(0);
}else
{
for(i=1;i<=all;++i)
{
hash[u]=i;
dfs(u+1);
}
++all;
hash[u]=all;
dfs(u+1);
--all;
}
}

int main()
{
freopen("laser.in","r",stdin);freopen("laser.out","w",stdout);
int i,j,l,o;
cin>>n>>k;
for(i=1;i<=n;++i)
{
cin>>val[i].first>>val[i].second;
}
p10[0]=1;
for(i=1;i<=20;++i)
p10[i]=p10[i-1]*10;
sort(val+1,val+n+1);
for(i=1;i<=k;++i)
{
for(j=1;j<=n;++j)
{
LL u=(val[j].second/p10[i-1])%10;
LL d=(val[j].first/p10[i-1])%10;
int flag=((val[j].second-val[j].first)/p10[i])>0;
if(flag)
{
for(l=u+1;l<=9;++l)
{
LL a=val[j].second - (i>1?val[j].second % p10[i-1]:0 )+(p10[i-1]-1);
if( !check( a + (l - u) * p10[i-1] ) )
for(o=1;o<u;++o)
map[o][l]=map[l][o]=1;
a=val[j].second + (l - u ) * p10[i-1];
if(!check(a))
map[l][u]=map[u][l]=1;
}
for(l=d-1;l>=1;--l)
{
LL a=val[j].first - (i>1?val[j].first % p10[i-1]:0 );
//cout<<a<<endl;
if( !check(a + (l - d ) * p10[i-1] ) )
for(o=9;o>d;--o)
{
map[o][l]=map[l][o]=1;
}
a=val[j].first + (l - d ) * p10[i-1];
if(!check(a))
{
map[l][d]=map[d][l]=1;
}
}
}
else if(!flag && d!=u)
{
for(l=u;l<=9;++l)
{
LL a=val[j].second - (i>1?val[j].second % p10[i-1]:0 )+(p10[i-1]-1);
if( !check( a + (l - u) * p10[i-1] ) )
for(o=d;o<u;++o)
{
map[o][l]=map[l][o]=1;
}
a=val[j].second + (l - u ) * p10[i-1];
if(!check(a))
{
map[l][u]=map[u][l]=1;
}
}
for(l=d;l>=1;--l)
{
LL a=val[j].first - (i>1?val[j].first % p10[i-1]:0 );
if( !check(a + (l - d ) * p10[i-1] ) )
for(o=u;o>d;--o)
{
map[o][l]=map[l][o]=1;
}
a=val[j].first + (l - d ) * p10[i-1];
if(!check(a))
{
map[l][d]=map[d][l]=1;
}
}
}
else
{
for(l=1;l<=9;++l)
{
if( !check(val[j].first + (l - d ) * p10[i-1] ) )
{
for(o=u;o>=d;--o)
{
map[o][l]=map[l][o]=1;
}
}
}
for(l=1;l<=9;++l)
{
if( !check(val[j].second + (l - u ) * p10[i-1] ) )
{
for(o=u;o>=d;--o)
{
map[o][l]=map[l][o]=1;
}
}
}
}
}
}

//for(i=1;i<=9;++i,cout<<endl)
// for(j=1;j<=9;++j)
// cout<<map[i][j];

dfs(1);
}




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

历史上的今天

评论

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

页脚

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