本文主要是介绍11205 - The broken pedometer,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:11205 - The broken pedometer
题目大意:就是最少几盏灯可以表示所给的所有数字,这些灯可以不连续。
解题思路:枚举出每一盏灯的好坏情况,好的灯的话就说明可以亮,然后这题别人和我说的是巧用二进制位运算,后面发现真的很方便也很快。但是我做的不是这样的,=比较麻烦,用数组保存灯的状态,然后判断的时候逐个数相与, 保存在数组中,再转换成十进制,这样确实麻烦,用二进制的位运算的话本来的状态就是十进制的,只需要转换题目给你的那些数的表示数组, 灯的状态就不用了。
#include<stdio.h>
#include<string.h>const int N = 105;
const int M = 20;
int t, n, p, min;
int str[N];
int s[N][M];int find(int *);
void build(int * A, int cur, int n) {int i;if(cur != n) {for(i = 0; i < 2; i++) {A[cur] = i;build(A, cur + 1, n);}}else{if(find(A)) {int count = 0;for(i = 0; i < p; i++)if(A[i])count++;if(count < min)min = count;}}}int find(int *A) {int i, j;int ans[50000], s2[N][M];for(i = 0; i < n; i++)for(j = 0; j < p; j++)s2[i][j] = s[i][j];memset(ans, 0, sizeof(ans));for(i = 0; i < n; i++) {int sum = 0 ;for(j = 0; j < p; j++) s2[i][j] = (s2[i][j] & A[j]);for(j = 0; j < p; j++) sum = sum * 2 + s2[i][j];if(!ans[sum])ans[sum]++;elsereturn 0; } return 1;
}int main() {scanf("%d", &t); while(t--) {scanf("%d%d", &p, &n);int i, j;for(i = 0; i < n; i++)for(j = 0; j < p; j++)scanf("%d", &s[i][j]);min = 20;build(str, 0, p);printf("%d\n", min);}return 0;
}
这篇关于11205 - The broken pedometer的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!