AtCoder Beginner Contest 375

建议查看中文题面，不要问为什么*(问就是，英文题面就是复制过来的，中文体面精简些),数据范围详见题目链接

A.Seats

Seats

题目描述

There are $N$ seats in a row, numbered $1, 2, \ldots, N$.
The state of the seats is given by a string $S$ of length $N$ consisting of # and .. If the $i$-th character of $S$ is #, it means seat $i$ is occupied; if it is ., seat $i$ is unoccupied.
Find the number of integers $i$ between $1$ and $N - 2$, inclusive, that satisfy the following condition:

  • Seats $i$ and $i + 2$ are occupied, and seat $i + 1$ is unoccupied.

给定字符串 $s$ 其中字符串只含有 # 和 . ,# 表示当前位置有人, .表示当前位置无人.
问:有多少个位置满足左右有人，当前位置无人的.

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::string s;
  std::cin >> s;
  int ct = 0;
  for(int i = 1; i < n - 1; i++) {
    if (s[i] == '.' && s[i] != s[i + 1] && s[i + 1] == s[i - 1])
      ct++;
  }
  std::cout << ct << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

B.Traveling Takahashi Problem

Traveling Takahashi Problem

题目描述

Takahashi is at the origin on a two-dimensional coordinate plane.
The cost for him to move from point $(a, b)$ to point $(c, d)$ is $\sqrt{(a - c)^2 + (b - d)^2}$.
Find the total cost when he starts at the origin, visits $N$ points $(X_1, Y_1), \ldots, (X_N, Y_N)$ in this order, and then returns to the origin.

给定$n$个点，从点 $(0,0)$ 出发依次经过这些点,然后回到原点的代价.
从点 $(a,b)$ 移动到点 $(c,d)$ 的代价是 $\sqrt{(a-c)^{2} + (b-d)^{2}}$

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  double s = 0;
  int n;
  std::cin >> n;
  int x = 0, y = 0;
  for(int i = 0; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    s += std::hypot(u - x, y - v);
    x = u, y = v;
  }
  s += std::hypot(x, y);
  std::cout << fix(16) << s << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

C.Spiral Rotation

Spiral Rotation

题目描述

You are given a grid with $N$ rows and $N$ columns, where $N$ is an even number. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

Each cell is painted black or white. If $A_{i, j} =$ #, cell $(i, j)$ is black; if $A_{i, j} =$ ., it is white.

Find the color of each cell after performing the following operation for $i = 1, 2, \ldots, \frac{N}{2}$ in this order.

  • For all pairs of integers $x, y$ between $i$ and $N + 1 - i$, inclusive, replace the color of cell $(y, N + 1 - x)$ with the color of cell $(x, y)$. Perform these replacements simultaneously for all such pairs $x, y$.

题意太复杂，直接说重点，在 $N * N$ 的矩阵中,每个单元格都涂成黑色或白色。如果 $A_{i, j} =$ 则 $(i, j)$ 单元格为黑色；如果是 $A_{i, j} =$ .，则为黑色。."，则为白色。

依次对 $i = 1, 2, \ldots, \frac{N}{2}$ 进行以下操作:

对于 $i$ 和 $N + 1 - i$ 之间的所有整数对 $x, y$ ，将单元格 $(y, N + 1 - x)$ 的颜色替换为单元格 $(x, y)$ 的颜色。同时对所有这些单元格对 $x, y$ 进行替换。
最后打印这个矩阵。

解题思路

稍加推理就可以发现对于每次操作 $i$都是在对以 $(i,i)$为左上角，大小为 $(N-i+1)*(N-i+1)$ 的子矩阵进行顺时针旋转 $90^{\circ}$

参考代码

TLE code

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::vector<std::string> s(n);
  for(int i = 0; i < n; i++) {
    std::cin >> s[i];
  }

  for(int a = 0; a < n / 2; a++) {
    auto t = s;
    for(int i = a; i < n - a; i++) {
      for(int j = a; j < n - a; j++) {
        t[i][j] = s[n - j - 1][i];
      }
    }
    s = t;
  }

  for(auto i : s) {
    std::cout << i << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

AC code

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int N;
  std::cin >> N;
  std::vector<std::string> A(N), B(N, std::string(N, ' '));
  for(int i = 0; i < N; i++)std::cin >> A[i];
  for(int d = 0; d < N / 2; d++) {
    for(int t = 0; t < (d + 1) % 4; t++) {
      for(int x = d; x < N - d; x++) {
        B[x][d] = A[x][d];
        B[x][N - d - 1] = A[x][N - d - 1];
        B[d][x] = A[d][x];
        B[N - d - 1][x] = A[N - d - 1][x];
      }
      for(int x = d; x < N - d; x++) {
        A[d][N - x - 1] = B[x][d];
        A[N - d - 1][N - x - 1] = B[x][N - d - 1];
        A[x][N - d - 1] = B[d][x];
        A[x][d] = B[N - d - 1][x];
      }
    }
  }
  for(auto i : A) {
    std::cout << i << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

D.ABA

ABA

题目描述

You are given a string $S$ consisting of uppercase English letters.
Find the number of integer triples $(i, j, k)$ satisfying both of the following conditions:

  • $1 \leq i < j < k \leq |S|$
  • The length-$3$ string formed by concatenating $S_i$, $S_j$, and $S_k$ in this order is a palindrome.

Here, $|S|$ denotes the length of $S$, and $S_x$ denotes the $x$-th character of $S$.

给你一个由大写英文字母组成的字符串 $S$ 。
求满足以下两个条件的整数三元组 $(i, j, k)$ 的个数：

  • $1 \leq i < j < k \leq |S|$
  • 将 $S_i$ 、 $S_j$ 和 $S_k$ 按此顺序连接而成的长度为 $3$ 的字符串是一个回文字符串。

这里， $|S|$ 表示 $S$ 的长度， $S_x$ 表示 $S$ 的 $x$ -th字符。

解题思路

这个其实就是前缀和维护当前位置前的每个字母个数和当前位置后的每个字母个数

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::string s;
  std::cin >> s;
  std::vector ct(26, std::vector<int>(s.size() + 1, 0ll));
  for(int i = 0; i < s.size(); i++) {
    ct[s[i] - 'A'][i]++;
  }

  for(int i = 0; i < 26; i++) {
    for(int j = 1; j < s.size(); j++) {
      ct[i][j] += ct[i][j - 1];
    }
  }
  int ans = 0;
  for(int i = 1; i < s.size() - 1; i++) {
    for(int j = 0; j < 26; j++) {
      ans += ct[j][i - 1] * (ct[j][s.size() - 1] - ct[j][i]);
    }
  }

  std::cout << ans << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}