| The Broken Pedometer |
The Problem
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2146
题目的意思我是理解了，后来直接跟据Sample来考虑问题而可以完全忽略题目的描述，毕竟它给的LED上没有7条以上的管吧？题目要你求的就是至少需要多少条LED可以区分它给你的N条长度为P的symbols，
（WA的想法）
开始用自己的想法去做：将每一个symbol转换成十进制的数，然后将其作为被减数（天真地以为每个数都是独一无二的，但事实就是嘛）从1到P个位置每个位置的数套上权值转为十进制后都试试 减减 相应的被减数， 如果减后发现 N 个"代"被除数都不相同（这时代表可以区分） 所以这时才真正的减去减数，得到的差作为被减数（也就替换之前被减数的位置），如果有至少两个"代"被除数相同，那就找另外一个减数，依次将P个减数都试试。。。
后来提交错了不少次啊，弄了几个小时不得不垂头丧气，不得不找大神帮忙，后来他一眼看出枚举后1y解决了这题然后截图给我看（每次都这样，习惯了，也习惯了郁闷了），发给代码给他看的时候他还说我里面用了贪心，并告诉我最大的时间复杂度是多少，这点我觉得最重要，因为知道了复杂度以为着你解题的思维。而我没这样的分析能力！后来他给了AC的代码给我，还问我知不知道位运算（怪不得后面我搜题解时都是位运算的影子）
正确的思路：
暴力枚举出来，复杂度为2^15*100 不大，具体看代码
代码我撸不过去，只能看别人的了：
http://www.cnblogs.com/staginner/archive/2011/09/02/2163990.html
关于位运算，除了百度百科后还可以看这里：
http://www.cnblogs.com/guifaliao/archive/2013/04/13/3017988.html
#include<stdio.h> #include<string.h> int a[110][20], P, N, hash[100000], fac[20]; int main() { int i, j, k, t, min, sum, num, ok; fac[0] = 1; for(i=1; i<20; i++) fac[i] = 2*fac[i-1]; scanf("%d", &t); while(t--) { scanf("%d%d", &P, &N); for(i=0; i<N; i++) for(j=0; j<P; j++) scanf("%d",&a[i][j]); min=1000000000; for(i=0; i<(1<<P); i++) {//那么多种可能体现在 1 的数量和 1 所在的位置上了 memset(hash,0, sizeof(hash)); num=0; for(k=0; k<P; k++) if(i&(1<<k)) num++; ok=1; for(j=0; j<N; j++) { sum=0; for(k=0; k<P; k++) if(i & (1<<k)) sum += fac[k] * a[j][k]; if(hash[sum] == 0) hash[sum] = 1; else { ok=0; break; } } if(ok && num < min) min = num; } printf("%d\n",min); } return 0; }
附上Lys的AC代码：
View Code
WA的经历，记得是超过了五个小时从我代码里面找错，后来没了信心才不得不找厉害的人帮忙的，不过从大神中还算学到了东西，让我知道了自己一直进步那么慢的原因，努力吧，孩子，成长和生活就是这样过来的，记得保存就是了，下面是WA的代码
WA
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<math.h> 4 #include<string.h> 5 int matrix[110][20]; 6 int digitleft[110], digitright[110]; 7 8 int main() 9 { 10 11 int i, j, n, T, p, cnt, flag, temp, sum1, sum2, sum, rate; 12 scanf("%d", &T); 13 while(T--) 14 { 15 memset(digitleft, 0, sizeof(digitleft)); 16 memset(digitright, 0, sizeof(digitright)); 17 scanf("%d%d", &p, &n); 18 for(i=0; i<n; ++i) 19 { 20 for(j=0; j<p; ++j) 21 { 22 scanf("%d", &matrix[i][j]); 23 digitleft[i] = digitleft[i]*2 + matrix[i][j]; 24 digitright[i] = digitright[i]*2 + matrix[i][j]; 25 } 26 } 27 28 sum1 = 0; 29 for(cnt=p-1; cnt>=0; --cnt) 30 { 31 flag = 0; 32 rate = (int)pow(2.0, (double)(p-1-cnt)); 33 for(i=0; i<n-1; i++) 34 { 35 temp = digitleft[i]-matrix[i][cnt]*rate; 36 for(j=i+1; j<n; ++j) 37 if(temp == digitleft[j]-matrix[j][cnt]*rate) 38 { 39 flag = 1; 40 break; 41 } 42 if(flag) break; 43 } 44 if(flag == 0) 45 { 46 for(i=0; i<n; ++i) 47 digitleft[i] = digitleft[i]-matrix[i][cnt]*rate; 48 sum1++; 49 } 50 } 51 52 sum2 = 0; 53 for(cnt=0; cnt<p; ++cnt) 54 { 55 flag = 0; 56 rate = (int)pow(2.0, (double)(p-1-cnt)); 57 for(i=0; i<n-1; i++) 58 { 59 temp = digitright[i]-matrix[i][cnt]*rate; 60 for(j=i+1; j<n; ++j) 61 if(temp == digitright[j]-matrix[j][cnt]*rate) 62 { 63 flag = 1; 64 break; 65 } 66 if(flag) break; 67 } 68 if(flag == 0) 69 { 70 for(i=0; i<n; ++i) 71 digitright[i] = digitright[i]-matrix[i][cnt]*rate; 72 sum2++; 73 } 74 } 75 sum = sum1 > sum2 ? sum1 : sum2; 76 if(n == 1) printf("0\n"); 77 else printf("%d\n", p-sum); 78 } 79 return 0; 80 }
