编程题

T1 签到题

题目等价于 : 给出了 $n * m$ 的网格图 , 和一个点 $(x, y)$ , 每一个格子有一个数 $g [i] [j]$

求 $s u m g - g [x] [y] + 1$

通过 100%

代码参考

int main() {
    int n, m;
    cin >> n >> m;;
    int x, y;
    cin >> x >> y;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
            sum += w[i][j];
        }
    }
    cout << sum - w[x][y] + 1 << "\n";
    return 0;
}

T2 模拟题

类似 炸金花 游戏 , 给出 $N$ 张牌 , 求此时牌型的倍数

题目已经给出全部牌型的倍数可能 , 按情况分类输出即可.

输入 :
N 张牌大小 , 数据范围 $[1, 10]$
N 张牌类型 , 数据范围 $[A, E]$

通过 100%

代码参考

void solve() {
	cin >> n;
	unordered_map<int, int> mp1;
	unordered_map<char, int> mp2;
	for (int i = 0; i < n; i++) cin >> a[i], mp1[a[i]] ++;
	for (int i = 0; i < n; i++) cin >> b[i], mp2[b[i]] ++;
	for (int i = 0; i < n; i++) {
		if (mp1[a[i]] == 5) {
			cout << "15000\n"; return;
		}
		else if (mp2[b[i]] == 5) {
			sort(a, a + n);
			bool f = true;
			for (int j = 1; j < n; j++) {
				if (a[j] != a[j - 1] + 1) {
					f = false; break;
				}
			}
			if (f) cout << "8000\n";
			else cout << "300\n";
			return;
		}
	}
	for (int i = 0; i < n; i++) {
		if (mp1[a[i]] == 4) {
			cout << "150\n"; return;
		}
	}
	for (int i = 0; i < n; i++) {
		if (mp1[a[i]] == 3) {
			for (int j = 0; j < n; j++) {
				if (mp1[a[j]] == 2) {
					cout << "40\n"; return;
				}
			}
			cout << "6\n"; return;
		}
	}
	if (n == 5) {
		sort(a, a + n);
		bool f = true;
		for (int j = 1; j < n; j++) {
			if (a[j] != a[j - 1] + 1) {
				f = false;
				break;
			}
		}
		if (f) {
			cout << "20\n"; return;
		}
	}
	int o = 0;
	for (auto&[k, v] : mp1) if (v == 2) o++;
	if (o == 2) cout << "4\n";
	else if (o == 1) cout << "2\n";
	else cout << "1\n";
}

T3 字符串模拟题

题目描述

输入 : 给出一行字符串 $s$ , $s$ 为一段话 , 仅由英文字母的单词 , 标点和空格组成。
要求 :

将 $s$ 重新输出的 "好看点" ，给出 $n, m$ ，每一行最多 $n$ 个字符
当最后一个单词放置前该行没有 $n$ 个字符 , 放置后不超过 $n + m$ 字符 , 则允许放置一次 , 每行只能有一个这样的 "突破" 限制。
每行开头不允许出现空格，行末空格去除 , 若标点在某行的开头 , 可以无视限制 , 将该标点放在上一行行末。

输入的限制：

标点出现时有且仅有一个。
空格不存在连续空格。

输出 :

输出处理后的 $s$ 的行数和对应的 $s$

通过 100%

代码参考

bool judge(char c) {// 判断 c 是否是字符
	if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) return true;
	return false;
}
void solve() {
	cin >> n >> m; getchar();
	string s; getline(cin, s);
	int l = 0;
	vector<string> res;
	string add = "";
	while (l < s.size()) {
		bool o = false;
		if (l && s[l - 1] == ' ') o = true;// 是否需要加空格
		string w = "";
		while (l < s.size() && judge(s[l])) w += s[l++];

		if (w.empty() && s[l] != ' ') w = s[l++];// 标点的情况
		if (w.empty() && s[l] == ' ') {
			l++;
			continue;// 空格的情况
		}

		if (!judge(w[0])) {
			// 标点符号的情况
			if (add.empty()) {
				res.back() += w;
			}
			else {
				add += w;
			}
			continue;
		}

		// w 是单词的情况
		if (add.empty()) add += w;
		else {
			if (o) add += " ";
			if (add.size() == n) {
				// 因为有空格的存在
				res.push_back(add);
				add = w;
			}
			else if (add.size() > n) {
				// 已经突破 n 上限一次了
				res.push_back(add);
				add = w;
			}
			else if (add.size() + w.size() > n) {
				// 放单词 w 后将突破 n
				if (add.size() + w.size() > n + m) {
					// 突破上限
					res.push_back(add);
					add = w;
				}
				else {
					add += w;
				}
			}
			else {
				add += w;
			}
		}
	}
	if (!add.empty()) res.push_back(add);
	cout << res.size() << "\n";
	for (auto& i : res) cout << i << "\n";
}

T4 二分 + BFS

题目描述

输入 : 给出网格图 $g [N] [M], 1 \leq N, M \leq 700$ 源点 $(x, y)$ , 目标点 $(z, w)$

从源点出发只能 上下左右 走到 目标点 的路径 $p a t h$ , 消耗为 $p a t h$ 上的点的最大值

输出 :

开销的最小值

解题思路

因为若存在一条路径开销为 $cos t$ , 那么当 $u > cos t$ 一定也可以从源点到目标点 , 所以开销具有二分性质 , 所以二分开销即可。

通过 100%

代码参考

int n, m, x, y, z, w;
int g[N][N];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool vi[N][N];
bool judge(int mid) {
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) vi[i][j] = false;
	vi[x][y] = true;
	queue<int> q;
	q.push(x * N + y);
	while (!q.empty()) {
		auto t = q.front(); q.pop();
		int i = t / N, j = t % N;
		for (int d = 0; d < 4; d++) {
			int ni = i + dir[d][0], nj = j + dir[d][1];
			if (ni && ni <= n && nj && nj <= m && g[ni][nj] <= mid && !vi[ni][nj]) {
				if (ni == z && nj == w) return true;
				vi[ni][nj] = true;
				q.push(ni * N + nj);
			}
		}
	}
	return false;
}
void solve() {
	cin >> n >> m;
	cin >> x >> y;
	cin >> z >> w;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> g[i][j];
	}
	if (x == z && y == w) {
		cout << 0 << "\n"; return;
	}
	int l = max(g[x][y], g[z][w]), r = n * m;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (judge(mid)) {
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << r + 1 << "\n";
}