反思 - UNIQUE VISION Programming Contest 2025 Christ
(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输出格式输出一行，包含答案。输入样例 14 2 1 6 9 2 3 1输出样例 126输入样例 28 8 185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631 455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528输出样例 2529117255E - 对数组排序题目描述有 $N+1$ 个序列 $A_0, A_1, \dots, A_N$。$A_i$ 定义如下：. $A_0$ 是一个空序列。. $A_i$ $(1 \le i \le N)$ 是在序列 $A_{x_i}$ $(0 \le x_i < i)$ 的末尾添加整数 $y_i$ 后得到的序列。找出满足以下条件的排列 $P = (P_1, P_2, \dots, P_N)$（即 $(1, 2, \dots, N)$ 的一个排列）：. 对于 $i = 1, 2, \dots, N-1$，满足以下条件之一：. $A_{P_i}$ 在字典序上小于 $A_{P_{i+1}}$。. $A_{P_i} = A_{P_{i+1}}$ 且 $P_i < P_{i+1}$。换句话说，当将 $A_1, A_2, \dots, A_N$ 按字典序排列（当有多个相同的序列时，索引较小的在前）时，$P$ 就是该排列中出现的索引序列。约束条件$1 \leq N \leq 3 \times 10^5$$0 \leq x_i < i$$1 \leq y_i \leq 10^9$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N x_1 y_1 x_2 y_2 ⋮ x_N y_N输出格式在一行中输出 $P_1, P_2, \dots, P_N$，用空格分隔。输入样例 14 0 2 0 1 2 2 0 1输出样例 12 4 3 1解释：$A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1)$，所以 $P = (2, 4, 3, 1)$。输入样例 25 0 1 0 1 0 1 0 1 0 1输出样例 21 2 3 4 5输入样例 310 0 305186313 1 915059758 0 105282054 1 696409999 3 185928366 3 573289179 6 254538849 3 105282054 5 696409999 8 168629803输出样例 33 8 10 5 9 6 7 1 4 2F - 曼哈顿圣诞树 2题目描述在二维平面上有 $N$ 棵圣诞树。第 $i$ 棵（$1 \leq i \leq N$）圣诞树位于坐标 $(X_i, Y_i)$。给你 $Q$ 个查询。请按顺序处理这些查询。每个查询是以下两种类型之一：类型 1：以 1 i x y 的形式给出。将第 $i$ 棵圣诞树的坐标改为 $(x, y)$。类型 2：以 2 L R x y 的形式给出。输出从坐标 $(x, y)$ 到第 $L, L+1, \dots, R$ 棵圣诞树中最远的圣诞树的曼哈顿距离。这里，坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。约束条件$1 \leq N, Q \leq 2 \times 10^5$$-10^9 \leq X_i, Y_i \leq 10^9$$1 \leq i \leq N$$1 \leq L \leq R \leq N$$-10^9 \leq x, y \leq 10^9$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N Q X_1 Y_1 X_2 Y_2 ⋮ X_N Y_N query_1 query_2 ⋮ query_Q其中，第 $i$ 个查询 query_i 以下列两种格式之一给出：1 i x y 2 L R x y输出格式根据问题描述中的说明，输出查询的答案，每个答案占一行。输入样例 13 4 -1 -1 1 2 -2 1 2 1 2 0 0 2 1 3 -1 2 1 1 0 1 2 1 3 -1 2输出样例 13 3 2解释：最初，第 1、2、3 棵圣诞树分别位于坐标 $(-1, -1)$、$(1, 2)$、$(-2, 1)$。处理每个查询：从第 1、2 棵圣诞树到坐标 $(0, 0)$ 的曼哈顿距离分别为 $2$ 和 $3$。因此输出 $3$，即 $2, 3$ 中的最大值。从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $3$、$2$、$2$。因此输出 $3$，即 $3, 2, 2$ 中的最大值。将第 1 棵圣诞树的坐标改为 $(0, 1)$。第 1、2、3 棵圣诞树的坐标变为 $(0, 1)$、$(1, 2)$、$(-2, 1)$。从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $2$、$2$、$2$。因此输出 $2$，即 $2, 2, 2$ 中的最大值。输入样例 25 7 -9 5 -2 -9 10 -6 9 8 2 9 1 3 -9 -6 2 3 4 2 7 1 4 -2 -10 2 1 2 0 -10 2 3 4 10 -9 2 3 4 8 7 2 5 5 0 2输出样例 224 24 22 30 9G - 彩色圣诞树题目描述今年的圣诞节季节已经结束，终于到了新年的时刻。高桥正在忙着进行大扫除，要收起圣诞树。有一棵用三种颜色（红色、蓝色、绿色）装饰的灯泡装饰的圣诞树。圣诞树上有 $N$ 个灯泡，它们由 $N-1$ 条丝带连接。将灯泡视为顶点，丝带视为边，这个图是一棵树。灯泡编号从 $1$ 到 $N$，丝带编号从 $1$ 到 $N-1$。丝带 $i$ 连接灯泡 $u_i$ 和 $v_i$。灯泡 $i$ 初始亮着红色（如果 $c_i$ 是 R），绿色（如果 $c_i$ 是 G），或蓝色（如果 $c_i$ 是 B）。高桥正在考虑执行以下操作 $N-1$ 次来移除所有丝带：从尚未移除的丝带中选择一条，其两端的灯泡颜色不同，然后移除该丝带。设 $u$ 和 $v$ 是被移除丝带两端的灯泡。对于每个灯泡 $u$ 和 $v$，根据以下规则改变它们亮的颜色：如果之前亮红色，则改为亮绿色。如果之前亮绿色，则改为亮蓝色。如果之前亮蓝色，则改为亮红色。确定高桥是否可以通过重复此操作来移除所有丝带。如果可能，输出一种方法。给定 $T$ 个测试用例。请解决每个测试用例。约束条件$1 \leq T \leq 20000$$2 \leq N \leq 2000$$c_i$ 是 R、G 或 B。$1 \leq u_i, v_i \leq N$将灯泡视为顶点，丝带视为边，给定的图是一棵树。$T, N, u_i, v_i$ 是整数。单个输入文件中所有 $N^2$ 的总和不超过 $2000^2$。输入格式输入通过标准输入给出，格式如下：T case_1 case_2 ⋮ case_T每个测试用例的格式如下：N c_1 c_2 ... c_N u_1 v_1 u_2 v_2 ⋮ u_{N-1} v_{N-1}输出格式按顺序输出 case_1, case_2, ..., case_T 的答案，格式如下：如果无法移除所有丝带，输出 No。如果可能，设 $e_i$ 为第 $i$ 次操作移除的丝带编号，输出：Yes e_1 e_2 ... e_{N-1}其中 $(e_1, e_2, \dots, e_{N-1})$ 必须是 $(1, 2, \dots, N-1)$ 的一个排列。如果有多个解，任意一个都将被视为正确。输入样例 13 4 GBBR 1 2 1 3 1 4 3 RRR 1 2 2 3 5 RGBRG 1 2 2 3 3 4 3 5输出样例 1Yes 1 3 2 No Yes 1 4 2 3解释：对于第一个测试用例，例如，可以通过以下操作移除所有丝带：初始时，灯泡颜色依次（从灯泡 1 开始）为绿色、蓝色、蓝色、红色。移除丝带 1。移除后，灯泡颜色依次为蓝色、红色、蓝色、红色。移除丝带 3。移除后，灯泡颜色依次为红色、红色、蓝色、绿色。移除丝带 2。移除后，灯泡颜色依次为绿色、红色、红色、绿色。满足条件的 $(e_1, e_2, e_3)$ 是 $(1, 3, 2)$ 和 $(2, 3, 1)$，任意一个都将被视为正确。对于第二个测试用例，无论你如何操作，都无法移除所有丝带。反思A本题是一道签到题根据题意可知：$$ \text{总英寸数} = A \times 12 + B $$由于题目的数据范围过小，可直接使用顺序结构求解以下是我赛场时的代码#include <bits/stdc++.h> using namespace std; int a,b; int main(){ cin>>a>>b; cout<<a*12+b; }B题目的意思就是：题目要求计算每一行中主持人喊出的整数出现的个数，并输出这些个数的最大值由于数据范围过小，可直接使用数组存储，不需要使用任何数据优化方案思路：读入 $H,W,N$用二维数组 $A$ 存储矩阵用一个大小为 $91$ （∵ $1 \leq B_i \leq 90$）的布尔数组 isB 标记 $B$ 中的数对每一行遍历，统计这一行中有多少个数在 isB 中被标记为 true记录这些统计数的最大值并输出以下是我赛时的代码：#include <bits/stdc++.h> using namespace std; int H,W,N,i,j,b,cnt,ma,a[5][6],fl[91]; int main(){ cin>>H>>W>>N; for(i=0;i<H;i++) for(j=0;j<W;j++) cin>>a[i][j]; for(i=0;i<N;i++){ cin>>b;fl[b]=1; } for(i=0;i<H;i++){ cnt=0; for(j=0;j<W;j++) if(fl[a[i][j]]) cnt++; if(cnt>ma) ma=cnt; } cout<<ma; }根据题目思路就可以得出代码，非常 EasyC这题我在赛时并没有得出正确程序赛后，我邀请 deepseek 完成此题，我将对 deepseek 的内容进行阐述算法：贪心题目阐述：有 (N) 头驯鹿，每头驯鹿有体重 (W_i) 和力量 (P_i)。选择一部分驯鹿“乘坐雪橇”，剩下的“拉雪橇”。要求“拉雪橇”的驯鹿的力量总和 ≥ “乘坐雪橇”的驯鹿的体重总和。问最多可以让多少头驯鹿乘坐雪橇问题转化为：在不超过总力量 (S) 的前提下，最多能选择多少头驯鹿，使得它们的 (W_i + P_i) 之和不超过 (S)。这是一个典型的贪心问题：按 (W_i + P_i) 从小到大选择，直到总和超过 (S)对每个测试用例：读入 (N) 和每头驯鹿的 (W_i, P_i)计算总力量 (S = \sum P_i)计算每头驯鹿的 (a_i = W_i + P_i)，并排序从小到大累加 (a_i)，直到总和超过 (S)，累加的个数即为答案时间复杂度：$O(N \operatorname{log} N)$这是 deepseek 给出的代码：#include<iostream> #include<algorithm> using namespace std; int T,N,i,cnt; long long totalP,sum,W,P; long long a[100005]; int main(){ cin>>T; while(T--){ cin>>N; totalP=0; for(i=0;i<N;i++){ cin>>W>>P; a[i]=W+P; totalP+=P; } sort(a,a+N); sum=0; cnt=0; for(i=0;i<N;i++){ if(sum+a[i]<=totalP){ sum+=a[i]; cnt++; }else{ break; } } cout<<cnt<<endl; } return 0; }
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_2 \ C_2 $$$$ \vdots $$$$ R_M \ C_M $$输出格式输出答案。样例输入 14 3 1 1 2 2 2 3样例输出 12解释：下图展示了操作过程，黑色填充区域表示方块，红色边框区域表示下一个要放置方块的位置。操作 1：以格子 $ (1, 1) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。操作 2：以格子 $ (2, 2) $ 为左上角的 $ 2 \times 2 $ 区域中，格子 $ (2, 2) $ 已被占据，因此什么也不做。操作 3：以格子 $ (2, 3) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。因此，所有操作结束后，方格上有 2 个方块。样例输入 21000000000 4 1 1 1 101 101 1 101 101样例输出 24所有操作都可以放置方块。样例输入 38 10 6 5 7 3 6 7 3 4 4 2 3 7 1 3 7 4 6 1 6 1样例输出 38可能存在满足 $ (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。样例输入 13 4 ..a. #### ba#b样例输出 15解释：可以通过以下操作从单元格 $ (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 $，这是最小值。样例输入 23 4 ..a. #### b.#b样例输出 2-1无法从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $。样例输入 34 4 xxxx xxxx xxxx xxxx样例输出 31样例输入 47 11 u..#y..#... k..#.z.#.k. iju#...#x.. ########### ..x#.t.#..n abc#y..#... ..z#..t#.y.样例输出 412E - 最小交换次数问题描述给定一个整数序列 $ 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 $$输出格式输出答案。样例输入 15 3 1 4 2 5样例输出 16例如，可以通过以下三次操作达成目标：选择 $ (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。样例输入 22 2 1样例输出 21样例输入 320 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1样例输出 377F - 星空风景照问题描述在从 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 $$输出格式输出答案。样例输入 14 3 1 4 2样例输出 112例如，当 $ (l, r) = (2, 4) $，$ b = 3 $ 时，你可以拍摄包含两颗星星的照片：从东数第 2 颗星星和第 4 颗星星。包括这个在内，你可以拍摄以下 12 种不同的星星集合。每张照片中，较东的星星排在较左边，第 $i$ 亮的星星用整数 $i$ 标记。没有其他集合可以被捕捉，因此输出 12。样例输入 27 1 2 3 4 5 6 7样例输出 228样例输入 320 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1样例输出 3627G - 线性不等式问题描述给定一个长度为 $ 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 $ 取模）。样例输入 14 6 5 4 3 2样例输出 110满足条件的序列 $ 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。样例输入 26 89 4 7 5 10 7 6样例输出 238469样例输入 31 1000000007 1样例输出 31755655满足条件的序列 $ x $ 有 $ 1000000008 $ 个。输出其对 $ 998244353 $ 取模的结果，即 $ 1755655 $。样例输入 420 738894495848985641 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37样例输出 431156940反思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 easyB - 幻方阵这题需要一定的耐心来阅读题面文本。这题可以直接根据 题目描述 的题进行暴力编写程序，不需要一些复杂的抽象概念思考建模。我直接贴代码了，毫无技术含量。#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; }
P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解
传送门题目更好的阅读体验题目大意读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。分析题目括号字符串中，每一个叶节点都是对应一个 ()；字符串中的深度比实际深度大 $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)
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输出格式输出一行，包含答案。输入样例 14 2 1 6 9 2 3 1输出样例 126输入样例 28 8 185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631 455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528输出样例 2529117255E - 对数组排序题目描述有 $N+1$ 个序列 $A_0, A_1, \dots, A_N$。$A_i$ 定义如下：. $A_0$ 是一个空序列。. $A_i$ $(1 \le i \le N)$ 是在序列 $A_{x_i}$ $(0 \le x_i < i)$ 的末尾添加整数 $y_i$ 后得到的序列。找出满足以下条件的排列 $P = (P_1, P_2, \dots, P_N)$（即 $(1, 2, \dots, N)$ 的一个排列）：. 对于 $i = 1, 2, \dots, N-1$，满足以下条件之一：. $A_{P_i}$ 在字典序上小于 $A_{P_{i+1}}$。. $A_{P_i} = A_{P_{i+1}}$ 且 $P_i < P_{i+1}$。换句话说，当将 $A_1, A_2, \dots, A_N$ 按字典序排列（当有多个相同的序列时，索引较小的在前）时，$P$ 就是该排列中出现的索引序列。约束条件$1 \leq N \leq 3 \times 10^5$$0 \leq x_i < i$$1 \leq y_i \leq 10^9$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N x_1 y_1 x_2 y_2 ⋮ x_N y_N输出格式在一行中输出 $P_1, P_2, \dots, P_N$，用空格分隔。输入样例 14 0 2 0 1 2 2 0 1输出样例 12 4 3 1解释：$A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1)$，所以 $P = (2, 4, 3, 1)$。输入样例 25 0 1 0 1 0 1 0 1 0 1输出样例 21 2 3 4 5输入样例 310 0 305186313 1 915059758 0 105282054 1 696409999 3 185928366 3 573289179 6 254538849 3 105282054 5 696409999 8 168629803输出样例 33 8 10 5 9 6 7 1 4 2F - 曼哈顿圣诞树 2题目描述在二维平面上有 $N$ 棵圣诞树。第 $i$ 棵（$1 \leq i \leq N$）圣诞树位于坐标 $(X_i, Y_i)$。给你 $Q$ 个查询。请按顺序处理这些查询。每个查询是以下两种类型之一：类型 1：以 1 i x y 的形式给出。将第 $i$ 棵圣诞树的坐标改为 $(x, y)$。类型 2：以 2 L R x y 的形式给出。输出从坐标 $(x, y)$ 到第 $L, L+1, \dots, R$ 棵圣诞树中最远的圣诞树的曼哈顿距离。这里，坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。约束条件$1 \leq N, Q \leq 2 \times 10^5$$-10^9 \leq X_i, Y_i \leq 10^9$$1 \leq i \leq N$$1 \leq L \leq R \leq N$$-10^9 \leq x, y \leq 10^9$所有输入值均为整数。输入格式输入通过标准输入给出，格式如下：N Q X_1 Y_1 X_2 Y_2 ⋮ X_N Y_N query_1 query_2 ⋮ query_Q其中，第 $i$ 个查询 query_i 以下列两种格式之一给出：1 i x y 2 L R x y输出格式根据问题描述中的说明，输出查询的答案，每个答案占一行。输入样例 13 4 -1 -1 1 2 -2 1 2 1 2 0 0 2 1 3 -1 2 1 1 0 1 2 1 3 -1 2输出样例 13 3 2解释：最初，第 1、2、3 棵圣诞树分别位于坐标 $(-1, -1)$、$(1, 2)$、$(-2, 1)$。处理每个查询：从第 1、2 棵圣诞树到坐标 $(0, 0)$ 的曼哈顿距离分别为 $2$ 和 $3$。因此输出 $3$，即 $2, 3$ 中的最大值。从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $3$、$2$、$2$。因此输出 $3$，即 $3, 2, 2$ 中的最大值。将第 1 棵圣诞树的坐标改为 $(0, 1)$。第 1、2、3 棵圣诞树的坐标变为 $(0, 1)$、$(1, 2)$、$(-2, 1)$。从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $2$、$2$、$2$。因此输出 $2$，即 $2, 2, 2$ 中的最大值。输入样例 25 7 -9 5 -2 -9 10 -6 9 8 2 9 1 3 -9 -6 2 3 4 2 7 1 4 -2 -10 2 1 2 0 -10 2 3 4 10 -9 2 3 4 8 7 2 5 5 0 2输出样例 224 24 22 30 9G - 彩色圣诞树题目描述今年的圣诞节季节已经结束，终于到了新年的时刻。高桥正在忙着进行大扫除，要收起圣诞树。有一棵用三种颜色（红色、蓝色、绿色）装饰的灯泡装饰的圣诞树。圣诞树上有 $N$ 个灯泡，它们由 $N-1$ 条丝带连接。将灯泡视为顶点，丝带视为边，这个图是一棵树。灯泡编号从 $1$ 到 $N$，丝带编号从 $1$ 到 $N-1$。丝带 $i$ 连接灯泡 $u_i$ 和 $v_i$。灯泡 $i$ 初始亮着红色（如果 $c_i$ 是 R），绿色（如果 $c_i$ 是 G），或蓝色（如果 $c_i$ 是 B）。高桥正在考虑执行以下操作 $N-1$ 次来移除所有丝带：从尚未移除的丝带中选择一条，其两端的灯泡颜色不同，然后移除该丝带。设 $u$ 和 $v$ 是被移除丝带两端的灯泡。对于每个灯泡 $u$ 和 $v$，根据以下规则改变它们亮的颜色：如果之前亮红色，则改为亮绿色。如果之前亮绿色，则改为亮蓝色。如果之前亮蓝色，则改为亮红色。确定高桥是否可以通过重复此操作来移除所有丝带。如果可能，输出一种方法。给定 $T$ 个测试用例。请解决每个测试用例。约束条件$1 \leq T \leq 20000$$2 \leq N \leq 2000$$c_i$ 是 R、G 或 B。$1 \leq u_i, v_i \leq N$将灯泡视为顶点，丝带视为边，给定的图是一棵树。$T, N, u_i, v_i$ 是整数。单个输入文件中所有 $N^2$ 的总和不超过 $2000^2$。输入格式输入通过标准输入给出，格式如下：T case_1 case_2 ⋮ case_T每个测试用例的格式如下：N c_1 c_2 ... c_N u_1 v_1 u_2 v_2 ⋮ u_{N-1} v_{N-1}输出格式按顺序输出 case_1, case_2, ..., case_T 的答案，格式如下：如果无法移除所有丝带，输出 No。如果可能，设 $e_i$ 为第 $i$ 次操作移除的丝带编号，输出：Yes e_1 e_2 ... e_{N-1}其中 $(e_1, e_2, \dots, e_{N-1})$ 必须是 $(1, 2, \dots, N-1)$ 的一个排列。如果有多个解，任意一个都将被视为正确。输入样例 13 4 GBBR 1 2 1 3 1 4 3 RRR 1 2 2 3 5 RGBRG 1 2 2 3 3 4 3 5输出样例 1Yes 1 3 2 No Yes 1 4 2 3解释：对于第一个测试用例，例如，可以通过以下操作移除所有丝带：初始时，灯泡颜色依次（从灯泡 1 开始）为绿色、蓝色、蓝色、红色。移除丝带 1。移除后，灯泡颜色依次为蓝色、红色、蓝色、红色。移除丝带 3。移除后，灯泡颜色依次为红色、红色、蓝色、绿色。移除丝带 2。移除后，灯泡颜色依次为绿色、红色、红色、绿色。满足条件的 $(e_1, e_2, e_3)$ 是 $(1, 3, 2)$ 和 $(2, 3, 1)$，任意一个都将被视为正确。对于第二个测试用例，无论你如何操作，都无法移除所有丝带。反思A本题是一道签到题根据题意可知：$$ \text{总英寸数} = A \times 12 + B $$由于题目的数据范围过小，可直接使用顺序结构求解以下是我赛场时的代码#include <bits/stdc++.h> using namespace std; int a,b; int main(){ cin>>a>>b; cout<<a*12+b; }B题目的意思就是：题目要求计算每一行中主持人喊出的整数出现的个数，并输出这些个数的最大值由于数据范围过小，可直接使用数组存储，不需要使用任何数据优化方案思路：读入 $H,W,N$用二维数组 $A$ 存储矩阵用一个大小为 $91$ （∵ $1 \leq B_i \leq 90$）的布尔数组 isB 标记 $B$ 中的数对每一行遍历，统计这一行中有多少个数在 isB 中被标记为 true记录这些统计数的最大值并输出以下是我赛时的代码：#include <bits/stdc++.h> using namespace std; int H,W,N,i,j,b,cnt,ma,a[5][6],fl[91]; int main(){ cin>>H>>W>>N; for(i=0;i<H;i++) for(j=0;j<W;j++) cin>>a[i][j]; for(i=0;i<N;i++){ cin>>b;fl[b]=1; } for(i=0;i<H;i++){ cnt=0; for(j=0;j<W;j++) if(fl[a[i][j]]) cnt++; if(cnt>ma) ma=cnt; } cout<<ma; }根据题目思路就可以得出代码，非常 EasyC这题我在赛时并没有得出正确程序赛后，我邀请 deepseek 完成此题，我将对 deepseek 的内容进行阐述算法：贪心题目阐述：有 (N) 头驯鹿，每头驯鹿有体重 (W_i) 和力量 (P_i)。选择一部分驯鹿“乘坐雪橇”，剩下的“拉雪橇”。要求“拉雪橇”的驯鹿的力量总和 ≥ “乘坐雪橇”的驯鹿的体重总和。问最多可以让多少头驯鹿乘坐雪橇问题转化为：在不超过总力量 (S) 的前提下，最多能选择多少头驯鹿，使得它们的 (W_i + P_i) 之和不超过 (S)。这是一个典型的贪心问题：按 (W_i + P_i) 从小到大选择，直到总和超过 (S)对每个测试用例：读入 (N) 和每头驯鹿的 (W_i, P_i)计算总力量 (S = \sum P_i)计算每头驯鹿的 (a_i = W_i + P_i)，并排序从小到大累加 (a_i)，直到总和超过 (S)，累加的个数即为答案时间复杂度：$O(N \operatorname{log} N)$这是 deepseek 给出的代码：#include<iostream> #include<algorithm> using namespace std; int T,N,i,cnt; long long totalP,sum,W,P; long long a[100005]; int main(){ cin>>T; while(T--){ cin>>N; totalP=0; for(i=0;i<N;i++){ cin>>W>>P; a[i]=W+P; totalP+=P; } sort(a,a+N); sum=0; cnt=0; for(i=0;i<N;i++){ if(sum+a[i]<=totalP){ sum+=a[i]; cnt++; }else{ break; } } cout<<cnt<<endl; } return 0; }
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_2 \ C_2 $$$$ \vdots $$$$ R_M \ C_M $$输出格式输出答案。样例输入 14 3 1 1 2 2 2 3样例输出 12解释：下图展示了操作过程，黑色填充区域表示方块，红色边框区域表示下一个要放置方块的位置。操作 1：以格子 $ (1, 1) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。操作 2：以格子 $ (2, 2) $ 为左上角的 $ 2 \times 2 $ 区域中，格子 $ (2, 2) $ 已被占据，因此什么也不做。操作 3：以格子 $ (2, 3) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。因此，所有操作结束后，方格上有 2 个方块。样例输入 21000000000 4 1 1 1 101 101 1 101 101样例输出 24所有操作都可以放置方块。样例输入 38 10 6 5 7 3 6 7 3 4 4 2 3 7 1 3 7 4 6 1 6 1样例输出 38可能存在满足 $ (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。样例输入 13 4 ..a. #### ba#b样例输出 15解释：可以通过以下操作从单元格 $ (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 $，这是最小值。样例输入 23 4 ..a. #### b.#b样例输出 2-1无法从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $。样例输入 34 4 xxxx xxxx xxxx xxxx样例输出 31样例输入 47 11 u..#y..#... k..#.z.#.k. iju#...#x.. ########### ..x#.t.#..n abc#y..#... ..z#..t#.y.样例输出 412E - 最小交换次数问题描述给定一个整数序列 $ 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 $$输出格式输出答案。样例输入 15 3 1 4 2 5样例输出 16例如，可以通过以下三次操作达成目标：选择 $ (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。样例输入 22 2 1样例输出 21样例输入 320 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1样例输出 377F - 星空风景照问题描述在从 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 $$输出格式输出答案。样例输入 14 3 1 4 2样例输出 112例如，当 $ (l, r) = (2, 4) $，$ b = 3 $ 时，你可以拍摄包含两颗星星的照片：从东数第 2 颗星星和第 4 颗星星。包括这个在内，你可以拍摄以下 12 种不同的星星集合。每张照片中，较东的星星排在较左边，第 $i$ 亮的星星用整数 $i$ 标记。没有其他集合可以被捕捉，因此输出 12。样例输入 27 1 2 3 4 5 6 7样例输出 228样例输入 320 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1样例输出 3627G - 线性不等式问题描述给定一个长度为 $ 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 $ 取模）。样例输入 14 6 5 4 3 2样例输出 110满足条件的序列 $ 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。样例输入 26 89 4 7 5 10 7 6样例输出 238469样例输入 31 1000000007 1样例输出 31755655满足条件的序列 $ x $ 有 $ 1000000008 $ 个。输出其对 $ 998244353 $ 取模的结果，即 $ 1755655 $。样例输入 420 738894495848985641 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37样例输出 431156940反思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 easyB - 幻方阵这题需要一定的耐心来阅读题面文本。这题可以直接根据 题目描述 的题进行暴力编写程序，不需要一些复杂的抽象概念思考建模。我直接贴代码了，毫无技术含量。#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; }
传送门题目更好的阅读体验题目大意读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。分析题目括号字符串中，每一个叶节点都是对应一个 ()；字符串中的深度比实际深度大 $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 }
[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_1 A_2 … A_N输出格式输出当第一张骨牌向右倒下时，倒下的骨牌总数。样例输入 14 3 1 4 1样例输出 14样例解释 1当第一张骨牌向右倒下时，第二张和第三张骨牌也会向右倒下。当第三张骨牌向右倒下时，第四张骨牌也会倒下。样例输入 29 1 4 1 4 2 1 3 5 6样例输出 21样例解释 2当第一张骨牌向右倒下时，没有其他骨牌会倒下。样例输入 310 5 4 3 2 1 1 2 3 4 5样例输出 35思考数据范围 $N \le 5\times10^5$，暴力模拟每张骨牌的连锁倒下会超时，不能用 $O(N^2)$ 的暴力枚举了，必须用 $O(N)$ 贪心策略。核心是维护当前最远覆盖位置和遍历边界：第一张骨牌倒下的初始覆盖范围是 $1+A[1]-1$，记为 ma，用 tmp 记录当前需要遍历的右边界；从第 2 张骨牌开始，在 tmp 范围内遍历，不断更新 ma 为所有骨牌能覆盖的最远位置；遍历到 tmp 时，将 tmp 更新为新的 ma，扩展遍历范围；最终答案取 ma 和 $N$ 的较小值，避免覆盖范围超出骨牌总数。小声：我看到时间限制为 2s 的时候以为不用贪心，就用暴力枚举，结果 TLE 了我操，∵数据范围是指数级的，是 $2.5 \times {10}^{11}$，但实际上计算机每秒大约只能做 $10^9$ 次，∴会超时。代码#include <bits/stdc++.h> using namespace std; const int N=500010; int a[N],n,i,ma,tmp; int main(){ cin>>n; for(i=1;i<=n;i++) cin>>a[i]; if(n==0) return cout<<0,0; ma=1+a[1]-1; tmp=ma; i=2; while(i<=tmp&&i<=n){ if(i+a[i]-1>ma) ma=i+a[i]-1; if(i==tmp) tmp=ma; i++; } if(ma>n) cout<<n; else cout<<ma; }D - Reachability Query 2 可达性查询 2题面翻译时间限制：3 秒 / 内存限制：1024 MiB分数：425 分题目描述给定一个有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $X_i$ 指向顶点 $Y_i$ 的有向边。初始时，所有顶点均为白色。按顺序处理 $Q$ 个查询，每个查询为以下两种类型之一：1 v：将顶点 $v$ 染成黑色。2 v：判断从顶点 $v$ 出发，沿着边遍历是否能够到达某个黑色顶点。约束条件$1 \le N \le 3 \times 10^5$$0 \le M \le 3 \times 10^5$$1 \le Q \le 3 \times 10^5$$1 \le X_i, Y_i \le N$图中无自环（即 $X_i \neq Y_i$）。图中无重边（即所有 $(X_i, Y_i)$ 互不相同）。查询中，$1 \le v \le N$。所有输入值均为整数。输入格式输入数据通过标准输入给出，格式如下：N M X_1 Y_1 ⋮ X_M Y_M Q query_1 ⋮ query_Q其中 query_i 表示第 $i$ 个查询，格式为以下两者之一：1 v 2 v输出格式设第二类查询的数量为 $q$，输出 $q$ 行结果：对于第 $i$ 个第二类查询，若从顶点 $v$ 能到达黑色顶点，输出 Yes；否则输出 No。样例输入 15 6 1 2 2 3 3 1 4 5 1 4 2 5 5 1 3 2 1 2 4 1 5 2 4样例输出 1Yes No Yes样例解释初始时，给定的图如最左侧的图所示。第一个查询将顶点 3 染成黑色（如中间的图所示）。第二个查询中，从顶点 1 可以到达黑色顶点 3，故输出 Yes第三个查询中，从顶点 4 无法到达任何黑色顶点，故输出 No。第四个查询将顶点 5 染成黑色（如最右侧的图所示）。第五个查询中，从顶点 4 可以到达黑色顶点 5，故输出 Yes。思考很明显，这是一道图论题，其实我个人做的图论题也不多，我首先感觉是 P3916 图的遍历 - 洛谷 的升级版，多了染色和一些杂七杂八的东西，抽象。小声：我刚看到每个查询的时候我还以为他考的是并查集。一个经典的解决动态图可达性问题的方法是使用 bitset 或 分块，但 $N=3 \times 10^5$，bitset 太大（$N=3 \times 10^5 \space \text{bits}$ 约 $37.5 \space \text{KB}$ 每个顶点，总共 $N=3 \times 10^5$ 个顶点就是 $10^{10} \space \text{bits} \approx 1.25 \text{GB}$，太特么大了）。我草比赛怎么结束了？E - Cover query 覆盖查询题面翻译时间限制：2 秒 / 内存限制：1024 MiB分数：450 分题目描述有 $N$ 个单元格从左到右排成一行。从左数第 $i$ 个单元格（$1 \le i \le N$）被称为单元格 $i$。初始时，所有单元格均为白色。按顺序处理 $Q$ 个查询。第 $i$ 个查询（$1 \le i \le Q$）的内容如下：给定两个整数 $L_i$ 和 $R_i$（$1 \le L_i \le R_i \le N$）。将单元格 $L_i, L_i+1, \dots, R_i$ 全部染成黑色。在此操作中，原本白色的单元格会被染成黑色，原本黑色的单元格保持黑色不变。操作完成后，求出 $N$ 个单元格中仍为白色的单元格数量。约束条件$1 \le N \le 10^9$$1 \le Q \le 2 \times 10^5$$1 \le L_i \le R_i \le N$所有输入值均为整数输入格式输入数据通过标准输入按以下格式给出：N Q L_1 R_1 L_2 R_2 ⋮ L_Q R_Q输出格式输出 $Q$ 行。第 $i$ 行（$1 \le i \le Q$）输出第 $i$ 个查询的答案。样例输入 110 5 3 5 8 9 5 8 2 9 6 6样例输出 17 5 3 2 2样例解释初始时，10 个单元格从左到右排成一行。第一个查询将单元格 3、4、5 染成黑色。操作后，白色单元格为 1、2、6、7、8、9、10，共 7 个。第二个查询将单元格 8、9 染成黑色。操作后，白色单元格为 1、2、6、7、10，共 5 个。第三个查询将单元格 5、6、7、8 染成黑色。操作后，白色单元格为 1、2、10，共 3 个。第四个查询将单元格 2 到 9 染成黑色。操作后，白色单元格为 1、10，共 2 个。第五个查询将单元格 6 染成黑色。操作后，白色单元格仍为 1、10，共 2 个。因此，按顺序输出 7、5、3、2、2。样例输入 21000000000 1 1 500000000样例输出 2500000000思考[待补]F - Cat exercise 猫咪的锻炼题面翻译时间限制：2 秒 / 内存限制：1024 MiB分数：550 分题目描述有 $N$ 座猫塔从左到右排成一行，从左数第 $i$ 座猫塔（$1 \le i \le N$）的高度为 $P_i$。其中，序列 $(P_1,P_2,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列。从左数第 $i$ 座猫塔和第 $j$ 座猫塔之间的距离定义为 $|i-j|$。初始时，有一只猫位于高度为 $N$ 的猫塔顶端。高桥想要锻炼这只猫，方式是重复选择并移除猫塔。当高桥移除一座猫塔时，猫的移动规则如下：若猫不在被移除的猫塔顶端，则猫保持不动。若猫在被移除的猫塔顶端，且该猫塔的左侧或右侧至少有一座猫塔存在，则猫会移动到以下目标猫塔：目标猫塔的范围是：从被移除的猫塔出发，通过重复移动到相邻猫塔能够到达的所有猫塔（不包含被移除的猫塔）。目标猫塔是上述范围内高度最高的猫塔。此时，猫的移动距离计入总距离，该距离等于移动前所在猫塔和移动后所在猫塔之间的距离（与移动过程中经过的猫塔高度、数量无关）。若猫在被移除的猫塔顶端，且该猫塔的左右两侧都没有猫塔存在，则猫会跳进高桥的怀里，锻炼就此结束。这种情况下，不计入任何移动距离。注意：被移除的猫塔留下的空位不会被填补。也就是说，初始时从左数第 $i$ 座猫塔的相邻猫塔仅为第 $i-1$ 和第 $i+1$ 座猫塔（若存在），后续不会因为其他猫塔被移除而与非原本相邻的猫塔变成相邻关系。请你求出，锻炼结束前猫能够移动的最大可能总距离。约束条件$1 \le N \le 2 \times 10^5$$(P_1,P_2,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列所有输入值均为整数输入格式输入数据通过标准输入按以下格式给出：N P_1 P_2 … P_N输出格式输出锻炼结束前猫能够移动的最大可能总距离。样例输入 15 5 3 4 1 2样例输出 15样例解释 1初始时，猫塔的高度从左到右依次为 5、3、4、1、2。下文将从左数第 $i$ 座猫塔（$1 \le i \le 5$）简称为猫塔 $i$。初始时，猫位于猫塔 1 的顶端（高度为 5）。若高桥按照 1 → 2 → 3 → 5 → 4 的顺序移除猫塔，猫的移动过程如下：移除猫塔 1：从猫塔 1 出发，通过重复移动到相邻猫塔可到达的猫塔为 2、3、4、5（不含猫塔 1）。其中高度最高的是猫塔 3（高度为 4），猫移动到该猫塔。移除猫塔 2：猫不在该猫塔顶端，保持不动。移除猫塔 3：从猫塔 3 出发，可到达的猫塔为 4、5（不含猫塔 3）。其中高度最高的是猫塔 5（高度为 2），猫移动到该猫塔。移除猫塔 5：从猫塔 5 出发，可到达的猫塔仅有 4（不含猫塔 5），猫移动到该猫塔。移除猫塔 4：猫的左右两侧都没有猫塔，跳进高桥怀里，锻炼结束。此时，猫的总移动距离为 $|1-3| + |3-5| + |5-4| = 5$。不存在任何一种猫塔移除顺序，能让猫的总移动距离达到 6 或以上，因此输出 5。样例输入 23 1 3 2样例输出 21样例解释 2初始时，猫塔的高度从左到右依次为 1、3、2。下文将从左数第 $i$ 座猫塔（$1 \le i \le 3$）简称为猫塔 $i$。初始时，猫位于猫塔 2 的顶端（高度为 3）。若高桥按照 2 → 3 的顺序移除猫塔，猫的移动过程如下：移除猫塔 2：从猫塔 2 出发，可到达的猫塔为 1、3（不含猫塔 2）。其中高度最高的是猫塔 3（高度为 2），猫移动到该猫塔。移除猫塔 3：猫的左右两侧都没有猫塔，跳进高桥怀里，锻炼结束。此时，猫的总移动距离为 $|2-3|=1$，这是最大可能的总距离。注意：移除猫塔 2 后，猫塔 1 和猫塔 3 不会被视为相邻。思考[待补]G - Domino Arrangement 多米诺序列题面翻译时间限制：2 秒 / 内存限制：1024 MiB分数：600 分题目描述有 $N$ 个单元格从左到右依次编号为 $1$ 到 $N$。初始时，所有单元格均未被涂上任何颜色。共有 $M$ 种颜色，对于第 $i$ 种颜色，你可以选择单元格区间 $[L_i, R_i]$（即 $L_i, L_i+1, \dots, R_i$）内任意数量的单元格，将其涂为该颜色（可选择涂 0 个、1 个或多个）。请计算满足以下条件的涂色方案数，并将结果对 $998244353$ 取模：对于每一个单元格 $i$：若该单元格被涂上了某一种颜色，则其左侧相邻单元格 $i-1$ 和右侧相邻单元格 $i+1$ 中，恰好有一个 单元格被涂成了与 $i$ 相同的颜色；特别说明：单元格 $0$ 和 $N+1$ 被视为未被任何颜色涂色（即不存在的单元格）。约束条件$1 \le N,M \le 5 \times 10^5$$1 \le L_i \le R_i \le N$所有输入值均为整数输入格式输入数据从标准输入按以下格式给出：N M L_1 R_1 L_2 R_2 ⋮ L_M R_M输出格式输出满足条件的涂色方案数（对 $998244353$ 取模）。样例输入 15 2 1 3 1 5样例输出 111样例解释 1第 1 种颜色可涂色的单元格范围是 $1,2,3$，第 2 种颜色可涂色的单元格范围是 $1,2,3,4,5$。满足条件的涂色方案共有 11 种。样例输入 23 3 1 1 2 2 3 3样例输出 21样例解释 2唯一满足条件的方案是：不涂任何单元格（若给任意单元格涂色，都无法满足“恰好一个相邻单元格同色”的条件）。样例输入 3500000 10 1 499999 2 499998 3 499997 4 499996 5 499995 6 499994 7 499993 8 499992 9 499991 10 499990样例输出 3775503999补充说明答案需对 $998244353$ 取模后输出。思考[待补]
感受我也不是打 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=1;i<=n;i++) cin>>a[i],ma+=a[i]; for(m=1;m<n;m++){ t+=a[m]; if(2*t>ma) ans+='1'; else ans+='0'; } cout<<ans<<"\n"; } }太好力，又水了一篇 blogMX-S11
尝试通过打表的方法通过《P1304 哥德巴赫猜想》
学校训练 栈+队列+堆+优先队列【历史存档】
【知识要点】栈、队列、堆、优先队列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; cin >> n; priority_queue<int, vector<int>, greater<int>> q; for(int i = 0; i < n; i++) { int x; cin >> x; q.push(x); } while(q.size() > 1) { int x = q.top(); q.pop(); int y = q.top(); q.pop(); ans += x + y; q.push(x + y); } cout << ans; return 0; }时间复杂度分析：O(n log n)3.2 互数问题问题描述：给定素数集合S，生成由S中素数乘积构成的"互数集合"，求第n小的互数。解决方案：typedef long long ll; int main() { ll k, n; cin >> k >> n; vector<ll> primes(k); priority_queue<ll, vector<ll>, greater<ll>> heap; set<ll> seen; for(int i = 0; i < k; i++) { cin >> primes[i]; heap.push(primes[i]); seen.insert(primes[i]); } ll humble = 1; for(int i = 0; i < n; i++) { humble = heap.top(); heap.pop(); for(auto p : primes) { ll num = humble * p; if(seen.find(num) == seen.end()) { seen.insert(num); heap.push(num); } } } cout << humble; return 0; }时间复杂度分析：O(nk log n)3.3 两个序列的最小N个和问题描述：有两个长度为N的有序序列A和B，求A和B中各取一个数相加得到的N²个和中最小的N个。解决方案：#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; struct HeapNode { int x, val; bool operator < (const HeapNode &other) const { return val > other.val; // 小根堆 } }; int main() { int n, a[maxn], b[maxn], pos[maxn] = {0}; priority_queue<HeapNode> q; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; // 初始时每个a[i]配b[0] for(int i = 0; i < n; i++) { q.push({i, a[i] + b[0]}); } for(int i = 0; i < n; i++) { HeapNode tmp = q.top(); q.pop(); cout << tmp.val << " "; int x = tmp.x; if(++pos[x] < n) { q.push({x, a[x] + b[pos[x]]}); } } return 0; }时间复杂度分析：O(n log n)4. 高级应用提示Dijkstra算法优化：堆/优先队列可用于优化Dijkstra最短路径算法，将时间复杂度从O(V²)降低到O(E + V log V)单调队列：一种特殊的队列，可以高效解决滑动窗口最值问题多路归并：优先队列可以高效解决多路归并问题，如上面的最小N个和问题Huffman编码：优先队列可用于构建最优前缀编码树5. 总结数据结构特点主要操作时间复杂度典型应用栈(Stack)LIFOpush, pop, topO(1)函数调用、表达式求值队列(Queue)FIFOpush, pop, frontO(1)BFS、缓冲区优先队列(Priority Queue)自动排序push, pop, toppush/pop: O(log n), top: O(1)Dijkstra、Huffman编码、合并果子掌握这些基础数据结构及其应用场景，对于算法学习和编程竞赛至关重要。优先队列作为堆的高级抽象，在实际应用中更为方便，但理解其底层堆的原理同样重要。【熟能生巧】P9588 「MXOI Round 2」队列题目描述小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：$1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$；$2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；$3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；$4$：这是第四种操作，表示查询队列中所有元素的最大值。你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。输入格式第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【题目描述】。输出格式对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。输入输出样例 #1输入 #10 9 1 5 1 3 2 2 1 4 3 6 3 8 2 4 4 3 3输出 #13 2 4 1说明/提示【样例解释 #1】在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。【数据范围】设 $\sum x$ 表示单个测试点内 $x$ 之和。对于 $100\%$ 的数据，$1 \le q \le 2\times 10^5$，$1 \le x,y,z \le 10^9$，$0 \le \sum x \le 2\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。测试点编号$q \le$$x \le$$\sum x \le$特殊性质$1\sim3$$500$$500$$2\times10^5$C$4\sim8$$5000$$5000$$2\times10^7$无$9\sim10$$2\times10^5$$10^9$$2\times10^{14}$AB$11\sim12$$2\times10^5$$10^9$$2\times10^{14}$B$13\sim14$$2\times10^5$$10^9$$2\times10^9$AC$15\sim16$$2\times10^5$$10^9$$2\times10^9$C$17\sim18$$2\times10^5$$500$$2\times10^7$无$19$$2\times10^5$$10^9$$2\times10^9$无$20$$2\times10^5$$10^9$$2\times10^{14}$无特殊性质 A：没有第二种操作。特殊性质 B：没有第三种操作。特殊性质 C：没有第四种操作。P2723 [USACO3.1] 丑数 Humble Numbers题目描述对于一给定的素数集合 $S = \{ p_1, p_2, ..., p_k \}$, 考虑一个正整数集合，该集合中任一元素的质因数全部属于 $S$。这个正整数集合包括，$p_1$、$p_1 \times p_2$、$p_1 \times p_1$、$p_1 \times p_2 \times p_3$ ...(还有其它)。该集合被称为 $S$ 集合的“丑数集合”。注意：我们认为 $1$不是一个丑数。你的工作是对于输入的集合 $S$ 去寻找“丑数集合”中的第 $n$ 个“丑数”。保证答案可以用 32 位有符号整数表示。补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第 $n$ 个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第 $n$ 小的数。输入格式输入的第一行是两个的整数，分别代表集合 $S$ 的大小 $k$ 和给定的参数 $n$。输入的第二行有 $k$ 互不相同的整数，第 $i$ 个整数代表 $p_i$。输出格式输出一行一个整数，代表答案。输入输出样例 #1输入 #14 19 2 3 5 7输出 #127说明/提示数据规模与约定对于 $100\%$ 的数据，保证：$1 \leq k \leq 100$。$1 \leq n \leq 10^5$。$2 \leq p_i < 2^{31}$，且 $p_i$ 一定为质数。说明题目翻译来自 NOCOW。USACO Training Section 3.1P1323 删数问题题目描述一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。注：不存在所有数被删除的情况。输入格式只有一行两个整数，分别代表 $k$ 和 $m$。输出格式输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。输入输出样例 #1输入 #15 4输出 #1137915 95说明/提示数据规模与约定对于 $30\%$ 的数据，保证 $1\le k,m\le300$。对于 $100\%$ 的数据，保证 $1\le k,m\le3\times10^4$。P2085 最小函数值题目描述有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。输入格式第一行输入两个正整数 $n$ 和 $m$。以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。输出格式输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。输入输出样例 #1输入 #13 10 4 5 3 3 4 5 1 7 1输出 #19 12 12 19 25 29 31 44 45 54说明/提示数据规模与约定对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10$,$0 \leq B_i\le100$,$0 \leq C_i\le10^4$。【答案校对】队列#include <bits/stdc++.h> #define int long long using namespace std; const int N=800010; int c,T,t,i,cnt,op,x,del,qwq,f[N],l[N],r[N],a[N*2],h=1,n=400005; int read(){ int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return f*x; } void update(int x,int l,int r,int ql,int qr,int k){ int mid=(l+r)>>1; if(ql<=l&&r<=qr){ a[x]=k;return; } if(ql<=mid) update(x*2,l,mid,ql,qr,k); if(qr>mid) update(x*2+1,mid+1,r,ql,qr,k); a[x]=max(a[x*2],a[x*2+1]); } int query(int x,int l,int r,int ql,int qr){ int mid=(l+r)>>1,sum=0; if(ql<=l&&r<=qr){ return a[x]; } if(ql<=mid) sum=max(sum,query(x*2,l,mid,ql,qr)); if(qr>mid) sum=max(sum,query(x*2+1,mid+1,r,ql,qr)); return sum; } signed main(){ cin>>c>>T; while(T--){ op=read(); if(op==1) x=read(),l[++t]=1,r[t]=x,update(1,1,n,t,t,x),f[t]=f[t-1]+x; else if(op==2){ x=read();cnt=0; for(i=h;i<=t;++i){ cnt+=r[i]-l[i]+1; if(cnt>=x){ cnt-=r[i]-l[i]+1; l[i]+=x-cnt;del+=x-cnt; if(l[i]>r[i])update(1,1,n,i,i,0),++h; break; } del+=r[i]-l[i]+1;r[i]=l[i]=0;++h; update(1,1,n,i,i,0); } } else if(op==3){ x=read(); qwq=lower_bound(f+h,f+t+1,del+x)-f; printf("%lld\n",del+x-f[qwq-1]); } else printf("%lld\n",query(1,1,n,h,t)); } }丑数#include <bits/stdc++.h> #define int long long using namespace std; int n,m,i,j,a[105],b[105],s[100005],zx; signed main(){ cin>>n>>m; for(i=1;i<=n;i++) cin>>a[i]; s[0]=1; for(i=1;i<=m;i++){ zx=pow(2,31)-1; for(j=1;j<=n;j++){ while(a[j]*s[b[j]]<=s[i-1]) b[j]++; if(a[j]*s[b[j]]<zx) zx=a[j]*s[b[j]]; } s[i]=zx; } cout<<s[m]; }删数问题#include <bits/stdc++.h> #define int long long using namespace std; priority_queue<int,vector<int>,greater<int> > q; string p; int k,m,s; signed main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>k>>m; q.push(1); while(k){ int s=q.top(); p=p+to_string(s); q.pop(); q.push(s*2+1); q.push(s*4+5); k--; } cout<<p<<"\n"; while(true){ for(int i=0;i<p.size();i++){ if(p[i+1]>p[i]){ s++; p.erase(i,1); if(s>=m){ cout<<p; exit(0); } break; } } } }最小函数值#include <bits/stdc++.h> #define int long long using namespace std; int a[10001],b[10001],c[10001],n,m,s[10000001],i,j,t; signed main(){ cin>>n>>m; for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; for(i=1;i<=n;i++) for(j=1;j<=100;j++) s[++t]=a[i]*j*j+b[i]*j+c[i]; sort(s+1,s+1+t); for(i=1;i<=m;i++) cout<<s[i]<<" "; }