数论刷题笔记

互动｜ 你心里的“梦中情校”是哪所？

🏫 你心里的“梦中情校”是哪所？ hi，AC的同学们！ 谁心里还没个 “梦中情校” 呢？ 可能是因为： * 那所学校的校服巨好看，穿上就是全校最靓的仔 * 学校小卖部的烤肠是宇宙第一 * 社团有动漫社、街舞社、甚至养猫社 * 或者……单纯因为离你家近，可以多睡20分钟 🎯 玩法超简单： 在评论区，用一句话说出你的“梦中情校”+理由，初中，高中，大学都可以！ 🎁 奖励 活动截止后： * 点赞前5名 → 每人 罐头 × 50 * 随机抽5人 → 每人 罐头 × 20 ⏰ 时间 即日起至 2026年5月24日 💚 来吧，把那个让你心心念念的学校，大声说出来！ 说不定还能遇到未来的校友呢～ 往期互动

完了，总想说四维与自查多维DP的方法理解

为了不占用您的时间，如果您已经能对有关多维数组代码上的错误进行自查,我就不建议您看这篇 用无大用 无用也无大无用 的蒟蒻文章了 这里不做过多介绍。 引入理解主题的前言 三维介绍 其实都知道，三维是有x、y、z三个量，其中肯定有人想着“x，y是二维也就是平面直角坐标系的两个量，所以三维只是将平面加了一个z而已”注意，这段说辞的意思一般来说就是一个水平平面多增了一个高叫“z”，但是这是错的！在讲平面直角坐标系前，我们对于长方形、正方形，准确来说叫矩形的几何图形计算面积时会说“长乘宽等于其面积”但在往其他地方走一下可知：三角形叫高，是不是因为其所谓的宽（长）没有在这几何图形上，从而换了说法？ 三角形的那个没有在自己身上却进入计算的那一条边叫“高”（直角三角形除外，其高可以算作在一条直角边上），平行四边形也叫“高”（特殊的，长方形的高可以算作在一条边上），甚至是梯形也叫“高”（依旧有特殊） 那...矩形能叫“高”吗？其实从我们接触矩形的时候就不叫“长”与“宽”了，叫“底”与“高”，所以并不是换了说法，而是为了我们自身的理解叫成了“长”与“宽”。当我们开始接触三维，也就是立体几何图形时，方便后续理解，改回正确叫法：“底”“高”。 了解完这些，你应该会知道为何“x，y是二维也就是平面直角坐标系的两个量，所以三维只是将平面加了一个z而已”这段话是错的了吧，知道就看下一自然段，不知道继续看：“z”是我们常说的高，但在三维运用中，“z”只是二维上的高，“x”是二维上的底，那不用多说，“y”是啥？（以免还有人不知道，“y”是二维在不考虑平面直角坐标系中不存在的，也就是三维上的高） 跟我一样玩MC的小伙伴，在按下键盘上F3时，可以看见所处坐标，当你在不跳跃，只按下“w a s d”时，就会发现“x”与“z”坐标变化了，但“y”坐标始终没有变化（开自动跳跃的可以再去过一次清明节了），现在知道为什么了吧。 重头戏 四维 有过这方面知识储备的小盆友应该会知道，四维包含三个空间维度与一个时间维度，三个空间维度就是上文的“x z y”，既已理解四维，看下一自然段，不知的继续看：想象一个房间，这个房间里有一个盒子，过了一个单位的时间后，盒子变成了糖果，又过了一个单位的时间后，有一个不愿意透露姓名的小盆友一个瞬移进来迅速吃掉了糖果，又瞬移出去了，房间里甚都没有。又过了一个单位的时间，房间里莫名多出一个卡片。好，故事结束，当我们把这个房间里的状态以一个数组（列表）a以1开始来存储，那便是：a[1]=“盒子”，a[2]=“糖果”，a[3]=“NULL”(代表空)，a[4]=“卡”。这就是时间维度的存贮，一个单个单个的个体组成的一维时间维度，相当于一个0维的空间维度（一个点）被一个当把每个时间单位状态都记录下来的数组（列表）存了起来。若这个房间不再是一个一个的存，像第一个时间单位，不再只有一个盒子，而同时拥有一个盒子，一个袋子，设存储盒子这个位子的单独变化（盒子->糖->NULL->卡片）的数组（列表）为a1，若是袋子这个位子也在单独变化，则有一个a2数组（列表）来存储这个位子的变化，这就是两个时间线的变化量存储，但这里两个数组（列表）所表述的的都是这个房间里的变化，并且所记录位子也不重复，所以这里理应合并为一个数组（列表），一个2 * 4二维的数组（列表），但是表述的是一个时间维度与记录每个时间的两个位子状态的维度，而非“x”与“z”的维度。此时我们再延伸，这些位子有固定摆放顺序，不在只有两个位子，而是有四个位子摆成了2*2的样子，且每个位子与上述描述相同，那么这个a数组便改为三维数组（列表），同样是一个时间维度与一个“x”还有一个“z”组成的3维，而非“x”“z”“y”。最后，4个位子变成了8个，摆成了2 * 2 * 2的立体位子，且位子记录描述上同，就会是一个时间维度，与一个“x”和“z”还有一个“y”。再...我们第一次说的记录为a[时间]，则第二次为a[时间][x]，第三次a[时间][x][z]，第四次便是a[时间][x][z][y]。这就是我们的四维数组（列表）。恭喜你理解啦！（没理解？重看这一自然段“:(”） 别说了，ACgo网站是个编程网站，且c++用户居多（据我了解），所以四维空间该如何在DP代码中去进行理解呢？ 仔细看这四个数组（此乃c++数组，学P的理解成列表） 第一个相当于将一个 一个 的点变成一个 十个 的点，且这十个点连续； 第二个在第一个基础上，将每个 一个 的点变成每个 十个 的点，且这 每个 十个点连续； 第三个再在第二个基础上，将每个 一个 的点变成每个 十个 的点，且这 每个 十个点连续； 第四个同理。 简的来说第四个就是一个10 * 10 * 10的点阵，变成10 * 10 * 10的 长度为20的数组 阵 用处呢？ 在记忆化搜索中兴许有用 主要还是在DP（动态规划）上作每个状态量的记录。 ====================== ====================== ====================== 这里就举了理解四维的方法，这里再举5维的理解例子 （标题是“四维与自查多维DP代码的方法与理解”没说不能拓展） 简的来说 五维就是一个立体的点阵，变成立体的 面 阵， 前三个中括号代表10 * 10 * 10点阵，后两个中括号代表每一个点变成了20 * 20的面，所以这里来说就是“一个用20 * 20的面（不是吃的那个面）摆成的 10 * 10 * 10的立体阵列”（由于评论区搁那里讨论四维究竟是啥，我这里就不说五维是啥了，免得又起风波）（你这么理解，不再担心脑子在自查有关多维数组代码上错误时抽了。没懂？ 把这句话给AI，AI给你解释） ====================== ====================== ====================== 草草结束 希望这篇来自我自己的投稿能帮助到你理解四维空间转三维的原理来推论自己多维DP的代码原理以防报错后急着找不到从何下手 最后说一个东西，由于内容价值太小，就不单独发讨论了 在m=2时 与 其实是不等价的（不考虑时间复杂度，只考虑代码运行后的效果） 感谢您抽出时间观看完此文，若有错误，欢迎您在评论区留言，我会抽空回复的，谢谢

官方题解 | 挑战赛#31

挑战赛31题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 小午历险记之能量调节 入门 T2 小午历险记之宝石解密 普及- T3 小午历险记之古籍卷轴 普及- T4 小午历险记之星核碎片 普及- T5 小午历险记之蜂巢信标 普及/提高- T6 小午历险记之沙漠信标 普及/提高- T1 小午历险记之能量调节 题目大意 在一个大小为 MMM 的环形刻度盘上，刻度从 000 到 M−1M-1M−1，当前位置为 xxx，目标位置为 yyy，每次可以顺时针或逆时针移动一格，求最少需要多少次操作才能从 xxx 走到 yyy。 题解思路 由于刻度盘是环形的，从 xxx 到 yyy 只有两种走法：顺时针走或者逆时针走。顺时针的步数就是从 xxx 增加到 yyy 的距离，如果中途越过 M−1M-1M−1 就从 000 继续；逆时针则是从 xxx 减少到 yyy，如果减到 000 以下就从 M−1M-1M−1 继续。这两种距离都可以直接用取模来计算，分别是 (y−x+M) mod M(y-x+M)\bmod M(y−x+M)modM 和 (x−y+M) mod M(x-y+M)\bmod M(x−y+M)modM。实际最优方案一定是两者中较小的那个，直接输出最小值即可。整个过程只涉及常数次运算，时间复杂度为 O(1)O(1)O(1)，即使 MMM 非常大也完全没有问题。 参考代码 T2 小午历险记之宝石解密 题目大意 有 NNN 颗宝石，进行了 MMM 次解密仪式，每次仪式会同时激活若干颗宝石。需要判断是否对任意两颗不同的宝石 (u,v)(u,v)(u,v)，都存在至少一次仪式使它们同时被激活。 题解思路 由于 NNN 的范围很小，只有 100100100，可以直接用一个二维数组记录宝石之间是否“共现”过。初始化一个 N×NN \times NN×N 的布尔矩阵，表示任意两颗宝石是否在某次仪式中一起出现。对于每一次解密仪式，把其中所有宝石两两配对，在矩阵中标记为 truetruetrue。最后再枚举所有 1≤u<v≤N1 \le u < v \le N1≤u<v≤N，如果存在某一对没有被标记过，说明它们从未同时激活过，答案就是 No；如果所有宝石对都满足条件，则输出 Yes。这种做法直接模拟题意，复杂度在数据范围内完全可以接受。 参考代码 T3 小午历险记之古籍卷轴 题目大意 小午一开始有 NNN 本卷轴，编号任意。在开始研读前，可以反复进行“卖两本换一本”的操作。之后他要从第 111 卷开始，按顺序连续研读，问最多能连续研读到第几卷。 题解思路 可以把问题理解成：我们关心的是哪些编号的卷轴最终能被凑出来，而不是它们具体是怎么来的。只要某个编号最终能有一本，就可以用来研读。 先用一个布尔数组记录当前手中是否已经拥有某个编号的卷轴。读入初始卷轴时，如果编号已经出现过，或者编号大于当前可能用到的范围，这些卷轴都不可能直接用于研读，就当作“多余卷轴”，计入一个变量 sold，表示可以拿来卖掉的数量。 接下来用两个指针维护当前状态： L 表示当前最小缺失的编号，也就是下一本想要研读的卷号； R 表示当前最大的、已经拥有的编号，用来在必要时拆掉换资源。 循环中有两种操作方式： * 如果手里有至少 222 本多余卷轴，就可以直接“卖两本换一本”，把缺失的 LLL 号卷轴补出来； * 否则，只能从当前已有的最大编号 RRR 中拆掉一本，把它变成一份多余卷轴，再继续尝试。 当既无法合成新卷轴，又无法继续拆已有卷轴时，说明已经无法补出下一个连续编号，研读过程结束。此时 L−1L-1L−1 就是最多能连续研读到的卷号。 整个过程每本卷轴最多只会被处理常数次，时间复杂度是 O(N)O(N)O(N)。 参考代码 T4 小午历险记之星核碎片 题目大意 给定一个非负整数 NNN，把它看成一个二进制集合，要求输出所有非负整数 xxx，使得 xxx 的二进制中为 111 的位置全部包含在 NNN 的二进制为 111 的位置中，并按升序输出这些 xxx。 题解思路 把 NNN 的二进制中所有为 111 的位看成若干个可选的“位置”，题目要求的所有 xxx，本质上就是从这些位置中任选一些（也可以一个都不选）组成的所有子集。因为 NNN 中为 111 的比特位数量最多只有 151515 个，所以一共最多只有 2152^{15}215 种情况，可以直接枚举。 具体做法是先把 NNN 中所有为 111 的位的位置取出来，存到一个数组里。设这些位置一共有 kkk 个，那么用一个从 000 到 (1<<k)−1(1<<k)-1(1<<k)−1 的掩码来枚举所有子集。对于每一个掩码，如果第 jjj 位为 111，就把对应的位置加到当前数中，最终得到一个合法的 xxx。把所有生成的 xxx 存下来，排序后依次输出即可。由于总数很小，这样做时间和空间都完全没问题。 参考代码 T5 小午历险记之蜂巢信标 题目大意 在一个无限的六边形网格中，有 NNN 个被激活的单元，每个单元有一个整数坐标。如果两个激活单元能通过若干次“走到相邻的激活单元”互相到达，则它们属于同一个信标网络。要求统计这些激活单元一共能形成多少个互不连通的信标网络。 题解思路 这道题本质上就是在一个特殊邻接关系的网格图中统计连通块数量。每一个被激活的蜂巢单元都可以看成一个点，若两个点的坐标满足题目给出的六种相邻关系之一，就在它们之间连一条边。最终问题就变成：给定一个无向图，求连通块个数。 由于 NNN 只有 100010001000，可以先把所有激活单元的坐标存下来，再用一个哈希表把坐标映射到编号，方便快速判断“某个相邻坐标是否也是激活状态”。之后用 DFS 或 BFS 遍历图：维护一个访问数组，从每个尚未访问的点出发，搜索所有能到达的点，并标记为已访问，每启动一次搜索，就对应发现了一个新的信标网络。遍历结束后，搜索的次数就是答案。整体复杂度是 O(N)O(N)O(N) 级别，完全可以通过。 参考代码 T6 小午历险记之沙漠信标 题目大意 给定一张 n×mn \times mn×m 的网格地图，从起点 S 出发走到终点 T，可以上下左右移动。. 可以正常通过，# 不能通过，G 是检查点，整条路径中最多只能进入 一次 G，求最少步数，若无法到达输出 -1。 题解思路 这是一个带状态限制的最短路问题。普通的 BFS 只能记录位置，但这里还需要关心“是否已经用过一次进入 G 的机会”。因此把状态扩展为三维：当前位置 (x,y)(x,y)(x,y)，以及是否已经经过过 G。 用 d[x][y][k] 表示到达 (x,y)(x,y)(x,y)，且已经经过 kkk 次 G（k=0k=0k=0 或 111）时的最短步数。用 BFS 从起点开始扩展，每次尝试向四个方向走，如果遇到 # 就跳过；如果遇到 G，只有在当前还没用过（k=0k=0k=0）时才能走，并把状态转为 k=1k=1k=1；普通格子则直接走，状态不变。 最终答案是到达 T 的两种状态中较小的步数，只要有一种能到达即可。整个 BFS 过程中每个格子最多进队两次，时间复杂度是 O(nm)O(nm)O(nm)。 参考代码

谁懂拍毕业照的苦……

我真服了，昨天我们全年级拍毕业照，然后学校给我们整了一个空心的铁架子，就是那种用铁棍支撑起来的空心台阶(还必须横着走，不然就会掉下去)然后那摄影师还让我们在那架子上站半小时，腿都疼死了，自己在那发微信，然后稍微有一点声音就在那里吹哨子，搞得跟教官一样 大家有拍过毕业照的木

止 P 之殇

批话王还有 333 个小时降临地球，世界各大信竞训练平台将这条消息传唤的沸沸扬扬，他的到来，是单调队列还是优先队列，我无从得知，众说纷纭，我只想先吃个整体二分吧。 宇宙无穷，人生微渺，我从一无所有到生而为人的单调性中来，自当归于整体二分。唯独让我牵挂难以放下执念的，便是洛谷的整体二分了，整体二分不大，BIT\text{BIT}BIT 很干，初相识于一年前，我年少，她缥缈，浅尝一口:“哇”很美丽。可惜后来水群时间越来越晚，与曾经的挚爱想重逢却要隔着人山人海，我离线了一次又一次。批话王降临了，在 SH. 没有挂分，批话中，单调队列中，世界褪去了色彩 我到了，因为我必须来，作为新时代新青年，肩负文化科史命与伟大复兴重担，加入内卷，舍我其谁？ 可站在批话王脚下那一刻，我才意识到自己有多弱小，他比 WC✌️还要大，尽管我没去过 WC，但我刷过视频。 批话王停下进攻的脚步，低头看我，示意我把手给他，我不敢拒绝却也止不住的颤抖，原来他是要我手中的整体二分啊，看来无论何等高级的生命终无法抵御整体二分的美丽。一颗子弹贯穿我的胸膛，临死前耳畔传来天天的话语，在说我批话。 哈哈哈，这就是人性吗？批话王，我开始理解你了，不过，突然……好想去个……WC…啊………

CSP-J各年难度排行

帖炸了孩子们，明天补档

互动｜最近遇到过的离谱小事

互动｜😓 你最近遇到过的离谱小事 嗨，AC狗友们，生活有时候比段子还离谱 比如： * 去机房做作业，电脑开机三次蓝屏三次，第四次它自己更新了半小时。 * 老师说这道题很简单，像呼吸一样自然。结果他自己讲了四十分钟还没讲完。 * 在数学课睡过1800秒 不管多小的事，只要你觉得离谱、好笑、无语、神奇，都欢迎来分享。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎯 怎么参与？ 在评论区写下你最近遇到的一件真实发生的离谱小事。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 奖励 活动截止后（符合评论要求的）： * 评论点赞前5名 → 每人 罐头 × 50 ： @迷雾，@LIUXINCHEN，@Zorange(ZC)，@吐司汪汪，@天之神_†赛伊德† * 随机抽取5人 → 每人 罐头 × 20： @༺张秦轩 · 五年级 · 轻小༻，@超唐鼠王—金雨晗(打三角洲的处)，@亣戗，@胡睿熙的兄弟，@百大游戏解说官🤔 ⏰ 时间 即日起 至 2026年5月5日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 快来评论区说说：你最近遇到了什么离谱小事？ （越真实越好笑，越离谱越有奖） 往期互动

国内的编程（竞赛\认证\考级）难度排名

注意：本帖为个人客观排行，仅供参考，非真实难度排名；如有任何疏漏和不妥，欢迎各路大佬前来改正 本排名主要针对C++排序，不涉及其他编程语法难度（85分往后为AI提供简单说明） 排名主要规则： 1.全排名共34项，每一项都会给予打分，从低到高排序（满分100） 2.排名内所有项目与是否正规、是否入流无关 3.排名内会有一部分简写，例如级别则直接使用‘’-*‘’代替 宇宙免责声明：本人只是一个蓝水平的小菜鸡，可能会出现和您不同的观点，若感到排名疏漏过多，也别喷QAQ 耗时5小时手搓，求点赞QAQ 上榜喜报！评论我都会一一回复哒 新作品传送门： CSP-J各年难度排行 CSP-S各年难度排行 排名 名称 分数 简单说明/知识点 1 NCRE(计算机等级考试二级) 3 简单的语法，没有算法要求 2 中国电子学会C语言-1 5 顺序，分支，循环入门 3 GESP-1 5 顺序，分支，循环基础 4 中国电子学会C语言-2 8 循环嵌套，一维数组 5 GESP-2 10 分支循环综合，简单数学应用 6 中国电子学会C语言-3 12 二维数组，字符串基础 7 GESP-3 16 循环嵌套，枚举，简单排序 8 中国电子学会C语言-4 18 函数，递归基础 9 GESP-4 23 递推，排序，自定义函数，二分 10 中国电子学会C语言-5 25 栈，队列基础应用 11 GESP-5 31 字符串处理，分治（归并排序） 12 中国电子学会C语言-6 33 指针，结构体，链表 13 GESP-6 40 单调队列，树形DP，SPFA 14 中国电子学会C语言-7 42 二叉树遍历，贪心算法 15 CSP-J 47 综合应用基础算法，需解决3~4题 16 GESP-7 50 高级DP，哈希表，最短路 17 中国电子学会C语言-8 52 内并查集，最小生成树 18 GESP-8 60 斜率优化DP，网络流 19 中国电子学会C语言-9 63 线段树，拓扑排序 20 PAT乙级 65 基础数据结构与简单算法 21 中国电子学会C语言-10 68 复杂DP，LCA，数论 22 蓝桥杯省赛（C++大学组） 70 模拟，枚举，贪心(部分题目需一定思维能力) 23 团体程序设计天梯赛（个人奖） 73 多题综合，覆盖基础到进阶 24 蓝桥杯国赛 76 算法设计与优化，难度提升 25 PAT甲级 78 标准数据结构与算法，实现要求高 26 CSP-S 80 高级数据结构，复杂DP，图论 27 NOIP 81 与CSP-S相当，区分度更高 28 PAT顶级 85 极难题，涉及高级优化，数学 29 省选 88 综合高级算法，原创性强，区分度极大 30 NOI冬令营（WC） 91 国际区域赛风格，思维深度高 31 NOI 93 顶尖算法与数学推理，全国金牌水平 32 CTSC/国家队选拔赛 96 选拔IOI国家队队员，每题难度极高 33 IOI 100 世界顶尖个人赛，题目需发现深层性质 分数概念归纳（自定义段位）： D段（3~10）：入门级，明白基础语法。可完成多数 红 题目； C段（11~40）：ACGO站内大多数人水平。可完成 大量橙 少量黄 题目 B段（41~60）：来到了小高手层面，常见的瓶颈期大多出现在这里。可完成 大多数黄 少量绿 极少量蓝 题目 A段（61~80）：恭喜你，成功走出“新手村”，ACGO站内的佼佼者，来到了竞赛级别，这里已经是许多人的终点了。可完成 大多数绿 多数蓝 少量紫 题目 S段（81~90）：Perfect！你完成了CSP-S的“终极试炼”，已经迈向了省级！你需要面对省选，来奠定你的C++传奇之路。可完成 全部蓝 大多数紫 少量黑 题目 SSS段（91~100）：这个分段全国也屈指可数，可以为国争光啦！蓝紫难度对你来说已经是小菜一碟，黑难度也几乎不在话下 ，迈向国际大舞台，以中国身份出战，夯爆了！！！ 小声：我自己止步于A段80分，你们嘞？

浙江人都这样吗还是只有我家这样

我家管得应该算严的叭，我今年14没手机没Pad没电脑，小天才被收了，家里不让看小说，天官、魔道、伪渣、七芒星都被撕了，不过后面又买回来藏着就是了…… 再聊下压岁钱这事儿。 一年两万，爷爷奶奶外公外婆占大头，走亲戚一般最少给个一两百。 然后是卷。 隔壁同学小学六年级的时候学到初二初三，我爹五一让我干完初中化学，求何意味。 最后问下有同圈吗，我混天官魔道人鱼伪渣某某一屋暗灯二哈放学等我她的山她的海那兔ch罗小黑妖尾芙莉莲……

期中考试怎么样？!

主包今天刚刚考完期中考，很疑惑为什么要在兴奋激动期待的春假来临之前举行一次生死肉搏……嗯对老师这个批卷的速度也是很快好吧，成功获得 语文37(满分四十，只考阅读)，数学95，英语100科学28(满分三十只考实验)的好成绩了哈哈哈哈可以过个好假期啦。宝宝们都肿模样呢，欢迎打评论区哦