济南网站建设正规公司哪家好,通过信息系统融合和创新形成企业解决方案,wordpress验证密码,昆明公司网站制作记录刷题的过程、感悟、题解。 希望能帮到#xff0c;那些与我一同前行的#xff0c;来自远方的朋友#x1f609; 大纲#xff1a; 1、日期统计-#xff08;解析#xff09;-暴力dfs#xff08;#x1f609;蓝桥专属 2、01串的熵-#xff08;解析#xff09;-不要chu…记录刷题的过程、感悟、题解。 希望能帮到那些与我一同前行的来自远方的朋友 大纲 1、日期统计-解析-暴力dfs蓝桥专属 2、01串的熵-解析-不要chu认真读题并且知道log()怎么用就OK 3、冶炼金属-解析-其实推理极限用数学知识就能OK 4、飞机降落-解析-暴力搜索dfs蓝桥专属 5、接龙数列-解析-字典dp就是名字高大上点只是一道dp 6、岛屿个数-解析-bfsdfs重点在于会染色会读题广搜深搜一起整 7、子串简写-解析-一道简单的前缀和 8、整数删除-解析-优先队列双向链表模拟
9、10 是lca类型的题目这类题型攒着。到时候出个专题一块搞。 知识点
1、二分查找
2、emplace
3、log() ::cmath:: 1、日期统计 问题描述 小蓝现在有一个长度为 100 的数组数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3现在他想要从这个数组中寻找一些满足以下条件的子序列 子序列的长度为 8这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期并且要求这个日期是 2023 年中的某一天的日期例如 2023090220231223。yyyy 表示年份mm 表示月份dd 表示天数当月份或者天数的长度只有一位时需要一个前导零补充。 请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。 答案提交 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。 /* 其实本题非常简单因为它体现了蓝桥杯可以 暴力dfs的点 首先以2023开头是固定的你可以在前方先把这个给枝剪掉 然后再剩下mmdd这四位中爆搜dfs当然多层for循环也行就行把所有可能给列举出来 切记一定要防止日期重复这点很细节。 */
C题解
#include iostream
#include vector
using namespace std;vectorint vec{ // 年份剔除已经存储完毕3,8, 5 ,1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
};vectorvectorbool ymd(13,vectorbool(32,false)); // 已经非常确定了void t(int mm, int dd){ // 检测if(mm1||mm3||mm5||mm7||mm8||mm10||mm12){ // 31天if(0dddd31) ymd[mm][dd]true;}else if(mm2){ // 28天if(0dddd28) ymd[mm][dd]true;}else if(mm4||mm6||mm9||mm11){ // 30天if(0dddd30) ymd[mm][dd]true;}
}void dfs(int cur, int pla, string str){if(cur4){ // 判断int mm stoi(str.substr(0,2));int dd stoi(str.substr(2,2));t(mm,dd);return;}for(int ipla1; ivec.size(); i){dfs(cur1,i,str to_string(vec[i]));}
}int main()
{dfs(0,0,);int sum 0;for(int i0; iymd.size(); i){for(int j0; j32; j){if(ymd[i][j]) sum;}}coutsumendl;return 0;
}
Java题解
import java.util.ArrayList;
import java.util.List;public class Main {// 年份剔除已经存储完毕static ListInteger vec List.of(3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3);// 已经非常确定了static boolean[][] ymd new boolean[13][32];// 检查日期是否合法并标记static void t(int mm, int dd) {if (mm 1 || mm 3 || mm 5 || mm 7 || mm 8 || mm 10 || mm 12) {// 31 天的月份if (0 dd dd 31) {ymd[mm][dd] true;}} else if (mm 2) {// 28 天的月份if (0 dd dd 28) {ymd[mm][dd] true;}} else if (mm 4 || mm 6 || mm 9 || mm 11) {// 30 天的月份if (0 dd dd 30) {ymd[mm][dd] true;}}}// 深度优先搜索static void dfs(int cur, int pla, String str) {if (cur 4) {// 判断int mm Integer.parseInt(str.substring(0, 2));int dd Integer.parseInt(str.substring(2, 4));t(mm, dd);return;}for (int i pla 1; i vec.size(); i) {dfs(cur 1, i, str vec.get(i));}}public static void main(String[] args) {dfs(0, 0, );int sum 0;for (int i 0; i ymd.length; i) {for (int j 0; j 32; j) {if (ymd[i][j]) {sum;}}}System.out.println(sum);}
}
2、01串的熵 // 只要你不chu认真读题仔细观察还是能做本题的
/* 但是前提条件之一是你要知道log的用法 底数;cmath C中log默认是 ln(..) 要做到log(真数指数的底数)这一步 需要用换底公式ln(真数)/ln(指数的底数) 这涉及到数学中的指数式 与 对数的转换 细节log(float/double) 内部只能传递这两种类型传出也是否则也会被隐式转换 */ /* 本题的式子都给的这么明显了怎么可能还搞不出来 H(S) 首先是负号、然后观察 100一个1两个0。看出什么没 当然是后面的对应顺序呀。共3个1个1 1/3) (2个0 2/3还有个数。 “ 0 出现次数比 1 少 ” 根据题意所以0的个数一定1~23333333/2之间的某个数字。 */
C版
#include iostream
#include cmath
using namespace std;int main()
{int N 23333333;for(int i1; iN/2; i){int n0 i; // 0的个数;int n1 N-i; // 1的个数;double sum 0;sum-(double)n0/N*log((double)n0/N)/ log(2)*n0;sum-(double)n1/N*log((double)n1/N)/ log(2)*n1;if(fabs(sum-11625907.5798)1e-4){coutn0endl;break;}}return 0;
}
Java版
import java.lang.Math;public class Main {public static void main(String[] args) {int N 23333333;for (int i 1; i N / 2; i) {int n0 i; // 0的个数int n1 N - i; // 1的个数double sum 0;sum - (double) n0 / N * Math.log((double) n0 / N) / Math.log(2) * n0;sum - (double) n1 / N * Math.log((double) n1 / N) / Math.log(2) * n1;if (Math.abs(sum - 11625907.5798) 1e-4) {System.out.println(n0);break;}}}
}
3、冶炼金属 问题描述 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 VV 是一个正整数这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X当普通金属 O 的数目不足 V 时无法继续冶炼。 现在给出了 N 条冶炼记录每条记录中包含两个整数 A 和 B这表示本次投入了 A 个普通金属 O最终冶炼出了 B 个特殊金属 X。每条记录都是独立的这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。 根据这 N 条冶炼记录请你推测出转换率 V 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。 输入格式 第一行一个整数 N表示冶炼记录的数目。 接下来输入 N 行每行两个整数 A、B含义如题目所述。 输出格式 输出两个整数分别表示 V 可能的最小值和最大值中间用空格分开。 样例输入 3
75 3
53 2
59 2样例输出 20 25样例说明 当 V20 时有⌊75/20⌋3⌊53/20⌋2⌊59/20⌋2可以看到符合所有冶炼记录。 当 V25时有⌊75/25⌋3⌊53/25⌋2⌊59/25⌋2可以看到符合所有冶炼记录。 且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。 评测用例规模与约定 对于 30% 的评测用例1≤N≤10^2。 对于 60% 的评测用例1≤N≤10^3。 对于 100% 的评测用例1≤N≤10^41≤B≤A≤10^9。 // 本题为贪心算法-从局部推至整体、 // 我看网上其他人用了很多复杂的方法什么差分呐... // 好像用不到耶只需要推逼一下极限就行 /* 听好喽这几部很关键。 什么是转化率消耗的最小值 极限就是你刚好能转化 B1块 但因为是推理出来的极限实际上是不存在的也就是差一点点。所以要再结果上在1块 例75/4181811919就是此时的极限 同样什么是转化率消耗的最大值你的所有金属A刚好转哈为B块。A/B */ // 希望对你有帮助
C版
#include iostream
#define ll long long
using namespace std;
const ll maxl 0x3f3f3f3f3f3f3f3f; // 伪最大值int main()
{int t;cint;int maxVmaxl,minV0; // 涉及一个极端情况。int A,B;while(t--){cinAB;minVmax((A/(B1)1),minV); // 最小值maxVmin((A/B),maxV); // 最大值}coutminV maxV;return 0;
}
Java版
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);long maxV Long.MAX_VALUE; // 初始化为最大可能值long minV 0; // 初始化为最小可能值int t scanner.nextInt();for (int i 0; i t; i) {long A scanner.nextLong();long B scanner.nextLong();// 计算当前测试用例的最小和最大值long currentMin (A / (B 1)) 1;long currentMax A / B;// 更新全局的最小和最大值if (currentMin minV) {minV currentMin;}if (currentMax maxV) {maxV currentMax;}}System.out.println(minV maxV);}
}
4、飞机降落 问题描述 N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空到达时它的剩余油料还可以继续盘旋 Di 个单位时间即它最早可以于 Ti 时刻开始降落最晚可以于 TiDi 时刻开始降落。降落过程需要 Li 个单位时间。 一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不能在前一架飞机完成降落前开始降落。 请你判断 N 架飞机是否可以全部安全降落。 输入格式 输入包含多组数据。 第一行包含一个整数 T代表测试数据的组数。 对于每组数据第一行包含一个整数 N。 以下 N 行每行包含三个整数TiDi 和 Li。 输出格式 对于每组数据输出 YES 或者 NO代表是否可以全部安全降落。 样例输入 2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20样例输出 YES
NO样例说明 对于第一组数据可以安排第 3 架飞机于 0 时刻开始降落20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落40 时刻完成降落。 对于第二组数据无论如何安排都会有飞机不能及时降落。 评测用例规模与约定 对于 30% 的数据N≤2。 对于 100% 的数据 1≤T≤101≤N≤100≤Ti,Di,Li≤10^5。 // 我当时写的时候一直轮询检测超时。我还以为是太暴力了(┬┬﹏┬┬)结果...是蓝桥杯官网出问题了提交不了可恶。 // 人家都给你飞机了而且最多不会超过10架 // 题都给到这种程度了还犹豫什么直接爆搜把所有情况给枚举出来。最多10 // 所以说好听点本题本质上就是一道组合题目 /* 你要先创建一个数组used[N]这台飞机你遍历过没 然后在爆搜期间维持一个cnt(原count、简写)去记录到底停了几架飞机 ---以上这些只是方便缕清思路的一环接下来才是关键--- 咱假设cur_start是你的最晚开始落下时间、cur_last 其他飞机能开始落下的时间。 cur_startTiDi 是你的最晚开始落下时间、 而cur_lastTiDiLi 才是你最晚落下后并且能让其他飞机降落的时间。 也就是 cur_last cur_startLi; 但是认真读过题的都知道 开始降落的时间不一定非要是TiDi, 他取决于2点
上一架飞机是啥时候落下的other_last能不能在Ti最早时刻落下Ti。 此刻if(other_lastTi) cur_last other_last; if(other_lastTi) cur_last Ti; 确切的是画个图就知道了 OK知道这些了你确定你还会做不出来吗 爆搜开始 */
C版
#include iostream
#include vector
using namespace std;const int N 1e15;
int t,n;
vectorbool used(N,false); // 是否已经降落
vectorvectorint res(N,vectorint(3,0));int flag false;void dfs(int cur ,int tim){ // nif(curn){ // 成功的条件flagtrue;return;}for(int i0; in; i){// 标准回溯if(!used[i] tim(res[i][0]res[i][1])){ // timvec[i][1] 超过了最晚截止时间used[i]true;// couti used[i] tim res[i][0] res[i][1]endl;int cur_start max(res[i][0],tim);dfs(cur1,cur_startres[i][2]);used[i]false;}}}int main()
{cint;while(t--){for(int i0; in; i) used[i]false;cinn;for(int i0; in; i){cinres[i][0]res[i][1]res[i][2]; // 存}dfs(0,0);if(flag) coutYESendl;else coutNOendl;flag false;}return 0;
}Java版
import java.util.Scanner;
import java.util.ArrayList;public class Main {static final int N 105;static int t, n;static boolean[] used new boolean[N];static int[][] res new int[N][3];static boolean flag false;public static void main(String[] args) {Scanner scanner new Scanner(System.in);t scanner.nextInt();while (t-- 0) {for (int i 0; i N; i) {used[i] false;}n scanner.nextInt();for (int i 0; i n; i) {res[i][0] scanner.nextInt();res[i][1] scanner.nextInt();res[i][2] scanner.nextInt();}flag false;dfs(0, 0);if (flag) {System.out.println(YES);} else {System.out.println(NO);}}scanner.close();}static void dfs(int cur, int tim) {if (cur n) {flag true;return;}for (int i 0; i n; i) {if (!used[i] tim (res[i][0] res[i][1])) {used[i] true;int cur_start Math.max(res[i][0], tim);dfs(cur 1, cur_start res[i][2]);used[i] false;}}}
}
5、接龙数列 问题描述 对于一个长度为 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请你计算最少从中删除多少个数可以使剩下的序列是接龙序列 输入格式 第一行包含一个整数 N。 第二行包含 N 个整数 A1,A2,…,AN。 输出格式 一个整数代表答案。 样例输入 5
11 121 22 12 2023样例输出 1样例说明 删除 22剩余 11,121,12,2023 是接龙数列。 评测用例规模与约定 对于 20% 的数据1≤N≤20。 对于 50% 的数据1≤N≤10000。 对于 100% 的数据1≤N≤1051≤Ai≤109。所有 Ai 保证不包含前导 0。 // 有很多特殊的案例的11 12 13 35 // 额字典dp这玩意... 我真的还是第一次听说耶 // 挺值得思考的为什么我在第一次做本题的时候咋就没有往动态规划上想 // 他们都是这样解释字典dp的利用哈希表来储存和管理状态的优化方式 // 简而言之就是通过键值对储存最优解适用于不连续的场景或范围较大的场景 /* 好啦、知道啥是字典序了就来解决一下本题 -- 肯定很多人在一开始直接想到贪心、局部最优 推导 全局最优。 于是就吓唬乱删一通。 举个例子 11 12 13 35 你能乱删吗 删 13、35 - 你就会得到 11 12 删 12 - 你就会得到 11 13 15 那该怎么做难道是将所有的可能都给枚举出来删一遍 额、包超时的。 这个时候你仔细观察就会发现一个很有趣的现象。 毕竟题目就叫做接龙了。 不论你删谁都跟你的上一个以本首字母为结尾的字母的状态有关。 这不就是 动态规划能推导的前提吗 原顺序 13 35 34 45 56 __34-45 举个列子13- -56 56你接在谁后面 --35 这个时候35经过判断会接在56后边 所以这个时候维护一个dp[0~9]之后dp[i]的含义就是以i为起始位置的串的长度 递归公式 dp[last]max(dp[start]1,dp[last]); */
C版
#include iostream
using namespace std;int main()
{int dp[10]{0};int n; cinn;for(int i0; in; i){string str;cinstr;int i1 str[0]-0;int i2 str[str.size()-1]-0;dp[i2] max(dp[i1]1,dp[i2]);}int maxn0;for(int i0; i10; i) maxnmax(maxn,dp[i]);coutn-maxnendl;return 0;
}Java版
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int[] dp new int[10]; // 初始化动态规划数组int n scanner.nextInt();for (int i 0; i n; i) {String str scanner.next();int i1 str.charAt(0) - 0; // 首字符转数字int i2 str.charAt(str.length() - 1) - 0; // 尾字符转数字// 更新动态规划状态if (dp[i1] 1 dp[i2]) {dp[i2] dp[i1] 1;}}int maxn 0;for (int num : dp) {if (num maxn) {maxn num;}}System.out.println(n - maxn);}
}
6、岛屿个数 问题描述 小蓝得到了一副大小为 M×N 的格子地图可以将其视作一个只包含字符 0代表海水和 1代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。 在岛屿 A 所占据的格子中如果可以从中选出 kk 个不同的格子使得他们的坐标能够组成一个这样的排列(x0,y0),(x1,y1),…,(xk−1,yk−1)其中 (xi1modk,yi1modk)是由 (xi,yi)( 通过上/下/左/右移动一次得来的 (0≤i≤k−1)此时这 k 个格子就构成了一个“环”。如果另一个岛屿 B 所占据的格子全部位于这个“环”内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。 请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。 输入格式 第一行一个整数 T表示有 T 组测试数据。 接下来输入 T 组数据。对于每组数据第一行包含两个用空格分隔的整数 M、N 表示地图大小接下来输入 M 行每行包含 N 个字符字符只可能是 0 或 1。 输出格式 对于每组数据输出一行包含一个整数表示答案。 样例输入 2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111样例输出 1
3样例说明 对于第一组数据包含两个岛屿下面用不同的数字进行了区分 01111
11001
10201
10001
11111岛屿 2 在岛屿 1 的“环”内部所以岛屿 2 是岛屿 1 的子岛屿答案为 1。 对于第二组数据包含三个岛屿下面用不同的数字进行了区分 111111
100001
020301
100001
111111注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿因为岛屿 1 和岛屿 2 中均没有“环”。 评测用例规模与约定 对于 30 的评测用例1≤M,N≤10。 对于 100 的评测用例1≤T≤101≤M,N≤50。 // 注在上网了解一下emplace的作用。 // 搜索一下fill的作用 // 可恶啊预处理数组大小开小了。(┬┬﹏┬┬) // 本题是一道典型的搜索类型题目不论你是用dfs、还是用bfs还是俩个结合着用不论如何这都是非常酷的。 // 我非常确定肯定有些人一上来就直接被(x0,y0) (x1,y1)...(xi1modk,yi1modk) 给整成小迷糊 // 这样会导致失去很多细节 // 仔细审题最好在纸上画出来 // 就像本题、通过 上/下/左/右 移动得来的才算围成环画图时就会发现左上呢右下呢...等等等 /* 作为一道经典的板子题套路题 做这类型的题目一般就是现在外层围一圈海 简而言之就是在最外围多铺垫一层0; 本题最大的左右就是在左上角00的位置首先将所有外海染色 为啥(⊙_⊙)要染色呢因为没有染色的必然有两种情况 1、是岛屿 2、是内海 这时思路就清晰了只要岛屿在内海中他就是子岛屿不用计数但是也要染色方便继续搜索。 */ // 拓展一下就是emplace家族的用法。emplace_back、emplace // 优点是能直接在容器内构建元素避免不必要的拷贝提高性能 // vector用emplace_back(); list、map等可用emplace // 使用方法与insert、push类似。不过是传入构造元素所需参数。所需参数。
C版
#include iostream
#include vector
#include queue
using namespace std;
const int N 1e25;
int T,m,n; // 组 行 列
vectorvectorint arr(N,vectorint(N,0));
struct node{int x; // 行int y; // 列node(int cx,int cy):x(cx),y(cy){}
};
// 一共8个方向
int fa1[]{0,0,1,-1,1,1,-1,-1};
int fa2[]{1,-1,0,0,-1,1,-1,1};
queuenode q;
void bfs(){ // 广搜用于起始时将外海染色这个用深搜不太行因为没法地毯式染色while(!q.empty()){int x q.front().x, y q.front().y;q.pop();if(arr[x][y]!0) continue; // 不是外海水if(x0||xm1||y0||yn1) continue; // 越界arr[x][y]2;for(int i0; i8; i){ // 标准格式应该不是这样的if(xfa1[i]0||xfa1[i]m1||yfa2[i]0||yfa2[i]n1) continue; // 越界q.emplace(xfa1[i], yfa2[i]);}}
}
void dfs(int x, int y){ // 深搜用来将岛屿染色if(arr[x][y]!1) return; // 不是岛屿if(x0||xm1||y0||yn1) return; // 越界arr[x][y]3;for(int i0; i4; i){dfs( xfa1[i], yfa2[i] );}
}
int main()
{cinT;while(T--){for(int i0; iN; i)for(int j0; jN; j) arr[i][j]0;cinmn;for(int i1; im; i){string str;cinstr;for(int j1; jn; j) arr[i][j] str[j-1]-0;}q.emplace(0,0); // 广搜bfs();int sum0;for(int i1; im; i){for(int j1; jn; j){if(arr[i][j]!1||arr[i1][j]!2) continue; // 跳过sum;dfs(i,j); // 将这个岛屿统一染色。染成2}}coutsumendl;}return 0;
}Java版
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static final int N 102;static int T, m, n;static int[][] arr new int[N][N];static int[] fa1 {0, 0, 1, -1, 1, 1, -1, -1};static int[] fa2 {1, -1, 0, 0, -1, 1, -1, 1};static Queuenode q new LinkedList();static class node {int x;int y;node(int cx, int cy) {x cx;y cy;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);T scanner.nextInt();while (T-- 0) {for (int i 0; i N; i) {for (int j 0; j N; j) {arr[i][j] 0;}}m scanner.nextInt();n scanner.nextInt();for (int i 1; i m; i) {String str scanner.next();for (int j 1; j n; j) {arr[i][j] str.charAt(j - 1) - 0;}}q.add(new node(0, 0));bfs();int sum 0;for (int i 1; i m; i) {for (int j 1; j n; j) {if (arr[i][j] ! 1 || arr[i 1][j] ! 2) {continue;}sum;dfs(i, j);}}System.out.println(sum);}scanner.close();}static void bfs() {while (!q.isEmpty()) {int x q.peek().x;int y q.peek().y;q.remove();if (arr[x][y] ! 0) {continue;}if (x 0 || x m 1 || y 0 || y n 1) {continue;}arr[x][y] 2;for (int i 0; i 8; i) {if (x fa1[i] 0 || x fa1[i] m 1 || y fa2[i] 0 || y fa2[i] n 1) {continue;}q.add(new node(x fa1[i], y fa2[i]));}}}static void dfs(int x, int y) {if (arr[x][y] ! 1) {return;}if (x 0 || x m 1 || y 0 || y n 1) {return;}arr[x][y] 3;for (int i 0; i 4; i) {dfs(x fa1[i], y fa2[i]);}}
}
7、子串简写 问题描述 程序猿圈子里正在流行一种很新的简写方法对于一个字符串只保留首尾字符将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18nKubernetes 注意连字符不是字符串的一部分简写成 K8s, Lanqiao 简写成 L5o 等。 在本题中我们规定长度大于等于 K 的字符串都可以采用这种简写方法长度小于 K 的字符串不配使用这种简写。 给定一个字符串 SS 和两个字符 c1 和 c2 请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写 输入格式 第一行包含一个整数 K。 第二行包含一个字符串 S 和两个字符 c1 和 c2。 输出格式 一个整数代表答案。 样例输入 4
abababdb a b样例输出 6样例说明 符合条件的子串如下所示中括号内是该子串 [abab][abab]abdb [ababab][ababab]db [abababdb][abababdb] ab[abab][abab]db ab[ababdb][ababdb] abab[abdb][abdb] 评测用例规模与约定 对于 20 的数据2≤K≤∣S∣≤10000。 对于 100 的数据2≤K≤∣S∣≤5×10^5。S 只包含小写字母。c1 和 c2 都是小写字母。 ∣S∣ 代表字符串 S 的长度。 // 注查看二分解法lower_bound().. // 我看网上很多人都用的是二分解法这让我迷惑不已二分 // 这道题目用前缀和解决他不香吗 /* 其实本题只需要维护一个数组vec[N] N表示截止到这个位置包括这个位置到底有几个字符c1 ---------- abababdb 11223333 - 数字代表该下标之前有几个C1包括自己 ---------- 在遍历第二遍从k-1开始当遇到b时直接arr(下标-k1)求这个位置有几个能匹配成a--b;然后累加。 没喽 */
C版
#include iostream
#include vector#define ll long long
using namespace std;
const ll N 5e55;
int main()
{int k;cink;string str;char c1,c2;cinstr;cinc1c2;vectorll vec(N,0);if(str[0]c1) vec[0];ll sum0;for(int i1; istr.size(); i){if(str[i]c1) vec[i]vec[i-1]1;else vec[i]vec[i-1];}for(int ik-1; istr.size(); i){if(str[i]c2) sumvec[i-(k-1)];}coutsumendl;return 0;
}
Java版
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取间隔长度 kint k scanner.nextInt();// 读取字符串String str scanner.next();// 读取两个字符 c1 和 c2char c1 scanner.next().charAt(0);char c2 scanner.next().charAt(0);scanner.close();long[] vec new long[str.length()];// 初始化前缀和数组的第一个元素if (str.charAt(0) c1) {vec[0] 1;}// 计算前缀和数组for (int i 1; i str.length(); i) {if (str.charAt(i) c1) {vec[i] vec[i - 1] 1;} else {vec[i] vec[i - 1];}}long sum 0;// 遍历字符串统计满足条件的组合数量for (int i k - 1; i str.length(); i) {if (str.charAt(i) c2) {sum vec[i - (k - 1)];}}System.out.println(sum);}
}
8、整数删除 问题描述 给定一个长度为 NN 的整数数列A1,A2,…,AN。你要重复以下操作 K 次 每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除。并把与它相邻的整数加上被删除的数值。 输出 K 次操作后的序列。 输入格式 第一行包含两个整数 N 和 K。 第二行包含 N 个整数A1,A2,A3,…,AN。 输出格式 输出 N−K 个整数中间用一个空格隔开代表 K 次操作后的序列。 样例输入 5 3
1 4 2 8 7样例输出 17 7样例说明 数列变化如下中括号里的数是当次操作中被选择的数 [1] 4 2 8 7 5 [2] 8 7 [7] 10 7 17 7 评测用例规模与约定 对于 20 的数据1≤KN≤10000。 对于 100 的数据1≤KN≤5×10^50≤Ai≤10^8。 // 悠悠的叹息声为何先敬罗衣后敬魂 // 说实话本题一看我就知道本题跟优先队列有关但是有一件挺无奈的事情是他要不停的删除东西... // 众多周知priority_queue内部就是一个黑盒(会用就行-其实内部是堆heap) // 所以本题的难度就是如何将priority_queue内部的东西边用边删除 // 当然这里面也有一个非常重要的细节priority_queue重载的时候要分情况重载因为这是一个有序数组。 /* 其实也不难的有人说用并查集其实链表就能解决 只能说这道题你知道大概解法你就能做不知道你肯定不会 本题需要维护一个 双向链表可不是标准链表是用两个数组模拟一个链表pre[N],ne[N]; 然后在维护一个数组(sum[i])去记录那些值改变了 切记设置链表的时候最开始位置从1开始。方便 减1 or 加1 假设删掉下标为cur的值(num)的时候 pre[ne[y]]pre[y]; ne[pre[y]]ne[y]; 切记不是不是sum[cur-1]num,sum[cur1]num;导致链接错误 既然删掉该值了呐本坐标也就不再存在了所以接下来 要改变坐标。 这时你要将cur储存的 下一位的坐标--传给左边 将cur储存的上一个位置---传递给右边 ------------ pre 0 1 2 3 val 1 2 3 4 ne 2 3 4 5 ------------ 删掉val值2之后,1和3的pri与ne都回改变 ------------ pre 0 1 1 3 val 1 2 3 4 ne 3 3 4 5 ------------ OK了其他的想必大家就清楚了 切接priority_queue默认大堆顶 */
C版
#include iostream
#include vector
#include queue
#define ll long long
const ll N 1e65;
ll n,k;
using namespace std;
vectorll pre(N, 0);
vectorll ne(N, 0);
vectorll sum(N,0);
vectorll a(N,0);
// 重载
struct cmp{ // bool operator() (const pairll,ll p1, const pairll,ll p2){if(p1.first p2.first) return p1.second p2.second; // 值相同选下标小的return p1.first p2.first; }
};int main() // 天呐这些都是什么东西 ·
{cinnk;priority_queuepairll,ll,vectorpairll,ll,cmp p;ne[0]1;for(int i1; in; i){ll val;cinval;p.emplace(val,i);//pre[i]i-1;ne[i] i1;}while(k--){ // 进行k次操作ll val p.top().first;ll y p.top().second;while(sum[y]){val sum[y];p.pop();p.emplace(val,y);sum[y]0;// 更新val p.top().first;y p.top().second;}// 链表更新错误sum[pre[y]]val;sum[ne[y]]val;// 更新pre[ne[y]]pre[y];ne[pre[y]]ne[y];p.pop();}// 提取出来while(!p.empty()){a[p.top().second]p.top().first;p.pop();}for(int i1; in; i)if(a[i]sum[i]) couta[i]sum[i] ;return 0;
}Java版
import java.util.PriorityQueue;
import java.util.Scanner;// 自定义比较器用于优先队列
class PairComparator implements java.util.ComparatorPair {Overridepublic int compare(Pair p1, Pair p2) {if (p1.val p2.val) {return Long.compare(p1.index, p2.index);}return Long.compare(p1.val, p2.val);}
}// 定义 Pair 类用于存储值和索引
class Pair {long val;long index;Pair(long val, long index) {this.val val;this.index index;}
}public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);long n scanner.nextLong();long k scanner.nextLong();long[] pre new long[(int) (n 2)];long[] ne new long[(int) (n 2)];long[] sum new long[(int) (n 2)];long[] a new long[(int) (n 2)];// 优先队列使用自定义比较器PriorityQueuePair p new PriorityQueue(new PairComparator());ne[0] 1;for (int i 1; i n; i) {long val scanner.nextLong();p.offer(new Pair(val, i));pre[i] i - 1;ne[i] i 1;}// 进行 k 次操作for (long i 0; i k; i) {Pair top p.poll();long val top.val;long y top.index;while (sum[(int) y] ! 0) {val sum[(int) y];sum[(int) y] 0;p.offer(new Pair(val, y));top p.poll();val top.val;y top.index;}sum[(int) pre[(int) y]] val;sum[(int) ne[(int) y]] val;pre[(int) ne[(int) y]] pre[(int) y];ne[(int) pre[(int) y]] ne[(int) y];}// 提取优先队列中的元素while (!p.isEmpty()) {Pair pair p.poll();a[(int) pair.index] pair.val;}// 输出结果boolean first true;for (int i 1; i n; i) {if (a[i] sum[i] ! 0) {if (!first) {System.out.print( );}System.out.print(a[i] sum[i]);first false;}}System.out.println();scanner.close();}
}
后面的两道题咱时间有限就先跳过啦(▽)
要学会做减法。
当然大家有好的代码、解析也可以发给我让我瞅瞅。( •̀ ω •́ )✧我贴上去。
知识点
1、二分查找
二分查找主要位于algorithmn头文件中。常用的有lower_bound、upper_bound、binary_bound
lower_bound
查找第一个大于等于lower_bound的元素
auto it lower_bound(vec.begin(),vec.end(),num);
int place it-vec.begin();
upper_bound
查找最后一个大于lower_bound的元素
auto it upper_bound(vec.begin(),vec.end(),num);
int place it-vec.begin();
cout*it(it-vec.begin())endl; // 两者皆可
binary_bound
判断目标值是否存在
bool t binary_bound(vec.begin(),vec.end(),num);
set中也设置了lower_bound(); setint s;
...
auto it s.lower_bound(11);
2、emplace
C中emplace是 C11引入的用于在容器中构建元素避免复制/移动操作提高效率。
基本用法
container.emplace(args...);
与push的区别
push: 先构造对象可能会传递。 emplace传参、直接构造。 具体用法的话就是原本push怎么用emplace就代替成push。 如push_back--emplace_back push--emplace
std::vectorstd::pairint, int vec;
// 传统 push_back
vec.push_back(std::make_pair(1, 2));
vec.push_back({3, 4}); // C11后可简化// 使用 emplace_back
vec.emplace_back(5, 6); // 直接构造 pair更高效
适用容器 支持 emplace 的容器 序列容器vector、deque、list关联容器map、set、unordered_map、unordered_set适配器priority_queue底层容器支持即可 不支持 emplace 的容器 queue、stack 等适配器接口限制。
3、log() ::cmath::
在 C 里log() 函数一般是指 cmath 头文件里用于进行对数运算的函数。下面会详细介绍 log() 函数的具体用法。
log() 函数原型
cmath 头文件里定义了几个不同版本的 log() 函数常用的有
// 计算自然对数以 e 为底
double log(double x);
float log(float x);
long double log(long double x);这些函数接收一个浮点数参数 x并返回 x 的自然对数以自然常数 e 为底。
以其他底数计算 其他对数函数
除了 log() 函数cmath 头文件还提供了其他对数相关的函数C11及之后适用
