ACGO欢乐赛66 第2题题解

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

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

止 P 之殇

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

完了，总想说四维（标题改成这样开心了吧）

为了不占用您的时间，如果您已经能对有关多维数组代码上的错误进行自查,我就不建议您看这篇 用无大用 无用也无大无用 的蒟蒻文章了 这里不做过多介绍。 引入理解主题的前言 三维介绍 其实都知道，三维是有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时 与 其实是不等价的（不考虑时间复杂度，只考虑代码运行后的效果） 感谢您抽出时间观看完此文，若有错误，欢迎您在评论区留言，我会抽空回复的，谢谢

这新头像框太棒了

我去，跟我名字太搭了 我C，我K，我K我K，520的这一天，大约6:10 AC君竟然给我的帖子点赞了，细节反复确认，发现确实是真的AC君，嘿嘿，我不仅喜欢认真负责的AC君，还喜欢不摆架子的AC君

“520”你准备和谁过？

N年不见上榜了 开心地笑（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 作为520的一个发帖子的人，我给大家写了几个“和谁过” 唐勿喷 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 和老师过 * 和家长过 * 和同学过 * 和床过 * 和题过 * 和希沃白板过 * 错过 * 略过 * 悔过 * 跳过 * 熬过 * 走过 * 路过 * 难过 * 擦肩而过 * 得过且过 * 大人不记小人过 * 沉舟侧畔千帆过

盘点MC中的指令

盘点MC中的指令 > /help — 查看指令帮助 > /list — 查看在线玩家 > /seed — 查看地图种子 > /stop — 关闭服务器 > /save-on — 开启自动存档 > /save-off — 关闭自动存档 > /save-all — 手动强制保存地图 > /gamemode 0 — 切换生存 > /gamemode 1 — 切换创造 > /gamemode 2 — 切换冒险 > /gamemode 3 — 切换旁观 > /gamemode 1 玩家名 — 给指定玩家切创造 > /gamemode 0 玩家名 — 给指定玩家切生存 > /difficulty peaceful — 和平 > /difficulty easy — 简单 > /difficulty normal — 普通 > /difficulty hard — 困难 > /time add 2000 — 增加游戏时间 > /time query daytime — 查询当前时间 > /weather clear — 晴天 > /weather rain — 下雨 > /weather thunder — 雷雨 > /time set 1000 — 跳过时间 > /time set day — 设置白天 > /time set night — 设置夜晚 > /time set morning — 清晨 > /time set noon — 中午 > /tp 玩家1 — 将自己传送到玩家1 > /tp 玩家 1 玩家 2 — 传送玩家 1 到玩家 2 > /tp @s x y z — 自己传送到指定坐标 > /tp @a x y z — 全员传送到指定坐标 > /tp @e x y z — 传送所有实体到指定坐标 > /setworldspawn — 设置世界出生点 > /setworldspawn x y z — 指定坐标设出生点 > /spawn — 返回服务器出生点 > /locate desert_pyramid — 定位沙漠神殿 > /locate jungle_pyramid — 定位丛林神庙 > /locate end_city — 定位末地城 > /locate stronghold — 定位末地要塞 > /locate mansion — 定位林地府邸 > /locate nether_fortress — 定位下界要塞 > /locate monument — 定位海底神殿 > /locate village — 定位村庄 > /give @s diamond_sword — 给自己钻石剑 > /give @s diamond_sword n — 给自己 n 把钻石剑 > /give 玩家 minecraft:gold_ingot 64 — 给玩家一组金锭 > /clear 玩家 — 清空玩家全部背包 > /clear @s — 清空自己背包 > /clear 玩家 stone — 只清空玩家的石头 > /enchant @s sharpness 5 — 手持物品附魔锋利 5 > /enchant @s unbreaking 3 —手持物品附魔 耐久 3 > /enchant @s mending 1 — 手持物品附魔经验修补 > /item replace entity @s hotbar.5 minecraft:apple — 替换快捷栏物品 > /summon zombie — 生成僵尸 > /summon skeleton — 生成骷髅 > /summon creeper — 生成苦力怕 > /summon spider — 生成蜘蛛 > /summon enderman — 生成末影人 > /summon slime — 生成史莱姆 > /summon magma_cube — 生成岩浆怪 > /summon ghast — 生成恶魂 > /summon wither_skeleton — 生成凋灵骷髅 > /summon ender_dragon — 生成末影龙 > /summon wither — 生成凋灵 > /summon iron_golem — 生成铁傀儡 > /summon snow_golem — 生成雪傀儡 > /kill @s — ** > /kill @a — 杀死所有玩家 > /kill @p — 杀死最近玩家 > /give @s netherite_sword[enchantments:{levels:{"附魔名称英文ID":等级数字(最高255)}}] — 自定义附魔 > /gamerule keepInventory true —— 死亡不掉落 打个广告：点此进入(有更多有趣的MC指令)

CSP-J各年难度排行（补档失败QAQ）

紧急通知！我现在任何关于CSP-J的补档全会失败，计划紧急叫停！！！ 深表歉意，辜负大家的期望，虽遗憾，但是确实做不了 =( 我补了三次档，每一次都会变成null，明明提高组都好好的，但是普及就是不行，开了新帖子也没用 SO： 之后可能不会再做关于J组的排行了，但我依然会尝试重发，直到成功 我会将之后的重心大多数放在粉丝投稿（因为我自己确实也没有灵感了） 最后： 希望ACGO放过我，不然我真的要转到洛谷了=( 其他作品传送门： 其他作品点这里！椰丝CO的枢纽

官方题解 | 挑战赛#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)。 参考代码

如何仿制当期热门帖（14）

也许你不知道我在评判什么，但现在看到我说的这句话时你就知道了，高尚的东道主 如果这些就是您想对我说的所有的话，那您大可以单开帖子并在你那掉几把意义都没有的原帖添加一个神秘的链接说不是吗，毕竟还能吸引一波节奏并让我变成一个万众瞩目的小丑不是吗，这样操作，生怕来看你那无敌帖子的人看不到，这未免太隐晦了吧东道主我真是对不起您啊，如果您觉得我评判了您的什么东西，请你将证据摆出来，就事说事，你一个证据不摆张口闭口就是滚你认为自己天下无敌了是吗，还有我翻遍了您的帖子并未找到任何关于我评判与辱骂您的文字，鉴于没有证据我无法相信您的说辞，抱歉，我也不知道你在滚什么，东子 我可能知道我评判了什么，可能是这个如果是的话，那只能说明兄弟的对号入座能力和大脑敏感程度需要进行一个治疗，当然不排除其他可能，以及请问您还要让我当多久名人，我注册ACGO这么久还是第一次见对于一件事连根叼毛解释都没有还能置顶一个雷霆无敌大阴爆缸猪塞评论整整3天的，也不排除我的帖子流量过少导致入不了那高贵的24K纯金眼睛吧，继续加油哦，加油让你的帖子超过官方互动帖吧！我会一直支持你的

谁懂拍毕业照的苦……

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