壹鲦热带鱼的小窝 - 算法
type: channel
link: https://www.fmcraft.top/tag/%E7%AE%97%E6%B3%95/
items: 反思 - UNIQUE VISION Programming Contest 2025 Christ
items: 【abc436】AtCoder Beginner Contest 436
items: P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解
items: 反思 - UNIQUE VISION Programming Contest 2025 Christmas (AtCoder Beginner Contest 437)
items: 【abc435】AtCoder Beginner Contest 435
items: 关于 MX-S11
items: 尝试通过打表的方法通过《P1304 哥德巴赫猜想》
items: 学校训练 栈+队列+堆+优先队列【历史存档】

反思 - UNIQUE VISION Programming Contest 2025 Christ
type: item
date: 2026-03-23T19:47:00+08:00
description: (x)abc437题面A - 英尺分值：100 分题目描述1 英尺等于 12 英寸。请问 A 英尺 B 英寸换算成英寸是多少英寸？约束条件$1 \leq A \leq 8$$0 \leq B \leq 11$所有输入值均为整数输入格式输入通过标准输入按以下格式给出：A B输出格式将答案输出在一行中。省略单位（英寸）进行输出。输入样例 16 7输出样例 1796 英尺 7 英寸换算成英寸为 $6 \times 12 + 7 = 79$ 英寸。输入样例 24 11输出样例 2594 英尺 11 英寸换算成英寸为 $4 \times 12 + 11 = 59$ 英寸。输入样例 38 0输出样例 3968 英尺 0 英寸换算成英寸为 $8 \times 12 + 0 = 96$ 英寸。B - 幸运抽奖题目描述有一个 $H$ 行 $W$ 列的网格。每个格子中写着一个整数，所有整数互不相同。从上到下第 $i$ 行、从左到右第 $j$ 列的格子中写有整数 $A_{i,j}$。现在，主持人喊出了 $N$ 个互不相同的整数 $B_1, \dots, B_N$。对于每一行，计算出主持人喊出的整数中，有多少个出现在该行中。这些数量的最大值是多少？约束条件$1 \leq H \leq 3$$1 \leq W \leq 5$$1 \leq N \leq 90$$1 \leq A_{i,j} \leq 90$$A_{i,j}$ 互不相同$1 \leq B_i \leq 90$$B_i$ 互不相同所有输入值均为整数输入格式输入通过标准输入给出，格式如下：H W N A_{1,1} ... A_{1,W} ... A_{H,1} ... A_{H,W} B_1 ... B_N输出格式输出一行，包含答案。输入样例 13 4 5 12 3 5 7 6 10 11 9 1 2 4 8 2 4 9 6 11输出样例 13输入样例 23 5 2 81 63 31 16 15 30 3 6 54 24 26 41 48 64 66 44 79输出样例 20输入样例 33 5 12 78 19 70 58 83 12 30 80 20 27 48 71 8 43 82 82 30 43 8 80 70 20 78 12 71 19 48输出样例 35C - 驯鹿与雪橇 2题目描述有 $N$ 头驯鹿和 1 架雪橇。第 $i$ 头驯鹿的体重为 $W_i$，力量为 $P_i$。对于每头驯鹿，需要选择是让它“拉雪橇”还是“乘坐雪橇”。但是，拉雪橇的驯鹿的力量总和必须大于等于乘坐雪橇的驯鹿的体重总和。最多可以让多少头驯鹿乘坐雪橇？给定 $T$ 个测试用例。请分别回答每个用例。约束条件$1 \leq T \leq 10^5$$1 \leq N \leq 3 \times 10^5$$1 \leq W_i, P_i \leq 10^9$所有输入值均为整数。单个输入文件中所有 $N$ 的总和不超过 $3 \times 10^5$。输入格式输入通过标准输入给出，格式如下：T case_1 case_2 ⋮ case_T每个测试用例的格式如下：N W_1 P_1 W_2 P_2 ⋮ W_N P_N输出格式输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。输入样例 13 3 3 1 4 1 5 9 5 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 10 133180711 458704923 531424946 225863856 141986070 637075158 500770732 289806469 502866767 408857335 559714289 569084545 287444582 992432993 559747907 753133304 432846188 949871298 727072164 756020367输出样例 12 0 6D - 差之和题目描述给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个长度为 $M$ 的正整数序列 $B = (B_1, B_2, \dots, B_M)$。求 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|$ 的值，并对 $998244353$ 取模。约束条件$1 \leq N, M \leq 3 \times 10^5$$1 \leq A_i, B_j < 998244353$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N M A_1 A_2 ... A_N B_1 B_2 ... B_M输出格式…

【abc436】AtCoder Beginner Contest 436
type: item
date: 2026-03-23T19:47:00+08:00
description: abc436 反思题面A - o 判定问题描述给定一个整数 $ N $ 和一个由小写英文字母组成的字符串 $ S $，其长度小于 $ N $。请输出通过持续在字符串 $ S $ 的开头添加小写英文字母 o 直到其长度变为 $ N $ 所得到的字符串。约束条件$ 2 \leq N \leq 100 $$ N $ 为整数$ S $ 是由小写英文字母组成的字符串，长度介于 $ 1 $ 到 $ N-1 $ 之间（包含边界）。输入格式输入通过标准输入以如下格式给出：$$ N $$$$ S $$输出格式输出答案字符串。样例输入 15 abc样例输出 1ooabc解释：$ N=5 $，$ S $ 的长度为 $ 3 $，因此需要在 $ S $ 的开头添加 $ 5 - 3 = 2 $ 个 o。样例输入 22 o样例输出 2oo样例输入 312 vgxgpuam样例输出 3oooovgxgpuamB - 幻方阵问题描述给定一个大于等于 $ 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} $$样例输入 13样例输出 18 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 $。依此类推……样例输入 25样例输出 217 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…

P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解
type: item
date: 2026-03-23T19:46:00+08:00
description: 传送门题目更好的阅读体验题目大意读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。分析题目括号字符串中，每一个叶节点都是对应一个 ()；字符串中的深度比实际深度大 $1$，需要减去 $1$ 再进行计算；扫描字符串，遇到 ( 深度 $+1$，否则深度 $-1$；当遇到 () 时，当前的深度 $-1$ 就是根节点到此处的距离；时间复杂度为 $O(n)$ 可以通过此题。算法步骤扫描字符串，记为 $s_i$；对 $s_i$ 作判断，( 和 ) 需要分情况讨论；如果遇到 (，深度 $+1$，并且，如果下一个字符是 ) 说明找到了叶节点，将 深度-1 记录到答案，需要注意下个字符是否为合法边界；如果遇到 )，深度 $-1$；输出答案。代码#include <bits/stdc++.h> #define int long long // 将所有的 int 替换成 long long，否则会爆 int using namespace std; string s; int ans,depth,i; signed main(){ // 因为 int 会被替换成 long long，但是返回值不允许 long long，所以使用 signed cin>>s; // 对应步骤 1 for(i=0;i<s.length();i++) // 对应步骤 2 if(s[i]==\'(\'){ // 对应步骤 3 及下面两行 depth++; if(i+1<s.length()&&s[i+1]==\')\') ans+=depth-1; // 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 }else depth--; // 对应步骤 4 cout<<ans; // 对应步骤 5 }

反思 - UNIQUE VISION Programming Contest 2025 Christmas (AtCoder Beginner Contest 437)
type: item
date: 2025-12-20T22:09:00+08:00
description: abc437题面A - 英尺分值：100 分题目描述1 英尺等于 12 英寸。请问 A 英尺 B 英寸换算成英寸是多少英寸？约束条件$1 \leq A \leq 8$$0 \leq B \leq 11$所有输入值均为整数输入格式输入通过标准输入按以下格式给出：A B输出格式将答案输出在一行中。省略单位（英寸）进行输出。输入样例 16 7输出样例 1796 英尺 7 英寸换算成英寸为 $6 \times 12 + 7 = 79$ 英寸。输入样例 24 11输出样例 2594 英尺 11 英寸换算成英寸为 $4 \times 12 + 11 = 59$ 英寸。输入样例 38 0输出样例 3968 英尺 0 英寸换算成英寸为 $8 \times 12 + 0 = 96$ 英寸。B - 幸运抽奖题目描述有一个 $H$ 行 $W$ 列的网格。每个格子中写着一个整数，所有整数互不相同。从上到下第 $i$ 行、从左到右第 $j$ 列的格子中写有整数 $A_{i,j}$。现在，主持人喊出了 $N$ 个互不相同的整数 $B_1, \dots, B_N$。对于每一行，计算出主持人喊出的整数中，有多少个出现在该行中。这些数量的最大值是多少？约束条件$1 \leq H \leq 3$$1 \leq W \leq 5$$1 \leq N \leq 90$$1 \leq A_{i,j} \leq 90$$A_{i,j}$ 互不相同$1 \leq B_i \leq 90$$B_i$ 互不相同所有输入值均为整数输入格式输入通过标准输入给出，格式如下：H W N A_{1,1} ... A_{1,W} ... A_{H,1} ... A_{H,W} B_1 ... B_N输出格式输出一行，包含答案。输入样例 13 4 5 12 3 5 7 6 10 11 9 1 2 4 8 2 4 9 6 11输出样例 13输入样例 23 5 2 81 63 31 16 15 30 3 6 54 24 26 41 48 64 66 44 79输出样例 20输入样例 33 5 12 78 19 70 58 83 12 30 80 20 27 48 71 8 43 82 82 30 43 8 80 70 20 78 12 71 19 48输出样例 35C - 驯鹿与雪橇 2题目描述有 $N$ 头驯鹿和 1 架雪橇。第 $i$ 头驯鹿的体重为 $W_i$，力量为 $P_i$。对于每头驯鹿，需要选择是让它“拉雪橇”还是“乘坐雪橇”。但是，拉雪橇的驯鹿的力量总和必须大于等于乘坐雪橇的驯鹿的体重总和。最多可以让多少头驯鹿乘坐雪橇？给定 $T$ 个测试用例。请分别回答每个用例。约束条件$1 \leq T \leq 10^5$$1 \leq N \leq 3 \times 10^5$$1 \leq W_i, P_i \leq 10^9$所有输入值均为整数。单个输入文件中所有 $N$ 的总和不超过 $3 \times 10^5$。输入格式输入通过标准输入给出，格式如下：T case_1 case_2 ⋮ case_T每个测试用例的格式如下：N W_1 P_1 W_2 P_2 ⋮ W_N P_N输出格式输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。输入样例 13 3 3 1 4 1 5 9 5 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 10 133180711 458704923 531424946 225863856 141986070 637075158 500770732 289806469 502866767 408857335 559714289 569084545 287444582 992432993 559747907 753133304 432846188 949871298 727072164 756020367输出样例 12 0 6D - 差之和题目描述给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个长度为 $M$ 的正整数序列 $B = (B_1, B_2, \dots, B_M)$。求 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|$ 的值，并对 $998244353$ 取模。约束条件$1 \leq N, M \leq 3 \times 10^5$$1 \leq A_i, B_j < 998244353$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N M A_1 A_2 ... A_N B_1 B_2 ... B_M输出格式输出一…

【abc436】AtCoder Beginner Contest 436
type: item
date: 2025-12-14T13:34:00+08:00
description: abc436 反思题面A - o 判定问题描述给定一个整数 $ N $ 和一个由小写英文字母组成的字符串 $ S $，其长度小于 $ N $。请输出通过持续在字符串 $ S $ 的开头添加小写英文字母 o 直到其长度变为 $ N $ 所得到的字符串。约束条件$ 2 \leq N \leq 100 $$ N $ 为整数$ S $ 是由小写英文字母组成的字符串，长度介于 $ 1 $ 到 $ N-1 $ 之间（包含边界）。输入格式输入通过标准输入以如下格式给出：$$ N $$$$ S $$输出格式输出答案字符串。样例输入 15 abc样例输出 1ooabc解释：$ N=5 $，$ S $ 的长度为 $ 3 $，因此需要在 $ S $ 的开头添加 $ 5 - 3 = 2 $ 个 o。样例输入 22 o样例输出 2oo样例输入 312 vgxgpuam样例输出 3oooovgxgpuamB - 幻方阵问题描述给定一个大于等于 $ 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} $$样例输入 13样例输出 18 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 $。依此类推……样例输入 25样例输出 217 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…

P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解
type: item
date: 2025-12-13T15:11:00+08:00
description: 传送门题目更好的阅读体验题目大意读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。分析题目括号字符串中，每一个叶节点都是对应一个 ()；字符串中的深度比实际深度大 $1$，需要减去 $1$ 再进行计算；扫描字符串，遇到 ( 深度 $+1$，否则深度 $-1$；当遇到 () 时，当前的深度 $-1$ 就是根节点到此处的距离；时间复杂度为 $O(n)$ 可以通过此题。算法步骤扫描字符串，记为 $s_i$；对 $s_i$ 作判断，( 和 ) 需要分情况讨论；如果遇到 (，深度 $+1$，并且，如果下一个字符是 ) 说明找到了叶节点，将 深度-1 记录到答案，需要注意下个字符是否为合法边界；如果遇到 )，深度 $-1$；输出答案。代码#include <bits/stdc++.h> #define int long long // 将所有的 int 替换成 long long，否则会爆 int using namespace std; string s; int ans,depth,i; signed main(){ // 因为 int 会被替换成 long long，但是返回值不允许 long long，所以使用 signed cin>>s; // 对应步骤 1 for(i=0;i<s.length();i++) // 对应步骤 2 if(s[i]=='('){ // 对应步骤 3 及下面两行 depth++; if(i+1<s.length()&&s[i+1]==')') ans+=depth-1; // 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 }else depth--; // 对应步骤 4 cout<<ans; // 对应步骤 5 }

【abc435】AtCoder Beginner Contest 435
type: item
date: 2025-12-06T21:50:00+08:00
description: [collapse status="false" title="Typora 渲染后的 PDF"]https://www.fmcraft.top/usr/uploads/2025/12/4031836290.pdf[/collapse]abc435A - Triangular Number 三角数题面翻译时间限制：2 秒 / 内存限制：1024 MiB分数：100 分题目描述给定一个正整数 $N$。输出从 1 到 $N$ 的所有整数的和，即 $1+2+\dots+N$。约束条件$1 \le N \le 100$$N$ 是整数输入格式输入从标准输入按以下格式给出：N输出格式输出从 1 到 $N$ 的所有整数的和。样例输入 15样例输出 115样例解释 1因为 $1+2+3+4+5=15$，所以输出 15。样例输入 21样例输出 21样例输入 329样例输出 3435思考很简单，方法在题面中已经给出了，即 $\sum_{i=1}^{n} i$ ，这个算法的时间复杂度是 $O(n)$ 的。也可以使用高斯求和的方法， $\frac{n(1+n)}{2}$。我太懒了，使用高斯求和的方法。代码#include <bits/stdc++.h> using namespace std; int n,x,i,s; int main(){ cin>>n; for(i=1;i<=n;i++) s+=i; cout<<s; }B - No-Divisible Range 无因数区间题目翻译时间限制：2 秒 / 内存限制：1024 MiB分数：200 分题目描述给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。请找出满足 $1 \le l \le r \le N$ 的整数对 $(l,r)$ 的数量，要求这些整数对满足如下条件：对于所有满足 $l \le i \le r$ 的整数 $i$，$A_i$ 不是区间 $[l,r]$ 内所有元素的和的约数。约束条件$1 \le N \le 50$$1 \le A_i \le 1000$所有输入值均为整数输入格式输入数据通过标准输入给出，格式如下：N A_1 A_2 … A_N输出格式输出满足条件的整数对 $(l,r)$ 的数量。样例输入 15 8 6 10 5 7样例输出 16样例解释 1序列 $A=(8,6,10,5,7)$。例如，整数对 $(l,r)=(1,2)$ 满足条件：区间和为 $A_1+A_2=14$，$A_1=8$ 和 $A_2=6$ 都不是 14 的约数。而整数对 $(l,r)=(1,3)$ 不满足条件：区间和为 $A_1+A_2+A_3=24$，$A_1=8$ 是 24 的约数。满足条件的整数对为 $(1,2),(1,4),(2,3),(2,4),(3,5),(4,5)$，共 6 个，因此输出 6。样例输入 23 1 1 1样例输出 20思考就不打炮打蚊子了。直接暴力枚举 $l$ 到 $r$，求和为 $S$ ，公式为 $S=\sum_{i=l}^{r} a_i$，然后判断从 $l$ 到 $r$ 如果能被 $S$ 整除，那这个就不是一个无因数区间，不应该计入到答案，否则就计入到答案，最后输出即可。警告：暴力枚举 $l$ 到 $r$ 的时候，需要排除 $l > r$ 的状态，即 if(l>r) continue;。时间复杂度为 $O(n^3)$，题目规定 $N \leq 50$，可以通过。代码#include <bits/stdc++.h> using namespace std; int n,i,a[60],fl,s,t,w,ans; int main(){ cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(t=1;t<=n;t++) for(w=1;w<=n;w++){ if(t>w) continue; fl=1;s=0; for(i=t;i<=w;i++) s+=a[i]; for(i=t;i<=w;i++) if(s%a[i]==0) fl=0; ans+=fl; } cout<<ans; }C - Domino 多米诺题面翻译时间限制：2 秒 / 内存限制：1024 MiB分数：300 分题目描述有 $N$ 张多米诺骨牌排成一行，放置在数轴上。第 $i$ 张骨牌位于坐标 $i$ 处，高度为 $A_i$。当第 $i$ 张骨牌向右倒下时，坐标在 $i$ 到 $i+A_i-1$（包含两端）范围内的所有骨牌都会向右倒下。当第一张骨牌向右倒下时，总共会有多少张骨牌倒下？约束条件$1 \le N \le 5 \times 10^5$$1 \le A_i \le N$所有输入值均为整数输入格式输入数据通过标准输入给出，格式如下：N A…

关于 MX-S11
type: item
date: 2025-11-19T20:01:00+08:00
description: 感受我也不是打 noip 的货，也很菜题解梦熊 NOIP 2025 模拟赛 3 题解T1 战争游戏题目描述游戏在一行 $n$ 个城市上进行，城市 $i$ 初始有士兵 $a_i$ 人。前 $m$ 个城市属于小L，其余属于小K，两人交替操作，小L先手。操作包含三种：转移：选择己方地盘上相邻（$|x-y|=1$）的两个城市 $x$、$y$，将 $x$ 的所有士兵转移到 $y$，$a_x$ 变为 0。攻占：选择己方城市 $x$ 和对方相邻城市 $y$，小L操作需满足 $a_x > a_y$，小K操作需满足 $a_x \geq a_y$，攻占后 $y$ 归己方，士兵转移方式同转移操作。不进行任何操作。当一方占据所有城市时获胜，需对 $m=1,2,...,n-1$ 分别输出获胜方。关键思路特殊性质B：若先手第一步无法攻占，双方会优先集中兵力，最终比较分界线两侧总兵力。特殊性质C：若先手第一步可攻占对方城市且后手无法反制，比较攻占后两侧总兵力。正解：先手攻占后需判断对手是否能反制，若能则选择转移兵力，否则执行攻占，核心是比较关键状态下的兵力总和。T2 加减乘除题目描述给定一棵以 1 为根的树，每个节点 $u$ 有运算符号 $op_u$（加或减）和数值 $a_u$。$q$ 次询问，每次给定 $x$，从根节点出发，需满足边的范围条件 $[l_v, r_v]$（即经过节点 $u$ 运算后的 $x'$ 需在子节点 $v$ 的边范围内）才能走向子节点，求能到达的节点个数。正解区间预处理：每个节点 $u$ 对应可到达的 $x$ 区间 $[L_u, R_u]$，初始根节点区间为 $[-\infty, +\infty]$。区间更新：向下遍历树时，运算操作会平移区间，边的范围条件会取区间交集，以此递推得到所有节点的 $[L_u, R_u]$。高效查询：对所有区间端点离散化，用差分法给每个区间 $[L_u, R_u]$ 加 1，查询时二分找到 $x$ 对应的区间，即可得到答案。时间复杂度：$O((n+q) \log n)$。T3 空之碎物题目描述定义二进制不退位减法 $\ominus$，给定序列 $a$，对于区间 $[l, r]$，$f(l, r)$ 表示将该区间元素作为多重集，经若干次合并操作（选两个数合并为其不退位减法结果）后剩余的最大值。求 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(i, j)$ 对 998244353 取模的值。核心性质性质1：最终操作结果可表示为 $x \ominus(y \ominus a_1 \ominus a_2 \ominus ... \ominus a_{n-2})$（$a_1~a_{n-2}$ 为除 $x,y$ 外的元素）。某二进制位无1时无影响，恰好一个1时贡献由 $y$ 选择决定，至少两个1时贡献为0。性质2：若区间长度超过 $\log_2 V + 2$（$V$ 为元素最大值，此处 $V < 2^{25}$），则 $f(l, r)$ 等于区间最大值。正解处理长区间：直接累加所有长度超过 $\log_2 V + 2$ 的区间的最大值。处理短区间：枚举每个二进制位，对该位有两个1的元素建立连边，通过枚举连边计算贡献，时间复杂度 $O(n \log_2^2 V)$。T4 Ice Drop题目描述一个正整数序列是“好的”，当且仅当对任意正整数 $k$，序列中所有 $k$ 的倍数位置连续。给定序列 $a$，$f(b)$ 表示满足以下条件的“好的”序列 $b'$ 的数量：$|b'| = |b|$；若 $b_i > 1$，则 $b_i' = b_i$；$LCM(b_1,...,b_m) = LCM(b_1',...,b_m')$（$m$ 为 $b$ 的长度）。$q$ 次询问，每次给定 $l, r$，求 $\sum_{x=l}^{r} \sum_{y=x}^{r} f(a[x,y])$ 对 $10^9+7$ 取模的值。关键思路核心等价：序列是“好的”等价于每个质因子的指数序列是单峰的。特殊性质A（$q=1$）：不能新增质因子，也不能超过原质因子最大指数，通过组合数计算合法填充方式，答案为各质因子贡献乘积。特殊性质B：若只有一个质因子，合法区间是若干不交区间的子集，答案非0即1。正解：用扫描线结合线段树，维护全局乘、单点修、查历史和，对每个不交区间单独处理，时间复杂度 $O(n \log n)$。个人代码T1主要思路：骗分#include <bits/stdc++.h> using namespace std; int T,n,i,m,ma,t,a[100010]; string ans; int main(){ cin>>T; while(T--){ cin>>n;t=ma=0;ans=""; for(i=…

尝试通过打表的方法通过《P1304 哥德巴赫猜想》
type: item
date: 2025-10-23T21:33:00+08:00
description: P1304 哥德巴赫猜想 - 洛谷第一代代码#include <bits/stdc++.h> using namespace std; int i,n,a,b,fl,t; int prime[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351…

学校训练 栈+队列+堆+优先队列【历史存档】
type: item
date: 2025-10-12T15:38:00+08:00
description: 【知识要点】栈、队列、堆、优先队列1. 栈(Stack)和队列(Queue)基础1.1 基本概念对比数据结构特性操作位置C++声明插入操作删除操作栈(Stack)LIFO (后进先出)同一端(栈顶)stack<T> s;s.push()s.pop()队列(Queue)FIFO (先进先出)一端插入(队尾)，另一端删除(队头)queue<T> q;q.push() (enqueue)q.pop() (dequeue)1.2 队列的详细定义队列是C++标准库中的重要数据结构允许删除的一端称为队头(Front)允许插入的一端称为队尾(Rear)空队列：队列中没有元素的状态操作原则：先进先出(FIFO)1.3 C++队列基本操作示例#include<bits/stdc++.h> using namespace std; int main() { queue<int> q; // 定义一个空队列 for(int i=0; i<5; i++) { q.push(i); // 将i插入到队尾 } q.emplace(32); // 将32放置到队尾，作用和push一样 cout << q.size() << endl; // 输出队列中元素的个数 while(!q.empty()) { // 当队列不为空时，继续循环 cout << q.front() << endl; // 输出队列中的首元素 q.pop(); // 将元素从队头删除 } return 0; }1.4 队列queue的完整函数列表q.pop() - 删除queue的队头元素q.front() - 返回队列的队头元素，但不删除q.back() - 返回队列的队尾元素，但不删除q.push(arg) - 将元素arg插入到队列的队尾q.emplace(arg) - 将元素arg放置到队列的尾部(效果同push)q.size() - 返回队列中元素的个数q.empty() - 队列为空时返回true，否则falseq.swap(q1) - 交换q和q1中的元素(交换底层数据结构)swap(q,q1) - 非成员函数，效果同成员函数swap1.5 队列的应用场景BFS(广度优先搜索)算法单调队列缓冲区管理任务调度2. 堆(Heap)与优先队列(Priority Queue)2.1 堆的基本概念堆是一类特殊的数据结构，常用的是二叉堆形式上是一个数组，本质上是一棵完全二叉树分为大根堆和小根堆：大根堆：除根节点外，每个节点的值都大于等于其子节点的值公式表示：A[parent(i)] >= A[i]小根堆：除根节点外，每个节点的值都小于等于其子节点的值公式表示：A[parent(i)] <= A[i]堆中的任一子树也还是堆2.2 堆的基本操作push操作(插入)：往堆尾加入元素，并通过从下往上调整保持堆性质get操作(删除)：取出堆顶元素，用堆尾元素覆盖堆顶，再从上往下调整2.3 优先队列的实现C++中用 priority_queue实现堆的功能：#include <bits/stdc++.h> using namespace std; int main() { // 默认大根堆 priority_queue<int> max_heap; // 小根堆定义方式 priority_queue<int, vector<int>, greater<int>> min_heap; // 自定义结构体的优先队列 struct Node { int u, len; bool operator < (const Node &x) const { return x.len < len; // 注意这里是反向定义，实现小根堆效果 } }; priority_queue<Node> custom_heap; return 0; }2.4 优先队列的操作函数push(Elem e) - 插入元素，时间复杂度O(log n)pop() - 删除顶部元素，O(log n)top() - 返回顶部元素，O(1)size() - 返回元素数量empty() - 判断是否为空2.5 优先队列的特殊注意事项不支持除顶部外其他元素的访问和操作没有内置的clear()操作，需要手动实现：void clear(priority_queue<int> &q) { while (!q.empty()) q.pop(); }访问top()前必须检查队列是否为空3. 经典问题与解决方案3.1 合并果子问题问题描述：有n堆果子，每次合并两堆消耗体力值为两堆果子数之和，求最小总消耗。解决方案：#include <bits/stdc++.h> using namespace std; int main() { int n, ans = 0;…