在C++中，我们为了完善程序功能和阅读程序方便会开很多变量或函数等的名称。看看下面列举的名称你开过那些？ > 1、n > > > n一般是用于多组数据输入时的组数，最常见的是一维数组中确定长度的时候大多都用变量n。 > > 2、t和n > > > 正如我们在ACGO欢乐赛、排位赛、挑战赛中所见一样，有时候竞赛题目中会有多组数据，一共有t组，每组又有n个小组数据。 > > 3、n和m > > > 还记得二维数组深度一般是n，宽度一般是m，形式如array[n][m]的二维数组在迷宫题目中很常见。 > > 4、st > > > 在使用集合时，我们常常会把集合set缩写为st作为集合名称，这很常见，只可惜ACGO还没有发布集合的题目。 > > 5、v或vec或ve或vect > > > 在使用动态数组（又称向量）vector的时候，我们也会把它缩写为v或vec作为变量名，当然ve、vect等都可以。但是用到vector的题目较少，一些vector用到时都可以用数组 > > 6、s，t，v > > > 小学的时候，路程=速度*时间的公式就耳熟能详了，那么，在换成字母时，我们常常把路程写成s，速度写成v，时间写成t。 > > 7、a或arr > > > 数组（array）是编程中一个重要的工具，可以存储一连串相同类型的数据。而很多时候我们会把数组名写为array缩写arr，甚至更简单的是a来代替。当然，有的人在用了arr后，喜欢往后延续写作brr、crr、……。 > > 8、bucket或b > > > 说到数组，不由得会想到桶排序时我们用到的桶数组，大多人会根据它的英文名叫它：bucket。当然，你也可以取它的首字母b作为数组名称。 > > 9、stk > > > 栈是一个LIFO的容器（Last In First Out），它可以帮助我们解决一些生活中的问题，比如火车进出站时总是先进来的在里面，后进来的在外面，导致后进先出。栈英文名叫做stack，许多人喜欢缩写为stk来作为变量名。 > > 10、q > > > 队列是一个FIFO的容器（First In First Out），它也可以解决生活中的一些问题，比如排队人们自觉排在队尾（当然一些插队狂和VIP除外）。队列queue读音非常像字母Q的发音，所以大家都喜欢取它首字母q作为变量名。 > > 11、mp或者MAP或者mapp或者ma或者…… > > > map有两个含义：一个是C++或Python中的字典（实际上Python中叫做dict或者dictionary），另一个是深搜/广搜中的地图。在作为变量名时，为了不和容器map搞混，常常会省略中间的a或者开大写或者double p或者省略p或者……………………。 > > 12、vis > > > 学到搜索时你会知道：标记数组是个好用的东西。标记数组在搜索时，常被命名为vis，当然也有人喜欢叫他vid或者b等其他名字。 > > 13、p > > > 都知道map是由键值对构成的，那么它每项就是一对一对的。在C++ 中，有个容器叫做pair，常常被简写为p作为变量名。当然，C++中开p的名称，除了pair还有可能是指针变量的名称，指针英文叫做pointer，因此一般把指针变量名称取名为英文名称的首字母p。 > > 14、dp > > > dp是动态规划英文的缩写，因此我们也常常把它作为动态规划数组的名称。当然，也不是不可以作为递推的数组名称。 > > 15、dq > > > 双端队列deque虽然叫做队列，但是实际上它不是线性表。因为名字读起来像DQ，所以常常开变量名叫做dq。如果p和q容易搞混的话，那么dp和dq就更容易分不清了。 > > 16、str或s > > > string字符串是一个比较神奇的东西，它是C++才加进来的面向对象的概念，在C语言中它是char类型数组。string类型在Python中叫做str，所以会有人把它叫做str。本人而言，s是优选，因为s不光可以表示字符串，还可以用作变量、数组、集合、递推数组、甚至于dp数组的名字上，个人觉得还是“万能”的。 > > 17、node和tree > > > 如果学到了树就知道，树很少用链表或者一般用数组。当开了结构体来表示树的节点时，node是树的一个节点类型名称，而tree一般是数组的名称。 > > 18、x和y > > > 在二维数组中，需要用array[i][j]表示二维数组中的一个元素，到了搜索时常常用x和y表示一个节点的位置，和平面直角坐标系类似。唯一不同的是，它和平面直角坐标系是相反的。 > > 19、c或ch > > > 众所周知，有个数据类型叫做char，字符变量一般取char首字母c或者前缀ch来表示。当然，对于特定情况而言，你也可以把c作为计数变量的名称，一是因为c是count的缩写，二是因为当自增时写为c++十分“有趣” > > 20、cnt > > > 前面提到了count，而一般情况下我们是把计数变量开为cnt而不是c，或者不导入<algorithm>库时用count直接表示也可以。当你导入algorithm库是千万不能开count，因为algorithm库中有个函数名称叫做count。 > > 21、ans或answer > > > 二分答案中，我们会得到一个最终通过二分得到的答案，而这个答案一般用ans保存。事实上，计算结果、统计结果等都可以用answer或者其缩写形式——ans来表示。 > > 22、f或flag > > > 相信大家都开过标志变量，就是类型为bool的01状态的那种变量。标志变量就相当于一面小旗子，提醒我们是否完成了某件事或达到某个程度或目标，所以用flag，简写为f > > 23、lst > > > 学到链表后就会知道，万能头中包含了一个库叫做list，其实就是链表。Python中列表叫做list，所以Python中列表变量名叫做lst，C++中也适用。 > > 24、sum > > > 为什么我喜欢用s来代替一些变量和数组？sum是一个好的例子。sum用作变量时可以存放一个数组中[l,r]区间的元素和，用作数组时是前缀和数组，实际上是一个数组的预处理。当然，在sum用作变量的时候，也可以作为累加器，累加一个容器（如数组，也可以是不断的输入）中所有数值的和，非常好用。 > > 25、d > > > d实际上是difference的缩写，d一般用于差或者差分数组的名称，十分好用，在差分时会避免模拟带来的TLE。 > > 26、i，j，k，…… > > > 只要学到for循环就会用一个代码框架：for(int i=0;i<n;i++)。在这之中，i是一个int类型的变量，它只能在for循环内使用，也叫局部变量、临时变量。临时变量其实可以随意开，i、j、k等等都行，这也是最常见的局部变量。 > > 27、dfs和bfs > > > 这两个函数名分别代表了深搜和广搜。深搜（深度优先搜索Depth First Search）和广搜（又称宽搜，广度/宽度优先搜索）是搜索好帮手，迷宫问题的克星。深搜运用递归写，属于不开函数不行的那种；广搜也可以不开函数，在主函数中用结构体队列完成。 > > 28、is_prime(prime)和is_pal(pal) > > > 事实上，官方AC君已经在题目中给过我们这两个函数了，is_prime判断是否为质数，is_pal判断是否为回文数。证据确凿，这道题就有。 > > 29、cmp > > > 在结构体数组排序时，如果你不想手写一个冒泡/选择/插入/……时，你可以用algorithm库中的sort函数配上你的cmp（compare）函数来排序。 > > 30、l或left，r或right，m或mid或middle > > > 这是二分查找和二分答案常常用到的变量名，确定好下限l和上限r后，进行中间mid检测，然后重定范围进行折半查找数值或答案。 > > 31、st > > > 根据ACGO用户评论，C++中有一个容器叫做st表，它一般也可以用st表示，所以当你用到集合和st表时，最好集合用s或set1等，把st留给st表吧。 > > 32、tag > > > 根据用户评论：线段树必带 dat/val，线段树存值的地方。 > > 33、check > > > 确实，虽然我没有开过check，但是确实看到很多用户喜欢在搜索中判断是否越界用check函数，十分的好用，免得到时候if里边一长串看得头晕。 > > 34、mx或ma或maxn，mn或mi或minn > > > 这些是为了防止和iostream头文件里自带的函数max和min重名，自己开的最大最小值的变量名。当然，数组中也可以用algorithm库中的max_element和min_element函数求最大最小值。 > > 35、n，m，k > > > 打过欢乐赛的用户都知道，ACGO官方喜欢在题目中提到n、m、k三个变量名，ACGO用户评论：这是编程数量变量名的三巨头。 > > 36、n1，n2，n3，a，b，c，etc. > > > 这些是用户常常为了偷懒做的一些事情：在一个字母后面加上数字变成不同变量名，或者直接从a开始一个个字母往下用。萌新为了节省时间可以用，但：一定要搞清楚每个变量的含义！ > > 37、cost和dis和val > > > 根据ACGO用户评论：这几个名称有时候也会开，是为了记忆化搜索，但是相对其他而言比较冷门。当然，你也可以用这个写图论。 > > 38、f或fun或func > > > 这些都是函数英文function的缩写，一般而言，如果练习或者随便定义的函数，或许会用到这些名字。 > > 39、start_x或sx，start_y或sy，end_x或ex，end_y或ey > > > 这些变量最大作用是在于搜索时告诉你开始位置字符为Z结束位置字符为W这种类似的情况，我们可以对字符进行判断，并把坐标存储在这四个变量中。当然，也不排除只要sx和sy或只要ex和ey或什么也不要的情况。 > > 40、sort之类的函数 > > > 说到排序，一定会想到这些：冒泡排序Bubble_Sort()，选择排序Selection_Sort()，插入排序Insertion_Sort()，桶排序Bucket_Sort()，快速排序Quick_sort()或者qsort()等方法，以及<algorithm>库中的sort()函数。其实，一般写排序函数的时候就会写一个sort()在不导入algorithm库的情况下，当然也可以写全称；但是在写快排的时候，我们一般写成qsort()。这些都是比较容易理解的排序方法。 > > 41、find() > > > find()函数存在于<algorithm>库中，一般适用于数组、向量、集合（当然集合自带一个二分的find，效率更高）等数据类型中。自己写find主要是 “并查集” 中查找朋友（或者形象地说应该叫老大）或者亲戚的时候会手搓一个递归写的find()函数。对于合并，一般自己定名字，个人建议带有union（集合的并集叫做set_union()）但不要写为union（因为union是关键字）。 > > 42、大写N或者MAXN等 > > > 之所以不写成int s[10005]是因为可能还有其他的数组要开这样大小，到时候直接写成int s1[N]会比int s1[10005]方便许多。常量N会帮我们简化代码量（个人觉得有点像数学中的换元法）。 > > 43、fin，fout > > > 当我们使用fstream头文件完成文件输入输出时，我们会定义两行代码：ifstream fin("file.in")和ofstream fout("file.out")。这之中，使用了文件输入输出流，可以使我们用fin>>a和fout<<a这样的代码完成文件输入输出。其中，我们定义的是fin和fout，当不导入iostream的时候，也可以改写为ifstream cin("file.in")和ofstream cout("file.out")，此时定义的名称为cin何cout。 > > 44、ll > > > 在C++中，你或许见过这样的代码： > > > > 或者是这样的： > > > > 还可能是这样的： > > > > 这样其实是把long long类型简写为了ll，只是为了打代码更方便，你再次使用long long也可以。 > > 45、pre，now，next > > > 根据ACGO用户反馈：pre，now，next三大时态家族，都是dfs，bfs，A*，IDA*，链表，启发式，模拟的神。 > > 46、p（另外的用法） > > > 据ACGO用户评论：当用到p的时候，一般是图论、几叉树（eg：如二叉树、三叉树、……），还可以是究极大模拟！ > > 47、tmp或temp或t > > > 这是临时变量tmp、temp、t，常用的地方如交换两个变量的值和手搓的gcd()最大公因数函数中。 > > 48、gcd，lcm > > > gcd(Greatest common divisor)是最大公因数的缩写，常常用while循环或者递归完成函数定义。lcm(Least common multiple)是最小公倍数的缩写，定义函数时一般是先求出乘积，再除以gcd的返回值得到的。 > > 49、dir(s) > > > 玩过dfs和bfs的用户都知道，如果一个一个方向自己手打的话来搜索太累了。于是，我们可以使用方向数组dir。以迷宫为例，往上下左右移动一步就是dir[4][2]={1,0,0,1,-1,0,0,-1}；针对马走日或马的遍历，有dir[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1}；对于八个方向的走法，如数水坑或水洼计数，方向数组因变为dir[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1}。当然，在作为数组名时，dir(direction缩写)会包含多个方向，所以可以在后边加上s。 > > 50、mod或Mod或MOD > > > 一些题目因为最终数据结果Ti大了，所以会要求结果对一个数取余，这个数一般会写成这样的形式： > > > > 这样，我们最后结果就可以直接写成： > > > > 这样的形式，看上去比较简洁，尤其是在要多个地方取余时很实用。 > > 51、h、e、w、ne > > > 据ACGO用户评论：这四个变量也很常见，主要在链式前向星上一起使用 > > 52、f（或l、r等其它等价用法） > > > 在广度优先搜索时，我们会需要取队列的首元素，这个时候，我们经常把存放首元素的变量开为f（front的首字母），也有时候用其它的名字。 > > 53、x和xx和nx，y和yy和ny > > > 在搜索算法中，对于迷宫类型题目，我们常常需要坐标(x,y)来表示搜索到的位置，在dfs()函数中一般会传参数： > > > > 这时x和y表示的是当前坐标；当然在深搜中会遇到走到新的位置的情况，那么一般是写成这样： > > > > 而在bfs的过程中，结构体队列每个元素结构大概是这样子： > > > > 这里结构体成员里面也有x和y，这两个也是表示坐标的；而在广搜过程中也需要去找下一个节点坐标，一般是这样： > > > > 注：以上代码中提到的dir数组表示方向数组，是一个二维数组。（详见49条） > > 54、i8，i16，i32，i64 > > > 这些实际上是数据类型的别名。当我们用long long的时候可能会觉得打完这个数据类型太繁琐了，尤其是程序中有许多地方要这样打，由于long long实际上是64为的整型(integer)，所以就会取别名为i64。同理，我们可以把int写成i32，short写成i16，char（本身运算逻辑其实还是整数类型）写成i8。 > > 实际上，在ACGO中，用户可以通过<cstdint>中的int8_t来表示char，int16_t来表示short，int32_t来表示int，int64_t来表示long long。上面说到的i8、i16、i32、i64实际上类似于<cstdint>中这些表示的方法。 > > 55、ss或sstream等 > > > 说到这个，大家可能有点陌生。因为这个事头文件<sstream>中的stringstream类型变量的常用名称。由于stringstream可以拆分为string和stream，所以取拆分后两个单词的首字母ss作为变量名比较合适。 > > [附] stringstream： > > sstream实际上是stringstream的缩写，即“字符串流”<sstream>头文件可以帮助我们将整数、浮点数等转换为字符串，也可以实现十转八、十转十六、十六转十、八转十这四个进制转换的操作。主要运算符和<iostream>类似，都是<<左移运算符和>>右移运算符。 > > 56、bs > > > bs可以是二分查找 （Binary Search） 的缩写，即我们在做二分查找题目时为了方便或使用递归时定义的函数。当然，bs这个名字也可以作为<bitset>头文件中的bitset类型变量的名称。取名方法和上面的"ss"类似，将bitset拆成bit和set各取首字母即可。 > > [附] bitset： > > bitset有一个作用是帮助我们实现十转二（调用to_string()方法）和二转十（调用to_ulong()方法）的功能，和sstream进制转换功能有些相似。 > > 57、pi或pai > > > 在C++编程时，有时候我们会根据需要调用sin等三角函数而将角度改为弧度。那么这时，我们一般会定义一个变量存圆周率的值，通常写成const\red{const}const double\blue{double}double pi=3.1415926535，或者取名为pai也可以。 > > 58、pq或heap > > > C++<queue>头文件中有个叫做priority_queue的数据类型，即优先队列。平时用优先队列时，我们可以把它的变量名叫做pq，即选取它的两个首字母p和q。当然，学了完全二叉树后，我们知道完全二叉树可以用一个叫做 “堆” 的东西来存储，而写代码时一般把堆用priority_queue实现，由于堆的英文名称是heap，所以我们也会将这样的变量名称叫做heap。 > > 59、res或result > > > 这两个实际上和ans差不多，因为ans是answer答案的缩写，res是result结果的缩写，都是表示算法结果的意思。只不过我印象中，好像Python编程时上课经常开res，但是到了C++的编程算法课堂就开ans居多了。 > > 60、x，y，z > > > x、y、z实际上类似于x轴、y轴、z轴，可以用它来表示三维的立体东西。当然，在C++中，我们可以用x、y、z来表示三维数组的一个位置上的元素，比如V[x][y][z]这样，就像表示三维坐标系中的一个点一样。 > > 61、it或iter > > > 这个对于经常玩STL容器玩得滚瓜烂熟的小伙伴（简称玩的6）十分熟悉，因为vector、set、map、甚至于冷门的deque都可以用迭代器指针::iterator来遍历，比如，vector可以for(vector<int>::iterator it=v.begin();it!=v.end();it++)cout<<*it<<" ";这样子。 > > 62、pos > > > 在有些题目中（包含迷宫搜索的题目）可能会提到坐标或位置这种词，这时候，我们就可以用pos来表示这个位置（或坐标），因为pos是position的缩写。一般而言，pos可能是int或者double类型的变量来表示在数轴上的位置，而当表示平面直角坐标系（二维坐标）上的位置时更多的可能是pair或者结构体类型。 > > 63、L,R,LL,LR,RL,RR,LC,RC > > > 据ACGO用户评论：这些是“窗口一家子”，就是说它们一家应该是用来表示题目中提到的这些“窗口”的位置和长度变量的，可以在相关题目中找到它们的身影。 > > 64、u和v > > > 据ACGO用户评论：这两个变量在ACGO图论算法题目中经常碰到，表示从u到v的一条有向/无向边，实际上也很常用。 当然，上述名称可能因人而异，还是要根据个人喜好。不过，在写题解时建议不要太随意取名字，以免造成误会。 好啦，以上的名称，你开过几个呢？ （持续更新中...）

AC君点赞的帖子，还不参加？！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 进入链接：复仇者联盟ASH主题 欢乐赛#4 邀请码：J5CJ 赛制：IOI 总分：33分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参加有奖！！！ 电影《头脑特工队2》：获取链接 密码：HAPPY2024 当然，第一名可以再选择一部喜欢的电影哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 此外，也可以加入复仇者联盟哦~ 本团官方QQ群如下： 点击链接加入群聊【复仇者联盟 探讨群】（主群） 点击链接加入群聊【复仇者联盟 娱乐群】（副群） 点击链接加入群聊【复仇者联盟 交流群】（副群） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排行榜： 【注：退站_小ZUZU 作弊，代码为AI生成，其成绩做零分处理！所以成绩做0分处理。不过鉴于现在他已经将原先作弊的代码覆盖，且退出了复仇者联盟。就不追究责任了。】 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 已报名31人 已参赛11人〔一人作弊〕 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 敬请加入吧！

-1.在这篇文章之前 01背包，相信大家都会（不会请自学）。 然而，在アイドル的排位赛中，总有那么几道01背包，在模板上加一些奇妙的东西使其变得非常不可读 所以，饱受火星背包折磨的我，将做出此文，为抵抗01变式做出贡献 0.前置知识 01背包，众所周知，不会就去上网学 1.最初的起点——01背包模板 01背包第一形态：模板形态 【背包】01背包(优化) 题目描述 一个旅行者有一个最多能装 C 的背包，现在有 n 件物品，它们的重量分别是 w1，w2，...,wn,w_1，w_2，...,w_n,w1 ，w2 ，...,wn ,它们的价值分别为v1,v2,...,vn，v_1,v_2,...,v_n，v1 ,v2 ,...,vn ，每件物品都可以选择装入背包或者不装入，求旅行者能获得最大总价值。 输入格式 第 1 行：两个整数，C (背包容量，0 < C ≤ 30000) 和 N (物品数量，0 < N ≤ 10000)； 第 2~N+1行：每行二个整数 wi，viw_i，v_iwi ，vi ，表示每个物品的重量和价值。 输出格式 仅一行，一个数，表示最大总价值。 样例 #1 样例输入 #1 样例输出 #1 经典01背包，当然要套最经典的模板 复杂度也是经典的O(nm) CODE: 2.当N开始变小的时候 当n开始变小的时候，就说明你要做火星背包全家桶了 火星背包I 01背包第二形态：N小余极形态 这题观察到我们的wi,vi,mw_i,v_i,mwi ,vi ,m都特别大，显然最终的时间复杂度肯定只能带n了 咋办？？ 不急，是时候掏出黑科技——折半搜索了（选学，因为我也不懂） 时间复杂度为O(2n2)O(2^{\frac{n}{2}})O(22n ) CODE: 火星背包II 01背包第三形态：火星式逆转形态 这题一看n和viv_ivi 都小，其余的我们承受不住。所以显然时间复杂度显然只能带n和viv_ivi 。 不妨想一下，你n和viv_ivi 都小，我们是不是可以反过来，直接枚举最后的答案然后判断答案是否可行呢？ 这么一思索，脑子里便能瞬间变出一个dp[i]呢（dp[i]指在想让最后价值变为i时的最小重量） 在思索一下，是不是dp[0]=0呢 这边界和公式都有了,接下来就交给代码了 时间复杂度为O(n∑i=1nvi)O(n\sum_{i=1}^nv_i)O(n∑i=1n vi ),最大1e8,勉强卡常过去 CODE 3.当N开始变大的时候 01背包第4形态：多重01形态 显然，你就要去写一些思维题了 这道题比较有价值，建议思考一下再看题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解： 1.直觉 你在刚看到这题的反应估计是：这不 01 背包模板题吗，为啥会在绿题？ 于是，你就高高兴兴的把 01 背包的模板修改了一下，放了上去。 结果就会这样 。 也是在这时，你看到了数据： n,m≤105n,m \le 10^5n,m≤105 。 所以说，这题用传统 01 背包的 O(nm)O(nm)O(nm) 还真做不出来。 然而正在你苦苦思索时，你一看 aia_iai 和 bib_ibi 的数据。 0≤ai,bi≤100\le a_i,b_i \le 100≤ai ,bi ≤10。 2.思路 aia_iai 和 bib_ibi 这么小，所有男家丁的状态最多只有 11×1111\times1111×11 多种，nnn 又很大，肯定会有重复的情况，于是我们就可以定义一个二维数组 sss 来保存当前状态的男家丁有多少个，这样子我们就得到了一个多重背包问题。 2.1二进制优化 然而普通多重背包的时间复杂度是 O(n×m×(背包个数))O(n \times m \times(背包个数))O(n×m×(背包个数))，显然是会超时间的。所以说还得用到二进制优化，把时间复杂度优化为 O(n×m×log⁡2背包个数)O(n\times m \times \log_2背包个数)O(n×m×log2 背包个数)。 ⋇\divideontimes⋇:这里的 nnn 最大为 10510^5105，mmm 最多为 11×1111\times1111×11， log⁡2\log_2log2 (背包个数) 顶多也就 101010 多一点点地样子，开个O2时间勉强能卡过。 3.MYCODE\MATHBF{3.MYCODE}3.MYCODE ： //抄袭可耻！！！ 4.探寻本质 看了这么多题目，相信你也发现了： 1.01变式最重要的就是挑软柿子捏，找到小的数据，根据这个想出对应的思路 2.没有小数据的背包一般都不在考背包 所以，“山重水复疑无路，柳暗花明又一村”，只要它还是背包，就一定是有一个比较简单的解的（火星背包I除外）。 5.结语 看到这里的，请按照以下操作进行： 1.@AC君：精选置顶 2.其他：点赞，评论（发个ding都行） byebye~

ACGO 排位赛#12 - 题目解析 本文同步于 CSDN：点击跳转 > 别问为什么没有挑战赛#11，因为挑战赛#11被贪心的 Yuilice 吃掉了（不是）。 > > 本次挑战赛难度相比较前面几次有所提升。 > > 爆料：小鱼现在已经入职了研发部门，排位赛的算分级制将在未来的几场排位赛中做出重大改变。之后就不会出现大家段位都很低的情况了。对于程度好的同学，稍微打一两把排位赛段位就会有很大的提升。 第一题 - 50%𝐴𝐼, 50%𝐻𝑢𝑚𝑎𝑛 题目链接跳转：点击跳转 STL 大法真好，用自带的 string.size() 方法就可以快速求出一个字符串的长度。具体思路见代码，根据题目要求模拟就好了。 本题的 AC 代码如下： 第二题 - 统计区间内奇数与偶数的数量 题目链接跳转：点击跳转 对于这种区间的问题，可以先考虑一部分。如果要求出从 [1,L][1, L][1,L] 区间内满足条件的数字我们应该怎么办？假设 LLL 是一个偶数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就应该是 L/2L / 2L/2。相同地，假设 LLL 是一个奇数，那么 [1,L][1, L][1,L] 区间的奇数和偶数就分别是 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2。注意到 L/2+1L / 2 + 1L/2+1 和 L/2L / 2L/2 两个公式都可以被简写成 (L+1)/2(L + 1) / 2(L+1)/2。 设 odd(L)odd(L)odd(L) 和 even(L)even(L)even(L) 分别为区间 [1,L][1, L][1,L] 的奇数个数和偶数个数。那么可以得出结论，如果要求 [L,R][L, R][L,R] 区间的奇数个数，答案就应该是 odd(R)−odd(L−1)odd(R) - odd(L-1)odd(R)−odd(L−1) 和 even(R)−even(L−1)even(R) - even(L-1)even(R)−even(L−1)。 本题的 AC 代码如下，代码并没有使用函数，见谅： 第三题 - 火星背包 II 题目链接跳转：点击跳转 一道反向 0/10/10/1 背包的模板题目。通常，0/10/10/1 背包问题的目标是选择若干物品，使得这些物品的总重量不超过背包容量，并且这些物品的总价值最大化。而反向 0/10/10/1 背包问题则是反其道而行之，其目标是选择若干物品，使得这些物品的总重量不低于给定的最小值，并且这些物品的总价值最小化。 主要就是状态的定义比较难：设 dp[j]dp[j]dp[j] 表示恰好凑出总重量为 jjj 的最小代价。那么我们可以得到如下的状态转移方程： dpj=min⁡(dpj,dpj−wi+vi);dp_j = \min(dp_j, dp_{j-w_i} + v_i); dpj =min(dpj ,dpj−wi +vi ); 根据状态的定义，我们将 dpdpdp 数组一开始全部初始化为正无穷大，同时另 dp0=0dp_0 = 0dp0 =0，表示恰好凑出重量为 000 的物品的最小代价为 000，正无穷大代表暂时还没有答案，需要在后续的循环中更新。 之后就是跑一遍正常的 Knapsack 01 代码就好了。在输出答案的时候，我们需要找到一个满足条件 (dp[i]≤m)(dp[i] \le m)(dp[i]≤m) 的最大值。用一个 for 循环就可以搞定了。 本题的 AC 代码如下： 第四题 - 可分数列 题目链接跳转：点击跳转 题目很简单，但需要仔细想一会儿才行。这道题的解决思路就是 找规律！没错，就是找一下规律就好了。我们只需要关注如何将这 4N+24N + 24N+2 个数列在去掉两个元素后可以被平均分成 NNN 个等差数列。 通过手动模拟的方式，注意到我们只需要把这些数字竖着排列就可以解决问题。另每一列有四个元素，但其中有两列有五个元素（代表 4N+24N + 24N+2 的 +2+2+2 部分），共有 NNN 列。例如数列 [1,3,5,7,9,11,13,15,17,19,21,23,25,27][1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27][1,3,5,7,9,11,13,15,17,19,21,23,25,27]。竖着排列之后就是这个样子的： 可以看到这些元素构成了三个等差数列，且两个等差数列的长度为 555。那么对于长度为 444 的等差数列我们完全可以不用管，直接输出就好了。而对于这两个长度为 555 的等差数列，我们考虑从这两个等差数列中各删除一个数字来构成新的等差数列。综合来看，我们发现删除元素 333 和 252525 后，新的两个等差数列依旧满足题目限定的条件。 再多列举几个例子，发现规律也是相通的。那么因此我们可以得出结论，对于任意一个长度为 4N+24N + 24N+2 的等差数列，只需要删除这个等差数列的第 222 项和第 4N+14N + 14N+1 项，剩下的 4N4N4N 个元素一定可以组成 NNN 个长度为 444 的等差数列。 > 关于本题的更多信息，可以阅读 アイドル 老师的题解作为补充：链接跳转。 找到规律后代码就很好写了，本题的 AC 代码如下： 第五题 - 花火大会 题目链接跳转：点击跳转 > 这道题的输出不是故意为难大家，因为输出实在太大了，超出了 CF 限定了 64MB 的限制，因此只能将输出地图改为了输出地图的哈希值（对于没有学过哈希的同学来说，输出答案也是一个比较困难的事情）。 本道题的难度其实不大，就是一个多源不同权的无权最短路问题。但由于数据量比较大，使用普通的优先队列维护会超时（别问我是怎么知道的，我一开始就用了优先队列，然后在 #13 测试点就 TLE 了），因此我们需要考虑如何找到一个 workaround 来替换优先队列。 注意到我们只需要另外再使用一个 while，在每次获取头节点的时候判断某一个烟花是否刚好在该时间点燃放，如果烟花正好燃放，我们就把这个烟花的坐标加入到队列之中。 由于每一个烟花每一个单位时间只会影响附近的一个格子，说明在放入烟花的时候队列中队头和队尾的权重是相同的，这样就保证队列内的元素权重一定是单调递增的。这这种情况下，这道题就转换成了使用 BFS 来求多源无权最短路的条件。 本题的 AC 代码如下： 第六题 - 剑之试炼 题目链接跳转：点击跳转 > 这道题超级恶心，我发自内心地对那些在比赛过程中 AC 此题目的同学表示尊敬。 思路上非常好想，由于所有的怪兽都要打，且打每一个怪兽的时间都是固定的，因此我们可以在一开始就先预处理出打完所有怪兽的时间，需要优化的就只有赶路的时间了。 先考虑每一层的情况，对于任意一层来说，关键点就是找到一个最优的路径（从某一个起点出发，经过所有的点后再传送到下一层的最短路径）即可。学习过状态压缩动态规划的同学可以很容易想到模板题【最短 Hamilton 路径】（洛谷链接：链接跳转）。 对于每一层来说，具体的实现方法和函数如下： 1. cover(dist, grid, "#*"); * 将dist和grid中标记为"#"或"*"的所有障碍物进行覆盖处理。这一步的作用是标记出所有不可通行的区域，为后续的距离计算或路径规划提供基础。 2. getMinDist(dist, grid, "#"); * 计算从当前所在位置到grid中标记为"#"（障碍物）位置的最短距离。这一步的作用是为后续的路径规划获取到障碍物的距离信息，方便下一步进行路径选择。 3. hamilton(dist, grid); * 在dist和grid上执行哈密顿路径（Hamiltonian Path）的计算，目的是找到一条经过所有目标点的路径。这一步的作用是根据前面的距离信息，找到一条经过所有必经点的路径。 4. cover(dist, grid, "#."); * 对dist和grid中标记为"#"（障碍物）和"."（空地）的部分进行覆盖处理。这一步是为了确保后续的距离计算排除已标记的障碍物，并识别可通行的路径。 5. getMinDist(dist, grid, "#"); * 再次计算从当前所在位置到grid中标记为"#"的最短距离。这一步是为了更新经过路径覆盖处理后的最短距离，确保得到最新的距离信息。 除此之外就是一些小的细节优化了，具体请参阅代码注释。 本题的 AC 代码如下（本代码参考了黄老师的 std，并加以修改（我是不会说我数组传来传去把自己传死了，讨厌指针的一天）），若需要更详细的解答，可以 参考本文：

ACGO 第 12 次排位赛题解 写在前面 本场比赛所有题目经过一轮 ChatGPT−4o\tt{ChatGPT-4o}ChatGPT−4o 测试，测试结果如下： 题目 A B C D E F 分数 100 160 110 14 187 0 测试点通过比例 20/20 20/20 10/25 1/25 11/25 0/35 本场排位赛的所有题目的难度评级为： 题目编号 题目标题 难度 A. 50%AI, 50%Human 入门 B. 统计区间内奇数与偶数的数量 入门 C. 火星背包 II 普及- D. 可分数列 普及/提高- E. 花火大会 普及/提高- F. 剑之试炼 提高+/省选- 非常感谢大家参加本场排位赛！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 直播预告 直播时间：9月14日（周六）16:00 开始 直播地址：B站ACGO官方账号 直播内容：排位赛#12复盘 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解简述 以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。 A - 50%AI, 50%HUMAN 我们可以以使用一个变量 M 来统计所有「AI」生成的变量； 每个变量名为一个字符串，一共有 NNN 个变量名，我们可以使用一个执行 NNN 次的循环，每次循环，使用一个 std::string 类型变量 s 读入变量名，并使用 s.size() 来获取字符串的长度，若长度大于 555 则令 m 加 111。 最终就可以得到 NNN 个变量名中「AI」编写的变量的数量 M。 由于需要向上取整，我们可以使用以下方法…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ B - 统计区间内奇数与偶数的数量 标签：前缀和；数学 对于每个查询，若直接使用循环暴力统计 [Li,Ri][L_i, R_i][Li ,Ri ] 内的奇数或偶数，时间复杂度为 O(Ri−Li)\mathrm{O}(R_i - L_i)O(Ri −Li )。本题 1≤Li≤Ri≤1091 \le L_i \le R_i \le 10^91≤Li ≤Ri ≤109。暴力统计会超出时间限制。 我们不妨思考一个问题：给定任意正整数 NNN，求 [1,N][1, N][1,N] 中所有「奇数」的数量，如何解决这个问题？ 不妨枚举，打表找找规律，1,3,5,7,9,11,⋯1, 3, 5, 7, 9, 11, \cdots1,3,5,7,9,11,⋯。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C - 火星背包 II 标签：背包问题 本道题目不难想到套用经典的「01背包问题」，定义 dp[i][j]\tt{dp[i][j]}dp[i][j] 为前 iii 个物品，背包容量为 jjj 可以获取的最大价值，然后使用 dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])\tt{dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])}dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) 进行转移。 此种做法只能够拿到一部分分数（约 40%40\%40%），无法通过本题，原因是本题背包的容量和物品的重量都特别大 (1≤wi≤M≤109)(1 \le w_i \le M \le 10^9)(1≤wi ≤M≤109)。使用上述方式解决这道题目的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)。 但本题 NNN 以及 viv_ivi 的值都比较小，我们不妨…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ D - 可分数列 标签：构造；数学 对于本道题目，不难发现，公差以及首项的值是不重要的，我们需要关注的点主要是如何将这 4N+24N + 24N+2 个元素去掉 222 个元素以后按照题目要求的形式分成 NNN 组。 首先观察样例。 我们将按照『从上到下』，『从左到右』的顺序，除最后一列外，每列 NNN 个元素的方式排列。 将 A2A_2A2 和 A13A_{13}A13 去除掉后，可以将剩余的元素分成 [1,4,7,10][1, 4, 7, 10][1,4,7,10]，[5,8,11,14][5, 8, 11, 14][5,8,11,14]，[3,6,9,12][3, 6, 9, 12][3,6,9,12] 三组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ E - 花火大会 标签：最短路径；广度优先搜索 本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。 当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。 以上两个问题都可以使用 BFSBFSBFS 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。 容易想到的一个策略是使用「优先队列」替换「队列」来实现 BFSBFSBFS。但此种方法的复杂度为 O(NMlog⁡NM)\mathrm{O}(NM\log{NM})O(NMlogNM) 在本题时间复杂度比较大的情况下无法通过本题。 假设队列中的点是按照最短路的大小从小到大排好序的，例如： [1,2,2,2,3,3,3,4,5][1, 2, 2, 2, 3, 3, 3, 4, 5][1,2,2,2,3,3,3,4,5] 第一个点的最短路为 111，当其出队的时候，扩展的到的点的最短路为 222。 我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（DijkstraDijkstraDijkstra 算法的思想）。 那么我们不妨将这些点按照最短路大小进行分组： [[1],[2,2,2],[3,3,3],[4],[5]][[1], [2, 2, 2], [3, 3, 3], [4], [5]][[1],[2,2,2],[3,3,3],[4],[5]] 我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ F - 剑之试炼 标签：最短路径；状态压缩动态规划；广度优先搜索； 本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。 由于要求必须击败所有的「波克布林」，且从地下 iii 层传送至地下 i+1i + 1i+1 层须花费 111 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 cost\tt{cost}cost。 把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 KKK 层地图上的所有特殊点需要最短时间，将其标记为 mint\tt{mint}mint。 那么本题的答案为 cost+mint\tt{cost + mint}cost+mint。 接下来解决如何计算 mint\tt{mint}mint 的问题。 因为计算 mint\tt{mint}mint 比较复杂，我们可以将其划分成若干个子问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

省赛成绩已出！ 考得不差，希望国赛不要考崩（如果国赛是下午考试的话，那我就得半夜爬起来做蓝桥杯的题目了。这真是个悲伤的事情）。 > 本帖只提供六道编程题的解题思路，部分题目并不提供实际的代码（因为我赛时忘记把代码截图下来了）。 T1 - 看书 题干描述： 一本书共 nnn 页，小明计划第一天看 xxx 页，此后每一天都要比前一天多看 yyy 页，请问小明几天可以看完这本书？ 输入格式： 一行输入三个整数 nnn，xxx，yyy (20≤n≤5000，1≤x，y≤20)(20\le n\le 5000，1\le x，y\le 20)(20≤n≤5000，1≤x，y≤20)，分别表示书的总页数、计划第一天看的页数以及此后每天都要比前一天多看的页数，整数之间以一个空格隔开。 输出格式： 输出一个整数，表示小明几天可以看完这本书。 样例输入：100 10 5 样例输出：5 解题思路： 防爆零题。用一个 while 循环来判断还有多少页的书需要看，循环里拿一个变量来记录循环次数作为答案即可。 T2 - 数字交换 题干描述： 给定一个正整数 nnn，请将 nnn 的最高位与最低位的数字进行交换，并输出交换后的结果。如果交换后的结果有前导 000，去除前导 000 后再输出结果。 输入描述： 输入一个正整数 n(100≤n≤109)n (100\le n\le10^9)n(100≤n≤109)。 输出描述： 输出答案。 样例输入： 173 样例输出： 371 解题思路： 以字符串的形式来读入字符，先用 C++ 自带的 swap 交换该字符串的第一位和最后一位。之后用 while 循环记录第一个合法数字出现的位置（即删除前导零）。最后用 string 类的 .substr() 方法截取字符串有效子串。 T3 - 出现奇数次的数 题干描述： 给定 nnn 个整数，其中只有一个数出现了奇数次，请找出这个数。 输入格式： 第一行输入一个整数 n(1≤n≤105)n (1\le n \le 10^5)n(1≤n≤105)。 第二行输入 nnn 个整数 (1≤整数≤109)(1\le 整数\le 10^9)(1≤整数≤109)，整数之间以一个空格隔开（数据保证只有一个数出现了奇数次） 输出格式： 输出一个整数，表示出现了奇数次的数。 样例输入： 样例输出： 解题思路： 这道题可以有多种算法来解。一种方法是使用 sort 函数对数组排序，然后找出某个出现奇数次的数即可。还可以用 STL 的 map 数据结构，类似桶排序的方法，来记录某一个键出现的次数，最后扫一遍就可以找出来了。 最方便的做法是使用异或的性质来快速找到某个出现奇数次的数。具体地，将数组中的所有元素依次进行异或运算，最终结果就是唯一一个出现奇数次的数，因为出现偶数次的数都会在异或中抵消掉。 代码展示： T4 - 字母移位 > 这道题是我觉得整一场比赛中最有问题的题目了。开了 long long 过不了，不开 long long 不取模竟然是过得了的。这证明这道题的数据是有问题的。（一个半小时的考试，这道题浪费了我一个小时的调试时间。我只能说，出题组太垃圾了）。 题干描述： 字母移位：表示将字母按照字母表的顺序进行移动。 例如：'b' 向右移动一位是 'c'，“向左移动两位是 'd'。 特别地，'a' 向左移动一位是 'z'，'z' 向右移动一位是 'a'。 给定一个仅包含小写字母且长度为 nnn 的字符串 sss，以及 nnn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_na1 ,a2 ,…,an ，接下来对字符串 sss 按如下规律操作： 1. 将第 111 位字符向左移动 a1a_1a1 位； 2. 再将第 1、21、21、2 位字符都向右移动 a2a_2a2 位； 3. 再将第 1、2、31、2、31、2、3 位字符都向左移动 a3a_3a3 位； 4. 再将第 1、2、3、41、2、3、41、2、3、4 位字符都向右移动 a4a_4a4 位； 以此类推，直到将 sss 的第 111 到第 nnn 位字符都（按规律向左或向右）移动完毕。 最后，将操作完成后的字符串 sss 输出。 例如：n=5n = 5n=5，字符串 s = "abcde"，555 个正整数为 1, 3, 5, 7, 9； 将 "abcde" 的第 111 位字符 "a" 向左移动 111 位，sss 变为 "zbcde"； 再将 "zbcde" 的前 222 位字符 "zb" 向右移动 333 位，sss 变为 "cecde"； 再将 "cecde" 的前 333 位字符 "cec" 向左移动 555 位，sss 变为 "xzxde"； 再将 "xzxde" 的前 444 位字符 "xzxd" 向右移动 777 位，sss 变为 "egeke"； 再将 "egeke" 的前 555 位字符 "egeke" 向左移动 999 位，sss 变为 "vxvbv"。 最后，将操作完成后的字符串 "vxvbv" 输出。 样例输入： 样例输出： 解题思路： 首先看数据量，发现这道题的数据量特别大，如果暴力的话肯定是会 TLE 的（亲测，暴力可以拿到 36%36\%36% 的高分。考虑按照以下方法优化： 注意到对于字符串的第 i 个字符，在完全模拟的过程中会调整 n−i+1n - i + 1n−i+1 次。但事实上，我们只需要记录某一个字符最终的偏移量就好了。参考样例，a 字符在经过 -1, +3, -5, +7, -9 （ASCII 码位移）后，最终只会偏移 -5 位。我们只需要记录每一位的最终偏移量就好了。 为了优化算法，考虑使用差分的策略来进行区间位移的操作。具体代码如下（正解，但因数据问题无法 AC）： 备注：记得开 int，开 long long 不拿分。 T5 - 通关游戏的最少能量值。 题干描述： 有一款新游戏，通关这个游戏需要完成 nnn 个任务，这 nnn 个任务可按任意次序完成。每个任务设置了启动能量值和完成任务消耗的能量值，且消耗的能量值小于等于该任务的启动能量值。如果玩家当前的能量值低于该任务启动能量值，则不能开始该任务。 例 1：玩家当前的能量值为 777，当前任务的启动能量值为 555，完成任务消耗的能量值为 333，则可以开始该任务，完成任务后玩家剩余能量值为 444； 例 2：玩家当前的能量值为 555，当前任务的启动能量值为 888，则无法开始该任务。 游戏开始时玩家需要一个初始能量值用来完成这 nnn 个任务。当给定每个任务的启动能量值和完成任务消耗的能量值时，请问初始能量的最小值是多少？ 样例输入： 样例输出： 解题思路： 考虑使用二分+贪心的策略。首先用贪心算法求得一个最优的打怪顺序。在这里，我们可以按照打完怪兽的剩余血量对数组进行排序。之后二分答案判断以 mid 为初始血量是否可以打完所有的怪物即可。 T6 - 物品分组 > 巧了，洛谷原题。我在 NNN 年前做过这道题目。链接：P1182 数列分段 数列分段 SECTION II 题目描述 题干描述： 对于给定的一个长度为 NNN 的正整数数列 A1∼NA_{1\sim N}A1∼N ，现要将其分成 MMM（M≤NM\leq NM≤N）段，并要求每段连续，且每段和的最大值最小。 样例输入： 样例输出： 解题思路： 也是一道很经典的二分答案题目，二分判断当每一段的和最大为 mid 时，是否可以分成 mmm 段即可。check 函数也是比较好写的。

📋 ACGO社区帮助手册 🌟 站务汇总 * 站务汇总 🏆 赛事信息 * 巅峰排行榜规则介绍 * 排位分机制揭秘 🗨️ 讨论区指南 * 发帖规范 * 删帖原因 团队招募帖子通常不应发布在“学习讨论”板块； 发布无意义内容； 发布违反社区规范的内容； 发布格式混乱，难以阅读的题解，不符合题解规范的题解。 📘 格式手册 * LaTeX数学公式语法 * Markdown语法教程 🤔 提问与解答 * 提问的智慧 * 题解编写技巧 🤖 AC助手使用指南 * AC助手的正确食用方法 🧠 知识点精华贴 * 知识点精华贴

谢谢

#include <iostream> using namespace std; int main(){ int m,d; cin>>m>>d; if(m1 || m3 || m5 || m7 || m8 || m10 || m12){ cout<<"Oh!No!"; } else if(m2 || m4 || m6 || m9 || m11){ if(d%2==0){ cout<<"Play!"; } else{ cout<<"Oh!No!"; } } return 0; }

温馨提示： 1.本程序仅Windows电脑可用 2.本程序含声音，请勿在上课时播放 3.请勿随意播放SOS（...---....） 4.本程序作者亲测可运行，不喜勿喷！ 5.发现任何BUG请及时找本人联系！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

A465似乎输出样例错了，样例是以1为下标，但正确的下标不应该是从0开始吗？可以查查看（不喜勿喷）

链接描述 > 本人发的第一个题解，欢迎吐槽

666这个测试数据是错的

就是这题2

🎯 倒计时开始！为了帮助大家更好地备战CSP-J/S初赛，本周我们将陆续推出精心挑选的初赛模拟题，让你在实战中磨练技巧，提升解题速度。 📚 这些题目都是我们精心挑选，覆盖了竞赛中可能出现的各种题型和难点。通过这些模拟题的练习，你将能够： 🔍 熟悉竞赛题型，提前适应考试节奏 💡 巩固算法知识，提高解题效率 🚀 发现自己的不足，及时查漏补缺 🌈 我们预祝所有参赛者在CSP竞赛中发挥出色，顺利通过初赛，迈向更高的荣誉！ 让我们共同期待，一起为即将到来的CSP竞赛加油助威！ J组： 一、单选题 1.c++语言面向对象的三大基本特征是什么 （） A. 封裝、继承、多态 B. 封装、继承、重载 C. 封裝、重載、多态 D. 重载、继承、多态 2.有6个元素，按照a、b、c、d，e、f 顺序进入栈q，请问下列哪个出栈序列是合法的 （） A. c, a, b, d, e, f B. a, d, b, c, e, f C. c, b, a, e, d, f D. a, b, e, c, d, f 3.运行以下代码块的行为是 （） A.将指向a的地址 B.将c指向b的地址 C.将d指向a的地址 D.将d指向b的地址 4. 顺序存储的优点是() A.可以在O(1) 的时间复杂度内进行插入操作。 B.可以在O(1) 的时间复杂度内进行删除操作。 C.可以在O(1) 的时间复杂度内随机访问元素。 D.顺序存储在申请空间时不需要连续分配空间。 5. 假没栈S和队列Q的初始状态为空。存在1、2、3、4、5、6六个互不相同的数据，每个数据按照进队列Q，出队列Q、进栈S、出栈S的顺序操作，不同数据间的操作可能会交错。已知队列Q中依次有数据1、2、3、4、5和6进队列，栈S依次有数据3、2、1、5、4和6出栈。则栈S的容最至少是 （）个数据。    A. 2 B. 3 C. 4 D. 5 二、读程题： 1.假设输入的n 都是奇数，输入的n个元素中，只有一个元素会出现1次，其他元素都出现2次，完成下面的判断题和单选题： 2.将 第 5 行 的ans赋值为0,最后输出的结果不变。(  ) 3.将第10行中的^运算变成|运算最终的结果不变。(  ) 4.当程序输入”5 2 2 3 3 4”时，输出为4。(  ) 5.当程序输入"1  1"时，输出为0。(  ) 6.当程序输入的元素为int 范围内时，ans的值不会超过int 范围。(  ) 7.当程序输入为201,其中[1,100]之间的数都出现两次，101出现一次，输出为( )。 A.98 B.99 C.100 D.101 答案

x = int(input()) y = 100 + x z = 600 - x * 5 answer = y * z print(answer)

x = int(input()) y = 100 + x z = 600 - x * 5 answer = y * z print(answer)

不知

指针的基本概念 指针是C中一个非常重要的概念，它是一个变量，其值为另一个变量的内存地址。通过指针，可以直接访问和操作内存中的数据，这为C提供了强大的内存管理能力。 指针的声明与初始化 在C++中，指针的声明需要指定指针所指向的数据类型。例如，声明一个指向整数的指针： Cpp 复制 int *ptr; // 声明一个指向整数的指针 指针可以通过取地址运算符&来获取变量的地址，并将其赋值给指针： Cpp 复制 int num = 10; int ptr = # // ptr指向num的地址 指针的使用 通过指针，可以访问和修改其所指向的变量的值。使用解引用运算符可以获取指针所指向的变量的值： Cpp 复制 int num = 10; int *ptr = # std::cout << *ptr; // 输出10 *ptr = 20; // 修改num的值为20 std::cout << num; // 输出20 指针与数组 指针与数组在C++中有密切的联系。数组名本身就是一个指向数组第一个元素的指针。例如： Cpp 复制 int arr[5] = {1, 2, 3, 4, 5}; int *ptr = arr; // ptr指向数组的第一个元素 stdcout << *ptr; // 输出1 stdcout << *(ptr + 1); // 输出2 动态内存分配 指针在动态内存分配中扮演着重要角色。使用new运算符可以动态分配内存，并返回指向该内存的指针： Cpp 复制 int *ptr = new int; // 动态分配一个整数大小的内存 *ptr = 10; delete ptr; // 释放动态分配的内存 指针的常见问题 空指针：指针可以被初始化为nullptr，表示它不指向任何有效的内存地址。 野指针：未初始化的指针或指向已释放内存的指针称为野指针，使用野指针会导致未定义行为。 内存泄漏：动态分配的内存如果未被释放，会导致内存泄漏。 指针的高级应用 指针在C++中还有许多高级应用，如函数指针、智能指针（如stdunique_ptr和stdshared_ptr）、指针与多态等。这些应用进一步扩展了指针的功能和灵活性。

程序阅读 1.删的代码越多越可能对，少则越关键 2.看不懂时去掉范围不符，越界，死循环的选项，剩下的随机