USACO2.1 Hamming Codes【枚举+二进制处理+输出格式+题意理解】

这道题加了2个看起来奇奇怪怪的$tag$

1.输出格式：不得不说这个格式输出很恶心，很像$UVA$的风格，细节稍微处理不好就会出错。

因为这个还$WA$了一次：

 　　int t=,m=n;

     while(m>=)

     {

         for(int i=t+;i<=t+;i++)

             printf("%d ",ans[i]);

         printf("%d\n",ans[t+]);

         t+=;

         m-=;

     }

     if(m==) return ;//一定要注意这个东西!!!

     for(int i=t+;i<n;i++)

         printf("%d ",ans[i]);

     printf("%d\n",ans[n]);

就是刚刚好个数是整十数的时候，$while$外面的循环是没有用的，循环虽然进不去，外面的$ans[n]$却能被输出，所以就会错。

其实$m$有点多余来着，只需要$t$控制就可以了，不过这么写，会直观一点吧。

2.题意理解：这道题题目描述也比较唬人，搞了好多进制转化的东西出来，然而并没有什么用，因为即使是在不同的进制下，数的大小是不会变的。

所以这个东西就是来唬人的，直接用10进制从小到大枚举就可以了。

所以题意就是求尽量小的$n$个数，使两两之间二进制不相同的位数大于等于$d$就可以了。（怎么突然想到线性基误）

从小到大枚举，然后依次与前面的数判断不相同的位数是否大于等于$d$，如果有一个数不满足，就不能把这个数加进去。

判断2个数的二进制不相同的位数，只需要将这两个数异或一下，再求异或的结果中有多少个1就可以了（异或就是那一位两个不相同就是1，相同就是0）。

 /*

 ID: Starry21

 LANG: C++

 TASK: hamming

 */

 #include<iostream>

 #include<string>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define N 70

 #define ll long long

 #define INF 0x3f3f3f3f

 int n,b,d;

 int ans[N];

 int bitcnt(int x)

 {

     int res=;

     while(x)

     {

         x&=(x-);

         res++;

     }

     return res;

 }

 int check(int x,int y)

 {

     int k=x^y;

     return bitcnt(k);

 }

 int main()

 {

     //freopen("hamming.in","r",stdin);

     //freopen("hamming.out","w",stdout);

     scanf("%d %d %d",&n,&b,&d);

     int k=,cnt=;

     ans[]=;

     while(cnt<n)

     {

         bool f=;

         for(int i=;i<=cnt;i++)

             if(check(ans[i],k)<d)

             {

                 f=;

                 break;

             }

         if(!f) ans[++cnt]=k;

         k++;

     }

     int t=,m=n;

     while(m>=)

     {

         for(int i=t+;i<=t+;i++)

             printf("%d ",ans[i]);

         printf("%d\n",ans[t+]);

         t+=;

         m-=;

     }

     if(m==) return ;//一定要注意这个东西!!!

     for(int i=t+;i<n;i++)

         printf("%d ",ans[i]);

     printf("%d\n",ans[n]);

     return ;

 }

Code

巴特西

USACO2.1 Hamming Codes【枚举+二进制处理+输出格式+题意理解】

最新文章

热门文章