专栏文章

AtCoder Beginner Contest 383 A~D

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

文章操作

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

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

A - Humidifier 1

洛谷链接
AtCoder链接

题目

AtCoder 公司办公室有一个加湿器。当前时间是 00，加湿器内没有水。
你要给这个加湿器加水 NN 次。第 ii 次加水（1≤i≤N1 \le i \le N）发生在时间 TiT_i，您加了 ViV_i 升水。保证所有 1≤i≤N−11 \le i \le N-1 的 Ti<Ti+1T_i<T_{i+1}。
但是，加湿器漏水了，只要里面有水，单位时间内水量就会减少 11 升。
求在 TNT_N 时加完水后加湿器中剩余的水量。

代码

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

using namespace std;

int n, t[110], v[110], s;

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i ++ )
		scanf("%d %d", &t[i], &v[i]);
	s = v[0];
	for (int i = 1; i < n; i ++ )
	{
		s -= t[i] - t[i - 1];
		if (s < 0)
			s = 0;
		s += v[i];
	}
	cout << s << '\n';
	return 0;
}

B - Humidifier 2

洛谷链接
AtCoder链接

题目

AtCoder 公司办公室可以表示为由 HH 行和 WW 列组成的网格。(i,j)(i,j) 表示从上往下第 ii 行和从左往上第 jj 列的单元格。
每个单元格的状态由一个字符 Si,jS_{i,j} 表示。如果 Si,jS_{i,j} 是 #，则该单元格包含一张桌子；如果 Si,jS_{i,j} 是 .，则该单元格是一层楼。可以保证至少有两个楼层单元格。
您将选择两个不同的楼层单元格，并在每个单元格中放置一个加湿器。
放置加湿器后，当且仅当一个单元格 (i,j)(i,j) 与至少一个加湿器单元格 (i′,j′)(i',j') 的曼哈顿距离 DD 在内时，该单元格 (i,j)(i,j) 才被加湿。(i,j)(i,j) 和 (i′,j′)(i',j') 之间的曼哈顿距离定义为 ∣i−i′∣+∣j−j′∣|i-i'|+|j-j'|。请注意，任何放置了加湿器的楼层单元总是加湿的。
求加湿楼层单元的最大可能数目。

代码

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

using namespace std;

int H, W, D, maxCount, n, humidifiedCount, dist, distB;
vector<pair<int, int> > floorCells;

int main()
{
	scanf("%d %d %d", &H, &W, &D);
	vector<string> S(H);
	for (int i = 0; i < H; i ++ )
		cin >> S[i];
	for (int i = 0; i < H; i ++ )
	{
		for (int j = 0; j < W; j ++ )
		{
			if (S[i][j] == '.')
				floorCells.push_back(make_pair(i, j));
		}
	}
	n = floorCells.size();
	for (int a = 0; a < n; a ++ )
	{
		for (int b = 0; b < n; b ++ )
		{
			if (a!= b)
			{
				humidifiedCount = 0;
				pair<int, int> cellA = floorCells[a];
				pair<int, int> cellB = floorCells[b];
				for (auto cell : floorCells)
				{
					dist = abs(cell.first - cellA.first) + abs(cell.second - cellA.second);
					distB = abs(cell.first - cellB.first) + abs(cell.second - cellB.second);
					if (dist <= D || distB <= D)
						humidifiedCount ++;
				}
				maxCount = max(maxCount, humidifiedCount);
			}
		}
	}
	cout << maxCount << '\n';
	return 0;
}

C - Humidifier 3

洛谷链接
AtCoder链接

题目

AtCoder 公司办公室是一个由 HH 行和 WW 列组成的网格。让 (i,j)(i,j) 表示从顶部起第 ii 行和从左侧起第 jj 列的单元格。
每个单元格的状态由一个字符 Si,jS_{i,j} 表示。如果 Si,jS_{i,j} 为 #，则表示该单元格有一堵墙；如果 Si,jS_{i,j} 为 .，则表示该单元格是一个地板；如果 Si,jS_{i,j} 为 H，则表示该单元格在地板上放置了一个加湿器。
如果从至少一个加湿器单元格向上、向下、向左或向右移动最多 DD 次且不经过墙壁，则该单元格被视为加湿单元格。需要注意的是，任何带有加湿器的单元格总是加湿的。
求加湿地板单元格的数量。

思路

这道题是经典的 BFS。
BFS 即广度优先搜索，对于每一个符合条件的点，我们都寻找他的上下左右四个点，去寻找下一个满足条件的点，并把他加入到一个容器里面方便下一次求解。那么什么容器可以先进先出呢，没错就是队列，于是我们就可以用队列来解决广度优先搜索的题目。
关于这一道 BFS 题，我们可以发现在题目中提到我们在地板上放置若干个加湿器，每个加湿器可以触及到的范围，我们可以设每一个加湿器是一个起点，搜索可以触及到的点，这道题就迎刃而解了。

代码

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

using namespace std;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; // 右、左、下、上
char grid[1010][1010];
bool vis[1010][1010];
int h, w, d, steps, si, nx, ny, cnt;
queue<pair<int, int> > q;

int main()
{
	scanf("%d %d %d", &h, &w, &d);
	for (int i = 0; i < h; i ++ )
		cin >> grid[i];
	for (int i = 0; i < h; i ++ )
	{
		for (int j = 0; j < w; j ++ )
		{
			if (grid[i][j] == 'H')
			{
				q.push({i, j}); // 每一个加湿器入队
				vis[i][j] = 1; // 加湿器位置标记为加湿
			}
		}
	}
	// BFS可以算作模板了
	while (!q.empty() && steps < d) // 队列不为空且范围不到 d
	{
		si = q.size();
		for (int i = 0; i < si; i ++ )
		{
			auto x = q.front().first, y = q.front().second;
			q.pop();
			for (int d = 0; d < 4; d ++ )
			{
				nx = x + dx[d];
				ny = y + dy[d];
				if (nx >= 0 && nx < h && ny >= 0 && ny < w && !vis[nx][ny] && grid[nx][ny] == '.') // 边界条件、是否访问过、是否为地板不是墙
				{
					vis[nx][ny] = 1; // 标记走过了
					q.push({nx, ny}); // 入队
				}
			}
		}
		steps ++;
	}
	// 统计加湿的地板单元格数量
	for (int i = 0; i < h; i ++ )
	{
		for (int j = 0; j < w; j ++ )
		{
			if (vis[i][j])
				cnt ++;
		}
	}
	cout << cnt << '\n';
	return 0;
}

D - 9 Divisors

洛谷链接
AtCoder链接

题目

找出不大于 NN 且恰好有 99 个因数的正整数的个数。

思路

突破点在于 99 个因子这一部分。显然我们可以发现结果必然是一个完全平方数。在经过思考，我们可以发现这个完全平方数还是由两个质数相乘得到的。
思考路程如下：设两个质数 a,ba,b 且 a≠ba \ne b，它们乘积的平方为所得完全平方数，即 a2b2a^2b^2。此时有因子 1,a,b,a2,ab,b2,a2b,ab2,a2b21,a,b,a^2,ab,b^2,a^2b,ab^2,a^2b^2，恰好为 99。
可以证明惟有 a,ba,b 是不相等质数时有如上结论。
此外我们还需考虑八次方数，易证。
先用线性筛筛出所有质数，然后枚举即可。
由于极限情况下可以发现答案并不大，所以暴力即可。

代码

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

using namespace std;

const long long maxn = 1000000;
long long n, ans, w, w2;
vector<long long> p;
bool vs[1000010];

int main()
{
	scanf("%lld", &n);
	for (long long i = 2; i <= maxn; i ++ )
	{
		if (!vs[i])
			p.push_back(i);
		for (long long j = 0; j < p.size() && i * p[j] <= maxn; j ++ )
		{
			vs[i * p[j]] = 1;
			if (i % p[j] == 0)
				break;
		}
	}
	for (long long i = 0; i < p.size(); i ++ )
	{
		w = pow(p[i], 8);
		if (w > n)
			break;
		ans ++;
	}
	for (long long i = 0; i < p.size(); i ++ )
	{
		w = pow(p[i], 2);
		if (w * w > n)
			break;
		for (long long j = i + 1; j < p.size(); j ++ )
		{
			w2 = w * pow(p[j], 2);
			if (w2 > n)
				break;
			ans ++;
		}
	}
	cout << ans << '\n';
	return 0;
}

评论

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

正在加载评论...