AtCoder Beginner Contest 377

A.Rearranging ABC

Rearranging ABC

题目描述

You are given a string $S$ of length $3$ consisting of uppercase English letters.
Determine whether it is possible to rearrange the characters in $S$ to make it match the string ABC.

给定字符串$s$,判断是否可以组成 $ABC$

解题思路

排个序就行了

参考代码

#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::sort(s.begin(), s.end());
  std::cout << (s == "ABC" ? "Yes" : "No") << endl;
}

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

B.Avoid Rook Attack

Avoid Rook Attack

题目描述

There is a grid of $64$ squares with $8$ rows and $8$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(1\leq i\leq8)$ and $j$-th column from the left $(1\leq j\leq8)$.
Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence $(S_1,S_2,S_3,\ldots,S_8)$ of $8$ strings of length $8$. Square $(i,j)$ $(1\leq i\leq8,1\leq j\leq8)$ is empty if the $j$-th character of $S_i$ is ., and has a piece if it is #.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square $(i,j)$ can capture pieces that satisfy either of the following conditions:

  • Placed on a square in row $i$
  • Placed on a square in column $j$
    For example, a piece placed on square $(4,4)$ can capture pieces placed on the squares shown in blue in the following figure:

    How many squares can you place your piece on?

给出棋盘，其中放有的位置为 #, 在放有棋子的上下左右四个方向不能放棋子，问有多少个位置可以放棋子.

解题思路

模拟下即可

参考代码

#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::vector<std::string> s(8, "");
  for(int i = 0; i < 8; i++) {
    std::cin >> s[i];
  }

  std::vector a(8, std::vector<int>(8, 1));
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
      if (s[i][j] == '#') {
        for(int l = 0; l < 8; l++) {
          a[i][l] = 0;
        }

        for(int l = 0; l < 8; l++) {
          a[l][j] = 0;
        }
      }
    }
  }
  int res = 0;
  for(auto i : a) {
    for(auto j : i) {
      res += j;
    }
  }

  std::cout << res << endl;
}

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

C.Avoid Knight Attack

Avoid Knight Attack

题目描述

There is a grid of $N^2$ squares with $N$ rows and $N$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(1\leq i\leq N)$ and $j$-th column from the left $(1\leq j\leq N)$.
Each square is either empty or has a piece placed on it. There are $M$ pieces placed on the grid, and the $k$-th $(1\leq k\leq M)$ piece is placed on square $(a_k,b_k)$.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square $(i,j)$ can capture pieces that satisfy any of the following conditions:

  • Placed on square $(i+2,j+1)$
  • Placed on square $(i+1,j+2)$
  • Placed on square $(i-1,j+2)$
  • Placed on square $(i-2,j+1)$
  • Placed on square $(i-2,j-1)$
  • Placed on square $(i-1,j-2)$
  • Placed on square $(i+1,j-2)$
  • Placed on square $(i+2,j-1)$
    Here, conditions involving non-existent squares are considered to never be satisfied.
    For example, a piece placed on square $(4,4)$ can capture pieces placed on the squares shown in blue in the following figure:

    How many squares can you place your piece on?


给定$n * n$ 的棋盘和 $m$个棋子位置,其中棋子能走的位置上图所示,问多少个位置可以放棋子,并且不被吃掉

解题思路

模拟，需要注意边界处理

参考代码

#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, m;
  std::cin >> n >> m;

  int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2},
      dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

  auto check = [&](int x, int y) {
    return 0 < x && x <= n && 0 < y && y <= n;
  };
  std::set<pii > se;
  for(int i = 0; i < m; i++) {
    int x, y;
    std::cin >> x >> y;
    se.insert({x, y});
    for(int j = 0; j < 8; j++) {
      int u = x + dx[j], v = y + dy[j];
      if (check(u, v)) se.insert({u, v});
    }
  }

  std::cout << n * n - se.size() << endl;

}

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

D.Many Segments 2

Many Segments 2

题目描述

You are given two sequences of positive integers of length $N$, $L=(L_1,L_2,\ldots,L_N)$ and $R=(R_1,R_2,\ldots,R_N)$, and an integer $M$.
Find the number of pairs of integers $(l,r)$ that satisfy both of the following conditions:

  • $1\le l \le r \le M$
  • For every $1\le i\le N$, the interval $[l,r]$ does not completely contain the interval $[L_i,R_i]$.

给你两个长度分别为 $N$ 、 $L=(L_1,L_2,\ldots,L_N)$ 和 $R=(R_1,R_2,\ldots,R_N)$ 的正整数序列，以及一个整数 $M$ 。
求满足以下两个条件的整数对 $(l,r)$ 的个数：

  • $1\le l \le r \le M$
  • 对于每一个 $1\le i\le N$ ，区间 $[l,r]$ 并不完全包含区间 $[L_i,R_i]$ 。

解题思路

考虑 $O(m)$的同时，维护一个左边界，就是当前位置能最多往前多少是刚好不完全覆盖的，最后这个左边界需要取个 max ，因为如果前面的左边界更右，那后面的左边界也要和前面一样。

参考代码

#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, m;
  std::cin >> n >> m;

  std::vector<int> a(n + m, 1);
  for(int i = 0, l, r; i < n; i++) {
    std::cin >> l >> r;
    a[r] = std::max(a[r], l + 1);
  }

  for(int i = 1; i <= m; i++) {
    a[i] = std::max(a[i], a[i - 1]);
  }

  int res = 0;
  for(int i = 1; i <= m; i++) {
    res += i - a[i] + 1;
  }

  std::cout << res << endl;
}

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

E.Permute K times 2

Permute K times 2

题目描述

You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.
The following operation will be performed $K$ times:

  • For $i=1,2,\ldots,N$, simultaneously update $P_i$ to $P_{P_i}$.
    Print $P$ after all operations.

给定长度为 $N$的数组 $P$,将 $P_{i}$替换为 $P_{P_{i}}$操作 $K$次,输出 $K$次操作后的数组.

解题思路

在替换时，某个数多替换几轮就可能回到替换前的位置，那么我们就只需要找出环的大小即可，随后再取模即可

参考代码

#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, k;
  std::cin >> n >> k;
  std::vector<int> P(n);

  for(int i = 0; i < n; i++) {
    std::cin >> P[i], P[i]--;
  }

  auto qpow = [&](int a, int b, int p) {
    int res = 1;
    while (b) {
      if (b & 1) res = res * a % p;
      a = a * a % p;
      b >>= 1;
    }
    return res;
  };

  std::vector<bool> vis(n, false);
  for(int i = 0; i < n; i++) {
    if (vis[i]) continue;
    int j = i;
    std::vector<int> t;
    while (!vis[j]) {
      vis[j] = true, t.push_back(j);
      j = P[j];
    }

    int w = qpow(2, k, t.size());
    for(int x = 0; x < t.size(); x++) {
      P[t[x]] = t[(x + w) % t.size()];
    }
  }

  for(int i = 0; i < n; i++) std::cout << P[i] + 1 << " \n"[i == n - 1];
}

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