逆天学校

互动｜期中成绩，谁懂啊

🎤 期中成绩出来那一刻，谁懂啊 📚 期中分数揭晓，你的CPU干烧了吗？ * “啊啊啊这分数是真实存在的吗！”——直接表演一个原地起飞！ * “和预估一模一样，不愧是我。”——稳了，这次真的稳了。 * “比预想高两分，难道我就是天选之子？”——小小的庆幸了一下。 * “妈，你听我解释…这次真的上难度了…”——汗流浃背了家人们。 * “好好好，下次一定…”——经典保留节目，启动！ 🎤 评论区，交出你的“成绩reaction 主打一个真实！玩梗、凡学、发疯文学……统统端上来吧！ 🎁 参与有奖，主打一个真诚 随机抽5位天选之子，送出 ACGO冰箱贴碎片 随机1片！🛸 ⏰ 活动截止：11月30日 23:59 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 速来评论区！ 💥 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

中文c's能打出什么？

啊啊啊榜四了上榜一换头像 打出你c's的第一个词语！ 这儿有一个低脂小团

令你红温的计算题

如果你在学习树穴的过程中遇到令你崩溃的计算题可以发到评论区！然后作者会放在下面的列举里！ 榜3了？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.当你在做简便计算时遇到例如56+4356 + 4356+43这种凑不了整十整百的数时@风之叹 2.当你遇到这种小数乘小数的题目：0.115×0.33370.115 × 0.33370.115×0.3337一乘就5分钟的无法变成整数的计算题@风之叹 3.计算时算出除数为000的数，而且前面还列了一大堆式子，结果发现第一步就错了@风之叹 4.做分数乘法或除法的题目时做到类似514÷710\FRAC{5}{14}÷\FRAC{7}{10}145 ÷107 的题目，本以为化成乘法就可以开开心心地约分，可是刚写下去：514×107\FRAC{5}{14}×\FRAC{10}{7}145 ×710 就EMO了@风之叹 5.算了半天4.137Π4.137\PI4.137Π加6.125Π6.125\PI6.125Π，算完得一个小数已经崩溃了，题目让我再乘7，算完了发现他让保留Π\PIΠ @༺ཌༀ我要上南开ༀད༻ 6.736+637\FRAC{7}{36}+\FRAC{6}{37}367 +376 @༺ཌༀ我要上南开ༀད༻ 7.考试算出6.3756.3756.375个人一组@༺ཌༀ我要上南开ༀད༻ 8.21221^2212+22222^2222@༺ཌༀ我要上南开ༀད༻ 9.题目让Π=3.14159\PI = 3.14159Π=3.14159@风之叹 10.让算81Π81\PI81Π，转化成9Π×99\PI×99Π×9，算完了又除以999验算，的确是9Π9\PI9Π，发下来卷子发现9Π9\PI9Π背错了 @༺ཌༀ我要上南开ༀད༻ 11.让用(40.125Π+9.75Π)×93(40.125\PI+9.75\PI)×93(40.125Π+9.75Π)×93，算完思想崩溃了，检查时发现Π\PIΠ取333@凤凰_星火燎原—月落 12.[(35.125Π+3.7Π)×306×5360]÷3.795[(35.125Π + 3.7Π) × 306 × 5³⁶⁰] ÷ 3.795[(35.125Π+3.7Π)×306×5360]÷3.795@至少比你帅（佐助，水门本人） 13.文具店进了一批铅笔，第一天卖出了总数的13\FRAC{1}{3}31 多 666 支，第二天卖出了剩下的 12\FRAC{1}{2}21 少 333 支，第三天卖出了剩下的 23\FRAC{2}{3}32 后，还剩下的数量比第一天卖出后剩下的 14\FRAC{1}{4}41 多 222 支。请问这批铅笔原来有多少支?这道题可以列方程，设这批铅笔原来有X支，按每天卖出的规则逐步推导剩余数量：19X=14(23X−6)+2\FRAC{1}{9}X = \FRAC{1}{4}(\FRAC{2}{3}X - 6) + 291 X=41 (32 X−6)+2，结果X=−9X = -9X=−9,白解一个方程。@柒梅久久 14.有这样的一个完美长方形，求周长: @TN HACKER 15.对于 A1A2AA3A4‾\OVERLINE{A_1A_2AA_3A_4}A1 A2 AA3 A4 ，解方程： a1≠a4,a2≠a3,a2=a1+2,a4=2a3,a2a3a4‾+a1a3a4‾+a1a2a4‾+a1a2a3‾∣39,1≤a1,2,3,4≤9a_1 \neq a_4,a_2 \neq a_3,a_2=a_1+2,a_4=2a_3,\overline{a_2a_3a_4}+\overline{a_1a_3a_4}+\overline{a_1a_2a_4}+\overline{a_1a_2a_3} | 39,1 \le a_{1,2,3,4} \le 9 a1 =a4 ,a2 =a3 ,a2 =a1 +2,a4 =2a3 ,a2 a3 a4 +a1 a3 a4 +a1 a2 a4 +a1 a2 a3 ∣39,1≤a1,2,3,4 ≤9 解法： 设 A=A1,B=A3A=A_1,B=A_3A=A1 ,B=A3 ,枚举 A,B 的 81 种可能，可以证明答案为 A=4,B=4A=4,B=4A=4,B=4,因此答案为 464846484648@不会C++的NOAH 16.已知有个容器足够高，先到入水再倒入油，然后再放入一个长4厘米，宽8厘米，高15厘米，铁块，然后油和水升高了3厘米，问：原来的水油有多高，原本是能答对的，结果忘记还会有溢出的情况@AC是最好的 17.[(2÷12345302.378)MOD2.78]+⌊0.91÷534⌋[(2 ÷ 12345^302.378) MOD 2.78] + ⌊0.91 ÷ 534⌋[(2÷12345302.378)MOD2.78]+⌊0.91÷534⌋@至少比你帅（佐助，水门本人） 18.找规律：2,9,28,65,126,2172,9,28,65,126,2172,9,28,65,126,217，规律为：N3+1N^3+1N3+1@咕咕咕 19.上课的时候列二元一次方程组，算租了多少辆车，算了1小时，算出来租了-3辆车@抑相>...< 20.算几何图形时算半天，批完一发下来，最后的得数算错了，算出来一个班408个人@ENTJ 21.算出师父做了一小时16000个零件，徒弟做了42000@凤凰_星火燎原—月落 22.没看见约，以为能除尽，算到小数点后十几位@ZDZL_HACKER_小逍遥 23.解一个方程题时，都算对了，结果被判全错问老师为什么老师说"这题让你求YYY，谁让你求辅助计算的XXX的？! "单元模拟考的题目，水灵灵五分全扣光了@我是辞E，听取红色WA声一片 24.谁能懂，考试的时候算出，小明身高22.89ML2^{2.89}ML22.89ML的无力感@鬼嘲深渊——嘲灾 25.天天站在第9.15道跑道上@ENTJ 26.一辆汽车一小时行驶47100KM@ENTJ 27.当你算完一个复杂的多项式相加的时候，猛地一看发现选项里没有这个选项@‮༺དༀ༒∞░∞༒ༀཌ༻ 28.1÷1+(1÷(1+1÷(1+1÷7)))1÷ 1+(1÷(1+1÷(1+1÷7)))1÷1+(1÷(1+1÷(1+1÷7)))@朱朗枫 29.一个带绝对值的式子 ∣6T−32∣+6T|6T-32| + 6T∣6T−32∣+6T 算成了 −32-32−32@KALI 30.方程算着算着把XXX算没了@ZDZL_HACKER_小逍遥 31.把6(2X+4)=14X−46(2X+4)=14X-46(2X+4)=14X−4算到12X−8=14X+412X-8=14X+412X−8=14X+4@橙子同学 32.答案算出来无限循环小数@ZDZL_HACKER_小逍遥 33.用方程算了101010分钟，得出小明37.537.537.5岁，他爸414141@橙子同学 34.因式分解：A2+2ABA^2+2ABA2+2AB 解：原式=A2+2AB+X2−X2=(A−X)2−X2解：原式=A^2+2AB+X^2-X^2=(A-X)^2-X^2解：原式=A2+2AB+X2−X2=(A−X)2−X2@暴力出奇迹，结果TLE 35.当你把16−2X16-2X16−2X写成∣2X−16∣|2X-16|∣2X−16∣然后丢了一分从120到了119@BIANHL 36.(3X−6)÷(X−2)=4(3X-6)÷(X-2)=4(3X−6)÷(X−2)=4,XXX应该=2=2=2，但除数不能为000，所以X≠2X≠2X=2@朱朗枫 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎发到评论区！！！

【互动】哪道题让你怀疑自己智商？

📌 哪道题让你怀疑自己智商？ 🤯 学编程，谁没经历过几个“我是谁？我在哪？”的瞬间？ 📌 无论是： * 看完题解后，依然云里雾里的顿悟时刻 * 苦思冥想一下午，结果败给一个边界条件的崩溃 * 自信满满写出代码，结果连样例都过不了的尴尬 * 看到别人优雅的AC代码，开始怀疑自己智商的灵魂拷问 这些都是我们共同的成长印记！ ✨ 参与方式： 1. 在评论区写下那道让你怀疑人生的题目标题与链接。 2. 吐槽、段子、表情包统统欢迎！越真实，越能收获大家的“眼泪与赞”！ 🎁 活动奖励： 我们将从所有合规评论中，随机抽取 5位 “同病相怜”的幸运同学，送出 ACGO随机冰箱贴碎片 ！ @张橙@柒梅久久 @真的会汪 @54188（（（（官方正版挂壁猴 @盛翰祺 ⏰ 活动时间： 即日起至11月17日 23:59 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

5年级小蒟蒻11月日志

上榜一叫所有点赞的人爸爸 > 榜5了，芜湖！祝我破鼎冲上榜一！ 欠欠@༺ཌༀ我要上南开ༀད༻一下，姐姐的六年级开学日记和 六年级内卷日记真的很好，我很佩服。 希望姐姐能给这个帖子给建议。 11月-1-3日 人话就是10月30日 周末有啥好写的\Huge\color{white}{周末有啥好写的}周末有啥好写的 直接放假好吧 —————————————————————————————————————————— 11月3日 周末被我吃了 555，班长没选上 大家都讨厌美术，其实我也挺讨厌的 举行了个“抗美援朝” 解析 美：美术，朝：明天的朝阳 此词语表达了同学们对美术的讨厌与厌恶之情 (刚才我第二人格出来了，你们不必在意) 沈某被咳血牢湿紫菜了，于是： 抱歉，我第二人格又出来了，再来： (那个表情包发不出来了) 11月4日 一个小问答： 以下哪只是龙系 A.喷火龙——9人 B.暴鲤龙——3人 C.热带龙——2人 D.龙头地鼠——5人 E.沙漠蜻蜓——5人 F.化石翼龙——13人 G.班吉拉斯——3人 鱼纹老湿猜对了，欧皇呀！ 奥数课三阶幻方第一名 （不是，这很难吗？） —————————————————————————————————————————— 11月5-9日 生病了，咳咳 （看什么看，快点赞） —————————————————————————————————————————— 11月10日 今天考了语文考试，找了班级里的卦师算了一卦，大吉，还不如洛谷准 作文写了个“附魔金苹果”MC迷狂喜，老师竟然改对了，还是金句！ 没啥有意思的 补充 97分，芜湖！！！ MD，把正确答案改掉了 —————————————————————————————————————————— 11月11日 双十一耶 英语考 凭啥要在双十一英语考试 英语老师！！！ —————————————————————————————————————————— 11月12日 美术被老师夸了，爽歪歪 本蒟蒻美术挺差的 秋游前一天这不去，那不去 结果谁都去 具体会在秋游结束后更 请谅解！ 体育跑了2800米，累亖了 回家休息 —————————————————————————————————————————— 11月14日 秋游特别篇 上午 上午去了兰亭，一见到教官就怨言很重 也正常，150RMB给我们军训，隔壁班童靴说我们是“欠费的劳动力“ （太可怕了，好吧） 不让带手表，TMD！ 还好还好，没那么狠，只是吓一下我们的锐气 听了一个上午的广播 下午 下午带我们去什么在树下 吃饭时亿群虫子追着我们班不放，我们虽然是小蜜蜂中队，但也没那么招虫引蝶呀 先做梯子，一群人在那挖矿，还做出了木镐 然后烤红薯，我们除了红薯没烧熟，其他烤熟了 如：香肠，干脆面，方便面等 最后cos幕川北，做了个“捕鼠陷阱” 这是一个“捕鼠陷阱” ······ 当鼠鼠来这里吃食，活塞（木棍）被激活 头上的铁砧（石头）掉落，这时，你们猜会发生什么？ ······ （其实还有捕鸟陷阱） 去重庆啦 —————————————————————————————————————— 11月15日 绍兴秋假的时候到了 去重庆了！ 洛谷连续两天吉网购，这是咋的？ 在重庆，只有1楼和22楼 wow,so hot! 辣的我都要长痔疮了！ 为啥各种水帖都能上榜，窝的不能，Look at my eyes.Tell me why！ 实则心里 —————————————————————————————————————— 11月16日 去了皇冠大扶梯 太高了吧！ 要是真掉下去了， 那就真是自由落体（地狱版本） 又去了长江索道，要是底下是钢化玻璃会更刺激一点，我是不是“司令部”有点问题啊 芜湖，童鞋来重庆咯！ 什么呀，他刚下机场，我就去成都了 偶遇铜人，本以为是打卡点，没想到是收费站，1张6.7RMB，一下三张 还是小吉，洛谷你准不准呀？大凶才差不多 —————————————————————————————————————— 11月17日 去看熊猫： 憨态可掬的大熊猫 身形灵敏的小熊猫 我的观点： 大熊猫更像熊，小熊猫更像猫 真可爱 逛商场被坑了，1包日元的ptcg宝可梦卡牌，你卖我100RMB 不过我没买 没撑住，22:48睡了 —————————————————————————————————————— 11月18日 去了三星堆 碰上我们班的女神了，布吉岛回去会不会被那群磕CP的人磕 （虽然已经咋俩的CP过时了） 你们也不要磕 不然我啥了你 大家都去看彩蛋呀 我希望登录有很多消息呀 （突然觉得篇幅好少） 发个互动吧！ 你最喜欢的老师？（说明理由） 你最讨厌的老师？（说明理由） 你最喜欢的学科？（说明理由） 你最讨厌的学科？（说明理由） 猜猜我的（答对在你一个帖子上发，生我者父母，知我者（昵称）也） —————————————————————————————————————— 11月19日 榜2了！！！ 不，又榜四了！！！ 为啥AC君的帖子也能上榜 建议@AC君放个Ac专区，榜就给我们尽情上榜，对冲榜一的人很有用 昨天有小学来研学，是哪个小学的，说！ 秋假结束，准备上学！ 后面会更得慢一些哦 —————————————————————————————————————— 11月20日 新学了一个梗：受着！ 同学们看我上榜了，羡慕的要疯了 还举办了科技界开幕式活动，我那个位置正好在角落里，看也看不到啊！🤬🤬 没办法，自认倒霉吧 今天班里没什么事 回家看见了30多条消息，感谢大家这么努力和支持 —————————————————————————————————————— 11月21日 （如何证明老师是小黑子） 我们：老师这节课干什么？ 韩老师:唱跳rap！ 我们：篮球！！ 韩老师：逗你们玩的！排练！ 不！！！！！！！ 我们：ACO！！！ 又和科学老师争论： 老师想象的：和人争论时，突然掏出一本书看了起来 老师观点：错 我们想象的：和人吵架时，回到座位上看书 我们观点：对 我们赢了！！！ 英语老师说下周一考，结果今天考！不！ 为啥《慈母情深》就能刀我！ —————————————————————————————————————— 各位大佬给点建议： @AAA“婉安”批发商（慕温） @‮rewolf laununu @じょうこうよう @stars_dream @‮༺དༀ༒∞░∞༒ༀཌ༻ @poop @Earth. 谢谢各位 点个赞吧！ 不！@风之叹，不要呀!你牛掰 彩蛋区： 各科老师

我还不信了没一个同圈子的

来吃刀子！ 启明星升起来了，河谷对岸的朗帕寨传来雄鸡报晓的啼叫。夜色依然浓得像团墨，但这是黎明前的黑暗。 天边出现一道鱼肚白，天快亮了。 天边玫瑰色的霞光代替了山岔口篝火的光亮，山峦、河流和草原的轮廓逐渐清晰了。 天上纷纷扬扬地飘扬着大雪，不一会就填平了狼冢，抹净了痕迹。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 火红的夕阳下，那只金色的翅膀直直地僵硬地伸向天空，犹如一块金色的墓碑。 看懂的说说是什么书？

《触不可及》

触不可及 又何必在意 Homework will be finished before I go to sleep 触不可及 未来的自己 To write down the answer on down the question tips Down the question tips 无数个点灯熬油的夜里 梦见我在桌前做题 漫无目的 有时候我.靠在桌旁看着 周围同学冷漠表情 匆匆的来去 不止一次我想要休息不再拼命 却陷入恐惧开学的漩涡里 触不可及 又何必在意 Homework will be finished before I go to sleep 触不可及 未来的自己 To write down the answer on down the question tips Down the question tips 当夜幕将临我要跑步出去 奔向远方用尽全力 去哪儿都没关系 再放一首我最爱的音乐 跟着节奏做题 书上笔迹就随意 作业总是太过强硬 太多难题 我只想去看沿途未写的试题 触不可及 又何必在意 Homework will be finished before I go to sleep 触不可及 未来的自己 To write down the answer on down the question tips 触不可及 又何必在意 Homework will be finished before I go to sleep 触不可及 未来的自己 To write down the answer on down the question tips Down the question tips Down the question tips Down the question tips

超时了几个样例，不知各位有没有改进方法

大大大补档

官方题解 | 巅峰赛 27

赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 Alice 的简单数组 入门 T2 Alice 的数学构造 普及- T3 Alice 的交通网络 普及+/提高 T4 Alice 的分段游戏 普及+/提高 T5 Alice 的奇妙字段 普及+/提高 T6 Alice 的奇妙通信 普及+/提高 T1 题目大意 现在给你一个数组 a , 每次你可以将数组左移一格，问最终能否让这个数组，非降序。 题解 把数组视作首尾相接的环。定义“下降点”为满足 ai>a(i+1) mod na_i > a_{(i+1)\bmod n} ai >a(i+1)modn 的下标 iii。 充要条件： 存在某个左旋次数 rrr 使数组非降，当且仅当环上的下降点个数 ≤1\le 1≤1。 * 若下降点个数 cnt = 0：原数组已非降，最小 r=0r=0r=0。 * 若 cnt > 1：无论从哪切开，总会把至少一个下降点放到中间位置，无法整体非降，答案 −1-1−1。 * 若 cnt = 1：设唯一下降点在 (i)（即 ai>ai+1a_i>a_{i+1}ai >ai+1 ）。则左旋 (r=i+1) 次（把 ai+1a_{i+1}ai+1 放到开头）后序列必为非降；且这是最小的可行旋转次数。 参考代码 T2 题目大意 给定 TTT 组询问，每组给一个正整数 nnn。设 aaa 是 {1,2,…,n}\{1,2,\dots,n\}{1,2,…,n} 的某个排列，定义前缀乘积序列 b1≡a1(modn),bi≡bi−1⋅ai(modn)  (2≤i≤n).b_1 \equiv a_1 \pmod n,\qquad b_i \equiv b_{i-1}\cdot a_i \pmod n\ \ (2\le i\le n). b1 ≡a1 (modn),bi ≡bi−1 ⋅ai (modn)  (2≤i≤n). 若序列 bbb 恰好是 {0,1,…,n−1}\{0,1,\dots,n-1\}{0,1,…,n−1} 的一个排列（每个余数出现且只出现一次），则称该排列 aaa 可行。要求对每个 nnn 判断是否存在可行排列。 判定结论： 当且仅当 n∈1,2,4n\in{1,2,4}n∈1,2,4 或 nnn 为素数时，答案为 YES，否则为 NO。 题解 必要性 令排列为 a=(a1,…,an)\boldsymbol{a} = (a_1,\dots,a_n)a=(a1 ,…,an )，前缀积为 b1≡a1(modn),bi≡bi−1×ai(modn)  (2≤i≤n).b_1\equiv a_1 \pmod{n},\qquad b_i\equiv b_{i-1} \times a_i \pmod{n}\ \ (2\le i\le n). b1 ≡a1 (modn),bi ≡bi−1 ×ai (modn)  (2≤i≤n). 1. nnn 必须在末位：若某个 ak=na_k=nak =n 出现在 k<nk<nk<n，则 bk≡0b_k\equiv 0bk ≡0，而此后 bk+1,…,bnb_{k+1},\dots,b_nbk+1 ,…,bn 也都 ≡0\equiv 0≡0，无法成为 0,1,…,n−1{0,1,\dots,n-1}0,1,…,n−1 的排列。因此必须 an=na_n=nan =n，且恰有 bn≡0b_n\equiv 0bn ≡0。 2. (n−1)!≢0(modn)(n-1)!\not\equiv 0\pmod{n}(n−1)!≡0(modn) 必须成立：由于前 n−1n-1n−1 个元素正好是 1,…,n−1{1,\dots,n-1}1,…,n−1 的某个排列， bn−1≡∏i=1n−1ai≡(n−1)!(modn).b_{n-1}\equiv \prod_{i=1}^{n-1} a_i \equiv (n-1)!\pmod{n}. bn−1 ≡i=1∏n−1 ai ≡(n−1)!(modn). 为避免 bn−1=0b_{n-1}=0bn−1 =0 与 bn=0b_n=0bn =0 重复，必须 (n−1)!≢0(modn)(n-1)!\not\equiv 0\pmod{n}(n−1)!≡0(modn)。 经典数论结论：对一切合数 nnn，都有 (n−1)!≡0(modn),(n-1)!\equiv 0\pmod{n}, (n−1)!≡0(modn), 仅有 n=4n=4n=4 例外（3!≡6≡2(mod4)3!\equiv 6\equiv 2\pmod{4}3!≡6≡2(mod4)）。而 nnn 为素数时由威尔逊定理 (n−1)!≡−1(modn)≠0(n-1)!\equiv -1\pmod{n}\ne 0(n−1)!≡−1(modn)=0。再合并平凡情形 n=1,2n=1,2n=1,2，得必然条件：n∈1,2,4n\in{1,2,4}n∈1,2,4 或 nnn 为素数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 充分性（构造） * n=1n=1n=1：取 a=(1)a=(1)a=(1)，b=(0)b=(0)b=(0)。 * n=2n=2n=2：取 a=(1,2)a=(1,2)a=(1,2)（或 a=(2,1)a=(2,1)a=(2,1)），b=(1,0)b=(1,0)b=(1,0) 为全体剩余。 * n=4n=4n=4：取 a=(1,3,2,4)a=(1,3,2,4)a=(1,3,2,4)，b=(1,3,2,0)b=(1,3,2,0)b=(1,3,2,0)。 * n=pn=pn=p 为素数：构造 a1=1,ai≡i⋅(i−1)−1(modp)  (2≤i≤p−1),ap=p.a_1=1,\quad a_i\equiv i\cdot (i-1)^{-1}\pmod{p}\ \ (2\le i\le p-1),\quad a_p=p. a1 =1,ai ≡i⋅(i−1)−1(modp)  (2≤i≤p−1),ap =p. 其中 (i−1)−1(i-1)^{-1}(i−1)−1 指模 ppp 的乘法逆元。则 bi≡∏j=1iaj≡∏j=2ijj−1≡i(modp)(1≤i≤p−1),b_i\equiv \prod_{j=1}^i a_j \equiv \prod_{j=2}^i \frac{j}{j-1} \equiv i \pmod{p}\quad(1\le i\le p-1), bi ≡j=1∏i aj ≡j=2∏i j−1j ≡i(modp)(1≤i≤p−1), 且 bp≡0b_p\equiv 0bp ≡0，于是 bbb 正好是 0,1,…,p−1{0,1,\dots,p-1}0,1,…,p−1 的排列。 参考代码 T3 题目大意 给定一棵有 nnn 个点的无根树，第 iii 个点有正整数点权 aia_iai 。要求恰好切断树上 kkk 条边，把树分成 k+1k+1k+1 个连通块。每个连通块的代价等于该块内点权和的平方，总代价 Cost=∑i=1k***i2,\mathrm{Cost}=\sum_{i=1}^{k+1} s_i^2, Cost=i=1∑k****i2 , 其中 sis_isi 是第 iii 块的点权和。求最小可能的总代价。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解 思路 任选根 111。在每个结点 uuu 的子树内维护“已结算代价 + 携带块点和”的二元状态，自底向上合并；切边时把子树携带块的平方落地，不断开时只合并点和，最后在根把剩余携带块平方收尾。 状态 对每个结点 uuu，定义 DPu[t]={(c, s) }\mathrm{DP}_u[t]=\{ (c,\ s)\ \} DPu [t]={(c, s) } 表示在 uuu 的子树内恰好切了 ttt 条边，已结算代价为 ccc，且仍与父亲连通的携带块点权和为 sss（此块平方尚未计入 ccc）。 叶子初始： DPu[0]=(0, au),DPu[t>0]=∅.\mathrm{DP}_u[0]={(0,\ a_u)},\qquad \mathrm{DP}_u[t>0]=\varnothing. DPu [0]=(0, au ),DPu [t>0]=∅. 合并转移 设从 DPu[i]\mathrm{DP}_u[i]DPu [i] 取 (c1,s1)(c_1,s_1)(c1 ,s1 )，从儿子 vvv 的 DPv[j]\mathrm{DP}_v[j]DPv [j] 取 (c2,s2)(c_2,s_2)(c2 ,s2 )，有两类转移： * 不断开边 u–vu\text{--}vu–v（合并携带块，不加切边）： (i,j) → (i+j),(c′,s′)=(c1+c2, s1+s2).(i,j)\ \to\ (i+j),\qquad (c',s')=(c_1+c_2,\ s_1+s_2). (i,j) → (i+j),(c′,s′)=(c1 +c2 , s1 +s2 ). * 切开边 u–vu\text{--}vu–v（儿子侧携带块在此落地结算）： (i,j) → (i+j+1),(c′,s′)=(c1+c2+s22, s1).(i,j)\ \to\ (i+j+1),\qquad (c',s')=(c_1+c_2+s_2^2,\ s_1). (i,j) → (i+j+1),(c′,s′)=(c1 +c2 +s22 , s1 ). 对所有 i,ji,ji,j（不超过 kkk）枚举并取更优。 收尾 整树处理完后，在根 rrr： Answer=min⁡(c,s)∈DPr[k] (c+s2).\text{Answer}=\min_{(c,s)\in \mathrm{DP}_r[k]}\ \big(c+s^2\big). Answer=(c,s)∈DPr [k]min  (c+s2). 支配剪枝（控状态） 对固定的切边数 ttt，对 DPu[t]\mathrm{DP}_u[t]DPu [t] 的候选按 sss 递增排序，仅保留使 Φ(c,s)=c+s2\Phi(c,s)=c+s^2 Φ(c,s)=c+s2 严格下降的“前沿”。因为后续操作只会使携带和 sss 非减且落地代价是 s2s^2s2（凸），被支配的状态在将来不可能更优。 正确性要点 * 单次记账：携带块只在切边处落地平方一次；不断开时不计平方，避免重复。 * 完备与不重：每条父子边都在“切/不断开”二选一中被唯一处理。 * 最优子结构：合并仅依赖 ,(c,s),,(c,s),,(c,s), 的可加性与携带性质，满足 DP 要求。 * 剪枝不伤最优：若同 ttt 下有 s1≤s2s_1\le s_2s1 ≤s2 且 c1+s12≤c2+s22c_1+s_1^2\le c_2+s_2^2c1 +s12 ≤c2 +s22 ，则任意后续合并/落地操作后前者不劣于后者。 复杂度 设剪枝后每个 ttt 的候选至多为 mmm（经验上很小）。一次父子合并约为 O(k2m2)O(k^2m^2)O(k2m2)，全树 O(n⋅k2⋅m2),空间 O(n⋅k⋅m),O\big(n\cdot k^2 \cdot m^2\big),\qquad \text{空间 }O(n\cdot k\cdot m), O(n⋅k2⋅m2),空间 O(n⋅k⋅m), 对 n≤5×103, k≤30n\le 5\times 10^3,\ k\le 30n≤5×103, k≤30 可行。 边界校验 * k=0k=0k=0：答案为整树总和 SSS 的平方 S2S^2S2（根处结算）。 * k=n−1k=n-1k=n−1：每点成块，答案 ∑ai2\sum a_i^2∑ai2 。 * 点权全正，直觉与剪枝一致（块越大平方越贵，早落地有利于优化）。 参考代码 T4 一、二分阈值 XXX 答案 fff 显然单调：若阈值从 XXX 变大到 X′X'X′（X′≥XX'\ge XX′≥X），可行性不会变差。 因此二分 XXX。边界可取 L=max⁡iai,R=∑i=1nai,L=\max_i a_i,\qquad R=\sum_{i=1}^n a_i, L=imax ai ,R=i=1∑n ai , 在 [L,R][L,R][L,R] 上二分，判定函数 ok(X) 判断“是否能用 ≤k\le k≤k 段满足条件”。 若数组中压根没有目标颜色（∃i, coli∈S\exists i,\ \text{col}_i\in S∃i, coli ∈S 不成立），直接输出 −1-1−1。 二、判定 OK(X)：转化与 DP 约束 1：段和 ≤X\le X≤X 令前缀和 pre[i]=∑t=1iatpre[i]=\sum_{t=1}^i a_tpre[i]=∑t=1i at ，并设 lim[i]=min⁡,j∈[0,i−1]∣pre[i]−pre[j]≤X,.\text{lim}[i]=\min{,j\in[0,i-1]\mid pre[i]-pre[j]\le X,}. lim[i]=min,j∈[0,i−1]∣pre[i]−pre[j]≤X,. 在 ai≥0a_i\ge 0ai ≥0 时，lim[i]\text{lim}[i]lim[i] 可用双指针线性求出：对每个 iii，让 jjj 右移，使区间和 ≤X\le X≤X。 约束 2：每段必须含 SSS 用 nxt[i]nxt[i]nxt[i] 表示从位置 iii 开始向右的第一个“目标颜色”所在下标（若不存在取 n+1n+1n+1）。 那么分一段 [j+1,i][j+1,i][j+1,i] 合法   ⟺  \iff⟺ nxt[j+1] <= i。 DP 设计 设 g[i]g[i]g[i] 表示前 iii 个位置最少需要多少段（满足两项约束），g[0]=0g[0]=0g[0]=0，其余初始为无穷大。 则 g[i];=;1+min⁡,g[j]∣lim[i]≤j≤i−1, 且 nxt[j+1]≤i,.g[i] ;=; 1+\min{,g[j]\mid \text{lim}[i]\le j\le i-1,\ \text{且}\ nxt[j+1]\le i,}. g[i];=;1+min,g[j]∣lim[i]≤j≤i−1, 且 nxt[j+1]≤i,. 单调队列优化 当 iii 从小到大推进时： * 允许作为转移来源的 jjj 必须满足 nxt[j+1] <= i。也就是，当 iii 到达某值时，新的 jjj 会陆续“解锁”。 * 同时 j≥lim[i]j \ge \text{lim}[i]j≥lim[i]，即窗口左端还要随着 lim[i]\text{lim}[i]lim[i] 右移而弹出。 维护一个按 g[j]g[j]g[j] 非降的双端队列 QQQ 存可行的 jjj。推进步骤： 1. 把新“解锁”的 jjj 依次入队，入队前把队尾中 ggg 不优的下标弹出，保持队列内 ggg 非降； 2. 把不满足 j≥lim[i]j\ge \text{lim}[i]j≥lim[i] 的队首弹出； 3. 若队首存在，g[i]=g[Q.front()]+1g[i]=g[Q.front()]+1g[i]=g[Q.front()]+1，否则 g[i]=∞g[i]=\inftyg[i]=∞。 这样 ok(X) 即判断 g[n] <= k。 代码 T5 题目大意 有一串数 (a1,…,an)(a_1,\dots,a_n)(a1 ,…,an )。你可以最多一次把某一段连续区间里（长度不超过 LLL）的数全部取反（乘 −1-1−1）。翻完之后，再从新数组里选一个非空连续子段，让它的和尽量大。问这个最大值是多少（也可以选择不翻）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解 思路解释 想象最后你选出来的“最大子段”是一整段，中间有一小段被你翻转过。那这件事等价于： * 左边：接一段原数组的“最好尾巴”（以某个位置结尾的最大和，负数就不取）； * 中间：接一段被翻转的区间（长度 ≤L\le L≤L）。 注意：翻转某一段，其贡献就是把这段的和从 SSS 变成 −S-S−S，净变化是 减去 2S2S2S。所以“翻哪一段最赚”？——在你选的整段里面，找一个和尽可能小、长度 ≤L\le L≤L 的中间段去翻； * 右边：再接一段原数组的“最好开头”（以某个位置开始的最大和，负数就不取）。 于是，我们只要把“左边最好尾巴 +++ 中间翻转 +++ 右边最好开头”的组合做到最优即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 怎么高效做 1. 先算一个保底答案：不翻转时的最大子段和（经典的最大子段和，一次扫描）。 2. 准备三样“辅助信息” * 前缀和 P[i]P[i]P[i]（方便快速算任意一段的和）； * pre[i]\texttt{pre}[i]pre[i]：以 iii 结尾的最大子段和（负就当 000，不取）； * suf[i]\texttt{suf}[i]suf[i]：从 iii 开始的最大子段和（负就当 000，不取）。 pre 正向扫一遍，suf 反向扫一遍就好了。 3. 把“翻转中间段”变成滑窗问题 设中间段的右端是 rrr。那它的左端 lll 只能在区间 [,r−L+1, r,][,r-L+1,\ r,][,r−L+1, r,] 里（长度 ≤L\le L≤L）。 这时“左边最好尾巴 +++ 这段被翻后带来的收益 +++ 右边最好开头”可以写成： 选 j=l−1∈[,r−L,,r−1,] 去最大化：(pre[j]+P[j]) + (suf[r+1]−P[r]).\text{选 } j=l-1\in[,r-L,,r-1,]\ \text{去最大化：}\quad (\texttt{pre}[j]+P[j])\ +\ (\texttt{suf}[r+1]-P[r]) . 选 j=l−1∈[,r−L,,r−1,] 去最大化：(pre[j]+P[j]) + (suf[r+1]−P[r]). 对于固定的 rrr，右边括号中的 (suf[r+1]−P[r])(\texttt{suf}[r+1]-P[r])(suf[r+1]−P[r]) 是常数； 左边需要在区间 j∈[,r−L,,r−1,]j \in [,r-L,,r-1,]j∈[,r−L,,r−1,] 里取 (pre[j]+P[j])(\texttt{pre}[j] + P[j])(pre[j]+P[j]) 的最大值。 ——这就是一个滑动窗口最大值：用一个单调队列维护窗口内的最大 (pre[j]+P[j])(\texttt{pre}[j]+P[j])(pre[j]+P[j]) 即可。每次 rrr 右移一步，就： * 把窗口左端过期的 jjj 弹掉； * 把新进入的 j=r−1j=r-1j=r−1 按值递减地入队； * 用队头的最大值更新答案。 4. 别忘了比较“不翻”的保底答案 最终答案 =max⁡不翻的最大子段和, 上面滑窗得到的最大值=\max{\text{不翻的最大子段和},\ \text{上面滑窗得到的最大值}}=max不翻的最大子段和, 上面滑窗得到的最大值。 如果 L=0L=0L=0（不能翻），那就直接输出最大子段和的结果。 参考代码 T6 题面简介 给定一个最初无边的 nnn 点图，按时刻 t=1…qt=1\ldots qt=1…q 发生三类事件： 1. 1 x y：在无向点对 (x,y)(x,y)(x,y) 之间新增一条通道（允许多重边，计数 +1+1+1）； 2. 2 x y：在 (x,y)(x,y)(x,y) 之间摧毁一条通道（计数 −1-1−1，保证此时计数 ≥1\ge 1≥1）； 3. 3 x y：询问此刻 xxx 与 yyy 是否连通。 把所有回答为“连通”的询问的时刻记为 t1,t2,…t_1,t_2,\dotst1 ,t2 ,…，输出 X=t1⊕t2⊕⋯ .X=t_1\oplus t_2\oplus \cdots . X=t1 ⊕t2 ⊕⋯. 若没有一次连通询问，输出 000。图允许多重边，连通按“仍存在的通道”是否能成路来判断。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解 1. 离线把“边的存在”转成时间区间 对每个无序点对 e=x,ye={x,y}e=x,y 维护当前计数 cnt[e]（初始 000）与“活跃区间起点” st[e]。从 t=1t=1t=1 到 qqq 顺序扫描事件： * 1 x y：令 e=x,ye={x,y}e=x,y。若 cnt[e]==0，则 st[e]=t；随后 cnt[e]++。 * 2 x y：令 e=x,ye={x,y}e=x,y。先 cnt[e]--；若此时 cnt[e]==0，则产生一个活跃区间 [,st[e], t−1,][,st[e],\ t-1,][,st[e], t−1,]，表示这条边在该时间段存在。 * 计数语义的关键：我们只在计数从 0→10\to 10→1 与 1→01\to 01→0 时开/闭区间（多重边只要计数 >0>0>0，这条无向边就视为存在）。 扫描结束后，若某些边仍满足 cnt[e]>0，则补上区间 [,st[e], q,][,st[e],\ q,][,st[e], q,]。 于是，每条逻辑“边是否存在”的历史都被表示为若干时间区间。 2. 时间线段树上挂边 建一个覆盖区间 [1,q][1,q][1,q] 的线段树。把每条边的活跃区间 [L,R][L,R][L,R] 加到线段树所有与之相交的结点上（常规“区间加到节点”的做法，复杂度 O(log⁡q)O(\log q)O(logq) 每条区间）。 这样，线段树每个结点维护的是“它所覆盖的时间段内恒为存在”的边集合。 3. 回滚并查集（DSU WITH ROLLBACK） 准备可回滚的并查集：parent[] / size[] 以及一条操作栈用于记录每次 union 的变更（谁挂到谁、被改变的 size 值等）。提供函数： * save()：记录当前栈大小； * rollback(S)：把栈回滚到大小为 S 的状态（逐一撤销 union 的 parent/size 改动）； * union(x,y)：若本来就同属一集合则不入栈；若合并，按启发式把小树挂大树并把改动入栈，便于回退； * find(x)：路径不压缩的版本（避免难以回滚），只配合按秩/按大小合并即可。 4. 深搜线段树处理查询 从根结点 DFS： * 入结点前：记下当前栈大小 S；把该结点挂着的所有边执行 union； * 若是叶子（对应唯一时刻 ttt）：若第 ttt 个事件是询问 3 x y，则判断 find(x)==find(y)；若连通，则做 ans := ans ⊕ t.\text{ans}\ \mathrel{:=}\ \text{ans}\ \oplus\ t. ans := ans ⊕ t. * 递归处理左右子结点； * 回到本结点退出前：rollback(S) 撤销本结点施加的所有合并，环境还原给兄弟分支使用。 最终输出 ans。 参考代码

慕慕慕团队聊天室

不是哥们？上榜了？！666\HUGE 不是哥们？上榜了？！666不是哥们？上榜了？！666 > 团队入口 这里是慕慕慕团队聊天室。 慕慕慕成员这里可以讨论以下内容： 日常生活、八卦分享、创编题目、举办竞赛… 不能讨论以下内容： 攻击他人、造谣传谣… 有事私信联系副队长：@༺ཌༀ我要上南开ༀད༻、@凤凰_星火燎原—月落 正队长：@祈安驾到(原慕温) 支持一下