目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 989C - Codeforces

---

二、解题报告

1、思路分析

题目让构造网格图，图中四个元素的连通块个数分别为a,b,c,d

观察数据范围，网格图最大是50 * 50，而1 <= a, b, c, d <= 100

我们不妨考虑a，b，c，d都是100的时候

我们无脑开50* 50 的网格图，然后每个元素分25 * 25的区域

这样每个元素初始连通块个数都是1

然后显然要增加每个元素的连通块个数，我们考虑通过在其他元素中增加本元素来增加本元素的连通块个数

不妨以a为例，我们考虑在b中插入a，插入位置满足周围8个元素都是b

那么对于25*25的b区域而言，可以给a提供12 * 12 = 144个插入位置，即144个连通块，这远大于题目要求的100

那么我们让b给a提供，c给b提供，d给c提供，a给d提供，这样就一定能够构造出合法解

2、复杂度

时间复杂度：O(2500) 空间复杂度：O(2500)

3、代码详解

​

import sys
# sys.stdin = open('in.txt', 'r')
cnt = list(map(int, input().split()))

n, m = 50, 50
st = 'ABCD'

g = [[''] * 50 for _ in range(50)]

for i in range(50):
    for j in range(50):
        g[i][j] = st[i // 25 * 2 + j // 25]
for i in range(4):
    cnt[i] -= 1
    dx, dy = divmod((i + 1) % 4, 2)
    for x in range(1,25,2):
        for y in range(1, 25, 2):
            if not cnt[i]:
                break
            g[x + dx * 25][y + dy * 25] = st[i]
            cnt[i] -= 1
        else:
            continue
        break
print(n, m)
for x in g:
    print(''.join(x))