专栏文章

AtCoder Beginner Contest 375 A~C

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

文章操作

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

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

A - Seats

洛谷链接
AtCoder链接

题目

一排有 NN 个座位，编号为 1,2,…,N1,2, \ldots ,N。
座位的状态由长度为 NN 的字符串 SS 给出，该字符串由 # 和 . 组成。如果 SS 的第 ii 个字符是 #，则表示座位 ii 有人；如果是 .，则表示座位 ii 无人。
求在 11 和 N−2N-2 之间，满足以下条件的整数 ii 的个数：
  • 座位 ii 和 i+2i+2 有人，座位 i+1i+1 无人。

代码

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

using namespace std;

int n, cnt;
string s;

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

B - Traveling Takahashi Problem

洛谷链接
AtCoder链接

题目

高桥位于二维坐标平面的原点。
他从点 (a,b)(a,b) 移动到点 (c,d)(c,d) 所需的费用是 (a−c)2+(b−d)2\sqrt{(a-c)^2+(b-d)^2}。
求他从原点出发，依次访问 NN 点 (X1,Y1),…,(XN,YN)(X_1,Y_1), \ldots ,(X_N,Y_N)，然后返回原点的总费用。

思路

定义数组 xx 和 yy。
因为从 (0,0)(0,0) 出发，最后回到 (0,0)(0,0)，所以将 x0x_0 和 y0y_0 赋值为 00。从下标 11 开始输入坐标，然后将 xn+1x_{n+1} 和 yn+1y_{n+1} 赋值为 00。
最后逐个计算，输出结果保留小数点后 2020 位。

代码

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

using namespace std;

int n, x[200010], y[200010];
double ans;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
		scanf("%d %d", &x[i], &y[i]);
	x[n + 1] = y[n + 1] = 0;
	for (int i = 0; i <= n; i ++ )
		ans += sqrt(pow(x[i] - x[i + 1], 2) + pow(y[i] - y[i + 1], 2));
	printf("%.20lf", ans);
	return 0;
}

C - Spiral Rotation

洛谷链接
AtCoder链接

题目

有一个 NN 行 NN 列的网格，其中 NN 是偶数。让 (i,j)(i,j) 表示从顶部起第 ii 行和从左侧起第 jj 列的单元格。
每个单元格都涂成黑色或白色。如果 Ai,j=A_{i,j}= #，则 (i,j)(i,j) 单元格为黑色；如果是 Ai,j=A_{i,j}= .，则为白色。
按以下顺序对 i=1,2,…,N2i=1,2, \ldots , \frac{N}{2} 进行操作后，找出每个单元格的颜色。
  • 对于 ii 和 N+1−iN+1-i 之间的所有整数对 x,yx,y，用单元格 (x,y)(x,y) 的颜色替换单元格 (y,N+1−x)(y,N+1-x) 的颜色。同时对所有这些单元格对 x,yx,y 进行替换。

思路

当 xx 和 yy 位于 ii 和 N+1−iN+1-i 之间时，正方形 (y,N+1−x)(y,N+1-x) 的颜色会被替换为正方形 (x,y)(x,y) 的颜色；这里要注意，这种替换与 ii 无关。另外，当且仅当 yy 和 N+1−xN+1-x 位于 ii 和 N+1−iN+1-i 之间时，xx 和 yy 位于 ii 和 N+1−iN+1-i 之间。
原方格 (x,y)(x,y) 与运算后的方格如何对应？（每次运算都可以看作是对 {1,2,⋯ ,N}2\{1,2, \cdots ,N \}^2 的双射，我们以此来考虑对应关系）。
根据上面的讨论，如果 xx 和 yy 介于 ii 和 N+1−iN+1-i 之间，那么原方格 (x,y)(x,y) 对应的方格转换为 (x,y)→(y,N+1−x)→(N+1−x,N+1−y)→(N+1−y,x)→(x,y)→⋯(x,y) \to (y,N+1-x) \to (N+1-x,N+1-y) \to (N+1-y,x) \to (x,y) \to \cdots。
因此，如果 ii 中 xx 和 yy 的索引数在 ii 和 N+1−iN+1-i 之间，那么原始正方形 (x,y)(x,y) 对应的正方形就是应用替换 (x,y)↦(y,N+1−x)(x,y) \mapsto (y,N+1-x)、cc 两次后得到的正方形。由于这样循环四次后，我们可以取 cc 除以 44 的余数，从而知道最多进行 33 次操作前后对应的平方。(将运算视为相对于网格中心的旋转可能有助于直观理解）。
值 cc 可以明确写成 min⁡(x,N+1−x,y,N+1−y)\min(x,N+1-x,y,N+1-y)。现在，每个正方形都对应着网格中的一个正方形，因此总共只需 O(N2)O(N^2) 时间就能得到答案。

代码

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

using namespace std;

int n, d, ni, nj, ti, tj;
char a[3010][3010], ans[3010][3010];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i ++ )
	{
		for (int j = 0; j < n; j ++ )
			cin >> a[i][j];
	}
	for (int i = 0; i < n; i ++ )
	{
		for (int j = 0; j < n; j ++ )
		{
			d = min({i + 1, j + 1, n - i, n - j});
			ni = i;
			nj = j;
			for (int _ = 0; _ < d % 4; _ ++ )
			{
				ti = nj;
				tj = n - 1 - ni;
				ni = ti;
				nj = tj;
			}
			ans[ni][nj] = a[i][j];
		}
	}
	for (int i = 0; i < n; i ++ )
	{
		for (int j = 0; j < n; j ++ )
			cout << ans[i][j];
		puts("");
	}
	return 0;
}

评论

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

正在加载评论...