欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-04-27 11:35:26
...

ACM模版

描述

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

题解

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

这里我们直接都构造成 5050 的,这个题据说有无数种解法(虽然有些夸张),但是基本上都是直接构造 5050 的大小的。

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

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

代码

#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;
}
相关标签: 构造