AtCoder Beginner Contest 375 A~C

· · 题解

A - Seats

洛谷链接

AtCoder链接

题目

一排有 N 个座位，编号为 1,2, \ldots ,N。

座位的状态由长度为 N 的字符串 S 给出，该字符串由 # 和 . 组成。如果 S 的第 i 个字符是 #，则表示座位 i 有人；如果是 .，则表示座位 i 无人。

求在 1 和 N-2 之间，满足以下条件的整数 i 的个数：

代码

#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) 移动到点 (c,d) 所需的费用是 \sqrt{(a-c)^2+(b-d)^2}。

求他从原点出发，依次访问 N 点 (X_1,Y_1), \ldots ,(X_N,Y_N)，然后返回原点的总费用。

思路

定义数组 x 和 y。

因为从 (0,0) 出发，最后回到 (0,0)，所以将 x_0 和 y_0 赋值为 0。从下标 1 开始输入坐标，然后将 x_{n+1} 和 y_{n+1} 赋值为 0。

最后逐个计算，输出结果保留小数点后 20 位。

代码

#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链接

题目

有一个 N 行 N 列的网格，其中 N 是偶数。让 (i,j) 表示从顶部起第 i 行和从左侧起第 j 列的单元格。

每个单元格都涂成黑色或白色。如果 A_{i,j}= #，则 (i,j) 单元格为黑色；如果是 A_{i,j}= .，则为白色。

按以下顺序对 i=1,2, \ldots , \frac{N}{2} 进行操作后，找出每个单元格的颜色。

思路

当 x 和 y 位于 i 和 N+1-i 之间时，正方形 (y,N+1-x) 的颜色会被替换为正方形 (x,y) 的颜色；这里要注意，这种替换与 i 无关。另外，当且仅当 y 和 N+1-x 位于 i 和 N+1-i 之间时，x 和 y 位于 i 和 N+1-i 之间。

原方格 (x,y) 与运算后的方格如何对应？（每次运算都可以看作是对 \{1,2, \cdots ,N \}^2 的双射，我们以此来考虑对应关系）。

根据上面的讨论，如果 x 和 y 介于 i 和 N+1-i 之间，那么原方格 (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。

因此，如果 i 中 x 和 y 的索引数在 i 和 N+1-i 之间，那么原始正方形 (x,y) 对应的正方形就是应用替换 (x,y) \mapsto (y,N+1-x)、c 两次后得到的正方形。由于这样循环四次后，我们可以取 c 除以 4 的余数，从而知道最多进行 3 次操作前后对应的平方。(将运算视为相对于网格中心的旋转可能有助于直观理解）。

值 c 可以明确写成 \min(x,N+1-x,y,N+1-y)。现在，每个正方形都对应着网格中的一个正方形，因此总共只需 O(N^2) 时间就能得到答案。

代码

#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;
}