主要内容 #

1. 统计方形
2. 涂国旗

1. 统计方形 #

1.1 问题描述
有一个 nxm 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。
1.2 输入格式
一行，两个正整数 n,m（n≤5000,m≤5000）。
1.3 输出格式
一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。
1.4 输入输出样例
输入
2 3
输出
8 10
1.5 分析
矩形包含长方形和正方形，因此可以算出棋盘有多少个矩形，再找出有多少个正方形，两个相减就可以算出长方形的个数。这里枚举的方法比较多，可以枚举点，也可以枚举边。
这里以枚举边为例。横向所有可能的边长为((n + 1) * n) / 2，纵向所有可能的边长为((m + 1) * m) / 2，则棋盘包含的所有的矩形个数为两式相乘。再计算正方形的个数，正方形最大边长一定是m和n中的较小的那一个，于是再循环枚举所有可能的正方形边长，即1、2、3、…、min(m，n)，再相减就能得到长方形的个数。
1.6 参考代码

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long n, m;
    long long seq = 0;  //正方形个数
    long long rec, sum;  //长方形个数、矩形总个数
    cin >> n;
    cin >> m;
    long long x = n;
    long long y = m;
    sum = (((n + 1) * n) / 2) * (((m + 1) * m) / 2);
    for(int i = 1; i <= min(m, n); i++)
    {
        seq += x * y;
        x--;
        y--;
    }
    rec = sum - seq;
    cout << seq << ' ' << rec << endl;
    return 0;
}

2.涂国旗 #

2.1 问题描述
某国法律规定，只要一个由 N×M 个小方块组成的旗帜符合如下规则，就是合法的国旗。

1. 从最上方若干行（至少一行）的格子全部是白色的；
2. 接下来若干行（至少一行）的格子全部是蓝色的；
3. 剩下的行（至少一行）全部是红色的；

现有一个棋盘状的布，分成了 N行 M列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。
小a很懒，希望涂最少的格子，使这块布成为一个合法的国旗。
2.2 输入格式
第一行是两个整数 N,M（N,M≤50）。
接下来 N 行是一个矩阵，矩阵的每一个小方块是W（白），B（蓝），R（红）中的一个。
2.3 输出格式
一个整数，表示至少需要涂多少块。
2.4 输入输出样例
输入
4 5
WRWRW
BWRWB
WRWRW
RWBWR
输出
11
2.5 分析
首先，三种颜色都要占一行，然后从边界开始枚举每一种情况所需要操作的次数，记录最小值
2.6 参考代码

#include<iostream>
#include<algorithm>
#define N 55
using namespace std;
char flag[N][N];
int min_num = 10000;  //存储最小的涂装数目，初始值一定是一个足够大的数
int main()
{
    int n, m;
    int step;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cin >> flag[i][j];      //输入旗子原本的颜色
    }
    for(int i = 1; i <= n - 2; i++)  //白与蓝的边界
    {
        for(int j = i + 1; j <= n - 1; j++)  //蓝与红的边界
        {
            step = 0;
            //开始枚举
            for(int k = 1; k <= i; k++)
                for(int l = 1; l <= m; l++)
                {
                    if(flag[k][l] != 'W')
                        step++;
                }
            for(int k = i + 1; k <= j; k++)
                for(int l = 1; l <= m; l++)
                {
                    if(flag[k][l] != 'B')
                        step++;
                }
            for(int k = j + 1; k <= n; k++)
                for(int l = 1; l <= m; l++)
                {
                    if(flag[k][l] != 'R')
                        step++;
                }
            min_num = min(min_num, step);
        }
    }
    cout << min_num;
    return 0;
}