杭电多校第十场 1003 Mine Sweeper 题解

题目大意

给你一个数字s，求出满足地图上所有数字和为s的扫雷地图。

解题思路

这个应该算是签到题吧。

想到了应该挺简单的。

这个构造还不算难。

如果$s\leq 24$，只需要构造出一条“$.X$”，满足长度为s+1。

如果$s>24$，可以表示成$8a+3b$，首先，一个单独的X，可以提供8点，在第一行放下连续的X，每个可以提供3点，接下来对余数分析。

如果余数为1，4，7，可以表示成$b+=last/3+3,a–$。

可以减去一个8，加上一个9。

如果余数为2，5，可以表示成$b+=last/3+6,a-=2$。

可以减去一个16，加上一个18。

如果余数为3，6，可以表示成$b+=last/3$。

所以所有情况都是满足的，不存在不满足的情况。

第一行输出b个连续X，后面输出a个单独的X即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 30;
char Map[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int s; cin >> s;
		if (s <= 24) {
			int flag = 1;
			s++;
			cout << 1 << ' ' << s << endl;
			while (s--) {
				if (flag == 1) cout << '.';
				else cout << 'X';
				flag *= -1;
			}
			cout << endl;
		}
		else {
			int a = s / 8, last = s % 8, b = 0;
			if (last == 1 || last == 4 || last == 7)    b += last / 3 + 3, a--;
			else if (last == 2 || last == 5)    b += last / 3 + 6, a -= 2;
			else   b += last / 3;
			int i;
			for (int i = 1; i <= 25; i++) {
				if (b)	Map[1][i] = 'X',b--;
				else Map[1][i] = '.';
			}
			for (i = 2; i <= 25 && a; i++) {
				if (i & 1) {
					for (int j = 1; j <= 25; j++) {
						if (j & 1 || !a)	Map[i][j] = '.';
						else if ((j & 1) == 0 && a)	Map[i][j] = 'X', a--;
					}
				}
				else {
					for (int j = 1; j <= 25; j++)	Map[i][j] = '.';
				}
			}
			for (int j = 1; j <= 25; j++)	Map[i][j] = '.';
			cout << i << ' ' << 25 << endl;
			for (int g = 1; g <= i; g++) {
				for (int j = 1; j <= 25; j++)	cout << Map[g][j];
				cout << endl;
			}
		}
	}
	return 0;
}