【abc436】AtCoder Beginner Contest 436

博主： DHEnry
发布时间：2025 年 12 月 14 日
29 次浏览
暂无评论
9088字数
分类：编程 Online Judge Atcoder

# abc436 反思

# 题面

### A - o 判定

#### 问题描述

给定一个整数 $ N $ 和一个由小写英文字母组成的字符串 $ S $，其长度**小于** $ N $。

请输出通过持续在字符串 $ S $ 的开头添加小写英文字母 `o` 直到其长度变为 $ N $ 所得到的字符串。

#### 约束条件

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

#### 输入格式

输入通过标准输入以如下格式给出：

$$
N
$$

$$
S
$$

#### 输出格式

输出答案字符串。

#### 样例输入 1

```
5
abc
```

#### 样例输出 1

```
ooabc
```

解释：$ N=5 $，$ S $ 的长度为 $ 3 $，因此需要在 $ S $ 的开头添加 $ 5 - 3 = 2 $ 个 `o`。

#### 样例输入 2

```
2
o
```

#### 样例输出 2

```
oo
```

#### 样例输入 3

```
12
vgxgpuam
```

#### 样例输出 3

```
oooovgxgpuam
```

---

### B - 幻方阵

#### 问题描述

给定一个大于等于 $ 3 $ 的奇数 $ N $。

有一个 $ N $ 行 $ N $ 列的方格，初始时所有格子均为空白。现在，按照以下步骤在方格中的每个格子上写入整数。
记格子 $ (i, j) $ 表示从上到下第 $ i+1 $ 行、从左到右第 $ j+1 $ 列的格子（$ 0 \leq i < N, 0 \leq j < N $）。

1. 在格子 $ \left(0, \frac{N-1}{2}\right) $ 中写入 $ 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 \leq N \leq 99 $
- $N$ 是奇数

#### 输入格式

输入通过标准输入以如下格式给出：

$$
N
$$

#### 输出格式

设格子 $ (i, j) $ 中写入的整数为 $ a_{i, j} $，并按如下格式输出：

$$
a_{0, 0} \ a_{0, 1} \ \dots \ a_{0, N-1} \\
\vdots \\
a_{N-1, 0} \ a_{N-1, 1} \ \dots \ a_{N-1, N-1}
$$

#### 样例输入 1

```
3
```

#### 样例输出 1

```
8 1 6
3 5 7
4 9 2
```

解释：

1. 在格子 $ (0, \frac{3-1}{2}) = (0, 1) $ 中写入 $ 1 $。
2. 格子 $ ((0-1) \bmod 3, (1+1) \bmod 3) = (2, 2) $ 是空白的，因此写入 $ 2 $。
3. 格子 $ ((2-1) \bmod 3, (2+1) \bmod 3) = (1, 0) $ 是空白的，因此写入 $ 3 $。
4. 格子 $ ((1-1) \bmod 3, (0+1) \bmod 3) = (0, 1) $ 非空白，因此在格子 $ ((1+1) \bmod 3, 0) = (2, 0) $ 中写入 $ 4 $。
5. 依此类推……

#### 样例输入 2

```
5
```

#### 样例输出 2

```
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
```

---

### C - 放置 2×2 方块

#### 问题描述

有一个 $ N $ 行 $ N $ 列的方格。记格子 $ (i, j) $ 表示从上到下第 $ i $ 行、从左到右第 $ j $ 列的格子。初始时，方格上没有任何方块。

现在将进行 $ M $ 次操作。第 $ i $ 次操作（$ 1 \leq i \leq M $）如下：

- 将以格子 $ (R_i, C_i) $ 为左上角的 $ 2 \times 2 $ 区域的方块放置到方格上，当且仅当该区域与已放置的其他方块不重叠。
  更精确地说，对于单元格集合 $ S = \{ (R_i, C_i), (R_i+1, C_i), (R_i, C_i+1), (R_i+1, C_i+1) \} $，如果方格上已存在的方块占据了 $ S $ 中的任意一个格子，则什么也不做；否则，放置一个占据 $ S $ 中全部 4 个格子的方块。

请计算所有操作结束后，方格上共有多少个方块。

#### 约束条件

- $ 2 \leq N \leq 10^9 $
- $ 1 \leq M \leq 2 \times 10^5 $
- $ 1 \leq R_i, C_i \leq N-1 $
- 输入均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N \ M
$$

$$
R_1 \ C_1
$$

$$
R_2 \ C_2
$$

$$
\vdots
$$

$$
R_M \ C_M
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
4 3
1 1
2 2
2 3
```

#### 样例输出 1

```
2
```

解释：
下图展示了操作过程，黑色填充区域表示方块，红色边框区域表示下一个要放置方块的位置。
![abc436_c.png](https://www.fmcraft.top/usr/uploads/2025/12/1188774367.png)

1. 操作 1：以格子 $ (1, 1) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。
2. 操作 2：以格子 $ (2, 2) $ 为左上角的 $ 2 \times 2 $ 区域中，格子 $ (2, 2) $ 已被占据，因此什么也不做。
3. 操作 3：以格子 $ (2, 3) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。

因此，所有操作结束后，方格上有 2 个方块。

#### 样例输入 2

```
1000000000 4
1 1
1 101
101 1
101 101
```

#### 样例输出 2

```
4
```

所有操作都可以放置方块。

#### 样例输入 3

```
8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1
```

#### 样例输出 3

```
8
```

可能存在满足 $ (R_i, C_i) = (R_j, C_j) $ 的 $ i, j $（$ i \neq j $）。

---

### D - 传送迷宫

#### 问题描述

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

- `.`：空单元格
- `#`：障碍单元格
- 小写英文字母（`a` - `z`）：传送单元格

在迷宫中，你可以按任意顺序执行以下两种类型的操作任意多次：

1. **步行**：从当前单元格移动到上下左右四个方向相邻的单元格。但是，不能移动到障碍单元格或网格外。
2. **传送**：当你处于一个传送单元格时，可以移动到写有相同字母的任意传送单元格。

判断是否可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，如果可能，求出所需的最小总操作次数。

#### 约束条件

- $ 1 \leq H, W \leq 1000 $
- $ H \times W \geq 2 $
- $ H $ 和 $ W $ 为整数
- $ S_{i, j} $ 是 `.`、`#` 或小写英文字母
- $ S_{1, 1} \neq \# $
- $ S_{H, W} \neq \# $

#### 输入格式

输入通过标准输入按以下格式给出：

$$
H \ W
$$

$$
S_{1, 1} \ S_{1, 2} \ \dots \ S_{1, W}
$$

$$
\vdots
$$

$$
S_{H, 1} \ S_{H, 2} \ \dots \ S_{H, W}
$$

#### 输出格式

如果可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，输出所需的最小总操作次数；否则输出 `-1`。

#### 样例输入 1

```
3 4
..a.
####
ba#b
```

#### 样例输出 1

```
5
```

解释：
可以通过以下操作从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $：

1. 从 $ (1, 1) $ 步行到 $ (1, 2) $
2. 从 $ (1, 2) $ 步行到 $ (1, 3) $
3. 从 $ (1, 3) $ 传送到 $ (3, 2) $
4. 从 $ (3, 2) $ 步行到 $ (3, 1) $
5. 从 $ (3, 1) $ 传送到 $ (3, 4) $

总操作次数为 $ 5 $，这是最小值。

#### 样例输入 2

```
3 4
..a.
####
b.#b
```

#### 样例输出 2

```
-1
```

无法从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $。

#### 样例输入 3

```
4 4
xxxx
xxxx
xxxx
xxxx
```

#### 样例输出 3

```
1
```

#### 样例输入 4

```
7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.
```

#### 样例输出 4

```
12
```

---

### E - 最小交换次数

#### 问题描述

给定一个整数序列 $ P = (P_1, P_2, \dots, P_N) $，它是 $ (1, 2, \dots, N) $ 的一个排列。这里保证 $ P $ 不等于 $ (1, 2, \dots, N) $。

你想要执行零次或多次以下操作，使 $ P $ 匹配序列 $ (1, 2, \dots, N) $：

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

设 $ K $ 为使 $ P $ 匹配序列 $ (1, 2, \dots, N) $ 所需的最少操作次数。

找出可以作为第一次操作的操作数量，使得存在一个操作序列能在 $ K $ 次操作内使 $ P $ 匹配序列 $ (1, 2, \dots, N) $。当且仅当选择的整数对 $ (i, j) $ 不同时，两个操作被视为不同。

#### 约束条件

- $ 2 \leq N \leq 3 \times 10^5 $
- $ 1 \leq P_i \leq N $（$ 1 \leq i \leq N $）
- $ P_i \neq P_j $（$ 1 \leq i < j \leq N $）
- 存在 $ 1 \leq i \leq N $ 使得 $ i \neq P_i $
- 所有输入值均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N
$$

$$
P_1 \ P_2 \ \dots \ P_N
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
5
3 1 4 2 5
```

#### 样例输出 1

```
6
```

例如，可以通过以下三次操作达成目标：

1. 选择 $ (i, j) = (1, 2) $。$ P $ 变为 $ (1, 3, 4, 2, 5) $
2. 选择 $ (i, j) = (2, 4) $。$ P $ 变为 $ (1, 2, 4, 3, 5) $
3. 选择 $ (i, j) = (3, 4) $。$ P $ 变为 $ (1, 2, 3, 4, 5) $

无法在两次或更少操作内达成目标，因此 $ K = 3 $。

如上所述，第一次操作选择 $ (1, 2) $ 可以在三次操作内达成目标。此外，如果第一次操作选择 $ (1, 3) $、$ (1, 4) $、$ (2, 3) $、$ (2, 4) $、$ (3, 4) $ 中的任意一个，那么通过适当执行接下来的两次操作，也可以使 $ P $ 变为 $ (1, 2, 3, 4, 5) $。

因此，输出 6。

#### 样例输入 2

```
2
2 1
```

#### 样例输出 2

```
1
```

#### 样例输入 3

```
20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
```

#### 样例输出 3

```
77
```

---

### F - 星空风景照

#### 问题描述

在从 AtCoder 星球看到的夜空中，有 $ N $ 颗星星，这些星星自东向西排成一条直线。从东数第 $ i $ 颗星星（$ 1 \leq i \leq N $）是这些星星中第 $ B_i $ 亮的。

Takahashi 决定用以下步骤拍摄夜空：

1. 选择一对整数 $ (l, r) $ 满足 $ 1 \leq l \leq r \leq N $，并调整相机，使得从东数第 $ l $ 颗、第 $ (l+1) $ 颗、…、第 $ r $ 颗星星全部进入取景框，且没有其他星星进入取景框。
2. 选择一个整数 $ b $ 满足 $ 1 \leq b \leq N $，并打开快门，使得所有 $ N $ 颗星星中亮度排名在第 1 到第 $ b $ 位（且在取景框内）的星星被拍摄到，其他星星不被拍摄。
   但是，他不能拍摄没有星星被捕捉到的照片。

求用这种方式拍摄的照片中，可以捕捉到的星星的不同集合的数量。

#### 约束条件

- $ 1 \leq N \leq 5 \times 10^5 $
- $ 1 \leq B_i \leq N $（$ 1 \leq i \leq N $）
- $ B_i \neq B_j $（$ 1 \leq i < j \leq N $）
- 所有输入值均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N
$$

$$
B_1 \ B_2 \ \dots \ B_N
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
4
3 1 4 2
```

#### 样例输出 1

```
12
```

例如，当 $ (l, r) = (2, 4) $，$ b = 3 $ 时，你可以拍摄包含两颗星星的照片：从东数第 2 颗星星和第 4 颗星星。

包括这个在内，你可以拍摄以下 12 种不同的星星集合。每张照片中，较东的星星排在较左边，第 $i$ 亮的星星用整数 $i$ 标记。
![abc436_f.png](https://www.fmcraft.top/usr/uploads/2025/12/2559987180.png)

没有其他集合可以被捕捉，因此输出 12。

#### 样例输入 2

```
7
1 2 3 4 5 6 7
```

#### 样例输出 2

```
28
```

#### 样例输入 3

```
20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
```

#### 样例输出 3

```
627
```

---

### G - 线性不等式

#### 问题描述

给定一个长度为 $ N $ 的正整数序列 $ A = (A_1, A_2, \dots, A_N) $ 和一个正整数 $ M $。

求满足以下条件的非负整数序列 $ x = (x_1, x_2, \dots, x_N) $ 的数量：

$$
\sum_{i=1}^{N} A_i x_i \leq M
$$

由于该数量可能非常大，请输出其对 $ 998244353 $ 取模的结果。

#### 约束条件

- $ 1 \leq N \leq 100 $
- $ 1 \leq A_i \leq 100 $（$ 1 \leq i \leq N $）
- $ 1 \leq M \leq 10^{18} $
- 所有输入值均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N \ M
$$

$$
A_1 \ A_2 \ \dots \ A_N
$$

#### 输出格式

输出满足条件的非负整数序列的数量（对 $ 998244353 $ 取模）。

#### 样例输入 1

```
4 6
5 4 3 2
```

#### 样例输出 1

```
10
```

满足条件的序列 $ x $ 有以下 10 个：
$ (0,0,0,0) $, $ (0,0,0,1) $, $ (0,0,0,2) $, $ (0,0,0,3) $, $ (0,0,1,0) $, $ (0,0,1,1) $, $ (0,0,2,0) $, $ (0,1,0,0) $, $ (0,1,0,1) $, $ (1,0,0,0) $。

因此，输出 10。

#### 样例输入 2

```
6 89
4 7 5 10 7 6
```

#### 样例输出 2

```
38469
```

#### 样例输入 3

```
1 1000000007
1
```

#### 样例输出 3

```
1755655
```

满足条件的序列 $ x $ 有 $ 1000000008 $ 个。

输出其对 $ 998244353 $ 取模的结果，即 $ 1755655 $。

#### 样例输入 4

```
20 738894495848985641
40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37
```

#### 样例输出 4

```
31156940
```

# 反思

### A - o 判定

**这是一道水题，但我只会做水题**
整理一下题意，意思就是说给出 $N$ 和 $S$，输出 $N-S_{size}$ 个 `o` 用于补全，然后再输出原来的字符串 $S$
时间复杂度：$O(N)$，可以通过！
然后就没什么东西了
可能需要注意一下 for 循环的三个语句，到底在做什么：

> 令 $k$ 为 $N-S_{size}$
> 若 $N=5 ,\space S=\text{fuck}$
> 则 $k=N-S_{size}=5-4=1$
> 所以应该输出 $1$ 个 `o`
> 然后再输出完整的 `S`

```cpp
#include <bits/stdc++.h>
using namespace std;
int x,i;
string s;
int main(){
	cin>>x>>s;
	for(i=1;i<=x-s.length();i++) cout<<'o';
	cout<<s;
}
```

就是这样，so easy

### B - 幻方阵

这题需要一定的耐心来阅读题面文本。
这题可以直接根据 题目描述 的题进行暴力编写程序，不需要一些复杂的抽象概念思考建模。
我直接贴代码了，毫无技术含量。

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100][100],n,r,c,k,nr,nc,i,j;
int main(){
	cin>>n;c=(n-1)/2;
	for(k=1;k<=n*n;k++){
		a[r][c]=k;
		nr=(r-1+n)%n;
		nc=(c+1)%n;
		if(a[nr][nc]!=0) nr=(r+1)%n,nc=c;
		r=nr;
		c=nc;
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cout<<a[i][j];
			if(j<n-1) cout<<" ";
		}
		cout<<"\n";
	}
	return 0;
}
```

最后修改：2025 年 12 月 14 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱

地址

【abc436】AtCoder Beginner Contest 436

DHEnry • 2025 年 12 月 14 日

# abc436 反思

# 题面

### A - o 判定

#### 问题描述

给定一个整数 $ N $ 和一个由小写英文字母组成的字符串 $ S $，其长度**小于** $ N $。

请输出通过持续在字符串 $ S $ 的开头添加小写英文字母 `o` 直到其长度变为 $ N $ 所得到的字符串。

#### 约束条件

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

#### 输入格式

输入通过标准输入以如下格式给出：

$$
N
$$

$$
S
$$

#### 输出格式

输出答案字符串。

#### 样例输入 1

```
5
abc
```

#### 样例输出 1

```
ooabc
```

解释：$ N=5 $，$ S $ 的长度为 $ 3 $，因此需要在 $ S $ 的开头添加 $ 5 - 3 = 2 $ 个 `o`。

#### 样例输入 2

```
2
o
```

#### 样例输出 2

```
oo
```

#### 样例输入 3

```
12
vgxgpuam
```

#### 样例输出 3

```
oooovgxgpuam
```

---

### B - 幻方阵

#### 问题描述

给定一个大于等于 $ 3 $ 的奇数 $ N $。

请找出按照此过程在每个格子中写入的整数。
可以证明，每个格子恰好会被写入一个整数。

#### 约束条件

- $ 3 \leq N \leq 99 $
- $N$ 是奇数

#### 输入格式

输入通过标准输入以如下格式给出：

$$
N
$$

#### 输出格式

设格子 $ (i, j) $ 中写入的整数为 $ a_{i, j} $，并按如下格式输出：

$$
a_{0, 0} \ a_{0, 1} \ \dots \ a_{0, N-1} \\
\vdots \\
a_{N-1, 0} \ a_{N-1, 1} \ \dots \ a_{N-1, N-1}
$$

#### 样例输入 1

```
3
```

#### 样例输出 1

```
8 1 6
3 5 7
4 9 2
```

解释：

#### 样例输入 2

```
5
```

#### 样例输出 2

```
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
```

---

### C - 放置 2×2 方块

#### 问题描述

有一个 $ N $ 行 $ N $ 列的方格。记格子 $ (i, j) $ 表示从上到下第 $ i $ 行、从左到右第 $ j $ 列的格子。初始时，方格上没有任何方块。

现在将进行 $ M $ 次操作。第 $ i $ 次操作（$ 1 \leq i \leq M $）如下：

请计算所有操作结束后，方格上共有多少个方块。

#### 约束条件

- $ 2 \leq N \leq 10^9 $
- $ 1 \leq M \leq 2 \times 10^5 $
- $ 1 \leq R_i, C_i \leq N-1 $
- 输入均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N \ M
$$

$$
R_1 \ C_1
$$

$$
R_2 \ C_2
$$

$$
\vdots
$$

$$
R_M \ C_M
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
4 3
1 1
2 2
2 3
```

#### 样例输出 1

```
2
```

因此，所有操作结束后，方格上有 2 个方块。

#### 样例输入 2

```
1000000000 4
1 1
1 101
101 1
101 101
```

#### 样例输出 2

```
4
```

所有操作都可以放置方块。

#### 样例输入 3

```
8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1
```

#### 样例输出 3

```
8
```

可能存在满足 $ (R_i, C_i) = (R_j, C_j) $ 的 $ i, j $（$ i \neq j $）。

---

### D - 传送迷宫

#### 问题描述

- `.`：空单元格
- `#`：障碍单元格
- 小写英文字母（`a` - `z`）：传送单元格

在迷宫中，你可以按任意顺序执行以下两种类型的操作任意多次：

判断是否可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，如果可能，求出所需的最小总操作次数。

#### 约束条件

- $ 1 \leq H, W \leq 1000 $
- $ H \times W \geq 2 $
- $ H $ 和 $ W $ 为整数
- $ S_{i, j} $ 是 `.`、`#` 或小写英文字母
- $ S_{1, 1} \neq \# $
- $ S_{H, W} \neq \# $

#### 输入格式

输入通过标准输入按以下格式给出：

$$
H \ W
$$

$$
S_{1, 1} \ S_{1, 2} \ \dots \ S_{1, W}
$$

$$
\vdots
$$

$$
S_{H, 1} \ S_{H, 2} \ \dots \ S_{H, W}
$$

#### 输出格式

如果可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，输出所需的最小总操作次数；否则输出 `-1`。

#### 样例输入 1

```
3 4
..a.
####
ba#b
```

#### 样例输出 1

```
5
```

解释：
可以通过以下操作从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $：

1. 从 $ (1, 1) $ 步行到 $ (1, 2) $
2. 从 $ (1, 2) $ 步行到 $ (1, 3) $
3. 从 $ (1, 3) $ 传送到 $ (3, 2) $
4. 从 $ (3, 2) $ 步行到 $ (3, 1) $
5. 从 $ (3, 1) $ 传送到 $ (3, 4) $

总操作次数为 $ 5 $，这是最小值。

#### 样例输入 2

```
3 4
..a.
####
b.#b
```

#### 样例输出 2

```
-1
```

无法从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $。

#### 样例输入 3

```
4 4
xxxx
xxxx
xxxx
xxxx
```

#### 样例输出 3

```
1
```

#### 样例输入 4

```
7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.
```

#### 样例输出 4

```
12
```

---

### E - 最小交换次数

#### 问题描述

给定一个整数序列 $ P = (P_1, P_2, \dots, P_N) $，它是 $ (1, 2, \dots, N) $ 的一个排列。这里保证 $ P $ 不等于 $ (1, 2, \dots, N) $。

你想要执行零次或多次以下操作，使 $ P $ 匹配序列 $ (1, 2, \dots, N) $：

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

设 $ K $ 为使 $ P $ 匹配序列 $ (1, 2, \dots, N) $ 所需的最少操作次数。

#### 约束条件

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N
$$

$$
P_1 \ P_2 \ \dots \ P_N
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
5
3 1 4 2 5
```

#### 样例输出 1

```
6
```

例如，可以通过以下三次操作达成目标：

1. 选择 $ (i, j) = (1, 2) $。$ P $ 变为 $ (1, 3, 4, 2, 5) $
2. 选择 $ (i, j) = (2, 4) $。$ P $ 变为 $ (1, 2, 4, 3, 5) $
3. 选择 $ (i, j) = (3, 4) $。$ P $ 变为 $ (1, 2, 3, 4, 5) $

无法在两次或更少操作内达成目标，因此 $ K = 3 $。

因此，输出 6。

#### 样例输入 2

```
2
2 1
```

#### 样例输出 2

```
1
```

#### 样例输入 3

```
20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
```

#### 样例输出 3

```
77
```

---

### F - 星空风景照

#### 问题描述

Takahashi 决定用以下步骤拍摄夜空：

求用这种方式拍摄的照片中，可以捕捉到的星星的不同集合的数量。

#### 约束条件

- $ 1 \leq N \leq 5 \times 10^5 $
- $ 1 \leq B_i \leq N $（$ 1 \leq i \leq N $）
- $ B_i \neq B_j $（$ 1 \leq i < j \leq N $）
- 所有输入值均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N
$$

$$
B_1 \ B_2 \ \dots \ B_N
$$

#### 输出格式

输出答案。

#### 样例输入 1

```
4
3 1 4 2
```

#### 样例输出 1

```
12
```

例如，当 $ (l, r) = (2, 4) $，$ b = 3 $ 时，你可以拍摄包含两颗星星的照片：从东数第 2 颗星星和第 4 颗星星。

没有其他集合可以被捕捉，因此输出 12。

#### 样例输入 2

```
7
1 2 3 4 5 6 7
```

#### 样例输出 2

```
28
```

#### 样例输入 3

```
20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
```

#### 样例输出 3

```
627
```

---

### G - 线性不等式

#### 问题描述

给定一个长度为 $ N $ 的正整数序列 $ A = (A_1, A_2, \dots, A_N) $ 和一个正整数 $ M $。

求满足以下条件的非负整数序列 $ x = (x_1, x_2, \dots, x_N) $ 的数量：

$$
\sum_{i=1}^{N} A_i x_i \leq M
$$

由于该数量可能非常大，请输出其对 $ 998244353 $ 取模的结果。

#### 约束条件

- $ 1 \leq N \leq 100 $
- $ 1 \leq A_i \leq 100 $（$ 1 \leq i \leq N $）
- $ 1 \leq M \leq 10^{18} $
- 所有输入值均为整数

#### 输入格式

输入通过标准输入按以下格式给出：

$$
N \ M
$$

$$
A_1 \ A_2 \ \dots \ A_N
$$

#### 输出格式

输出满足条件的非负整数序列的数量（对 $ 998244353 $ 取模）。

#### 样例输入 1

```
4 6
5 4 3 2
```

#### 样例输出 1

```
10
```

满足条件的序列 $ x $ 有以下 10 个：
$ (0,0,0,0) $, $ (0,0,0,1) $, $ (0,0,0,2) $, $ (0,0,0,3) $, $ (0,0,1,0) $, $ (0,0,1,1) $, $ (0,0,2,0) $, $ (0,1,0,0) $, $ (0,1,0,1) $, $ (1,0,0,0) $。

因此，输出 10。

#### 样例输入 2

```
6 89
4 7 5 10 7 6
```

#### 样例输出 2

```
38469
```

#### 样例输入 3

```
1 1000000007
1
```

#### 样例输出 3

```
1755655
```

满足条件的序列 $ x $ 有 $ 1000000008 $ 个。

输出其对 $ 998244353 $ 取模的结果，即 $ 1755655 $。

#### 样例输入 4

```
20 738894495848985641
40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37
```

#### 样例输出 4

```
31156940
```

# 反思

### A - o 判定

> 令 $k$ 为 $N-S_{size}$
> 若 $N=5 ,\space S=\text{fuck}$
> 则 $k=N-S_{size}=5-4=1$
> 所以应该输出 $1$ 个 `o`
> 然后再输出完整的 `S`

```cpp
#include <bits/stdc++.h>
using namespace std;
int x,i;
string s;
int main(){
	cin>>x>>s;
	for(i=1;i<=x-s.length();i++) cout<<'o';
	cout<<s;
}
```

就是这样，so easy

### B - 幻方阵

【abc436】AtCoder Beginner Contest 436

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

IP地址修改器 [bilibili配套]

关于 2025 CSP

个人对于身高歧视的评价

FMCRAFT Res领地插件使用教程【官方 and 非官方】

关于 2025 年浙江省初中名校发展共同体七年级第一学期考试反思

HUSTOJ常见问答（Plus版）

【abc435】AtCoder Beginner Contest 435

2025/12/22 to 2025/12/28 周记

2023年CSP-J第一轮卷后感

PHP 其实也能写在线评测系统：HUSTOJ 从安装到使用小白式讲解

【abc436】AtCoder Beginner Contest 436

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【abc436】AtCoder Beginner Contest 436

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款