- 博客(1068)
- 收藏
- 关注
RSS订阅原创 CCF-GESP计算机学会等级考试2025年12月四级C++T2 优先购买
摘要 本文介绍了解决商品优先购买问题的算法思路。题目要求根据预算和商品属性（优先级、价格、名称）选择购买顺序。核心步骤包括：1) 使用结构体存储商品信息；2) 按优先级、价格、名称字典序进行多级排序；3) 遍历排序后的商品列表，在预算范围内购买商品；4) 对购买结果进行字典序排序后输出。算法通过自定义排序函数实现了题目要求的购买策略，确保优先购买高优先级商品，兼顾价格和名称顺序。
2025-12-31 10:18:54
687
原创 CCF-GESP计算机学会等级考试2025年12月四级C++T1 建造
题目要求在地形图中找出所有3×3区域，其中最大高度和最小高度差不超过H，并计算这些区域中海拔之和的最大值。解题思路是遍历所有可能的3×3区域（左上角坐标范围为1~m-2行和1~n-2列），对每个区域进行合法性检查（最大高度差≤H），然后计算合法区域的海拔和并维护全局最大值。算法通过双层循环遍历所有潜在区域，使用辅助函数进行校验和求和，最终输出最大合法区域的海拔和。该方法确保覆盖所有可能区域并高效计算结果。
2025-12-31 09:51:10
439
原创 CCF-GESP计算机学会等级考试2025年12月三级C++T2 小杨的智慧购物
摘要：题目要求为M种文具各选最便宜的一件，计算总花费。解法有两种思路：1）使用数组记录每类文具的最低价格，遍历所有文具更新最低价后求和；2）按种类和价格排序后，取每类第一个价格累加。两种方法的时间复杂度分别为O(N+M)和O(N log N)，均能高效处理最大10^5的数据规模。示例输入中种类1最低价1元，种类2最低价3元，总花费4元。
2025-12-31 09:31:55
1377
原创 CCF-GESP计算机学会等级考试2025年12月三级C++T1 密码强度
本文介绍了一个密码强度检测器的实现方法。题目要求判断密码是否满足三个安全条件：长度≥8字符、包含至少一个大写字母和至少一个数字。解题思路采用分步验证：先快速检查密码长度，再遍历字符串标记是否存在大写字母和数字，最后综合判断。代码使用C++实现，通过布尔变量标记关键字符的存在性，高效完成检测。该算法时间复杂度为O(T*L)，适用于题目给定的数据范围（T≤100，L≤100），能够快速处理所有测试用例。
2025-12-31 09:13:16
735
原创 CCF-GESP计算机学会等级考试2025年12月二级C++T2 黄金格
本文分析了B4448 [GESP202512 二级] 黄金格问题的解法。题目要求统计满足特定数学不等式的格子数量。关键优化点在于将原始含平方根的不等式转化为纯整数运算，避免浮点数精度误差。解法采用双重循环遍历所有格子，通过整数平方运算判断条件，时间复杂度为O(H×W)。样例验证表明解法正确，同时提醒注意坐标起始值和精度处理问题。代码简洁高效，适合给定的数据范围。
2025-12-31 08:56:51
982
原创 CCF-GESP计算机学会等级考试2025年12月二级C++T1 环保能量球
摘要：题目要求计算小杨行走n公里后获得的总环保能量，包括基础能量（每公里1点）和额外奖励（每x公里1点）。对于每组测试数据，输入n和x，输出总能量n + n/x。例如，输入5公里、奖励间隔2公里，总能量为5+2=7点。解题关键是理解整数除法的取整特性，通过循环处理多组数据即可。代码实现简单，主要考察基础输入输出和数学运算能力。
2025-12-31 08:47:06
711
原创 CCF-GESP计算机学会等级考试2025年12月一级C++T2 手机电量显示
小杨的手机就像一个聪明的小助手，当电量变化时，它会用不同的方式来提醒我们，假设当前的电量百分比为PP≤1010P≤20P20。
2025-12-31 08:37:17
378
原创 CCF-GESP计算机学会等级考试2025年12月一级C++T1 小杨的爱心快递
题目要求计算快递运费，采用体积和重量两种计费方式中的较低值。体积运费为0.5×V元；重量运费在G<300克时为M元，否则为N元。输入包含V、G、M、N四个一位小数，输出运费（保留一位小数）。例如，当V=100.4、G=300.2时，体积运费50.2元低于重量运费70.5元，故输出50.2。程序通过比较两种运费计算结果，输出较小值即可。
2025-12-31 08:27:37
483
原创 P10454 奇数码问题
摘要：本文分析了奇数码问题的解法，核心是利用归并排序高效计算逆序对数量。对于两个n×n（n为奇数）的局面，可达的充要条件是它们忽略空格后的数字序列逆序对数量奇偶性相同。通过将二维矩阵展平为一维数组，采用归并排序统计逆序对，最后比较奇偶性判断可达性。该方法时间复杂度为O(n² log n)，适用于n<500的数据规模。
2025-12-27 21:14:50
788
原创 UVA10810 Ultra-QuickSort
选择全局变量是为了避免函数传参的繁琐，同时保证数组空间足够（500005满足题目n的上限要求）。为什么用long long？当n=500000时，最大逆序对数量为500000×4999992≈1.25×10112500000×499999≈1.25×1011，远超int的最大值（约2×1092×109），会导致溢出，因此ans必须定义为long long类型。
2025-12-27 18:52:47
635
原创 P1168 中位数
摘要： 题目要求对给定序列的前1、3、5...奇数项分别求中位数。采用双堆法（大根堆存较小半部分，模拟小根堆存较大半部分）高效维护中位数，保证大根堆始终比小根堆多1个元素。每次处理奇数项时调整堆大小，大根堆顶即为当前中位数。算法时间复杂度O(n log n)，空间复杂度O(n)，能处理1e5规模数据。核心是堆的平衡调整策略，避免暴力排序导致的超时问题。
2025-12-27 11:06:04
818
原创 P10453 七夕祭
摘要 七夕祭问题要求在环形网格中通过交换相邻摊点，使各行/列感兴趣的摊点数均匀分布。解题关键在于： 将问题拆分为行和列两个独立子问题； 利用环形均分纸牌模型，通过计算差值数组的前缀和并求中位数，确定最小交换次数； 时间复杂度为O(NlogN + MlogM)，能高效处理大规模数据。 解决方案先判断能否均分行/列，再分别计算最小交换次数，最后综合输出结果。核心算法结合了前缀和与中位数贪心的思想。
2025-12-27 08:01:56
707
原创 P10452 货仓选址
摘要：货仓选址问题要求在数轴上选择一个位置，使得货仓到各商店的距离之和最小。最优解是将货仓建在所有商店坐标的中位数位置。解题步骤：1) 输入商店坐标并排序；2) 取中位数作为货仓位置；3) 计算所有点到中位数的距离和。时间复杂度为O(N log N)，需注意用long long存储总距离防止溢出。示例输入[6,2,9,1]排序后中位数为2，输出最小总距离12。
2025-12-26 22:05:45
384
原创 CF670C Cinema
题目摘要： 给定n位科学家各自掌握的语言（编号1-1e9）和m场电影的配音/字幕语言，选择一场电影使得： 能听懂配音的科学家最多； 若配音人数相同，则选择能看懂字幕人数最多的电影。 输出最优电影的编号（从1开始）。 解法核心： 使用map统计每种语言的人数； 遍历每场电影，比较其配音和字幕的覆盖人数，按优先级规则更新最优选择； 时间复杂度为O(n log n + m log n)，适用于2e5数据规模。 示例说明： 输入样例1中，电影2的配音语言3有1人愉悦，字幕语言3有1人满意，优于电影1，故输出2。
2025-12-26 21:54:03
846
原创 上海计算机学会2025年12月月赛C++丙组T5 Random Access Emotions
本文探讨了如何通过调整序列中的0元素，最大化情绪稳定天数的问题。关键思路是将序列分为固定前缀和可调整段，利用哈希表统计各段前缀和的最大频次。具体步骤包括：处理前导无0段、按0分割后续段并统计频次，最后累加各段最大贡献。算法时间复杂度为线性，适用于大规模数据。通过合理利用前缀和性质和分段处理策略，高效解决了问题。
2025-12-19 21:39:41
1318
原创 上海计算机学会2025年12月月赛C++丙组T4 分形方阵
本文探讨了如何生成分形方阵的问题。给定级别N，分形方阵按递归规则构建：0级为1×1的"#"，k级方阵由三个k-1级方阵分别置于左上、左下、右上，右下填充"."。采用递归分治方法，先构建小规模子方阵，再复制到指定位置。时间复杂度为O(4ⁿ)，空间复杂度O(4ⁿ)。通过样例验证了算法的正确性，展示了递归在分形问题中的高效应用。
2025-12-19 21:22:14
566
原创 上海计算机学会2025年12月月赛C++丙组T3 Boilerplate
摘要：题目要求判断给定字符串能否通过至多n-1次操作（添加字符或复制粘贴子串）构造。核心思路是：当字符串长度n≤3时直接输出NO；否则检查是否存在重复的2字符子串，存在则输出YES（可通过复制操作减少总次数），否则输出NO。算法利用哈希表记录子串，时间复杂度O(n)，适用于大规模数据。样例分析验证了算法的正确性。
2025-12-19 21:12:21
995
原创 上海计算机学会2025年12月月赛C++丙组T2 民科？！
摘要 题目要求对于给定的整数 $n$，找到最小的质数 $m$，使得 $n+m$ 不是质数。通过暴力遍历的方法，从最小的质数 $m=2$ 开始逐个检查，直到满足条件。使用质数判断函数优化计算，确保在合理时间内处理多组测试数据（$T \leq 10^4$，$n \leq 10^5$）。样例输入输出验证了算法的正确性，如输入3时输出2、3、2分别对应 $n=2,3,4$ 的情况。
2025-12-19 20:55:32
321
原创 上海计算机学会2025年12月月赛C++丙组T1 强迫症
摘要：本文解决统计区间[1, n]内"整齐的数"的问题，即恰好一位非零的数（如5、60）。通过分析发现，k位数的整齐数共9个（d×10^(k-1)）。算法先累加所有更短位数段的9个整齐数，再计算当前位数段≤n的个数。代码通过循环缩短n的位数并累加9，最终加上剩余1位数值，时间复杂度O(Tlogn)。样例验证表明该解法高效正确，满足题目约束条件。
2025-12-19 20:41:47
827
原创 P10450 [USACO03MAR] Best Cow Fences G
摘要 题目要求在一个长度为n的非负整数序列中，找到长度不小于L的子段，使其平均数最大，并输出该平均数的1000倍整数。由于直接暴力枚举会超时，我们采用二分答案法结合前缀和优化来解决。核心思路是将平均数判断转化为子段和判断，通过二分猜测可能的平均数，利用前缀和数组快速验证是否存在满足条件的子段。为了避免浮点精度问题，先将所有元素乘以1000转化为整数运算。算法时间复杂度为O(n log M)，其中M=2×10^6，适用于n≤1e5的数据规模。最终输出最大的可行平均数×1000的整数值。
2025-12-09 12:05:15
531
原创 P2879 [USACO07JAN] Tallest Cow S
题目摘要：给定N头奶牛的排列，已知最高奶牛编号I和身高H，以及R条"A能看到B"的信息（表示A和B身高互不低于对方，中间奶牛身高严格小于它们）。要求计算每头奶牛在满足所有信息前提下的最大可能身高。使用差分法优化区间修改，避免重复处理相同信息，最终通过前缀和计算得到每头奶牛的身高。时间复杂度O(R log R + N)，适用于N,R≤1e4的数据规模。
2025-12-02 16:00:14
1374
原创 P4552 [Poetize6] IncDec Sequence
给定一个长度为n的数列a1a2⋯an，每次可以选择一个区间lr，使这个区间内的数都加1或者都减1。请问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。
2025-12-02 14:53:32
745
原创 P2280 [HNOI2003] 激光炸弹
本文解析了激光炸弹问题，要求计算边长为m的正方形能摧毁的最大目标价值总和。通过二维前缀和优化，将时间复杂度降至O(5×10^3×5×10^3)。关键步骤包括：坐标偏移处理、价值矩阵构建、前缀和计算，以及枚举所有可能的正方形区域求最大值。算法高效处理了边界条件、重复坐标和坐标偏移等问题，确保在合理时间内求解。
2025-12-01 21:46:32
860
原创 P1593 因子和
摘要 题目要求计算a^b的因子和对9901取模的结果。通过质因数分解将a表示为p1^c1 * p2^c2 ... pn^cn，则a^b的因子和可分解为各质因子等比数列和的乘积。使用快速幂和乘法逆元处理模运算中的除法问题，特殊处理p≡1(mod 9901)的情况。算法包括质因数分解、快速幂计算和逆元求解三个主要步骤，时间复杂度为O(√a + nlog(c_i*b))，能够高效处理大规模数据。代码实现了这一过程，并通过模运算确保结果正确性。
2025-11-29 21:35:11
803
原创 P10449 费解的开关
本文介绍了"费解的开关"问题解法。题目要求在5×5的灯阵中，每次操作一个灯会改变其上下左右灯的状态，判断能否在6步内使所有灯全亮。解法采用枚举第一行所有可能的32种操作组合，然后递推计算后续行的必要操作，最终验证最后一行是否全亮并统计操作步数。对于每个测试用例，输出最小步数或-1表示无法在6步内完成。核心算法通过位运算高效处理灯状态变化，复杂度为O(n×32×5)，适用于大规模数据。
2025-11-29 00:21:51
478
原创 B3623 枚举排列（递归实现排列型枚举）
本文介绍了如何使用深度优先搜索(DFS)递归实现排列型枚举。题目要求从n名学生中选出k人排成一列，按字典序输出所有可能的排列组合。通过DFS算法逐步构建排列，使用数组标记已选数字避免重复。当排列长度达到k时输出结果，否则继续枚举未使用的数字。代码简洁高效，适用于n≤10的小规模数据。
2025-11-28 21:35:02
203
原创 B3622 枚举子集（递归实现指数型枚举）
题目要求输出n位同学的所有可能选择方案，每位同学可选参加(Y)或不参加(N)。采用递归方法实现指数型枚举，按字典序输出所有组合。输入n后，通过深度优先搜索构建所有可能的字符串组合，当字符串长度达到n时输出。例如n=3时，输出从NNN到YYY共8种方案。算法时间复杂度为O(2^n)，适用于n≤10的情况。
2025-11-28 21:33:36
329
原创 B3622 枚举子集（递归实现指数型枚举）
题目要求输出n位同学的所有可能选择方案，每位同学可选参加(Y)或不参加(N)。采用递归方法实现指数型枚举，按字典序输出所有组合。输入n后，通过深度优先搜索构建所有可能的字符串组合，当字符串长度达到n时输出。例如n=3时，输出从NNN到YYY共8种方案。算法时间复杂度为O(2^n)，适用于n≤10的情况。
2025-11-28 21:04:44
283
原创 P10448 组合型枚举
题目要求从1到n的整数中选取m个数的所有组合，并按字典序输出。使用深度优先搜索(DFS)进行枚举，确保每个组合都是升序排列且不重复。具体实现时，通过递归填充数组并标记已使用的数字，当填满m个数时输出结果。时间复杂度为组合数C(n,m)，适用于n和m较小的情况。
2025-11-28 20:58:13
637
原创 B3621 枚举元组
摘要：题目要求枚举所有由n个元素组成的元组，每个元素取值范围为1到k，并按字典序输出。使用深度优先搜索(DFS)算法，递归生成所有可能的元组组合。当元组长度达到n时输出结果，否则继续枚举1到k的值填充当前位置。样例展示了n=2,k=3和n=3,k=3时的输出结果。数据范围限制n≤5且k≤4。
2025-11-28 20:47:37
226
原创 李煜东《算法竞赛进阶指南》题解目录
本文整理了算法竞赛中的基础算法题目，涵盖位运算、递推与递归、前缀和与差分、二分、排序、倍增和贪心七大专题。其中位运算部分包含快速幂、整数乘法等经典问题；递推递归部分涉及枚举、组合排列等题型；前缀差分部分包含激光炸弹等应用场景；二分排序部分收录了最佳牛栏、中位数等典型问题；倍增和贪心部分则整理了天才ACM、雷达安装等优化算法题目。这些题目来自Codeforces、USACO、NOIP等知名竞赛，适合算法学习者系统练习基础算法能力。
2025-11-27 19:07:35
314
原创 P2114 [NOI2014] 起床困难综合症
题目概述 本题描述了一个名为"起床困难综合症"的问题，涉及通过一系列位运算门后计算最大伤害值。给定n个位运算门（AND、OR、XOR）和一个初始攻击力上限m，需要选择一个0到m之间的初始值x，使得经过所有位运算门后的结果最大。 解题思路 位独立性：由于位运算的特性，每一位的运算结果互不影响，可以逐位独立处理。 贪心策略：从最高位到最低位依次处理，优先保证高位为1能获得更大结果。 可行性判断：对于每一位，分别计算初始值为0和1时的最终结果，在不超过m的前提下选择能使结果更大的值。 关键步骤
2025-11-27 19:00:04
1369
原创 P10447 最短 Hamilton 路径
题目摘要 题目P10447要求求解带权无向图中从起点0到终点n-1的最短Hamilton路径（经过所有点恰好一次）。给定n个点的邻接矩阵，使用状态压缩动态规划，用二进制位表示访问状态。算法核心是遍历所有可能状态组合，通过三重循环更新最小路径代价。最终输出访问所有点且到达终点的最小总代价。数据范围n≤20，保证邻接矩阵对称且满足三角不等式。
2025-11-27 18:52:43
621
原创 P10446 64位整数乘法
摘要 题目P10446要求计算大整数a和b的乘积对p取模的结果，其中a,b,p可达1e18量级。由于直接相乘会超出long long范围，解法采用二进制分解思想：将b分解为二进制位，通过循环每次将a翻倍并取模，当b的当前位为1时累加对应的a值到结果中。这种方法避免了直接大数相乘，确保在合理范围内完成计算。时间复杂度为O(logb)，适用于极大数运算。
2025-11-27 18:29:26
328
原创 P1226 【模板】快速幂
摘要：本文介绍了快速幂算法模板题，要求计算a^b mod p的值。通过将指数b进行二进制分解，将复杂度从O(b)降低到O(logb)。代码实现中，循环处理b的每一位，若当前位为1则累乘对应的a的幂次，并在每一步都取模防止溢出。输入输出格式要求输出形如"a^b mod p=s"的结果，适用于大数运算场景（0≤a,b<2^31）。
2025-11-27 18:18:14
178
原创 上海计算机学会2025年11月月赛C++丙组T5 平面
时间限制：2000 ms内存限制：256 MB平面上一共有 nnn 个整点，坐标为 (xi,yi)(x_i,y_i)(xi,yi)。任选两个点 A,BA,BA,B，我们称 A,BA,BA,B 两点间形成的直线为，A,BA,BA,B 相连且两端无限延申形成的图形。那么平面上的 nnn 个整点可以形成共 m=n(n−1)2m=\dfrac{n(n-1)}{2}m=2n(n−1) 条直线。Eve 想知道这 mmm 条直线有多少对是相交的。请注意：如果两条直线重合我们视作不相交。输入一行一个整数 nnn。接
2025-11-23 21:17:32
449
原创 上海计算机学会2025年11月月赛C++丙组T4 序列
摘要： 本题要求在允许将任意子段元素乘以x一次的条件下，求序列的最大子段和。使用动态规划维护三个状态：未使用乘法(dp0)、正在使用乘法(dp1)和已完成乘法(dp2)的最大子段和。每个状态转移时考虑当前元素是否参与乘法操作，并保持非负性质。最终答案为三个状态的最大值。算法时间复杂度O(n)，适用于大规模数据（n≤3×10^5）。样例输入5个元素和x=-2时，输出最大子段和22。
2025-11-23 20:58:38
309
原创 上海计算机学会2025年11月月赛C++丙组T3 幻影香水
摘要： 题目描述n名学生排成一列，每组轮流选择剩余学生中水平值最大的个体及其左右各k名同学（不足则全选），动态调整队列后确定最终分组。关键挑战在于高效处理动态队列和快速定位最大值。 解题思路： 优先选择：按水平值逆序遍历，确保每次选最大值。 双向链表优化：用l[]和r[]记录有效邻居，被选区间通过链表快速删除（O(1)时间）。 反向映射：数组b[val]存储水平值对应位置，实现O(1)查找。 复杂度：O(n)，适用于2×10⁵规模数据。
2025-11-23 20:48:08
908
原创 上海计算机学会2025年11月月赛C++丙组T2 水面之下
摘要：Bob 观看动画时，每天从第一集开始连续观看，直到当天看过的所有谜团都在当前集数内被解释。算法通过遍历每集，实时更新谜团解释集数的最大值，当最大值等于当前集数时天数加1。该解法时间复杂度为O(n)，空间复杂度O(1)，高效解决了问题。
2025-11-23 20:19:01
477
原创 上海计算机学会2025年11月月赛C++丙组T1 紫阳花
摘要：Alice要用红、紫、蓝三种紫阳花插花，要求紫色比红色多1朵，蓝色比紫色多1朵。求在给定花量(a,b,c)下能选的最大花数。解题关键在于找到满足x≤a、x+1≤b、x+2≤c的最大x，总花数为3(x+1)。核心解法是计算x=min(a,b-1,c-2)，最终结果为3*(x+1)。两种代码实现分别通过分步约束和直接求最小值来高效解决问题。
2025-11-23 20:01:36
314
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人