ABC436

Problem A

题目描述

给你一个整数 $N$ 和一个由小写英文字母组成的字符串 $S$，且字符串长度小于 $N$。 请你不断地在字符串 $S$ 的开头添加小写字母 o，直到它的长度达到 $N$ 为止，然后输出最终得到的字符串。

数据范围

• $2 \le N \le 100$
• $N$ 是一个整数。
• $S$ 是一个由小写英文字母组成的字符串，长度在 $1$ 到 $N - 1$ 之间（包含边界）。

题解

只需要先输出 $N - |S|$ 个 o 后，再输出字符串 $S$ 即可。

Problem B

题目描述

给你一个奇数 $N$，且它至少是 $3$。 有一个 $N$ 行 $N$ 列的网格，所有格子一开始都是空的。接下来，你要按照下面的步骤，在每个格子里写入整数。设 $(i, j)$ 表示从上往下第 $(i+1)$ 行、从左往右第 $(j+1)$ 列的格子 ($0 \le i < N, 0 \le j < N$)。

1. 在格子 $(0, \frac{N-1}{2})$ 写入数字 $1$。
2. 重复下面的操作 $N^2 - 1$ 次：
   • 设 $(r, c)$ 是上一次写数字的格子，写入的数字是 $k$。如果格子 $((r - 1) \bmod N, (c + 1) \bmod N)$ 为空，就在该格子写入 $k + 1$；否则，在格子 $((r + 1) \bmod N, c)$ 写入 $k + 1$。这里，$x \bmod N$ 是 $x$ 除以 $N$ 的余数。

求出按照这个过程，每个格子里最终写入的整数。可以证明，每个格子都会且只会被写入一次。

数据范围

• $3 \le N \le 99$
• $N$ 是一个奇数。

题解

按照题意直接模拟即可。

Problem C

题目描述

有一个 $N$ 行 $N$ 列的网格。令 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的单元格。初始时，网格上没有放置任何物品。

你将执行 $M$ 次操作。第 $i$ 次操作（$1 \le i \le M$）如下：

• 当且仅当一个 $2 \times 2$ 的方块的放置位置与网格上已有的任何方块都不重叠时，将该方块放置在以单元格 $(R_i, C_i)$ 为左上角的区域。更准确地说，对于单元格集合 $S = \{(R_i, C_i), (R_i + 1, C_i), (R_i, C_i + 1), (R_i + 1, C_i + 1)\}$，如果网格上已有的方块占据了 $S$ 中的任何一个单元格，则不执行任何操作；否则，放置一个占据 $S$ 中全部四个单元格的方块。

执行完所有操作后，请找出网格上一共放置了多少个方块。

数据范围

• $2 \le N \le 10^9$
• $1 \le M \le 2 \times 10^5$
• $1 \le R_i, C_i \le N - 1$
• 所有输入值均为整数。

题解

可以发现，如果我们 $(r_1, c_1)$ 和 $(r_2, c_2)$ 两个 block 有重合，当且仅当 $|r_1 - r_2| \le 1$ 且 $|c_1 - c_2| \le 1$。 所以我们只需要用 set 维护现在的 block 的左上角的集合，每次先检查 $[r-1, r+1] \times [c-1, c+1]$ 有没有已经放好的格子，如果没有的话当前的 block 就可以加入 set。

参考代码

#include <bits/stdc++.h>
using namespace std;

set<pair<int, int>> s;
bool check(int r, int c) {
  for (int dx = -1; dx <= 1; dx++) {
      for (int dy = -1; dy <= 1; dy++) {
        if (s.find({r + dx, c + dy}) != s.end()) return false;;
      }
  }
  return true;
}

int main() {
  int n, m;
  cin >> n >> m;
  
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    int r, c; cin >> r >> c;
    if (check(r, c)) {
      ans++;
      s.insert({r, c});
    }
  }
  cout << ans << endl;
}

Problem D

题目描述

有一个迷宫，由一个 $H$ 行 $W$ 列的网格组成。用 $(i, j)$ 表示位于从上往下第 $i$ 行、从左往右第 $j$ 列的格子。格子 $(i, j)$ 的类型由一个字符 $S_{i,j}$ 表示，每个字符代表的含义如下：

• .：空白格子
• #：障碍格子
• 小写英文字母 (a - z)：传送格子

在迷宫中，你可以任意次数、任意顺序地执行以下两种操作：

• 走路：从当前格子移动到上下左右相邻的一个格子，但不能走到障碍格子或迷宫外。
• 传送：当你站在一个传送格子时，可以瞬间移动到任何一个带有相同字母的传送格子。

请判断是否能从格子 $(1, 1)$ 移动到格子 $(H, W)$，如果能，求出完成这一步所需的最少操作次数。

数据范围

• $1 \le H, W \le 1000$
• $H \times W \ge 2$
• $H$ 和 $W$ 都是整数。
• $S_{i,j}$ 是 .、# 或小写英文字母。
• $S_{1,1} \neq \#$
• $S_{H,W} \neq \#$

题解

按照题意直接 BFS 即可：

• 在每一个格子，可以选择上下左右走到相邻的不是 # 的格子。
• 如果当前格子是 warp，则可以从这个格子到达所有相同字母的格子。

直接跑上面的 BFS 会导致 TLE，核心原因是走 warp 的路径太多了。但我们发现同一个字母对应的 warp 其实只需要被遍历一遍就好了，所以我们也给每个 warp 设置一个 vis 数组。如果这个 warp 已经通过其他位置被处理过了，后续就不再重复扫描该字母对应的所有位置。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1000 + 5;
char mp[N][N];
int h, w;

bool vis[N][N];
int dis[N][N];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<pair<int, int>> qq[30];

struct node {
  int x, y;
  bool operator< (const node &b) const {
    return dis[x][y] > dis[b.x][b.y];
  }
};

bool v[100];

void dijkstra() {
  queue<pair<int, int>> q;
  q.push({1, 1});
  dis[1][1] = 1;
  while (q.size()) {
    auto [x, y] = q.front(); q.pop();

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if (dis[nx][ny]) continue;
      if (mp[nx][ny] == '#') continue;
      
      dis[nx][ny] = dis[x][y] + 1;
      q.push({nx, ny});
    }
    if (mp[x][y] != '.') {
      if (v[mp[x][y] - 'a' + 1]) continue;
      v[mp[x][y] - 'a' + 1] = true;
      for (auto [nx, ny] : qq[mp[x][y] - 'a' + 1]) {
        if (dis[nx][ny]) continue;
        dis[nx][ny] = dis[x][y] + 1;
        q.push({nx, ny});
      }
    }
  }
  cout << (dis[h][w] == 0x3f3f3f3f ? -1 : dis[h][w] - 1) << endl;
}

int main() {
  cin >> h >> w;
  for (int i = 0; i <= w + 1; i++) mp[0][i] = mp[h + 1][i] = '#';
  for (int i = 0; i <= h + 1; i++) mp[i][0] = mp[i][w + 1] = '#';
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> mp[i][j];
      if (mp[i][j] >= 'a' && mp[i][j] <= 'z') qq[mp[i][j] - 'a' + 1].push_back({i, j});
    }
  }

  dijkstra();
}

Problem E

题目描述

给你一个整数序列 $P = (P_1, P_2, \dots, P_N)$，它是 $(1, 2, \dots, N)$ 的一个排列。这里保证 $P$ 不等于 $(1, 2, \dots, N)$。 你想通过执行以下操作零次或多次，让 $P$ 变成序列 $(1, 2, \dots, N)$：

• 选择一对满足 $1 \le i < j \le N$ 的整数 $(i, j)$，交换 $P_i$ 和 $P_j$ 的值。

设 $K$ 是让 $P$ 变成序列 $(1, 2, \dots, N)$ 所需的最少操作次数。 请你求出，有多少种操作可以作为第一步操作，使得通过一系列操作，$P$ 能在 $K$ 步内变成 $(1, 2, \dots, N)$。 两个操作只有在选的整数对 $(i, j)$ 不同的情况下才算不同。

数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le P_i \le N$ ($1 \le i \le N$)
• $P_i \neq P_j$ ($1 \le i < j \le N$)
• 存在 $1 \le i \le N$ 使得 $i \neq P_i$。
• 所有输入值均为整数。

题解

首先根据经典的排列相关理论，将 $i$ 和 $P_i$ 连边构成一张图，可以证明最小的交换次数就是 $n - \text{环的数量}$。 所以最优的交换操作一定要保证每一步都是让环的数量增加一，而这只有交换同一个环上的两个元素才能实现。 所以设这个图有 $m$ 个环，大小为 $s_i$，答案就是 $\sum_{i=1}^m \binom{s_i}{2}$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;

int n, p[N];
bool v[N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> p[i];
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    if (v[i]) continue;
    v[i] = true;
    int cnt = 1;
    int t = i;
    while (p[t] != i) t = p[t], v[t] = true, cnt++;
    ans += 1ll * cnt * (cnt - 1) / 2;
  }
  cout << ans << endl;
}

F - Starry Landscape Photo

题目描述

在 AtCoder 星球的夜空中，有 $N$ 颗星星，这些 $N$ 颗星星从东到西排成一条直线。第 $i$ 颗星从东边数起是这群星中第 $B_i$ 明亮的。 高桥决定用下面的步骤拍摄夜空：

1. 选一对整数 $(l, r)$，满足 $1 \le l \le r \le N$，并调整相机，使得从东边数第 $l, (l+1), \dots, r$ 颗星都能入镜，且没有其他星星进入画面。
2. 选一个整数 $b$，满足 $1 \le b \le N$，打开快门，捕捉所有在这 $N$ 颗星中，亮度排名从第 $1$ 到第 $b$ 的星星（且这些星星都在画面内），且不拍摄其他星星。

数据范围

• $1 \le N \le 5 \times 10^5$
• $1 \le B_i \le N$ ($1 \le i \le N$)
• $B_i \neq B_j$ ($1 \le i < j \le N$)
• 所有输入的值均为整数.

但不能拍出一张没有星星的照片哦。 请你计算，有多少种不同的星星组合能被这样拍摄到？

题解

考虑我们先从小到大枚举最终的集合中最大的数字是 $M$，那么此时可以假设操作 (2) 中的 $b = M$。 那么此时相当于首先只剩下了所有 $\le M$ 的数字，其次我们所有包含 $M$ 的子区间都对应一种唯一的集合。 设数字 $i$ 左边比它小的数字个数为 $l_i$，则子区间数量有 $(l_i + 1)(i - l_i)$ 个。 由于最大数字不同时，显然对应不同的集合，所以总答案就是 $\sum_{i=1}^n (l_i + 1)(i - l_i)$。 而 $l_i$ 可以通过扫一遍+用树状数组/权值线段树/平衡树维护求得。

Problem G

题目描述

给你一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$，还有一正整数 $M$。 请你求出满足以下条件的长度为 $N$ 的非负整数序列 $x = (x_1, x_2, \dots, x_N)$ 的数量： $\sum_{i=1}^N A_i x_i \le M$ 答案可能非常大，请对 $998244353$ 取模后输出。

题解

首先我们可以通过补充一个 $A_i = 1$ 的物品，将题目的限制变为 $\sum_{i=1}^N A_i x_i = M$。

而这是一个标准的卷积问题。第 $i$ 个物品的生成函数是 $1 + x^{A_i} + x^{2A_i} + \dots = \frac{1}{1 - x^{A_i}}$。

所以这个题目的答案就是：

$[x^M] \frac{1}{\prod_{i=1}^N (1 - x^{A_i})}$

记分母的式子为 $Q(x)$，其实就是要求 $[x^M] \frac{1}{Q(x)}$。但是 $M$ 太大了，直接多项式求逆做不了。

注意这里 $Q$ 的次数 $\le 10^4$，而我们又知道多项式求逆本质上就是一个常系数线性递推，所以当然可以构造出对应的线性递推式子后用常系数线性递推做。

但其实还有另一种更简便的方法：Bostan-Mori 算法。这个算法专门用来解决 $[x^M] \frac{P(x)}{Q(x)}$ 的计算（其中 $P, Q$ 是有理多项式）：

首先我们可以将原式变为 $[x^M] \frac{P(x)Q(-x)}{Q(x)Q(-x)}$，可以发现 $Q(x)Q(-x)$ 是偶函数，所以只有偶数项。

所以我们可以记 $Q(x)Q(-x) = T(x^2)$。此外我们将 $P(x)Q(-x)$ 按奇偶分类可以写成 $P(x)Q(-x) = xO(x^2) + E(x^2)$。

问题就变为 $[x^M] \frac{xO(x^2)}{T(x^2)} + [x^M] \frac{E(x^2)}{T(x^2)}$。这样对 $M$ 进行奇偶分类讨论后，就可以递归到两个中的其中一个去递归计算。此时 $M$ 就会减半。而 $O, E, T$ 的多项式次数与 $P, Q$ 还是相同的。