CF-Codeforces Round #487 (Div. 2)-C-A Mist of Florescence

ACM模版

描述

题解

给定 a,b,c,d$a,b,c,d$ 表示 A,B,C,D$A,B,C,D$ 四种字符的联通块数，构造满足条件的情况，最多构造的尺寸不能大于 50∗50$50\ast 50$。

这里我们直接都构造成 50∗50$50\ast 50$ 的，这个题据说有无数种解法（虽然有些夸张），但是基本上都是直接构造 50∗50$50\ast 50$ 的大小的。

我的代码使用的构造思路是，首先将要构造的矩阵分为四块，分别用四种字符填充，这样 A,B,C,D$A,B,C,D$ 的联通块数都为 1$1$，然后根据 A$A$ 剩下的联通块数往 D$D$ 区域插入，在不破坏 D$D$ 区域 D$D$ 的联通性的前提条件下插入，一共需要插入 a−1$a-1$ 块互不联通的 A$A$，同理，在 A$A$ 区插入 d−1$d-1$ 个彼此不联通且不破坏 A$A$ 联通性的 D$D$，……B，C$B，C$ 同理。

题目所给的样例还有样例解释在一定程度上是干扰的，导致一开始我在想画圈圈……

代码

#include <iostream>

using namespace std;

const int MAXN = 55;

int map[MAXN][MAXN];

int a, b, c, d;

void output()
{
    cout << 50 << ' ' << 50 << endl;
    for (int i = 0; i < 50; i++)
    {
        for (int j = 0; j < 50; j++)
        {
            putchar(map[i][j]);
        }
        putchar(10);
    }
}

int main(int argc, const char * argv[])
{
    while (cin >> a >> b >> c >> d)
    {
        a--;
        b--;
        c--;
        d--;

        for (int i = 0; i < 25; i++)
        {
            for (int j = 0; j < 25; j++)
            {
                map[i][j] = 'A';
            }
        }

//        output();

        for (int i = 25; i < 50; i++)
        {
            for (int j = 0; j < 25; j++)
            {
                map[i][j] = 'B';
            }
        }

//        output();

        for (int i = 0; i < 25; i++)
        {
            for (int j = 25; j < 50; j++)
            {
                map[i][j] = 'C';
            }
        }

//        output();

        for (int i = 25; i < 50; i++)
        {
            for (int j = 25; j < 50; j++)
            {
                map[i][j] = 'D';
            }
        }

//        output();

        for (int i = 0; i < 25; i += 2)
        {
            for (int j = 0; j < 25; j += 2)
            {
                if (d == 0)
                {
                    break;
                }

                map[i][j] = 'D';
                d--;
            }
        }

//        output();

        for (int i = 25; i < 50; i += 2)
        {
            for (int j = 0; j < 25; j += 2)
            {
                if (c == 0)
                {
                    break;
                }

                map[i][j] = 'C';
                c--;
            }
        }

//        output();

        for (int i = 0; i < 25; i += 2)
        {
            for (int j = 25; j < 50; j += 2)
            {
                if (b == 0)
                {
                    break;
                }

                map[i][j] = 'B';
                b--;
            }
        }

//        output();

        for (int i = 25; i < 50; i += 2)
        {
            for (int j = 25; j < 50; j += 2)
            {
                if (a == 0)
                {
                    break;
                }

                map[i][j] = 'A';
                a--;
            }
        }

        output();
    }

    return 0;
}