【abc436】AtCoder Beginner Contest 436
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
oooovgxgpuamB - 幻方阵
问题描述
给定一个大于等于 $ 3 $ 的奇数 $ N $。
有一个 $ N $ 行 $ N $ 列的方格，初始时所有格子均为空白。现在，按照以下步骤在方格中的每个格子上写入整数。
记格子 $ (i, j) $ 表示从上到下第 $ i+1 $ 行、从左到右第 $ j+1 $ 列的格子（$ 0 \leq i < N, 0 \leq j < N $）。
- 在格子 $ \left(0, \frac{N-1}{2}\right) $ 中写入 $ 1 $。
重复以下操作 $ 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解释：
- 在格子 $ (0, \frac{3-1}{2}) = (0, 1) $ 中写入 $ 1 $。
- 格子 $ ((0-1) \bmod 3, (1+1) \bmod 3) = (2, 2) $ 是空白的，因此写入 $ 2 $。
- 格子 $ ((2-1) \bmod 3, (2+1) \bmod 3) = (1, 0) $ 是空白的，因此写入 $ 3 $。
- 格子 $ ((1-1) \bmod 3, (0+1) \bmod 3) = (0, 1) $ 非空白，因此在格子 $ ((1+1) \bmod 3, 0) = (2, 0) $ 中写入 $ 4 $。
- 依此类推……
样例输入 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 9C - 放置 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解释：
下图展示了操作过程，黑色填充区域表示方块，红色边框区域表示下一个要放置方块的位置。
- 操作 1：以格子 $ (1, 1) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。
- 操作 2：以格子 $ (2, 2) $ 为左上角的 $ 2 \times 2 $ 区域中，格子 $ (2, 2) $ 已被占据，因此什么也不做。
- 操作 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, 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, 2) $
- 从 $ (1, 2) $ 步行到 $ (1, 3) $
- 从 $ (1, 3) $ 传送到 $ (3, 2) $
- 从 $ (3, 2) $ 步行到 $ (3, 1) $
- 从 $ (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
12E - 最小交换次数
问题描述
给定一个整数序列 $ 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例如，可以通过以下三次操作达成目标：
- 选择 $ (i, j) = (1, 2) $。$ P $ 变为 $ (1, 3, 4, 2, 5) $
- 选择 $ (i, j) = (2, 4) $。$ P $ 变为 $ (1, 2, 4, 3, 5) $
- 选择 $ (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
77F - 星空风景照
问题描述
在从 AtCoder 星球看到的夜空中，有 $ N $ 颗星星，这些星星自东向西排成一条直线。从东数第 $ i $ 颗星星（$ 1 \leq i \leq N $）是这些星星中第 $ B_i $ 亮的。
Takahashi 决定用以下步骤拍摄夜空：
- 选择一对整数 $ (l, r) $ 满足 $ 1 \leq l \leq r \leq N $，并调整相机，使得从东数第 $ l $ 颗、第 $ (l+1) $ 颗、…、第 $ r $ 颗星星全部进入取景框，且没有其他星星进入取景框。
- 选择一个整数 $ 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$ 标记。
没有其他集合可以被捕捉，因此输出 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
627G - 线性不等式
问题描述
给定一个长度为 $ 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
#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 - 幻方阵
这题需要一定的耐心来阅读题面文本。
这题可以直接根据 题目描述 的题进行暴力编写程序，不需要一些复杂的抽象概念思考建模。
我直接贴代码了，毫无技术含量。
#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;
}
