C语言程序设计100例之（38）：涂国旗
例38 涂国旗
题目描述
某国法律规定，只要一个由 N×M 个小方块组成的旗帜符合如下规则，就是合法的国旗。
从最上方若干行（至少一行）的格子全部是白色的；
接下来若干行（至少一行）的格子全部是蓝色的；
剩下的行（至少一行）全部是红色的；
现有一个棋盘状的布，分成了 N 行 M 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。
小a很懒，希望涂最少的格子，使这块布成为一个合法的国旗。
输入格式
第一行是两个整数 N,M。
接下来 N 行是一个矩阵，矩阵的每一个小方块是W（白），B（蓝），R（红）中的一个。
输出格式
一个整数，表示至少需要涂多少块。
输入样例
4 5
WRWRW
BWRWB
WRWRW
RWBWR
输出样例
11
（1）编程思路。
定义数组int w[51]，b[51]，r[51]；数组元素w[i]、b[i]和r[i]分别表示把前i行全部涂成白色、蓝色或红色所需要涂的格子数。
设蓝色所在的行是第i行到第j行，则第1行到第i-1行是白色，第j+1行到第n行是红色，此时需要涂的格子数为w[i-1]+b[j]-b[i-1]+r[n]-r[j]。
对蓝色所在的行i~j进行穷举，显然2≤i≤n-1，i≤j≤n-1。对穷举的每种情况找出所需要涂的格子数（w[i-1]+b[j]-b[i-1]+r[n]-r[j]）的最小值即可。
（2）源程序。
#include
int main()
{
int w[51]={0},b[51]={0},r[51]={0};
int n,m;
scanf("%d%d",&n,&m);
char s[51];
int i,j;
for (i=1;i<=n;i++)
{
scanf("%s",s);
for (j=0;j { if (s[j]!='W') w[i]++; if (s[j]!='B') b[i]++; if (s[j]!='R') r[i]++; } w[i]+=w[i-1]; b[i]+=b[i-1]; r[i]+=r[i-1]; } int ans=50*50; for (i=2;i<=n-1;i++) for (j=i;j<=n-1;j++) { int t; t=w[i-1]+b[j]-b[i-1]+r[n]-r[j]; if (ans>t) ans=t; } printf("%d\n",ans); return 0; } 本题选自洛谷题库 （https://www.luogu.org/problem/ P1460）。 题目描述 农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。 给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。 维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。 输入格式 第一行一个整数 v（1≤v≤25），表示需要的维他命的种类数。 第二行 v 个整数，表示牛每天需要的每种维他命的最小量。 第三行一个整数 g（1≤g≤15），表示可用来喂牛的饲料的种数。 下面 g 行，第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。 输出格式 输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。 如果有多个解，输出饲料序号最小的（即字典序最小）。 输入样例 100 200 300 400 50 50 50 50 200 300 200 300 900 150 389 399 输出样例 2 1 3 （1）编程思路。 g种饲料，每种有选用和不选用两种状态。一共有2g种状态，因为g最多为15，因此状态量最多为215，可以用二进制位运算枚举g种饲料的各种状态组合，检查每种状态组合是否满足牛所需的最低的维他命量，并进行相应的更新处理。 例如，当g=3时，有3种饲料（设为a,b,c这3种），8种组合状态，其中0（000）表示三种饲料均不选用，1（001）表示只选用饲料c，2（010）表示只选用饲料b，3（011）表示选用饲料b和c，4（100）表示选用饲料a，…，7（111）表示3种饲料全部选用。 （2）源程序。 #include int main() { int v,g; scanf("%d",&v); int a[26]; int i,j,k; for (i=0;i scanf("%d",&a[i]); scanf("%d",&g); int map[16][26]; for (i=0;i for (j=0;j scanf("%d",&map[i][j]); int cnt=15,num; for (k=1;k<(1< { int lowbit=k; int b[26]; for (i=0;i b[i]=0; int p=0; for (i=0; lowbit>0; i++,lowbit>>=1) if (lowbit&1) { p++; for (j=0;j { b[j]+=map[i][j]; } } for (i=0;i if (a[i]>b[i]) break; if (i>=v && p { cnt=p; num=k; } } printf("%d ",cnt); for (i=1; num>0;i++,num>>=1) if (num&1) printf("%d ",i); printf("\n"); return 0; } 本题选自洛谷题库 （https://www.luogu.org/problem/ P1461）。 题目描述 给出 n、b、d，要求找出n个由 0、1组成的编码，每个编码有b位，使得两两编码之间至少有 d个单位的 “Hamming距离”。 “Hamming距离”是指对于两个编码，它们二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234（十六进制数） 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 不同位 xxx xx 因为有五个位不同，所以“Hamming距离”是 5。 输入格式 一行，包括 n，b，d。1≤n≤64，1≤b≤8，1≤d≤7。 输出格式 n 个编码（用十进制表示），要排序，十个一行。 如果有多解，你的程序要输出这样的解：假如把它化为 2b进制数，它的值要最小。 输入样例 16 7 3 输出样例 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127 （1）编程思路。 由于二进制数位的异或运算具有一个特点：相同的数位异或为0，不同的数位异或为1。因此，两个数的“Hamming距离”实际就是两个数异或后，结果中二进制数位“1”的个数。 定义数组int a[256];存放满足“Hamming距离”大于或等于d的数。初始时a[0]=0，表示0是保存的第1个数。 用循环对1~2b-1之间的每个整数进行穷举，将穷举到的当前数i和a数组中已经保存的所有数据进行比较，若i分别与已保存的每个数异或的结果中“1”的个数均不小于d，则保存数据i。 （2）源程序。 #include int bitCount(int x) { int cnt=0; while (x!=0) { cnt++; x=x&(x-1); } return cnt; } int main(void) { int n,b,d; scanf("%d%d%d",&n,&b,&d); int a[256]; int cnt=1; a[0]=0; int i,j; for (i=1;i<(1< { for (j=0;j if (bitCount(i^a[j]) if(j>=cnt) a[cnt++] = i; if (cnt == n) break; } for (i=0;i { printf("%d ",a[i]); if ((i+1)%10==0) printf("\n"); } return 0; } 本题选自洛谷题库（https://www.luogu.org/problem/ P6200）。 题目描述 奶牛们最近从玩具商那里，买来了一套仿真版彩弹游戏设备（类似于真人 CS）。Bessie 把她们玩游戏的草坪划分成了 N×N 的矩阵（1≤N≤100），同时她算出了她的 K 个对手在草地上的位置（1≤K≤105），现在你需要帮 Bessie 算些东西。 在这个游戏中，奶牛们用一把枪向八个方向中的任意一个方向射出子弹，这八个方向分别是：正北，正南，正东，正西，东北，东南，西北，西南（东北指北偏东45°，东南，西北，西南同理）。 Bessie 想要你算出，有多少个位置可以让她射到所有对手。特别地，Bessie 可以和她的某一个对手站在同一格子，这时候她可以射到和她同一格子的对手。 输入格式 第一行两个整数 N，K。 接下来 K 行，每行两个整数 Ri和 Ci，表示第 i 头奶牛在第Ri行第Ci列。可能有两个奶牛在同一位置上。 输出格式 输出 Bessie 可以选择的格子数目。 输入样例 4 3 2 1 2 3 4 1 输出样例 （1）编程思路。 用二重循环对（1,1）~（N,N）这N2个位置进行穷举，若某个位置能射到所有对手，则计数。 （2）源程序。 #include int abs(int a) { return a>=0?a:-a; } int main() { int n,k; scanf("%d%d",&n,&k); int i,x,y; int tot=0,ans=0; int v[101][101]={0}; int a[10001][2]; for (i=1;i<=k;i++) { scanf("%d%d",&x,&y); if (!v[x][y]) { v[x][y]=1; a[tot][0]=x; a[tot][1]=y; tot++; } } for (x=1;x<=n;x++) for (y=1;y<=n;y++) { int f=1; for (i=0;i { int dx=abs(x-a[i][0]); int dy=abs(y-a[i][1]); if (dx!=dy && dx!=0 && dy!=0) { f=0; break; } } ans+=f; } printf("%d\n",ans); return 0; }习题38
38-1 健康的奶牛
38-2 海明码
38-3 彩弹游戏