龟速AK，%%% 7_dp_[0][0]_3，%%% 🐱‍🚀 两位神仙 T1 显然地，我们知道了 i,j,k,z,ni,j,k,z,ni,j,k,z,n 之后，可以求出 ppp，所以只需要一个四重循环。 Code: T2 看到质数有关的，先打一个欧拉筛上去。时间复杂度：O(n)O(n)O(n). 这样我们得到了所有不超过 nnn 的质数。数位分离一下，计算和并取模即可。 Code: T3 （显然的）kkk 是 A,BA,BA,B 的公约数。 所以我们枚举 gcd⁡(A,B)\gcd(A,B)gcd(A,B) 的所有约数就好了。 注意只枚举到 gcd⁡(A,B)\sqrt{\gcd(A,B)}gcd(A,B) 即可。因为约数成对出现。 特判完全平方数的情况。 Code: T4 枚举垂足点 iii。 如果我们知道另一个点 jjj，那么我们可以知道构成直角三角形的点 kkk 在某条直线上。 所以我们对于每一个 jjj，记录一下它的向量如何表示。 然后统计 kkk 的数量。 由于三角形算了两遍，记得除以 222。 Code: T5 首先我们对于每一个位置记录四方向是否可达。 我们知道，如果 {i,j) 可达 (k,l)(k,l)(k,l)，并且 (k,l)(k,l)(k,l) 可达 (i,j)(i,j)(i,j)，那么我们才能从这里走过去。（观察样例解释可以得到） 这就很好写了。 Code: T6 普通的 DP 很容易想出来，刷表法就行了。 优化：注意到每一次跳跃的距离永远在 [d−400,d+400][d-400,d+400][d−400,d+400] 之间，所以优化成 O(800N)O(800N)O(800N) 能过了。 为什么？ 我不知道啊，感觉是一个神秘的东西。 Code:

这谁设计的题目？？？

#include<iostream> using namespace std; int main(){ int n; cin>>n; for(int i=n;i>0;i--){ for(int x=0;x<n-i;x++){ cout<<' '; } for(int y=i2-1;y>0;y--){ cout<<''; } cout<<endl; } return 0; }

食用说明:较为简洁,只是做一个思路清理,(可能会出错),弥补短板,不是教程,也不会放一些梗或者扯皮什么的 总体基于老师发的深搜问题模型总结,只是在其上进行一个自己的理解,再将其与BFS进行比较 正文: 一.DFS的使用 1.01: 好像没有做过太多这种类型题目的变种? 做到过唯一的两种考察形态就是: 第一种:去一个什么地儿,然后买东西或者走路,有几个商店或者几条路 去或不去,买或不买,换汤不换药 第二种:去倒水或什么饮料,然后有到或不到两种,这种类型会在上面施加一些条件,要多加几个判断 然后唯一没有识别出来的是:考前临时抱佛脚,分为两个大脑,然后去枚举一个题放在左脑思考还是放在右脑思考 2.全排列 这个考察的好像会比01多一点... 基础的考察就是在DFS笔记那一篇里提到的抽奖,然后再难一点就是组合的输出,选数 这也是作者最不擅长的提醒之一(突然想起来好像要再多练一下这个题型) *八皇后是属于全排列吗? 3.搜索 这个...好像不太难,应该也可以用BFS做的... 可能是多源的...有一题记得比较清楚的是观星,但是好像是用BFS做的... *有一些比较特殊的,比如:求最大的最小值或者最小的最大值等 二.BFS的使用 BFS好像更容易理解吧...一般用于最短路 比较需要注意的是一些关键词,比如"最短""最少"之类的: 一般就是走迷宫,换密码之类的题目吧... 然后是好心人的友情提醒: 大概就是看数据范围,然后迅速判断.如果说类似于10~30的数据范围,可以先试一下DFS. 886,去试一下新学的方案喽... 我回来了.... 看得出来AC狗很激动...但是它先别激动.... 这样一想的话,好像DFS和BFS的差别还是比较大的. 放在一起学可能只是因为思路有一点相同:一个是按深度,一个是按广度. 搜易都有FS(First Search)

c++入门同学看过来 * 代码框架 常见头文件 * 常见数据类型 类型 范围（参数） bool true&false char 所有存在于ascii码表中的字符 int -2147483648 到 2147483647‌ long long -9223372036854775808 到 9223372036854775807 string 字符串 -->一定要导入头文件（<string>） double 双精度浮点数 float 单精度浮点数 short -32768 到 32767 auto 自动推断变量类型 void 无类型（无返回值） struct 结构体 * 输入输出 1:cin/cout 2:scanf/printf（确保已经引入<stdio.h>/<bits/stdc++.h>的头文件） 实例代码（实现输入n，输出n） —————————————————————————————————— 素材来源于网络及个人学习所得，侵权请联系删除 如果大家有更好的意见，尽管提！我会听！

#include<bits/stdc++.h> using namespace std; int main(){ }

1+1=2，2+2=？ 全网求解答

来来来，2025年3月GESP测评火热结束了 以下是二级的一道编程题： 题目条件 如果就现在是y年m月d天h小时，过k个小时后，就是y'年m'月d'天h'小时. 输入格式 第一行输入y,第二行输入m，第三行输入d，第四行输入h，第五行输入k 输出格式 一行内输出y',m',d',h',每个数字中间要有空格 样例组 输入1 2008 2 28 23 1 输出1 2008 2 29 0

你也玩塞尔达传说？？？

注意不是long long而是long

这是黄题？？？？？？？？

今天做gesp的真题，但为什么给的答案和运行结果不一样？

先报下个人难度：红 红 红 红 红/橙 红 本人未接触算法，如有错误望大神指出！本人会迅速改正！这次的欢乐赛真水 T1: 只需要简单的分支结构判断即可 时间复杂度:O(1)O(1)O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2： 本题先读取数组长度，在读取需要交换的元素索引，注意，下标是从一开始的，所以我们也从1开始： 时间复杂度:O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3： 本题需要在左上角、右上角、左下角、右下角的位置跳过，假设二维数组的行和列为a，下标从1开始，那么只需要在（1，a） (a，a) (1，1) （a，1）的位置跳过即可。剩下的位置我们用num变量相加。最后输出。 时间复杂度:O(n2)O(n^2)O(n2) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4: 本题可以先创建一个函数来分解数位，可以用while逐个拆解并相加,或者转换成字符串，之后用for相加，再减去'0'。最后在主函数里判断即可： 时间复杂度:O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5: 通过题面我们不难看出，整个字符串只会出现一次M，所以子串的个数就是M左边的K的数量乘以M右边的P的数量： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6: 本题由于数据量不大，所以暴力完全可以（要注意的是小于n，不是小于等于）： 时间复杂度为O(tnn)O(tn\sqrt n)O(tnn ) 本人第一次写题解，如有错误请指出，谢谢

1.基本框架 (1)头文件：#include<bits/stdc++.h>//万能头,可以只写这个 (2)命名空间 (3)主函数:有且只有一个 2.数据类型 2.1整型(integer) (1)int:整型 范围:-21亿~21亿 -2^31 ~ 2^31-1 (2)long long:长长整型 范围:-10^18 ~ 10^18 左右 2.2浮点型 (1)float:单精度浮点型(基本不用) (2)double: 双精度浮点型(小数就用这个) 2.3字符型 (1)char:定义单个字符 字符:字母、数字、符号等用 单引号 包起来的 单个符号 (2)ASCII码 'A'=65 'a'=97 '0'=48 ' '=32 //输出为'A' 2.4 字符串类型 string s; (1) 头文件 #include<string> (2) 计算长度 s.size(); s.length(); (3)输入字符串 a)cin>>s;(不带空格) b)getline(cin,s);(带空格) (4)比较大小:字典序(从大到小) 比较方式:按位一个个比较过去,直到第一个不相同,谁大就谁大 "123" < "2" "121" > "12" 3.输入输出 3.1 输入 (1)单个变量或者字符串: cin >> 变量名; (2)数组:循环输入 3.2输出 (1) cout<<endl; (2) printf:格式化输出 a) 小数:printf("%.2f",变量名); 保留两位小数 b) 右对齐-空格:printf("%5d",123); c) 右对齐-补0:printf("%05d",123); 4.条件分支语句 (1)单分支语句:如果条件成立,执行语句 if(条件){ 语句; } (2)双分支语句:如果条件成立,执行语句1;否则语句2 if(条件){ 语句1; } else{ 语句2; } (3)三目运算符:条件?语句1:语句2 如果条件成立,执行语句1;否则语句2 例如: (4)多分支语句 if(){ }else if(){ }else if(){ }else{ } 5.循环 (1)for循环 for(初始值;条件;变化量){ 循环体； ; } 初始值 -> 条件 -> 循环体 -> 变化量 -> … (2)while循环 while(条件){ 循环语句; } (3)do-while:相比while循环,如果条件不成立,至少执行一次 6.数组 (1)定义:变量类型 数组名[数组空间]; //数组空间=n的最大值+5~10 (2)遍历范围:0~n-1 或者 1-n => 注意循环范围 7.数位分离 (1)分离各位与求和 8. 函数(巨烦的啊啊啊！！！) (1)函数声明 - 省略 (2)函数定义 函数类型 函数名(变量类型 变量1,变量类型 变量名2,…){ 函数内容; } 函数类型 - 返回(int/double/string…) 无返回(void) (3)函数调用 函数名(变量名1,变量名2,…) => 注意:类型需要一一对应 9. sort (1)头文件:algorithm (2)模板:sort(数组名+开始下标,数组名+结束下标+1,排序方式) (3)升序:从小到大 sort(a,a+n); (4)降序:从大到小 10. 结构体 struct 结构体类型名{ 变量类型 变量名1; 变量类型 变量名2; 变量类型 变量名3; }结构体类型 结构体变量名; 例如: //等同于 student a[105],b,c => 类似于 int a[105],b,c; 11. 结构体排序 /* 题目：学生有语文、数学、英语成绩，总分，输入顺序是学号 (1)根据成绩从小到大 (2)如果成绩相同，语文成绩从大到小 (3)如果语文成绩从小到大 */

一、枚举优化 > 继续优化掉一层循环，利用已知的公式进行推倒计算。 参考程序 二、时间复杂度 > 表示程序的运行效率。用来衡量一个算法程序完成任务的时间长短。 三、一维前缀和 实例： 买书问题 > 前缀和（数组）：包含当前元素之前的所有数字之和 前缀和优化版本参考程序，时间复杂度为 O(N) 四、作业练习 完成ACGO欢乐赛#43中的任意3道题， 注意，比赛结束也可以继续提交的哦~

一、多分支结构 > 多种情况的分支，如果进入了某一个分支，其他的分支都不会执行。 > 注意最后的 else 是所有情况都不满足的时候才会进入执行。 实例：分数等级 二、SWITCH语句 1、switch语句的格式： 2、如果没有break > break 的作用是打破，这里是跳出switch语句 三、字符类型&字符串 > 字符（char）： 单引号，'a', '6', 'A', '#', '!', 'wo', '我' > 字符串(string): 双引号，多个字符串到一起 "I love C++" 实例：字符判断 四、逻辑运算符（简单了解，下节课还会说） 五、作业提示 仔细阅读题目，需要注意的是题目描述的是超过的部分按照规定的价格进行计算。比如按照题目的描述，用电20度，则实际收费为两个部分： 思考：如果输入的用电量是40，那么最终的费用分为3个部分，可以想想是哪3个部分？ 最后需要注意题目要求的输出需要保留小数点后两位。

虽然本题解所讲述的不是最优解，但是能过 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 数据范围 1≤T≤100 1≤a,b≤1000 可以考虑直接暴力，使用O(t*min(a,b))的时间复杂度来过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 已知4！=1* 2 * 3 * 4 = 24 已知num!=num*(num-1)! 所以只要x>=4,则x!包含4，即x是24的倍数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 这真的不应该是第一题吗？ 第三题肥肠简单，直接输出 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 如果我没记错的话 科普小知识：有一个函数叫做"next_permutation" 作用：搞出下一个排列 返回值:能否生成下一个更大的排列 时间复杂度：O(n) (n:数组的长度） 食用用方法：和sort一样。例：next_permutation(v.begin(),v.end()); 如果运运用这个函数，则时间复杂度为O(nm)，可以通过（当n=10时，max(m)=3628800) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 个人感觉这道题比第六题难 ”小王的任务是找到一个最大的数 y“ 能量值相同时，y的位数越多，则y越大（无前导零） 如何使y变大呢？ 例：x=6,能量值=6！ 6！=5！*6=5！*3！ 所以y=6或53 当然选53啦~ 根据观察，5、7只能等于5！、7！,但其它数字都可以改变。 以下是每个数字的最优解： 1：1 2：2 3：3 4：22 5：5 6：53 7：7 8：7222 9：7332 作者代码有点丑QAQ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 ”可以自由地将这个数组进行重新排列，并依照重新排列后的顺序逐个取出数组中的元素。小王可以选择任何一个元素作为开始。而之后，每次取出的元素如果比上一次取出的元素大，作为奖励，小明就会获得一束精美的玫瑰花，取第一个元素的时候，没有花“ 则可以将原来的数组分为几个数组。 怎样使玫瑰花数量最多呢？ 当数组为升序时，玫瑰花数量最多。 但是——排序之后，可能会出现l[i]==l[i+1]的现象。 所以我们可以将原来的单调不减数组弄成几个升序数组，这样就可以使玫瑰花的数量最多了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 太好了，终于写完了！

挑战赛#15 全题解 前记 太爽了极限 AK。 这里着重会讲万恶的 T5。 正式部分 T1 T1 小特想散步 很简单的一道题啊，字符串输入判断即可。 T2 T2 老猞狸的问题 同样很简单的题，每次遇到不同的贪心性交换后一位，如果不行直接 No，同时统计次数，次数 >1>1>1 时也要 No。 T3 T3 源石虫比赛 这能有黄？ 看到数据范围 1≤n≤1041 \le n \le 10^41≤n≤104，直接 O(n2)\mathcal O(n^2)O(n2) 自信过了。 理论上也可以加一个排序和二分，有人有时间打吧。 贪心性很明显，每次选择最小的比两接力位置之差大于或等于的原石虫就可以了。 注意一下它的输出结构。 T4 T4 简单集合之和 总算有点难度的题，不过数据范围 1≤n≤351 \le n \le 351≤n≤35，显然 2352^{35}235 的爆搜会 TLE，同时用背包的话 ai≤109a_i \le 10^9ai ≤109 也得凉。 其实不难让人想到是 折半搜索（meet in the middle） 算法。 该算法主要思路是： 1. 将 nnn 范围的数分成两半； 2. 将两半数 dfs，用两个数组统计其中的答案，两个数组的大小就是 2n2=2182^{\frac{n}{2}} = 2^{18}22n =218 是可以实现的; 3. 将其中一个数组排序（我这里选 ans2ans2ans2），然后遍历另一个数组进行 二分操作（这个后面讲）; 4. 最后统计一下答案就可以了。 对于这道题来讲，由于我们搜出来的答案对 xxx 取模，所以 0≤ansi<x0 \le ans_i < x0≤ansi <x。 同时不难证明，我们我们每次遍历的数 ans1i+ans2jans1_i + ans2_jans1i +ans2j 小于 xxx 的情况一定比大于等于 xxx 的情况模 xxx 要更大，所以二分操作就是选出令 ans1i+ans2j<xans1_i+ans2_j<xans1i +ans2j <x 中最大的 ans2jans2_jans2j ，注意可以重复选，也可以不选（ans20=0ans2_0=0ans20 =0）。 但注意 ans1ans1ans1 也可以不选。 最后时间复杂度是 O(2n2log⁡2n2)\mathcal O( 2^{\frac{n}{2}} \log 2^{\frac{n}{2}})O(22n log22n )，可以通过本题。 T5 T5 聪明图 万万差点没想到原来是线段树。 首先没看到 “保证每次操作后都会满足对于 i<ni<ni<n 存在从 iii 连向 i+1i+1i+1 的边” 的出来罚站，没救了。 那么既然有这个条件，那就说明对于任何 (i,j)∣i<j(i,j) |i<j(i,j)∣i<j，一定能从 iii 到 jjj。 问题到这已经非常线性了。 那么我们要做的就只有维护每个数能到的编号最小的数了，这里我用了一个 map 来记录维护，本质是红黑树，能在稳定 O(nlog⁡n)\mathcal O(n \log n)O(nlogn) 来维护。 那么对于每次加边删边，只有 x<yx<yx<y 的时候要改变，同时发现操作改变了的时候要修改到线段树。 接下来说一下查询，可以知道 xxx 号节点一定能到任何 ≥x\ge x≥x 的节点，所以我们只要知道我们能到的编号最小的节点就行了。第一次只用查询区间 [x,n][x,n][x,n] 中能到的编号最小的数最小值。区间？正好就是线段树的工作（你用树状数组或者 ST 表可能也行）。但是要知道不仅如此，设第一次答案为 ansansans，则它到了这个节点之后还能到区间 [ans,x−1][ans,x-1][ans,x−1]，以此类推，可以到 [ansi,ansi−1−1][ans_i,ans_{i-1}-1][ansi ,ansi−1 −1]，终止条件就是 ansi+1=ansians_{i+1}=ans_iansi+1 =ansi ，这时候能到 [ans,n][ans,n][ans,n] 的任一节点，所以答案就是 n−ansi+1n-ans_i+1n−ansi +1。 补充： 其实这样写有可能会被卡到 O(nq)\mathcal O(nq)O(nq) 的，出题人好心没卡。如果谁有时间可以试试做个记忆化，每次查询后 [ansi,x][ans_i,x][ansi ,x] 的区间可以记忆化，然后在真实修改了某一个数的能到的编号最小的数就覆盖掉。 T6 T6 串串 很明显，前缀长度增大时，答案单调不增，所以二分就可以。 但模式串字符串匹配，那就是 KMP 了，不多讲。 我之前想过 AC 自动机的，不过因为比较聪明不会拓扑建图，所以就算了。 总结 这次挑战赛出的还不错。