Written by razrlele
18:01 February 24, 2015
题意就是求最少只用几个LED灯就可以区分给出的所有的LED,这里关键就是用到状态压缩和与运算。
比如LED灯一开始是:
1 2 |
0 0 1 1 |
如果只用第一个灯和第二个灯的话状态就可以用一个二进制数表示(1表示用,0表示不用):
1 2 |
1 1 0 0 |
然后确定了要用哪些灯过后灯就变成了
1 2 |
0 0 1 1 & 1 1 0 0 = 0 0 0 0 |
每一个灯与状态码进行与运算过后再来判断彼此只有能否区分开来,倘若能即符合要求,最后求出需要开启最小数目的灯数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
/******************************************************** * File Name: uvaoj11205.cpp * Author: razrLeLe * Mail: razrlele@gmail.com * Homepage: https://yueyu.io * Created Time: Mon 23 Feb 2015 10:54:14 PM CST ******************************************************/ #include "vector" #include "set" #include "deque" #include "queue" #include "algorithm" #include "functional" #include "iostream" #include "cstdio" #include "cmath" #include "cstdlib" #include "string" #include "cstring" #include "string.h" #include "map" #include "cctype" #include "list" #include "stack" using namespace std; #define INF 0x3f3f3f3f #define LOCAL int P, N; int symbol[105]; bool isOk(int a, int b, int i) { a = a&i; b = b&i; if(a == b) return false; return true; } int getB(int a) { int ans = 1; while(ans < a) ans *= 2; return ans; } int getLED(int a) { int s = 0; while(a) { if(a&1) s++; a >>= 1; } return s; } int main() { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int numcase; scanf("%d", &numcase); while(numcase--) { int i, j; int tmp; scanf("%d %d", &P, &N); for( i = 0; i < N; i++) { symbol[i] = 0; for( j = 0; j < P; j++) { scanf("%d", &tmp); symbol[i] += tmp*(1<<j); }//每一个LED灯也用一个二进制数来存储 } int Lnum = P; int begin = getB(P); for(int i = begin; i < (1<<P+1); i++) { int tmp = getLED(i); int same = 0; for(int u = 0; u < N; u++) for(int v = u+1; v < N; v++) { if(!isOk(symbol[u], symbol[v], i)) { same = 1; break; } } if(!same && Lnum > tmp) Lnum = tmp; } printf("%d\n", Lnum); } return 0; } |