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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2461  

2010-06-16 13:27:13|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目是说求一个满足条件的字典序最小的二进制序列,开始没什么想法,写了个模拟看看结果
#include<cstdio>
#include<cstring>
int c[100],a[100][100];
int n,m,l,k,p;
int main(){
scanf("%d",&p);
for(int i=0;i<1<<(p-1);i++){
l=p-1;k=0;
memset(c,0,sizeof(c));
int temp=i;
while(temp){
c[k++]=temp&1;
temp>>=1;
}
for(int j=1;j<=l;j++){
for(int j0=1;j0<=l;j0++)
a[j-1][j0-1]=c[(j*j0)%(l+1)-1];
}
int mark=true;
for(int j=1;j<l;j++){
int kk=0;
if(a[0][0]!=a[j][0])
kk++;
for(int j0=1;j0<l;j0++)
if((a[0][j0]+kk)%2!=a[j][j0]){
mark=false;
break;
}
if(!mark)
break;
}
if(mark){
for(int i=0;i<l;i++)
printf("%d",c[i]);
printf("\n");
}
}
return 0;
}
于是发现都是有四个答案,注意到如果某序列是Magic Bitstrings,那么他的补也是Magic Bitstrings,所以实际上答案只有两个,去掉全为0的那个就只有一个了。
然后,再注意到矩阵,其实每一行都是和第一行形成了循环置换群,设每一个轮换中的生成元是a,对于每一个元素a^i,则a^i要么和a^(i-1)相等,要么不等,也就是说一个轮换中要么都相等,要么指数指数为奇数的都相等,偶数的都相等,所以让奇数的为1,偶数的为0即可,所有的偶数其实就是二次剩余的那些
#include<cstdio>
#include<cstring>
int a[100010],n,k;
int aa(int x,int y,int z){
long long m=((long long)x*y)%z;
return (int)m;
}
int main(){
while(scanf("%d",&n),n){
memset(a,0,sizeof(a));
if(n==2){
printf("Impossible\n");
continue ;
}
for(int i=1;i<n;i++)
a[aa(i,i,n)]=1;
for(int i=1;i<n;i++)
if(a[i])
printf("0");
else printf("1");
printf("\n");
}
return 0;
}

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

历史上的今天

评论

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

页脚

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