「AT1723」「CODE FESTIVAL 2015 OKINAWA OPEN」Automatic Map Generator

AutumnKite

题解AtCoderCODE FESTIVAL 2015 OKINAWA OPEN

发布于：2019年2月9日

次浏览

题目传送门

题意

构造一张 \(H\times W\) 的由岛屿#、海洋.组成的地图，岛屿为八连通，满足恰好包含 \(K\) 个联通块。

\(1\le H,W\le 100,1\le K\le 10000\)

题解

为了放置更多的联通块，每个联通块恰好为一个单位时显然最优。

所以放一张类似于下图所示的地图即可（即在奇数行奇数列放置#，直到放满 \(K\) 个）。

1
2
3

#.#.#.#.
........
#.#.#.#.

代码

#include <cstdio>
int n, m, t;
char a[105][105];
int main(){
    scanf("%d%d%d", &n, &m, &t);
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j)
            if (t && (i & 1) && (j & 1)) a[i][j] = '#', --t; else a[i][j] = '.';
    if (t) return printf("IMPOSSIBLE\n"), 0;
    for (register int i = 1; i <= n; ++i){
        for (register int j = 1; j <= m; ++j) putchar(a[i][j]);
        putchar('\n');
    }
}

更新于：2020年3月26日

构造

「AT1724」「CODE FESTIVAL 2015 OKINAWA OPEN」Beware of the Sogginess!

题目传送门题意给定 \(n\) 个二元组 \((a_i,b_i)\)。一个二元组 \((a,b)\) 可以变为 \((a+t,b-t)\ (0\le t\le b)\)。你现在可以选择一...

NOIP2018 题解

蒟蒻写的 NOIP2018 题解，欢迎吐槽。