专栏文章

AtCoder Beginner Contest 382 A~D

IIronMen
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqgsu9p
此快照首次捕获于
2025/12/04 04:33
3 个月前
此快照最后确认于
2025/12/04 04:33
3 个月前
查看原文

A - Daily Cookie

洛谷链接
AtCoder链接

题目

有 NN 个盒子排成一排，其中一些盒子里装有饼干。
这些盒子的状态由长度为 NN 的字符串 SS 表示。具体来说，如果 SS 的第 ii 个字符是 @，则从左边开始的第 ii 个方框 (1≤i≤N)(1 \le i \le N) 中包含一块饼干；如果是 .，则为空。
在接下来的 DD 天里，高桥每天都会从这些盒子里的饼干中选择并吃掉一块。
求 DD 天过去后，NN 个盒子中有多少个是空的。(可以证明这个值并不取决于高桥每天选择的饼干）。
可以保证 SS 中至少有 DD 次出现 @。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int n, d, cnt;
string s;

int main()
{
	scanf("%d %d", &n, &d);
	cin >> s;
	for (int i = 0; i < s.length(); i ++ )
	{
		if (s[i] == '@')
			cnt ++;
	}
	cout << n - (cnt - d) << '\n';
	return 0;
}

B - Daily Cookie 2

洛谷链接
AtCoder链接

题目

高桥选择 cookie 的方式和要求你找到的东西与问题 A 不同。
有 NN 个盒子排成一行，其中一些盒子里有饼干。
这些盒子的状态由长度为 NN 的字符串 SS 表示。具体来说，如果 SS 的第 ii 个字符是 @，那么从左边开始的第 ii 个盒子 (1≤i≤N)(1 \le i \le N) 包含一个 cookie，如果是 .，则为空。
在接下来的 DD 天里，高桥每天都会从这些盒子里的饼干中选择并吃掉一块。在每一天里，他都会选择最右边盒子里的饼干，因为该盒子里有一块饼干。
请判断 NN 个盒子中的每个盒子在 DD 天后是否装有饼干。
保证 SS 中至少有 DD 次出现 @。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int n, d;
string s;

int main()
{
	scanf("%d %d", &n, &d);
	cin >> s;
	for (int i = s.length() - 1; d != 0; i -- )
	{
		if (s[i] == '@')
		{
			d --;
			s[i] = '.';
		}
	}
	cout << s << '\n';
	return 0;
}

C - Kaiten Sushi

洛谷链接
AtCoder链接

题目

有 NN 人光顾一家传送带寿司店，他们的编号从 11 到 NN。第 ii 个的美食级别是 AiA_i。
现在，MM 块寿司将被放在传送带上。第 jj 个寿司的美味度为 BjB_j。每块寿司按照这个顺序从 1,2,…,N1,2, \ldots ,N 人面前经过。当美味程度不低于自己美食水平的寿司从面前经过时，每个人都会拿起并吃掉这个寿司；否则，他们什么也不会做。拿起并吃掉的寿司 ii 将不再从 j (j>i)j\ (j>i) 面前经过。
对于 MM 个寿司，确定谁吃了该寿司，或者是否没人吃，如果没人吃则输出 -1。
代码
CPP
#include <bits/stdc++.h>

using namespace std;

int n, m, a[200010], x[200010], cnt, app[200010], b, w;

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
		if (app[a[i]] == 0)
		{
			x[++ cnt] = a[i];
			app[a[i]] = i;
		}
	}
	sort(x + 1, x + 1 + cnt);
	for (int i = 2; i <= cnt; i ++ )
		app[x[i]] = min(app[x[i]], app[x[i - 1]]);
	while (m -- )
	{
		scanf("%d", &b);
		if (b < x[1])
		{
			puts("-1");
			continue;
		}
		w = upper_bound(x + 1, x + 1 + cnt, b) - x - 1;
		cout << app[x[w]] << '\n';
	}
	return 0;
}

D - Keep Distance

洛谷链接
AtCoder链接

题目

给你整数 NN 和 MM。
按词典顺序，打印所有长度为 NN 的整数序列 (A1,A2,…,AN)(A_1,A_2, \ldots ,A_N)，这些序列满足以下所有条件。
  • 1≤Ai1 \le A_i。
  • 从 22 到 NN 的每个整数 ii 的 Ai−1+10≤AiA_{i-1}+10 \le A_i。
  • AN≤MA_N \le M。

思路

这些序列最后可以很容易地按词序排序，因此我们将首先尝试简单地枚举符合要求的序列。
为便于解释，如果一个序列符合符合性序列的前缀（最初连续的几个项），我们就认为这个序列是好的。
我们将考虑如何枚举好的序列。
长度为 11 的序列 (A1)(A_1) 如果且仅如果 1≤A1≤M−10(N−1)1 \le A_1 \le M-10(N-1) 才是好序列。(如果 A1>M−10(N−1)A_1>M-10(N-1)，那么 ANA_N 即使是最小值，也会超过 MM）。
假设 2≤i≤N2 \le i \le N 和 (A1,A2,…,Ai−1)(A_1,A_2, \ldots ,A_{i-1}) 是一个好序列。那么，当且仅当 Ai−1+10≤Ai≤M−10(N−i)A_{i-1}+10 \le A_i \le M-10(N-i) 是良好序列时，AiA_i 的范围 (A1,A2,…,Ai−1,Ai)(A_1,A_2, \ldots ,A_{i-1},A_i) 才是良好序列。(理由与 A1A_1 相同）。
根据这一规则枚举出好序列，问题就迎刃而解了。
由于好序列最多有 (219)=293930\binom{21}{9} = 293930 个，因此如果实施得当，枚举速度已经足够快了。在某些情况下，可能会自然而然地产生按词典顺序排列的好序列。
即使不评估答案的数量，我们也可以猜测符合要求的序列没有那么多，因为我们被要求打印所有的序列，并认为只要操作的数量与好序列的数量一样多，算法就会在规定的时间内完成。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

int n, m, X;
vector<int> na;

int main()
{
	scanf("%d %d", &n, &m);
	vector<vector<int> > w = {{}};
	for (int i = 1; i <= n; i ++ )
	{
		vector<vector<int> > v;
		for (vector<int> a : w)
		{
			for (int x = (i == 1 ? 1 : a.back() + 10); x <= m - 10 * (n - i); x ++ )
			{
				na = a;
				na.push_back(x);
				v.push_back(na);
			}
		}
		swap(v, w);
	}
	X = w.size();
	cout << X << '\n';
	for (int i = 0; i < X; i ++ )
	{
		for (int j = 0; j < n; j ++ )
			cout << w[i][j] << " \n"[j == n - 1];
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...