- 博客(34)
- 收藏
- 关注
RSS订阅原创 蓝桥杯 顺子日期 日期问题 C++
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123；而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?
2025-04-09 21:00:08
206
原创 蓝桥杯 数字接龙 深度优先搜索 dfs C++
小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N x N 的格子棋盘上展开，其中每一个格子处都有着一个0...K -1之间的整数。游戏规则如下:1.从左上角(0,0)处出发，目标是到达右下角(N-1,N-1)处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。2.对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足:0,1,2,…,K−1,0,1,2,…,K−1,0,1,2…。3.途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。
2025-04-08 11:11:50
433
原创 洛谷 P3367 【模板】并查集 C++
对于 100% 的数据，1≤N≤2×10 5 ，1≤M≤10 6 ，1≤X i ,Y i ≤N，Z i ∈{1,2}。当 Z i =2 时，输出 X i 与 Y i 是否在同一集合内，是的输出 Y；对于每一个 Z i =2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N。接下来 M 行，每行包含三个整数 Z i ,X i ,Y i 。对于 50% 的数据，1≤N≤10 4 ，1≤M≤2×10 5。对于 35% 的数据，N≤100，M≤10 3。
2025-04-05 12:14:06
340
原创 蓝桥杯 一键3连 贪心 C++
给定一个长度为 n 的整数数列 A，A 中第i个元素为 Ai(1 <=i<= n)，整数res 初始为 0，如果一个数a存在于 A且a+1,a+2均存在于 A中，则res加 1，请输出最后 res 的值。对于所有评测数据，3 ≤ n ≤ 105,1 ≤ A <= 105。第一行包含一个整数 n，表示整数数列 A 中元素的个数。第二行包含 n 个整数，表示整数数列 A 中各元素的值。输出共一行，包含一个整数，表示最后 res 的值。
2025-04-04 12:38:13
160
1
原创 蓝桥杯 小明的背包2 力扣 面试题 08.11. 硬币 完全背包问题 C++
小明有一个容量为 V 的背包。这天他去商场购物，商场一共有 N 种物品，第 i种物品的体积为 wi，价值为 vi，小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少请你帮他算算。
2025-04-04 11:42:52
304
原创 蓝桥杯 小明的背包1 小兰的神秘礼物 01背包问题 模板 C++
n件物品，一个容量是m的背包。第i个物品的体积是w[i],价值是v[i]。求解将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大。
2025-04-03 20:40:03
395
原创 蓝桥杯 数组切分 线性DP C++
已知一个长度为N的数组:A1,A2,A3,...AN 恰好是1~ N的一个排列。{1}{3,2}{4}:{3,2}包含 2到3,是 一段连续的自然数,另外 1和 4 显然也是。{1,3,2}{4}:{1,3,2}包含1到3,是 一段连续的自然数,另外 4 显然也是。{1}{3,2,4}:{3,2,4}包含 2到4,是一段连续的自然数,另外1 显然也是。输出一个整数表示答案。{1,3,2,4}:只有一个子数组,包含1到4,是 一段连续的自然数。1324:每个单独的数显然是(长度为 1的)一段连续的自然数。
2025-04-02 21:14:17
249
原创 蓝桥杯 接龙数列 线性DP C++
对于一个长度为K的整数数列:A1,A2,…,AK，我们称之为接龙数列当且仅当 Ai的首位数字恰好等于Ai-1 的末位数字 (2 <=i<=K)。例如 12,23,35,56,61,11 是接龙数列;12,23,34,56 不是接龙数列，因为56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。现在给定一个长度为 N 的数列 A1,A2,…,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列?
2025-04-02 19:59:10
260
原创 蓝桥杯 路径之谜 深度优先搜索 dfs C++
按习俗，骑士要从西北角走到东南角，可以横向或纵向移动，但不能斜着走，也不能跳跃。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线。第一行一个整数 N(0 ≤ N ≤ 20)，表示地面有 N x N 个方格。本题的要求就是已知箭靶数字，求骑士的行走路径(测试数据保证路径唯一)第二行 N 个整数，空格分开，表示北边的箭靶上的数字(自西向东)第三行 N 个整数，空格分开，表示西边的箭靶上的数字(自北向南)小明冒充 X 星球的骑士，进入了一个奇怪的城堡。有时是可以的，比如上图中的例子。
2025-03-30 14:27:01
349
原创 AcWing 92. 递归实现指数型枚举 深度优先搜索dfs C++
从 1∼n 这 n个整数中随机选取任意多个，输出所有可能的选择方案。同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。对于没有选任何数的方案，输出空行。
2025-03-30 12:05:15
187
原创 AcWing 94. 递归实现排列型枚举 深度优先搜索(dfs) 全排列 模板 C++
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行相邻两个数用一个空格隔开。
2025-03-29 16:15:57
150
原创 AcWing 96. 奇怪的汉诺塔 递归 C++
汉诺塔问题，条件如下：1、这里有 A、B、C和 D 四座塔。2、这里有 n 个圆盘，n 的数量是恒定的。3、每个圆盘的尺寸都不相同。4、所有的圆盘在开始时都堆叠在塔 A 上，且圆盘尺寸从塔顶到塔底逐渐增大。5、我们需要将所有的圆盘都从塔 A 转移到塔 D 上。6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。请你求出将所有圆盘从塔 A 移动到塔 D ，所需的最小移动次数是多少。汉诺塔塔参考模型。
2025-03-29 12:09:44
318
原创 AcWing 1343. 挤牛奶 区间合并or差分 C++
每天早上 5 点，三名农夫去牛场给奶牛们挤奶。现在从 5 点开始按秒计时，第一名农夫在第 300 秒开始给牛挤奶，并在第 1000 秒停止挤奶。第二名农夫在第 700秒开始给牛挤奶，并在第 1200 秒停止挤奶。第三名农夫在第 1500秒开始给牛挤奶，并在第 2100 秒停止挤奶。
2025-03-26 21:15:05
378
原创 AcWing 422. 校门外的树 区间合并/差分 C++
某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0，1，2，……，L 0 都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
2025-03-25 20:38:17
261
原创 AcWing 3498. 日期差值 日期问题 C++
有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天。每组数据占两行，分别表示两个日期，形式为 YYYYMMDD。年份范围 [1,9999] , 保证输入日期合法。测试数据的组数不超过 100。每组数据输出一行，即日期差值。输入包含多组测试数据。
2025-03-23 16:10:31
160
原创 AcWing 1229. 日期问题 C++
小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
2025-03-23 12:23:08
312
原创 蓝桥杯 子串分值和 贡献法 C++
现在给定一个字符串 S[0...n-1](长度为 n)，请你计算对于所有 S 的非空子串 S....j(0 <i<j< n)，f(S i..)的和是多少。对于一个字符串 S，我们定义 S 的分值 f(S)为 S 中出现的不同的字符个数。例如 f(“aba”)=2,f(“abc”)= 3,f(“aaa”)= 1。输入一行包含一个由小写字母组成的字符串 S.其中，1 ≤n≤ 105。输出一个整数表示答案。
2025-03-22 13:24:14
150
原创 AcWing 4261. 孤独的照片 贡献法 C++
输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。
2025-03-22 11:55:32
251
原创 AcWing 2868. 子串分值 贡献法 C++
对于一个字符串 S ，我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。例如 f(“aba”)=1 ，f(“abc”)=3 , f(“aaa”)=0。现在给定一个字符串 S[0…n−1] （长度为 n ），请你计算对于所有 S 的非空子串 S[i…j](0≤i≤j<n) ， f(S[i…j]) 的和是多少。
2025-03-22 09:50:30
286
原创 力扣 912. 排序数组 归并排序 C++
给你一个整数数组 nums，请你将该数组升序排列。你必须在的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。输入：nums = [5,2,3,1]输出：[1,2,3,5]输入：nums = [5,1,1,2,0,0]输出：[0,0,1,1,2,5]
2025-03-19 20:57:44
212
原创 洛谷 P1147 连续自然数和 前缀和+二分 C++
每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。例子：1998+1999+2000+2001+2002=10000，所以从 1998 到 2002 的一个自然数段为 M=10000 的一个解。对一个给定的正整数 M，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 M。包含一个整数的单独一行给出 M 的值（10≤M≤2,000,000）。
2025-03-18 20:09:43
135
原创 AcWing 3624. 三值字符串 滑动窗口 应用 C++
给定一个字符串 s ，其中的每个字符都是 1 , 2 或 3。请你求出同时包含字符 1,2,3 的 s 的最短子串的长度。注意，子串必须是连续的。
2025-03-12 19:00:25
229
原创 AcWing 61. 最长不含重复字符的子字符串 滑动窗口 模板 C++
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含从a到z的字符。
2025-03-12 15:38:39
171
原创 洛谷 P11853 [CSP-J2022 山东] 植树节 差分算法 模板 C++
植树节快要到了，学校要组织志愿者去给树苗浇水。有一排树苗，编号依次是 0,1,2,…。现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [ai,bi] ，表示第 i 个志愿者将 [ai,bi] 这一区间内的每一棵树都浇一次水。如某个志愿者选择的浇水区间为 [4,9] ，表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。请你求出浇水最多的树苗被浇了多少次。
2025-03-11 21:06:24
175
原创 牛客竞赛 送分了QAQ 前缀和 C++
杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。相比62，他那里的人更加讨厌数字38，当然啦，还有4这个数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？
2025-03-08 11:48:23
175
原创 牛客竞赛 数圈圈 前缀和 C++
tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。顺便还数了a到b之间有多少个圈。但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。
2025-03-08 11:03:00
181
原创 洛谷 B3612 【深进1.例1】求区间和 前缀和 模板 C++
给定 n 个正整数组成的数列 a 1 ,a 2 ,⋯,a n 和 m 个区间 [l i ,r i ]，分别求这 m 个区间的区间和。
2025-02-10 12:17:12
316
原创 AcWing 3493. 最大的和 前缀和 C++
给定一个长度为 n 的正整数数列 a1,a2,…,an。初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。你可以选择一个长度恰好为 k 的区间 [i,i+k−1] ，使得 ai∼ai+k−1，这 k 个元素的状态全部变为可选。请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。
2025-02-07 10:52:43
181
原创 AcWing 1530.最短距离 前缀和 C++
一个环形高速公路上有 N 个出口，共有 M 次询问，每次询问你需要回答其中两个出口之间的最短距离是多少。
2025-02-05 11:12:27
217
原创 洛谷 P2249 【深基13.例1】查找 二分查找模板 C++
输入 n 个不超过10 9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 1 , 2 , … , a 1 ,a 2 ,…,a n ，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 − 1。
2025-01-23 18:05:08
185
原创 洛谷 P1258 小车问题 C++
甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。仅一行，三个实数，分别表示 AB 两地的距离 s，人的步行速度 a，车的速度 b。两人同时到达 B 地需要的最短时间，保留 6位小数。对于 100%的数据，保证 0≤s,a,b≤109。
2025-01-21 17:34:53
286
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人