例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 <stdio.h>

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<m;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;

}

习题38

38-1  健康的奶牛

        本题选自洛谷题库 （https://www.luogu.org/problem/ P1460）。

题目描述

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

输入格式

第一行一个整数 v（1≤v≤25），表示需要的维他命的种类数。

第二行 v 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 g（1≤g≤15），表示可用来喂牛的饲料的种数。

下面 g 行，第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。

输出格式

输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

输入样例

4

100 200 300 400

3

50  50  50  50

200 300 200 300

900 150 389 399

输出样例

2 1 3

         （1）编程思路。

        g种饲料，每种有选用和不选用两种状态。一共有2^g种状态，因为g最多为15，因此状态量最多为2¹⁵，可以用二进制位运算枚举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 <stdio.h>

int main()

{

    int v,g;

    scanf("%d",&v);

    int a[26];

    int i,j,k;

    for (i=0;i<v;i++)

       scanf("%d",&a[i]);

    scanf("%d",&g);

    int map[16][26];

    for (i=0;i<g;i++)

      for (j=0;j<v;j++)

         scanf("%d",&map[i][j]);

    int cnt=15,num;

    for (k=1;k<(1<<g);k++)      //  枚举所有状态

    {

       int lowbit=k;

       int b[26];

       for (i=0;i<v;i++)

           b[i]=0;

       int p=0;

       for (i=0; lowbit>0; i++,lowbit>>=1)

          if (lowbit&1)

          {

              p++;

              for (j=0;j<v;j++)

              {

                  b[j]+=map[i][j];

              }

           }

       for (i=0;i<v;i++)

            if (a[i]>b[i]) break;

       if (i>=v && p<cnt)

       {

          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;

}

38-2  海明码

        本题选自洛谷题库 （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 个编码（用十进制表示），要排序，十个一行。

如果有多解，你的程序要输出这样的解：假如把它化为 2^b进制数，它的值要最小。

输入样例

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~2^b-1之间的每个整数进行穷举，将穷举到的当前数i和a数组中已经保存的所有数据进行比较，若i分别与已保存的每个数异或的结果中“1”的个数均不小于d，则保存数据i。

      （2）源程序。

#include <stdio.h>

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<<b);i++)

    {

        for (j=0;j<cnt;j++)

            if (bitCount(i^a[j])<d) break;

        if(j>=cnt)

            a[cnt++] = i;

        if (cnt == n)

            break;

    }

    for (i=0;i<cnt;i++)

    {

        printf("%d ",a[i]);

        if ((i+1)%10==0)

            printf("\n");

    }

    return 0;

}

38-3  彩弹游戏

        本题选自洛谷题库（https://www.luogu.org/problem/ P6200）。

题目描述

奶牛们最近从玩具商那里，买来了一套仿真版彩弹游戏设备（类似于真人 CS）。Bessie 把她们玩游戏的草坪划分成了 N×N 的矩阵（1≤N≤100），同时她算出了她的 K 个对手在草地上的位置（1≤K≤10⁵），现在你需要帮 Bessie 算些东西。

在这个游戏中，奶牛们用一把枪向八个方向中的任意一个方向射出子弹，这八个方向分别是：正北，正南，正东，正西，东北，东南，西北，西南（东北指北偏东45∘，东南，西北，西南同理）。

Bessie 想要你算出，有多少个位置可以让她射到所有对手。特别地，Bessie 可以和她的某一个对手站在同一格子，这时候她可以射到和她同一格子的对手。

输入格式

第一行两个整数 N，K。

接下来 K 行，每行两个整数 Ri和 Ci，表示第 i 头奶牛在第Ri行第Ci列。可能有两个奶牛在同一位置上。

输出格式

输出 Bessie 可以选择的格子数目。

输入样例

4 3

2 1

2 3

4 1

输出样例

5

        （1）编程思路。

        用二重循环对（1,1）~（N,N）这N²个位置进行穷举，若某个位置能射到所有对手，则计数。

       （2）源程序。

#include <stdio.h>

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<tot;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;

}