《好消息是，AC狗进厂了》

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

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

谁！跟！我！说！句！话！

我玩某不知名单机游戏幽闭恐惧症犯了...谁来救救我

5年级小蒟蒻11月日志

瞎写写的，点个赞吧\Huge\color{white}{瞎写写的，点个赞吧}瞎写写的，点个赞吧 > 榜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过时了） 你们也不要磕 不然我啥了你 大家都去看彩蛋呀 我希望登录有很多消息呀 （突然觉得篇幅好少） 发个互动吧！ 你最喜欢的老师？（说明理由） 你最讨厌的老师？（说明理由） 你最喜欢的学科？（说明理由） 你最讨厌的学科？（说明理由） 猜猜我的（答对在你一个帖子上发，生我者父母，知我者（昵称）也） —————————————————————————————————————— 各位大佬给点建议： @AAA“婉安”批发商（慕温） @‮rewolf laununu @じょうこうよう @stars_dream @‮༺དༀ༒∞░∞༒ༀཌ༻ @poop 谢谢各位 点个赞吧！ 南开姐姐的帖子和我僵持住了 彩蛋区： 各科老师

令你红温的计算题

如果你在学习树穴的过程中遇到令你崩溃的计算题可以发到评论区！然后作者会放在下面的列举里！ 上榜了？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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_小逍遥 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎发到评论区！！！

官方题解 | 巅峰赛 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。 参考代码

【专项治理】讨论区净化

📢 【专项治理】讨论区净化 AC狗友们，在上次1024程序员节的社区互动中，我们收到了大量关于 “社区垃圾帖处理不及时” 的宝贵反馈。我们深知，随着社区用户和发帖量的快速增长，内容质量也面临着新的挑战。 为了能够共同营造一个更加纯净、优质、高效的氛围，我们将启动 “讨论区净化”专项治理行动。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🧹 行动细则：每周定期清理内容 从上周起，AC狗 已经开始重点针对以下几类内容进行清理： 1. 低质题解类 * 未使用 Markdown 进行规范排版的题解。 * 未使用 LaTeX 编写数学公式，影响阅读的题解。 * 仅有代码，没有解题思路、逻辑分析或注释的题解。 2. 无意义标题类 * 标题为无意义的乱码（如：uuu49hhi, tj, 6）或过于简单的词汇（如：AC, 题解），无法体现帖子内容的标题。 3. 不良互动类 * 内容为“挂人”、公开指责，但未提供确凿证据的帖子。 4. 版块错发类 * 本应发布在 「站务」 版块的社区功能建议、错误反馈等帖子。 为方便大家理解，以下是一些典型的待清理帖示例： （图示：无意义标题与低质内容示例） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们诚挚地邀请您，从下一次发帖开始： * 为您的题解配上清晰的思路。 * 用一个准确的标题，帮助更多人发现好内容。 * 使用 Markdown 与 LaTeX，让知识传递更优雅。 让我们携手，从每一个细节做起，一起将ACGO社区建设得更加美好！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 如何写好一篇题解？ > 规范使用 Markdown 排版

互动｜期中成绩，谁懂啊

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

【团队安全运营公告】重要提醒

【团队安全运营公告】致各位队长：关于权限管理与团队安全的重要提醒 各位队长，大家好！ 为确保您团队的稳定与安全，ACGO 运营团队特此发布一则重要安全提醒。 一、核心原则：权限即责任，授权须谨慎 在 ACGO 团队系统中，队长及被授权的管理员所执行的操作（如移出成员、修改信息等），均被视为团队内部管理行为。平台尊重团队的自我管理权，因此不会对团队内部的权限使用进行干预或追责。 请注意：系统默认的“管理员”角色权限极高，不仅可以管理普通成员，甚至可以管理其他管理员。若您将“管理员”角色授予他人，对方理论上拥有与您近乎同等的权力。若授权不当，可能导致团队成员被误删甚至恶意清空。 二、行动指南：立即自查，防患于未然 我们强烈建议您立即执行以下操作，保护团队安全： ✅ 第一步：进入角色管理 * 在团队主页中，进入 “角色管理” 或 “权限设置”。 ✅ 第二步：审查现有权限 * 仔细检查每个角色（如“副队长”、“管理员”等）的权限设置。 * 重点核查是否有人拥有不必要的“移出成员”权限。 ✅ 第三步：取消高风险权限 * 对于非绝对信任的成员，请务必取消其“移出成员”权限。原则上，此权限应仅由队长本人持有。 * 修改后请点击保存。 ✅ 第四步：新建角色，按需授权（关键！） * 核心建议：如对成员没有绝对信任，请避免直接授予默认的“管理员”角色。 * 安全做法：点击 “新建角色”，自定义一个新角色，仅勾选完成任务所必需的权限（如发布公告、管理题目等），务必取消勾选“移出成员”、“管理管理员”等高危权限。 三、紧急情况处理 如您有确切证据表明团队遭遇以下情况： 1. 利用系统漏洞的恶意行为； 2. 因账号被盗引发的内部破坏； 请立即私信 @AC君 并提供证据，我们将介入协助核查。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 团队的安全，首要责任在于队长的谨慎授权。请像保管密码一样，谨慎管理团队权限。 感谢各位队长的理解与配合，让我们共同守护团队的和谐与稳定！

《触不可及》

触不可及 又何必在意 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

【天梯闯关】保卫战正式打响

> AC军团们注意！🚨 你们期待的「天梯闯关」新副本已加载完毕！ 🎯 全新玩法亮点抢先看： ✅ 剧情式闯关体验 - 专属剧情导入，沉浸感拉满 ✅ 渐进式关卡挑战 - 从第一关开始攀登，层层解锁 ✅ 实时代码竞技场 - 禁用复制粘贴，纯手写代码见真章 ✅ 智能奖励系统 - 通关即获金币，失败推荐专属题单 🕹 闯关须知： * 必须登录才能进入天梯系统 * 严格关卡顺序，必须先通关前一关 * 每关限时挑战，代码需现场手写 * 通关条件：每关所有题目全部AC！ 💎 闯关奖励： * 每关通关即得金币奖励 * 登顶天梯榜的玩家将获得限定成就 * 失败也不怕，系统智能推荐提升题单 据说能登顶的都是能手撕算法、脚踩异常的真·大佬！你的头发和AC率都在等你拯救！ ❓ 最新情报： > 1. 第二关 Happy Birthday! 样例无误； > 2. 第三关《奇妙的数字变化》 10.22 已更新； > 3. 通关获得的罐头，之后可以兑换社区商城（年底前上线）的物品哦； > 4. 前方还有170关正在加载中，已通关的小伙伴请耐心等待； 👉 【立即挑战】：天梯入口 💬 互动话题： 1. 你觉得自己能冲到第几关？ 2. 最期待在天梯中遇到什么类型的题目？ 3. 来预测下谁会是第一个登顶的AC大神？ 4. 闯关截图合影留念！ 🎁🎁🎁 在评论区留下你的闯关宣言，随机抽3位幸运鹅送出ACGO拼图冰箱贴！10月31日公布获奖！