题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2146
题目大意是求最少的工作正常的LED(一条横杠或竖杠代表一个正常的LED)能够表示出题目给定的所有数字。LED最大数目是15,每一条LED要么亮(正常)要么不亮(不正常),所以最多的情况就是2^15=32768种,我们把所有的情况枚举完毕,得出所需的最少的正常的LED。
这道题目我们可以用二进制的1代表LED工作正常,0代表不正常。所以我们只需要从0开始枚举,一直枚举到2^P-1。即for(i=0;i<=2^P-1;i++),那么对于每一个i,我们都跟题目所给的N个数进行按位&运算(题目给定了N个要表示的数,题目是以二进制给出的,我们可以转换成10进制)。得到了N个&运算的结果,如果这N个数都是不相同的,那么说明这种情况下可以表示出所以的数字,我们再把这种情况下对应LED数目算出来(实际上就是i的二进制有多少个1),枚举完所有的i最后得出最少的LED数目。
之所以要进行按位&运算,就是说当这段LED是正常的并且要表示的数的这段LED是需要亮的时候这段LED才会发亮。&运算的结果可以看作是要表示的数的LED效果,当所有要表示的数的LED效果都不相同时,说明这种情况下是可以把所有的数表示出来的(这个i是合法的)。
题目大意是求最少的工作正常的LED(一条横杠或竖杠代表一个正常的LED)能够表示出题目给定的所有数字。LED最大数目是15,每一条LED要么亮(正常)要么不亮(不正常),所以最多的情况就是2^15=32768种,我们把所有的情况枚举完毕,得出所需的最少的正常的LED。
这道题目我们可以用二进制的1代表LED工作正常,0代表不正常。所以我们只需要从0开始枚举,一直枚举到2^P-1。即for(i=0;i<=2^P-1;i++),那么对于每一个i,我们都跟题目所给的N个数进行按位&运算(题目给定了N个要表示的数,题目是以二进制给出的,我们可以转换成10进制)。得到了N个&运算的结果,如果这N个数都是不相同的,那么说明这种情况下可以表示出所以的数字,我们再把这种情况下对应LED数目算出来(实际上就是i的二进制有多少个1),枚举完所有的i最后得出最少的LED数目。
之所以要进行按位&运算,就是说当这段LED是正常的并且要表示的数的这段LED是需要亮的时候这段LED才会发亮。&运算的结果可以看作是要表示的数的LED效果,当所有要表示的数的LED效果都不相同时,说明这种情况下是可以把所有的数表示出来的(这个i是合法的)。
#include<stdio.h> #include<math.h> #include<stdlib.h> int num[110],temp[110]; int countone(int n)//计算n的二进制表示中有多少个1 { int cnt=0; while(n>0) { if(n%2) cnt++; n/=2; } return cnt; } int cmp(void const *a,void const *b) { return *((int *)a)-*((int *)b); } int alldifferent(int *temp,int N)//判断temp数组中是否所有元素都不相同 { int i; qsort(temp+1,N,4,cmp); for(i=2;i<=N;i++) if(temp[i]==temp[i-1]) return 0; return 1; } int main() { int i,j,lim,T,P,N,Min; scanf("%d",&T); while(T--) { scanf("%d%d",&P,&N); for(i=1;i<=N;i++) { num[i]=0; for(j=1;j<=P;j++) { int tmp; scanf("%d",&tmp); num[i]=num[i]*2+tmp; } } Min=P; lim=pow(2,P); for(i=0;i<lim;i++) { for(j=1;j<=N;j++) temp[j]=num[j]&i; if(alldifferent(temp,N)) { int tmp=countone(i); if(tmp<Min) Min=tmp; } } printf("%d\n",Min); } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 901题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 811题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 723题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1639题目:http://uva.onlinejudge ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 873题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 695题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 659题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 763题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 603题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1126题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 879题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 656题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 873题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 787题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 824题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 745题目:http://uva.onlinejudge.org/i ...
相关推荐
The Privacy Friendly Pedometer stores the user's step count per hour. The user can review the recorded steps in a daily, weekly and monthly report. These reports also display the calculated distance ...
pedometer-master2
Pedometer 手机计步器
runtastic_Pedometer是一个锻炼身体的软件
Android开源项目pedometer-.zip
Wearable computing devices can range providing very specific, limited features like heart rate monitoring and pedometer capabilities to advanced “smart” functions and features similar to those a ...
一个简单,轻量的计步器app,使用硬件传感器计算步数,而且对电池的消耗非常小。
Pedometer 计步器 源代码 加速度传感器采用ADXL330
pedometer sensor sample
计步器上位机APP,兼容飞思卡尔sensor
该计步器使用内置传感器来计算步数。没有GPS跟踪,因此可以大大节省电池。它还会跟踪您消耗的卡路里,步行距离和时间等。所有这些信息将清楚地显示在图表中。 ...无论您的手机放在手,包,口袋或臂章中,即使屏幕被...
Android 开源项目pedometer源码 .rar
Android 开源项目pedometer.zip源码资源下载Android 开源项目pedometer.zip源码资源下载
一个简单,轻量的计步器app,使用硬件传感器计算步数,而且对电池的消耗非常小。对学习计步功能而言是不错的项目。
安卓开发-开源项目pedometer .zip
Pedometer仿微信运动走路步数统计源码
Android程序研发源码开源项目pedometer.zip
Android应用源码之开源项目pedometer .zip
Android应用源码之开源项目pedometer.zip