UVAOJ11205 | 哈喽哈咯

Written by razrlele 18:01 February 24, 2015

题意就是求最少只用几个LED灯就可以区分给出的所有的LED，这里关键就是用到状态压缩和与运算。

比如LED灯一开始是：

0 0 1 1

如果只用第一个灯和第二个灯的话状态就可以用一个二进制数表示（1表示用，0表示不用）：

1 1 0 0

然后确定了要用哪些灯过后灯就变成了

1 2	0 0 1 1 & 1 1 0 0 = 0 0 0 0

每一个灯与状态码进行与运算过后再来判断彼此只有能否区分开来，倘若能即符合要求，最后求出需要开启最小数目的灯数。

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;

}