例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("%dn",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种饲料,每种有选用和不选用两种状态。一共有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 <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 个编码(用十进制表示),要排序,十个一行。

如果有多解,你的程序要输出这样的解:假如把它化为 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 <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≤105),现在你需要帮 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)这N2个位置进行穷举,若某个位置能射到所有对手,则计数。

       (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("%dn",ans);

    return 0;

}

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/cs-whut/p/15647073.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!

相关课程