本文主要是介绍uva 11205 The broken pedometer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：
图片太多，省略了。。。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2146
题目链接
给你一个数据
1
3
1
1 0 1
你猜猜答案是多少啊（哈哈）
答案见解答~
大意：
题目别理解错了，不是让你去掉某一行！（按照去掉某一行的方法解居然tm和样例的结果一样，靠!）
而是给你一个由0和1组成的矩阵，现在让你挑出最少的列数，使得组成的新矩阵能够区分出每一行。
#include <bits/stdc++.h>
using namespace std;
//fstream in,out;
vector<int> mark[15];//把所有1的个数为i的数字都塞进mark[i]当中
bool Hash[32768];//hash判重
int Case,n,p,t;
int ptwo[16];//打表2的n次幂
int res[101];//输入的数据
int TotalOne(int x)//计算一个数的二进制含有1的个数
{int coun=0;while(x){x=x&(x-1);coun++;}return coun;
}
int main()
{ios::sync_with_stdio(false);ptwo[0]=1;for(int i=1;i<=15;i++)ptwo[i]=ptwo[i-1]*2;for(int i=0;i<=32767;++i)mark[TotalOne(i)].push_back(i);//打表cin>>Case;while(Case--){cin>>p>>n;for(int i=1;i<=n;i++){int tmp=0;for(int j=0;j<p;j++){cin>>t;tmp+=t*ptwo[j];}res[i]=tmp;}if(n==1)//注意n==1的情况！！{cout<<0<<endl;continue;}int flag;for(int i=1;i<=p;++i){for(int j=0;j<mark[i].size();j++){memset(Hash,0,sizeof(Hash));flag=0;for(int k=1;k<=n;k++){int tmp=mark[i][j]&res[k];//利用位运算取出一行中的某几位if(Hash[tmp])//判断是否重复，如果重复了就说明取出的列数不合理{flag=1;break;}elseHash[tmp]=true;}if(!flag)//如果hash一个重复的没有就说明可以表示每一行{cout<<i<<endl;break;}}if(!flag)break;}}return 0;
}解答：
这题刚读题的时候读错了，以为是去掉某一行以后找去掉编码最小的那个显像管后依然能够表示每一行，最蛋疼的是样例居然都过了orz。
之前入门了状态压缩动态规划的问题，受到启发。首先先枚举所有二进制，某位为1代表取该列，并记录该二进制1的个数，然后按照1的个数为下标保存在mark当中。
比如mark[3]中会有这样几个二进制数 111,10101…..
然后枚举每个二进制数去取出对应的列，然后用hash表去判断是否重复即可。
答案是0，呵了个呵！
这篇关于uva 11205 The broken pedometer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
