加入：https://www.acgo.cn/application/1824433474351996928 加入做题，可享受地铁JK护航俱乐部护航&大量金色，红色装备赠送，置换！！！ 行情好的时候还可以用一点点装备换把传说武器玩玩。 地铁护航 & 装备大礼包 你值得拥有~~ 加入我团还可享受精美地铁逃生头像&无伤刷boss指南等 ** 管理员们：禁止让老汉加入团队，不要乱给管理员权限，禁止！！！**

1、文艺复兴起源于那个国家 A.印度 B.意大利 c.法国 D.西班牙 2、文艺复兴三杰 A.米开郎基罗 达芬奇 亚里士多德 B.苏格拉底 米开朗基罗 拉斐尔 C. 米开郎基罗 达芬奇 拉斐尔 D.毕达哥拉斯 达芬奇 拉斐尔 3.下面那个不是达芬奇的作品 A.《最后的晚餐》 b.《圣母与微笑的圣婴》 c.《戴珍珠头饰的夫人》 d.《戴珍珠耳环的少女》 4.传说中洛神到了哪位三国人物 A.曹丕 B.曹仁 C.曹植 D.曹操 5.顾恺之是哪个时代的书画家 A.东晋 B.西晋 C.东汉 D.三国 6.拖拽题 略

亲爱的用户们，我们非常兴奋地宣布ZDZL团队官方网站博客部分的征文活动正式开启了！无论你是技术爱好者、行业专家，还是热衷于分享见解的内容创作者，这都是你展示才华和智慧的绝佳机会。 活动详情： * 主题不限：我们欢迎各种主题的文章，无论是技术创新、行业洞察、职业心得，还是生活随笔等。 * 字数要求：每篇文章建议在400字以上，以确保内容的充实与详尽。 * 投稿方式：请将您的文章以Word文档形式上传至ZDZL团队文件中，并标明作者。 * 评选机制：我们会对文章进行评选，入选文章将在ZDZL团队官方网站博客上发布。 * 活动时间：2024年12月6日起至2025年1月31日止。 为什么参与我们的征文活动？ * 广泛的影响力：ZDZL团队拥有庞大的用户群体和广泛的行业影响力，您的文章将被更多人看到。 * 提升写作能力：通过参与征文活动，您不仅可以锻炼自己的写作技巧，还能获得来自专业评审团的宝贵反馈。 期待您的精彩投稿！ 不要犹豫，拿起键盘，写下你的所思所想，与ZDZL团队和广大读者一起分享你的知识和见解吧！我们期待您的来稿。 联系我们： * 官方网站：https://zdzl.mysxl.cn/ 赶快行动起来，加入ZDZL团队的征文活动吧！期待您的精彩作品！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎加入ZDZL！

周杰伦 - 不能说的秘密 词：方文山 曲：周杰伦 编曲：林迈可 冷咖啡离开了杯垫 我忍住的情绪在很后面 拼命想挽回的从前 在我脸上依旧清晰可见 最美的不是下雨天 是曾与你躲过雨的屋檐 回忆的画面 在荡着秋千 梦开始不甜 你说把爱渐渐放下会走更远 又何必去改变 已错过的时间 你用你的指尖阻止我说再见 想象你在身边 在完全失去之前 你说把爱渐渐放下会走更远 或许命运的签 只让我们遇见 只让我们相恋这一季的秋天 飘落后才发现 这幸福的碎片 要我怎么捡 冷咖啡离开了杯垫 我忍住的情绪在很后面 拼命想挽回的从前 在我脸上依旧清晰可见 最美的不是下雨天 是曾与你躲过雨的屋檐 回忆的画面 在荡着秋千 梦开始不甜 你说把爱渐渐放下会走更远 又何必去改变 已错过的时间 你用你的指尖阻止我说再见 想象你在身边 在完全失去之前 你说把爱渐渐放下会走更远 或许命运的签 只让我们遇见 只让我们相恋这一季的秋天 飘落后才发现 这幸福的碎片 要我怎么捡

在一个平面上有一个圆和 n(0<n≤1000) 条直线，求这 n 条直线最多能将这个圆分割成几部分？ #include<bits/stdc++.h> using namespace std; int n,a[20009],v; int main(){ cin >> n; a[0]=1;//0条线将⚪分为1份 a[1]=2;//1条线将⚪分为2份 for(int i=2;i<=n;i++){ a[i]=a[i-1]+i; } cout<<a[n]; return 0; }

我和“啧啧啧啧啧啧啧啧啧啧啧啧~~”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1924450641296310272 我和“和平精英acgo大队”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1801215736138862592（玩和平的来，记得备注和平名方便加）

背景 是这样的，我最近向办一个公开赛（暂定名字叫 PIC），奈何没有合适人选，现在我面向全 ACGO 社区招聘出题人和验题人 要求 1.要求寒假期间有比较充裕的时间能用在 OI 上，并且有时间完成命题任务（其实也不多，每个人顶多命两三道题） 2.要求自身能力强，广泛参加各类市区级信息学比赛，要求有以下认证/竞赛奖项中至少一项： （一）USACO铜组别晋级 （二）GESP五级及以上 （三）CSP-J第二轮一等或CSP-S第二轮二等及以上 （四）NOC、蓝桥杯等白名单类赛事省赛一等奖或国赛二等奖及以上 （五）ACGO黄金段位及以上 （六）NOIP、NOI、WC、APIO、CTSC等较高级别信息学比赛获奖 （七）市、区级信息学竞赛获复赛或决赛一等奖 （八）其他有名、难度适中或较高的信息学比赛获得含金量较高奖次的 3.要求6个月内无社区违规行为 报酬 命题结束后，我按照在命题中承担的作用，从ACGO官方资助分钱下发 报名 加入命题组 我们会通过勋章来确认命题资质，若获奖不在奖项认证范围内，请私信发给我获奖凭证。

汇总 分汇总 在计算机科学中，图可以使用多种方式来进行存储，其中两种主要的表示方法是邻接矩阵和邻接表。 1. 邻接矩阵： * 邻接矩阵是一个二维数组，其中行和列分别代表图中的节点。 * 如果节点i和节点j之间有边，则矩阵中(i, j)和(j, i)的元素为1；否则为0。 * 对于有向图，矩阵中的值表示边的方向性。 * 优点：查找两个节点之间是否有边的时间复杂度为O(1)。 * 缺点：对于稀疏图会浪费空间；添加或删除节点的操作复杂度高。 2. 邻接表： * 邻接表是通过数组（或哈希表）和链表（或其他数据结构）的组合来表示图的方式。 * 对于每个节点，都有一个与之相连的边列表。 * 对于有向图，每个节点还可以包含指向其的边列表。 * 优点：对于稀疏图节省空间；添加或删除节点的操作更加高效。 * 缺点：查找两个节点之间是否有边的时间复杂度会受到链表查找的影响。 选择邻接矩阵还是邻接表取决于具体应用场景。一般来说，如果图比较稠密，邻接矩阵可能更适合；而对于稀疏图，邻接表可能更有效率。 除了这两种常见的表示方式外，还有其他一些图的存储方式，如关联矩阵、边表等，每种表示方式都有其特定的优缺点，根据实际需求选择最适合的方式。

看懂者受上赏

各位随便看看吧 1 三角函数基础与常用公式 1.1 基本定义与原理 三角函数是数学中用来描述角度与三角形边长关系的函数，最主要的三种函数是： 正弦（sin⁡\sinsin）：角的对边与斜边的比值 余弦（cos⁡\coscos）：角的邻边与斜边的比值 正切（tan⁡\tantan）：角的对边与邻边的比值 三角函数的定义基于直角三角形，也可以通过单位圆进行推广： 在半径为 111 的单位圆上，角度 θ\thetaθ 对应点的坐标是 (cos⁡θ,sin⁡θ)(\cos\theta,\sin\theta)(cosθ,sinθ)。 1.2 三角函数的基本公式 1.2.1 三角函数的诱导公式 sin⁡(−θ)=−sin⁡θ\sin(-\theta) = -\sin\thetasin(−θ)=−sinθ cos⁡(−θ)=cos⁡θ\cos(-\theta) = \cos\thetacos(−θ)=cosθ tan⁡(−θ)=−tan⁡θ\tan(-\theta) = -\tan\thetatan(−θ)=−tanθ 1.2.2 和差角公式 sin⁡(a±b)=sin⁡acos⁡b±cos⁡asin⁡b\sin(a \pm b) = \sin a \cos b \pm \cos a \sin bsin(a±b)=sinacosb±cosasinb cos⁡(a±b)=cos⁡acos⁡b∓sin⁡asin⁡b\cos(a \pm b) = \cos a \cos b \mp \sin a \sin bcos(a±b)=cosacosb∓sinasinb tan⁡(a±b)=tan⁡a±tan⁡b1∓tan⁡atan⁡b\tan(a \pm b) = \frac{\tan a \pm \tan b}{1 \mp \tan a \tan b}tan(a±b)=1∓tanatanbtana±tanb 1.2.3 倍角公式 sin⁡2a=2sin⁡acos⁡a\sin 2a = 2 \sin a \cos asin2a=2sinacosa cos⁡2a=cos⁡2a−sin⁡2a=2cos⁡2a−1=1−2sin⁡2a\cos 2a = \cos^2 a - \sin^2 a = 2 \cos^2 a - 1 = 1 - 2 \sin^2 acos2a=cos2a−sin2a=2cos2a−1=1−2sin2a tan⁡2a=2tan⁡a1−tan⁡2a\tan 2a = \frac{2 \tan a}{1 - \tan^2 a}tan2a=1−tan2a2tana 1.3 三角函数的常用性质与例题 1.3.1 单位圆示意 单位圆上，角度从 0∘0^\circ0∘ 到 360∘360^\circ360∘，sin⁡\sinsin 值对应点的 yyy 坐标，cos⁡\coscos 值对应 xxx 坐标。 角度越大，sin⁡\sinsin 与 cos⁡\coscos 变化呈周期性。 2 三角函数在题目和算法中的应用 2.1 计算角度的 SIN⁡\SINSIN 值（用余弦定理） 已知三角形三边长 a,b,ca,b,ca,b,c，求角 AAA 的 sin⁡\sinsin 值。 利用余弦定理： cos⁡A=b2+c2−a22bc\cos A = \frac{b^2 + c^2 - a^2}{2bc}cosA=2bcb2+c2−a2 sin⁡A=1−cos⁡2A\sin A = \sqrt{1 - \cos^2 A}sinA=1−cos2A 2.2 角度计算：两向量夹角的余弦值 向量 u=(x1,y1)u = (x_1,y_1)u=(x1 ,y1 )，v=(x2,y2)v = (x_2,y_2)v=(x2 ,y2 )，夹角 θ\thetaθ 满足： cos⁡θ=x1x2+y1y2∣u∣∣v∣\cos \theta = \frac{x_1 x_2 + y_1 y_2}{|u||v|}cosθ=∣u∣∣v∣x1 x2 +y1 y2 其中 ∣u∣=x12+y12|u| = \sqrt{x_1^2 + y_1^2}∣u∣=x12 +y12 2.3 例题3：求两向量夹角的余弦值 向量 u=(1,0)u = (1,0)u=(1,0)，v=(0,1)v = (0,1)v=(0,1) cos⁡θ=1×0+0×11×1=0\cos \theta = \frac{1 \times 0 + 0 \times 1}{1 \times 1} = 0cosθ=1×11×0+0×1 =0 夹角为 90∘90^\circ90∘ 3 数学例题 3.1 例题1 已知 sin⁡a=35\sin a = \frac{3}{5}sina=53 ，aaa 为第一象限角，求 cos⁡a\cos acosa。 答案点击我 →\rightarrow→ [1] 3.2 例题2 已知角 xxx 满足 sin⁡x=513\sin x = \frac{5}{13}sinx=135 ，且 xxx 在第二象限，求 cos⁡x\cos xcosx 和 tan⁡x\tan xtanx。 答案点击我 →\rightarrow→ [2] 3.3 例题3 点 P(2,3)P(2,3)P(2,3) 绕原点逆时针旋转 60∘60^\circ60∘，求旋转后的点 P′P'P′ 坐标。 答案点击我 →\rightarrow→ [3] 4 编程例题 4.1 移动的点 P 4.1.1 数学原理 点绕原点旋转 θ\thetaθ 度后的坐标变化如下： x′=x⋅cos⁡θ−y⋅sin⁡θy′=x⋅sin⁡θ+y⋅cos⁡θ x' = x \cdot \cos\theta - y \cdot \sin\theta y' = x \cdot \sin\theta + y \cdot \cos\theta x′=x⋅cosθ−y⋅sinθy′=x⋅sinθ+y⋅cosθ 其中 θ\thetaθ 必须用弧度制参与三角函数运算： θrad=θ×π180 \theta_{\text{rad}} = \theta \times \frac{\pi}{180} θrad =θ×180π 4.1.2 题目正解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 解：利用恒等式 sin⁡2a+cos⁡2a=1\sin^2 a + \cos^2 a = 1sin2a+cos2a=1 cos⁡a=1−sin⁡2a=1−(35)2=1−925=1625=45\cos a = \sqrt{1 - \sin^2 a} = \sqrt{1 - \left(\frac{3}{5}\right)^2} = \sqrt{1 - \frac{9}{25}} = \sqrt{\frac{16}{25}} = \frac{4}{5}cosa=1−sin2a =1−(53 )2 =1−259 =2516 =54 ↩︎ 2. 解：利用恒等式：sin⁡2x+cos⁡2x=1\sin^2 x + \cos^2 x = 1sin2x+cos2x=1 cos⁡x=−1−sin⁡2x=−1−(513)2=−1−25169=−144169=−1213\cos x = -\sqrt{1 - \sin^2 x} = -\sqrt{1 - \left(\frac{5}{13}\right)^2} = -\sqrt{1 - \frac{25}{169}} = -\sqrt{\frac{144}{169}} = -\frac{12}{13}cosx=−1−sin2x =−1−(135 )2 =−1−16925 =−169144 =−1312 （第二象限，cos⁡\coscos 负） tan⁡x=sin⁡xcos⁡x=513−1213=−512\tan x = \frac{\sin x}{\cos x} = \frac{\frac{5}{13}}{-\frac{12}{13}} = -\frac{5}{12}tanx=cosxsinx =−1312 135 =−125 ↩︎ 3. 解：用公式： x′=xcos⁡60∘−ysin⁡60∘=2×12−3×32=1−332x' = x \cos 60^\circ - y \sin 60^\circ = 2 \times \frac{1}{2} - 3 \times \frac{\sqrt{3}}{2} = 1 - \frac{3\sqrt{3}}{2}x′=xcos60∘−ysin60∘=2×21 −3×23 =1−233 y′=xsin⁡60∘+ycos⁡60∘=2×32+3×12=3+32y' = x \sin 60^\circ + y \cos 60^\circ = 2 \times \frac{\sqrt{3}}{2} + 3 \times \frac{1}{2} = \sqrt{3} + \frac{3}{2}y′=xsin60∘+ycos60∘=2×23 +3×21 =3 +23 所以新坐标： P′=(1−332,3+32)P' = \left(1 - \frac{3\sqrt{3}}{2}, \sqrt{3} + \frac{3}{2}\right)P′=(1−233 ,3 +23 ) ↩︎

这里是日志区，原帖子网址：https://www.acgo.cn/discuss/post/47443 2025/7/10：发帖了，第一次发帖，大家可不可以把我顶上去呀，谢谢大家 2025/7/22：感谢大家的支持，阅读已经上100了，谢谢大家 2025/7/22：感谢大家的支持，回复已经上50了，谢谢大家 2025/7/22：感谢大家的支持，点赞已经上10了，谢谢大家 2025/7/22：感谢大家的支持，阅读已经上150了，谢谢大家 2025/7/23：感谢大家的支持，点赞已经上25了，谢谢大家 2025/7/23：感谢大家的支持，阅读已经上200了，谢谢大家 2025/7/24：感谢大家的支持，阅读已经上250了，谢谢大家 2025/7/26：感谢大家的支持，点赞已经上50了，谢谢大家 2025/7/26：感谢大家的支持，阅读已经上300了，谢谢大家 2025/7/26：感谢大家的支持，我的帖子上热搜T:10了，谢谢大家 2025/7/26：感谢大家的支持，阅读已经上350了，谢谢大家 2025/7/27：感谢大家的支持，阅读已经上400了，谢谢大家 2025/7/27：感谢大家的支持，我的帖子上热搜T:9了，谢谢大家 2025/7/27：感谢大家的支持，我的帖子上热搜T:8了，谢谢大家 2025/7/27：感谢大家的支持，阅读已经上450了，谢谢大家 2025/7/27：感谢大家的支持，阅读已经上500了，谢谢大家 2025/7/27：感谢大家的支持，回复已经上100了，谢谢大家 2025/7/27：日志区移动到此帖子了，让您不便请原谅！ 2025/7/28：感谢大家的支持，阅读已经上550了，谢谢大家 2025/7/28：感谢大家的支持，阅读已经上600了，谢谢大家 2025/7/28：感谢大家的支持，我的帖子上热搜T:7了，谢谢大家 2025/7/28：感谢大家的支持，我的帖子上热搜T:6了，谢谢大家 2025/7/28：感谢大家的支持，阅读已经上650了，谢谢大家 2025/7/28：感谢大家的支持，阅读已经上700了，谢谢大家 2025/7/28：感谢大家的支持，我的帖子上热搜T:5了，谢谢大家 2025/7/29：感谢大家的支持，阅读已经上750了，谢谢大家 2025/7/29：感谢大家的支持，阅读已经上800了，谢谢大家 2025/7/29：感谢大家的支持，阅读已经上850了，谢谢大家 2025/7/29：感谢大家的支持，阅读已经上900了，谢谢大家 2025/7/29：感谢大家的支持，点赞已经上100了，谢谢大家 2025/7/30：感谢大家的支持，点赞已经上全站第一了，谢谢大家 2025/7/30：感谢大家的支持，阅读已经上1000了，谢谢大家 2025/7/31：感谢大家的支持，点赞已经上150了，谢谢大家 2025/7/31：感谢大家的支持，阅读已经上1050了，谢谢大家 2025/7/31：感谢大家的支持，阅读已经上1100了，谢谢大家 2025/7/31：感谢大家的支持，阅读已经上1200了，谢谢大家 2025/7/31：感谢大家的支持，阅读已经上1250了，谢谢大家 2025/8/1：感谢大家的支持，阅读已经上1300了，谢谢大家 2025/8/1：感谢大家的支持，回复已经上150了，谢谢大家 2025/8/1：感谢大家的支持，回复已经上200了，谢谢大家 2025/8/1：感谢大家的支持，我的帖子上热搜T:4了，谢谢大家 2025/8/3：感谢大家的支持，我的帖子上热搜T:3了，谢谢大家 2025/8/3：感谢大家的支持，回复已经上250了，谢谢大家 2025/8/4：感谢大家的支持，阅读已经上1500了，谢谢大家五百五百写 2025/8/5：感谢大家的支持，阅读已经上2000了，谢谢大家 2025/8/7：感谢大家的支持，阅读已经上2500了，谢谢大家 2025/8/8：感谢大家的支持，点赞已经上200了，谢谢大家 2025/8/9：感谢大家的支持，我的帖子上热搜T:2了，谢谢大家 2025/8/9：感谢大家的支持，回复已经上300了，谢谢大家 2025/8/10：感谢大家的支持，我的帖子上热搜T:1了，谢谢大家

欢迎新生入学 禁止恶意开除学生、教师 请勿随意更改备注名与分组，如想更改分组则可联系༺ཌༀ我要上南开ༀད༻或sunzeyang 行为恶劣的学生或教师关小黑屋，不可参与任何活动 本校开设积分表，日志，和皮皮虾合开的自习室，附属团，团队网站，讨论区，活动公示，法院等 祝大家做题愉快 真正的南开在这里 表扬榜：暂无 批评榜：暂无 有事请找 ID:4293588༺ཌༀ我要上南开ༀད༻ ID:4348708‮🐱‍🚀 ID:4888246sunzeyang

非原创

有成员私信问我：哎，魔力坤鸡，你们的Dev.坤++是怎么弄的呀？ 这不就来了吗，干货，接好！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先，我要普及一下define是怎么用的 我们的坤++暂时只要无参宏定义哈 无参宏定义 无参宏的宏名后不带参数。 其定义的一般形式为： #define 标识符 字符串 其中的“#”表示这是一条预处理命令。凡是以“#”开头的均为预处理命令。“define”为宏定义命令。“标识符”为所定义的宏名。“字符串”可以是常数、表达式、格式串等。 例如： #define MAXNUM 99999 这样MAXNUM就被简单的定义为99999。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 然后就进入正题了 众所周知，Dev.坤++中，没有多少是不用坤表示的，所以模板接好了！ 比如我可以做一个a+b 好了，这就是Dev.坤++2.5的框架了，赶紧拿去用吧！不要让我失望哦！ （嘘，有意见下面提……）

题目描述 医院处理挂号的规则如下:年龄 60 岁及以上的老人优先级高于普通人，同优先级下，按挂号顺序进行处理，小的在前。 现在给出 n 个人的姓名，年龄，挂号顺序，请给出接待顺序。 输入格式 第一行一个整数 n，表示人数。 接下来 n 行，每行包括一串字符和两个整数，代表年龄和挂号顺序。 输出格式 n 行，每行一个姓名，表示接待顺序。 输入输出样例 输入#1 5 张三 20 1 李四 80 2 王五 60 3 孙六 61 4 李七 60 5 输出#1 李四 孙六 张三 王五 李七 说明/提示 n < 200，姓名长度 < 10，年龄为 < 100 的正整数，挂号顺序为 < 10000 的正整数。

今日我准备弄一个比赛，名称：“#深深生米欢乐赛” 比赛内容： 比赛内容是多方面的，可能很多在我团队的明白在我团队会有两个组，一个是深深的生米组，另外一个是刷题组，这两个组对标的标准是不一样的，深深的生米组会时常收到一些关于深深的作业，刷题组（只有大佬才能加）会得到一些比较难的题目，会有点挑战性。 搞比赛的目的： 我这次搞竞赛的目的是为了中和两个组的实力，所以我在这次比赛中会出刷题组的题和深深的题轮流出，让大家能够更了解自己是更适合刷题组还是深深生米组 评分标准： 本次比赛的评分标准分为两种{ 1.深深的标准：有10道题，按100%来算，每做对一道题得分10% 2.刷题组标准：10道题，每道题20分，总共100分 } 加入方式： 点击下面图片加入： 关于题解： 1.由于深深生米组比赛有点难度，所以允许各位看题解 2.刷题组比赛内容为原创题，我会在第一时间发题解，谢谢大家了！

T1；糖果店（CANDY） 题干 P14635 [NOIP2025] 糖果店 题目描述 小 X 开了一家糖果店，售卖 nnn 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 iii (1≤i≤n1 \le i \le n1≤i≤n) 种糖果，购买第一颗的价格为 xix_ixi 元，第二颗为 yiy_iyi 元，第三颗又变回 xix_ixi 元，第四颗则为 yiy_iyi 元，以此类推。 小 R 带了 mmm 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出，mmm 元钱能购买的糖果数量的最大值。 输入格式 输入的第一行包含两个正整数 n,mn, mn,m，代表糖果的种类数和小 R 的钱数。 输入的第 i+1i+1i+1 (1≤i≤n1 \le i \le n1≤i≤n) 行包含两个正整数 xi,yix_i, y_ixi ,yi ，分别表示购买第 iii 种糖果时第奇数颗的价格和第偶数颗的价格。 输出格式 输出一行一个非负整数，表示 mmm 元钱能购买的糖果数量的最大值。 输入输出样例 #1 输入 #1 输出 #1 输入输出样例 #2 输入 #2 输出 #2 说明/提示 【样例 1 解释】 小 R 可以购买 4 颗第一种糖果，共花费 4+1+4+1=104 + 1 + 4 + 1 = 104+1+4+1=10 元。 【样例 2 解释】 小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1+2+12=151 + 2 + 12 = 151+2+12=15 元。 【样例 3】 见选手目录下的 candy/candy3.in 与 candy/candy3.ans。 该样例满足测试点 666 的约束条件。 【样例 4】 见选手目录下的 candy/candy4.in 与 candy/candy4.ans。 该样例满足测试点 8,98,98,9 的约束条件。 【样例 5】 见选手目录下的 candy/candy5.in 与 candy/candy5.ans。 该样例满足测试点 11,1211,1211,12 的约束条件。 【样例 6】 见选手目录下的 candy/candy6.in 与 candy/candy6.ans。 该样例满足测试点 131313 的约束条件。 【样例 7】 见选手目录下的 candy/candy7.in 与 candy/candy7.ans。 该样例满足测试点 17,1817,1817,18 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤n≤1051 \le n \le 10^51≤n≤105； * 1≤m≤10181 \le m \le 10^{18}1≤m≤1018； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 1≤xi,yi≤1091 \le x_i, y_i \le 10^91≤xi ,yi ≤109。 ::cute-table{tuack} 测试点编号 n≤n \len≤ m≤m \lem≤ 特殊性质 111 111 101010 无 2,32,32,3 222 202020 ^ 4,54,54,5 101010 ^ ^ 666 10210^2102 10210^2102 A 777 ^ ^ B 8,98,98,9 ^ ^ 无 101010 10310^3103 10410^4104 A 11,1211,1211,12 ^ ^ B 131313 ^ ^ 无 141414 10510^5105 10910^9109 A 15,1615,1615,16 ^ ^ B 17,1817,1817,18 ^ ^ 无 19,2019,2019,20 ^ 101810^{18}1018 ^ 特殊性质 A：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 xi=yix_i = y_ixi =yi 。 特殊性质 B：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 xi≥yix_i \ge y_ixi ≥yi 。 入口 洛谷入口：P14635 [NOIP2025] 糖果店 ACGO入口：A92615 [NOIP2025] 糖果店 解析 记所有糖果中 xi+yix_i + y_ixi +yi  最小的糖果为 ttt，最终选择的结果可看作选取 2k2k2k 个糖果 ttt 与其余若干糖果各一个，需满足 2kt+xp1+xp2+…+xpc≤m2kt + x_{p_1} + x_{p_2} + \ldots + x_{p_c} \leq m2kt+xp1 +xp2 +…+xpc ≤m。由于仅买一个的糖果应选取 xxx 最小的一部分，因此先将所有糖果按 xxx 的大小排序，枚举购买 111 个的糖果数量，剩余钱用于成对购买糖果 ttt（两个两个买），即可得到最大购买数量。 标程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2：清仓甩卖（SALE） 题干 P14636 [NOIP2025] 清仓甩卖 题目背景 额外提供了 0.5 秒的时限。 题目描述 小 X 的糖果促销策略很成功，现在糖果店只剩下了 nnn 颗糖果，其中第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果的原价为 aia_iai 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 111 元或 222 元。设第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果的清仓价格为 wi∈{1,2}w_i \in \{1,2\}wi ∈{1,2} 元，则它的性价比被定义为原价与清仓价格的比值，即 aiwi\frac{a_i}{w_i}wi ai 。 小 R 又带了 mmm 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大，于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若小 R 在考虑第 iii (1≤i≤n1 \le i \le n1≤i≤n) 颗糖果时剩余的钱至少为 wiw_iwi 元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则小 R 会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则小 R 会先考虑编号较小的糖果。 例如，若小 X 的糖果商店剩余 333 颗糖果，原价分别为 a1=1a_1=1a1 =1，a2=3a_2=3a2 =3，a3=5a_3=5a3 =5，而清仓价格分别为 w1=w2=1w_1=w_2=1w1 =w2 =1，w3=2w_3=2w3 =2，则性价比分别为 1,3,521, 3, \frac{5}{2}1,3,25 。因此小 R 会先考虑第 222 颗糖果，然后考虑第 333 颗糖果，最后考虑第 111 颗糖果。 小 R 想知道，在小 X 的所有 2n2^n2n 种定价方案中，有多少种定价方案使得他按照上述购买策略能购买到的糖果的原价总和最大。你需要帮助小 R 求出满足要求的定价方案的数量。由于答案可能较大，你只需要求出答案对 998,244,353998,244,353998,244,353 取模后的结果。 输入格式 本题包含多组测试数据。 输入的第一行包含两个非负整数 c,tc, tc,t，分别表示测试点编号与测试数据组数。c=0c=0c=0 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： * 第一行包含两个正整数 n,mn, mn,m，分别表示糖果的数量与小 R 的钱数； * 第二行包含 nnn 个正整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an ，分别表示每颗糖果的原价。 输出格式 对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价总和达到最大值的定价方案数对 998,244,353998,244,353998,244,353 取模后的结果。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 该样例即为【题目描述】中的例子。共有以下 666 种定价方案使得小 R 购买到的糖果原价总和最大，分别为： * w1=w2=w3=1w_1 = w_2 = w_3 = 1w1 =w2 =w3 =1，小 R 购买到的糖果原价总和为 888； * w1=w3=1w_1 = w_3 = 1w1 =w3 =1，w2=2w_2 = 2w2 =2，小 R 购买到的糖果原价总和为 666； * w1=1w_1 = 1w1 =1，w2=w3=2w_2 = w_3 = 2w2 =w3 =2，小 R 购买到的糖果原价总和为 555； * w2=w3=1w_2 = w_3 = 1w2 =w3 =1，w1=2w_1 = 2w1 =2，小 R 购买到的糖果原价总和为 888； * w3=1w_3 = 1w3 =1，w1=w2=2w_1 = w_2 = 2w1 =w2 =2，小 R 购买到的糖果原价总和为 555； * w1=w2=w3=2w_1 = w_2 = w_3 = 2w1 =w2 =w3 =2，小 R 购买到的糖果原价总和为 555。 注意：若 w1=w2=1w_1 = w_2 = 1w1 =w2 =1，w3=2w_3 = 2w3 =2，则小 R 会依次购买第 222 颗和第 111 颗糖果，原价总和为 444，但小 R 可以只购买第 333 颗糖果，原价总和为 555。因此该定价方案无法使小 R 购买到的糖果的原价总和达到最大值。 【样例 2】 见选手目录下的 sale/sale2.in 与 sale/sale2.ans。 该样例满足测试点 1∼31 \sim 31∼3 的约束条件。 【样例 3】 见选手目录下的 sale/sale3.in 与 sale/sale3.ans。 该样例满足测试点 4,54,54,5 的约束条件。 【样例 4】 见选手目录下的 sale/sale4.in 与 sale/sale4.ans。 该样例满足测试点 7∼97 \sim 97∼9 的约束条件。 【样例 5】 见选手目录下的 sale/sale5.in 与 sale/sale5.ans。 该样例满足测试点 10∼1210 \sim 1210∼12 的约束条件。 【样例 6】 见选手目录下的 sale/sale6.in 与 sale/sale6.ans。 该样例满足测试点 131313 的约束条件。 【样例 7】 见选手目录下的 sale/sale7.in 与 sale/sale7.ans。 该样例满足测试点 14,1514,1514,15 的约束条件。 【样例 8】 见选手目录下的 sale/sale8.in 与 sale/sale8.ans。 该样例满足测试点 171717 的约束条件。 【样例 9】 见选手目录下的 sale/sale9.in 与 sale/sale9.ans。 该样例满足测试点 19,2019,2019,20 的约束条件。 【样例 10】 见选手目录下的 sale/sale10.in 与 sale/sale10.ans。 该样例满足测试点 21∼2321 \sim 2321∼23 的约束条件。 【样例 11】 见选手目录下的 sale/sale11.in 与 sale/sale11.ans。 该样例满足测试点 24,2524,2524,25 的约束条件。 【数据范围】 设 NNN 为单个测试点内所有测试数据的 nnn 的和。对于所有测试数据，均有： * 1≤t≤5×1041 \le t \le 5 \times 10^41≤t≤5×104； * 1≤n≤5,0001 \le n \le 5,0001≤n≤5,000，N≤5×104N \le 5 \times 10^4N≤5×104，1≤m≤2n−11 \le m \le 2n - 11≤m≤2n−1； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 1≤ai≤1091 \le a_i \le 10^91≤ai ≤109。 ::cute-table{tuack} 测试点编号 n≤n \len≤ N≤N \leN≤ mmm 特殊性质 1∼31\sim 31∼3 555 5,0005{,}0005,000 ≤2n−1\le 2n - 1≤2n−1 无 4,54,54,5 101010 ^ ^ ^ 666 404040 ^ ^ ^ 7∼97\sim 97∼9 300300300 ^ =2=2=2 ^ 10∼1210\sim 1210∼12 ^ ^ ≤2n−1\le 2n - 1≤2n−1 B 131313 ^ ^ ^ 无 14,1514,1514,15 10310^3103 10410^4104 =2=2=2 ^ 161616 ^ ^ =2n−1=2n - 1=2n−1 ^ 171717 ^ ^ =2n−2=2n - 2=2n−2 ^ 181818 ^ ^ ≤2n−1\le 2n - 1≤2n−1 A 19,2019,2019,20 ^ ^ ^ B 21∼2321\sim 2321∼23 ^ ^ ^ 无 24,2524,2524,25 5,0005{,}0005,000 5×1045 \times 10^45×104 ^ ^ 特殊性质 A：a1=a2=⋯=ana_1 = a_2 = \cdots = a_na1 =a2 =⋯=an 。 特殊性质 B：对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 ai>5×108a_i > 5 \times 10^8ai >5×108。 入口 洛谷：P14636 [NOIP2025] 清仓甩卖 ACGO：A92616.[NOIP2025] 清仓甩卖 解析 1. 不优方案的条件 当存在三种糖果 X,Y,ZX,Y,ZX,Y,Z 满足 * wX=wZ=1w_X = w_Z = 1wX =wZ =1，wY=2w_Y = 2wY =2 * aX+aZ<aYa_X + a_Z < a_YaX +aZ <aY  且 aZ<12aY<aX<aYa_Z < \frac{1}{2}a_Y < a_X < a_YaZ <21 aY <aX <aY 贪心策略会因 XXX 性价比较高而错选 X,ZX,ZX,Z，忽略总收益更高的 YYY（ZZZ 可不存在）。核心问题是考虑 YYY 时仅剩 111 元，无法购买。 2. 方案数计算枚举糖果 * X,YX,YX,Y，将其他糖果分类： 1. 原价大于 aYa_YaY  的糖果(c1(c_1(c1  个）：必被选中，消耗 111 或 222 元 2.原价在 aX,aYa_X,a_YaX ,aY  之间的糖果(c2(c_2(c2  个)：出清价为 111 元时被选中，否则忽略 * 不合法方案数为 Cc1+c2m−c1−2C_{c_1+c_2}^{m-c_1-2}Cc1 +c2 m−c1 −2 （保证考虑 YYY 时仅剩 $1￥ 元）考 * 虑 ZZZ 的取值方案（含不存在情况），总方案数为 2c3×Cc1+c2m−c1−22^{c_3} \times C_{c_1+c_2}^{m-c_1-2}2c3 ×Cc1 +c2 m−c1 −2 ，其中 c3c_3c3  为原价不低于 ZZZ 的糖果数 标程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3：树的价值（TREE） 题干 P14637 [NOIP2025] 树的价值 题目描述 给定一棵 nnn 个结点的有根树，其中结点 1 为根，结点 iii (2≤i≤n2 \le i \le n2≤i≤n) 的父亲结点为结点 pip_ipi 。 对于 1≤i≤n1 \le i \le n1≤i≤n，定义结点 iii 的深度 did_idi 为结点 1 到结点 iii 的简单路径的边数，也就是说，d1=0d_1 = 0d1 =0，di=dpi+1d_i = d_{p_i} + 1di =dpi +1 (2≤i≤n2 \le i \le n2≤i≤n)。定义有根树的高度 hhh 为所有结点的深度的最大值，即 h=max⁡i=1ndih = \max_{i=1}^{n} d_ih=maxi=1n di 。 给定高度的上界 mmm。在本题中，给定的有根树的高度不超过 mmm。 你需要给每个结点设置一个非负整数作为它的权值。对于 1≤i≤n1 \le i \le n1≤i≤n，若结点 iii 的权值为 aia_iai ，令 SiS_iSi 表示结点 iii 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 ∑i=1nmex(Si)\sum_{i=1}^{n} \mathrm{mex}(S_i)∑i=1n mex(Si )，其中 mex(S)\mathrm{mex}(S)mex(S) 表示不在集合 SSS 中的最小非负整数。例如，在下图中，若设置 a1=3a_1 = 3a1 =3，a2=2a_2 = 2a2 =2，a3=a4=0a_3 = a_4 = 0a3 =a4 =0，a5=1a_5 = 1a5 =1，则 S1={0,1,2,3}S_1 = \{0,1,2,3\}S1 ={0,1,2,3}，S2={0,1,2}S_2 = \{0,1,2\}S2 ={0,1,2}，S3={0}S_3 = \{0\}S3 ={0}，S4={0}S_4 = \{0\}S4 ={0}，S5={1}S_5 = \{1\}S5 ={1}，树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 94+3+1+1+0=9。 你需要求出，在所有权值设置方案中，树的价值的最大值。 输入格式 本题包含多组测试数据。 输入的第一行包含一个正整数 ttt，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： * 第一行包含两个正整数 n,mn, mn,m，分别表示结点数量与高度的上界。 * 第二行包含 n−1n - 1n−1 个正整数 p2,p3,…,pnp_2, p_3, \ldots, p_np2 ,p3 ,…,pn ，分别表示每个结点的父亲结点。 输出格式 对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 该样例共包含两组测试数据。 对于第一组测试数据，可以设置 a1=3a_1 = 3a1 =3，a2=2a_2 = 2a2 =2，a3=a4=0a_3 = a_4 = 0a3 =a4 =0，a5=1a_5 = 1a5 =1，则树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 94+3+1+1+0=9。 对于第二组测试数据，可以设置 a1=4a_1 = 4a1 =4，a2=3a_2 = 3a2 =3，a4=2a_4 = 2a4 =2，a3=a6=1a_3 = a_6 = 1a3 =a6 =1，a5=a7=0a_5 = a_7 = 0a5 =a7 =0，则树的价值为 5+4+2+0+1+0+1=135 + 4 + 2 + 0 + 1 + 0 + 1 = 135+4+2+0+1+0+1=13。 【样例 2】 见选手目录下的 tree/tree2.in 与 tree/tree2.ans。 该样例满足测试点 3,43,43,4 的约束条件。 【样例 3】 见选手目录下的 tree/tree3.in 与 tree/tree3.ans。 该样例满足测试点 7,87,87,8 的约束条件。 【样例 4】 见选手目录下的 tree/tree4.in 与 tree/tree4.ans。 该样例满足测试点 13,1413,1413,14 的约束条件。 【样例 5】 见选手目录下的 tree/tree5.in 与 tree/tree5.ans。 该样例满足测试点 18,1918,1918,19 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤t≤51 \le t \le 51≤t≤5； * 2≤n≤8,0002 \le n \le 8,0002≤n≤8,000，1≤m≤min⁡(n−1,800)1 \le m \le \min(n - 1, 800)1≤m≤min(n−1,800)； * 对于所有 2≤i≤n2 \le i \le n2≤i≤n，均有 1≤pi≤i−11 \le p_i \le i - 11≤pi ≤i−1； * 给定的有根树的高度不超过 mmm。 ::cute-table{tuack} 测试点编号 n≤n \len≤ m≤m \lem≤ 1,21,21,2 777 n−1n-1n−1 3,43,43,4 131313 ^ 5,65,65,6 181818 ^ 7,87,87,8 404040 ^ 9,109,109,10 120120120 ^ 11,1211,1211,12 360360360 ^ 13,1413,1413,14 4,0004{,}0004,000 222 15∼1715\sim 1715∼17 ^ 101010 18,1918,1918,19 ^ 505050 20∼2520\sim 2520∼25 8,0008{,}0008,000 800800800 入口 ACGO入口：A92617.[NOIP2025] 树的价值 洛谷入口：P14637 [NOIP2025] 树的价值 解析 1. 核心定义 * 白点：不清空未分配权值节点，继承子树的 mex 值 * 黑点：清空未分配权值节点，增大 mex 值 * 状态定义： f[i][j][k]f[i][j][k]f[i][j][k]：白点i是树链第j个点，贡献为kkk的最大价值 g[i][j]g[i][j]g[i][j]：黑点i是树链第j个点的最大贡献2. 优化思路 * 性质：j≤kj \leq kj≤k（否则选黑点更优），k−jk-jk−j 不超过子树最深深度用长链剖分优化 DP 转移，时间复杂度O(nm)O(nm)O(nm)后缀加操作通过数据结构优化，最终时间复杂度O(nmlog⁡n)O(nm\log n)O(nmlogn) 标程 76PTS ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 序列询问（QUERY） 题干 P14638 [NOIP2025] 序列询问 题目背景 额外提供了 1 秒的时限。 题目描述 给定一个长度为 nnn 的整数序列 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 。 有 qqq 次询问，其中第 jjj (1≤j≤q1 \le j \le q1≤j≤q) 次询问将会给出 Lj,RjL_j, R_jLj ,Rj (1≤Lj≤Rj≤n1 \le L_j \le R_j \le n1≤Lj ≤Rj ≤n)。定义区间 [l,r][l, r][l,r] (1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n) 是极好的，当且仅当区间 [l,r][l, r][l,r] 的长度在 [Lj,Rj][L_j, R_j][Lj ,Rj ] 内，即 Lj≤r−l+1≤RjL_j \le r - l + 1 \le R_jLj ≤r−l+1≤Rj 。定义区间 [l,r][l, r][l,r] (1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n) 的权值为 ∑i=lrai\sum_{i=l}^{r} a_i∑i=lr ai 。对于所有 i=1,2,…,ni = 1, 2, \ldots, ni=1,2,…,n，求出所有包含 iii 的极好区间的最大权值，即 max⁡1≤l≤i≤r≤n{∑i=lrai∣Lj≤r−l+1≤Rj}\max_{1 \le l \le i \le r \le n} \{ \sum_{i=l}^{r} a_i \mid L_j \le r - l + 1 \le R_j \}max1≤l≤i≤r≤n {∑i=lr ai ∣Lj ≤r−l+1≤Rj }。 输入格式 输入的第一行包含一个正整数 nnn，表示序列长度。 输入的第二行包含 nnn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_na1 ,a2 ,…,an 。 输入的第三行包含一个正整数 qqq，表示询问次数。 输入的第 j+3j + 3j+3 (1≤j≤q1 \le j \le q1≤j≤q) 行包含两个正整数 Lj,RjL_j, R_jLj ,Rj ，表示第 jjj 次询问。 输出格式 对于每次询问，设包含 iii (1≤i≤n1 \le i \le n1≤i≤n) 的极好区间的最大权值为 kik_iki ，输出一行一个非负整数，表示 ⨁i=1n((i×ki) mod 264)\bigoplus_{i=1}^{n} \left( (i \times k_i) \bmod 2^{64} \right)⨁i=1n ((i×ki )mod264)，其中 ⊕\oplus⊕ 表示二进制按位异或。注意：对于任意整数 xxx，存在唯一的非负整数 x′x'x′ 满足 x′≡x(mod264)x' \equiv x \pmod{2^{64}}x′≡x(mod264) 且 0≤x′≤264−10 \le x' \le 2^{64} - 10≤x′≤264−1，则记 x mod 264=x′x \bmod 2^{64} = x'xmod264=x′。 输入输出样例 #1 输入 #1 输出 #1 说明/提示 【样例 1 解释】 对于第 111 次询问： * 包含 111 的极好区间为 [1,1][1,1][1,1] 和 [1,2][1,2][1,2]，权值分别为 2,62,62,6； * 包含 222 的极好区间为 [1,2][1,2][1,2]，[2,2][2,2][2,2] 和 [2,3][2,3][2,3]，权值分别为 6,4,−16,4,-16,4,−1； * 包含 333 的极好区间为 [2,3][2,3][2,3]，[3,3][3,3][3,3] 和 [3,4][3,4][3,4]，权值分别为 −1,−5,−4-1,-5,-4−1,−5,−4； * 包含 444 的极好区间为 [3,4][3,4][3,4] 和 [4,4][4,4][4,4]，权值分别为 −4,1-4,1−4,1。 因此 k1=6k_1 = 6k1 =6，k2=6k_2 = 6k2 =6，k3=−1k_3 = -1k3 =−1，k4=1k_4 = 1k4 =1。 对于第 2 次询问，k1=2k_1 = 2k1 =2，k2=2k_2 = 2k2 =2，k3=2k_3 = 2k3 =2，k4=2k_4 = 2k4 =2。 对于第 3 次询问，k1=6k_1 = 6k1 =6，k2=6k_2 = 6k2 =6，k3=2k_3 = 2k3 =2，k4=2k_4 = 2k4 =2。 【样例 2】 见选手目录下的 query/query2.in 与 query/query2.ans。 该样例满足测试点 2,32,32,3 的约束条件。 【样例 3】 见选手目录下的 query/query3.in 与 query/query3.ans。 该样例满足测试点 444 的约束条件。 【样例 4】 见选手目录下的 query/query4.in 与 query/query4.ans。 该样例满足测试点 6,76,76,7 的约束条件。 【样例 5】 见选手目录下的 query/query5.in 与 query/query5.ans。 该样例满足测试点 8∼108 \sim 108∼10 的约束条件。 【样例 6】 见选手目录下的 query/query6.in 与 query/query6.ans。 该样例满足测试点 11,1211,1211,12 的约束条件。 【样例 7】 见选手目录下的 query/query7.in 与 query/query7.ans。 该样例满足测试点 131313 的约束条件。 【样例 8】 见选手目录下的 query/query8.in 与 query/query8.ans。 该样例满足测试点 16∼2016 \sim 2016∼20 的约束条件。 【数据范围】 对于所有测试数据，均有： * 1≤n≤5×1041 \le n \le 5 \times 10^41≤n≤5×104，1≤q≤1,0241 \le q \le 1,0241≤q≤1,024； * 对于所有 1≤i≤n1 \le i \le n1≤i≤n，均有 ∣ai∣≤105|a_i| \le 10^5∣ai ∣≤105； * 对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 1≤Lj≤Rj≤n1 \le L_j \le R_j \le n1≤Lj ≤Rj ≤n。 ::cute-table{tuack} 测试点编号 n≤n \len≤ q≤q \leq≤ 特殊性质 111 10310^3103 111 无 2,32,32,3 3,0003{,}0003,000 505050 ^ 444 10410^4104 128128128 ^ 555 3×1043 \times 10^43×104 512512512 ^ 6,76,76,7 5×1045 \times 10^45×104 1,0241{,}0241,024 A 8∼108 \sim 108∼10 ^ 512512512 B 11,1211,1211,12 ^ ^ C 131313 ^ 1,0241{,}0241,024 D 14,1514,1514,15 ^ ^ E 16∼2016 \sim 2016∼20 ^ ^ 无 特殊性质 A：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj=RjL_j = R_jLj =Rj 。 特殊性质 B：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Rj≤32R_j \le 32Rj ≤32。 特殊性质 C：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj≤16L_j \le 16Lj ≤16 且 Rj≥n−1000R_j \ge n - 1000Rj ≥n−1000。 特殊性质 D：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj>n/2L_j > n/2Lj >n/2。 特殊性质 E：对于所有 1≤j≤q1 \le j \le q1≤j≤q，均有 Lj>n/4L_j > n/4Lj >n/4。 入口 洛谷入口P14638 [NOIP2025] 序列询问 ACGO入口A92618.[NOIP2025] 序列询问 做法一：分块预处理 1.预处理区间 [ql,qr]=[2k,2k+1−1][q_l, q_r] = [2^k, 2^{k+1}-1][ql ,qr ]=[2k,2k+1−1] 的答案 2.询问时将区间拆分为整块（预处理结果）和散块（满足 2ql>qr）3.2q_l > q_r） 3.2ql >qr ）3.散块通过 O(1)O(1)O(1) RMQ 求解，总时间复杂度 O(nlog⁡n+nq)O(n \log n + nq)O(nlogn+nq) 做法二：二维区间拆分 * 将可行区间拆分为两类三角形： 包含 [l,r][l,r][l,r] 且长度 ≤ LLL被 [l,r][l,r][l,r] 包含且长度 ≥ LLL枚举边界区间，结合前缀 min / 后缀 max 和单调栈维护覆盖关系，总时间复杂度 O(n)O(n)O(n) per query ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感悟 真的，难度是越来越大了，2026年难度不堪设想

> 前言（跳过不影响您观看）: 这个号是某人的小号，请不要光凭头像判断。这个名字是我同学的外号（经过本人同意）。本号专门用来打欢乐赛。个人感觉这次欢乐赛很水。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 本篇一共包含 666 道题。

【先叠个甲：内容纯属乱搞仅供娱乐，实测在洛谷会Unaccepted，抱着看乐子的心态看就行】 把两个数看成系数多项式 例一：123→3+2x+1x2123→3+2x+1x²123→3+2x+1x2 (系数[3,2,1]，x代表10的幂)(系数 [3,2,1]，x 代表 10 的幂)(系数[3,2,1]，x代表10的幂) 例二：45→5+4x45→5+4x45→5+4x (系数[5,4])(系数 [5,4])(系数[5,4]) 众所周知，两数相加 = 多项式系数对应相加 例：123+45→(3+5)+(2+4)x+1x2→8+6x+1x2123+45→(3+5)+(2+4) x+1x²→8+6x+1x²123+45→(3+5)+(2+4)x+1x2→8+6x+1x2 对应 168168168 正常直接加系数时间复杂度为 O(N)O(N)O(N)，但我要想出来一个比 O(N)O(N)O(N) 更牛逼的代码，于是我想到了FFT： 时间复杂度：O(Nlog⁡N)O(N \log N)O(NlogN) 但这还是不够，我们可以继续优化为 O(N2)O(N²)O(N2) 于是乎我们可以放弃 FFT，改用离散傅里叶变换，也就是 DFT 直接算 DFT 和 逆 DFT，其复杂度就达到了 O(N2)O(N²)O(N2) 离散傅里叶变换（DFT）的定义如下： 对长度为 nnn 的序列 a[0..n−1]a[0..n-1]a[0..n−1]，其 DFT 结果 A[0..n−1]A[0..n-1]A[0..n−1] 满足： A[k]=∑j=0n−1a[j]⋅Wnjk(0≤k<n)A[k] = \sum_{j=0}^{n-1} a[j] \cdot W_n^{jk} \quad (0 \leq k < n)A[k]=∑j=0n−1 a[j]⋅Wnjk (0≤k<n) 其中： Wn=e−2πi/nW_n = e^{-2\pi i / n}Wn =e−2πi/n 计算每个 A[k]A[k]A[k] 要遍历 nnn 个 a[j]a[j]a[j] ，做 nnn 次复数乘法和加法，要算 nnn 个 A[k]A[k]A[k] 逆离散傅里叶变换（IDFT）的定义类似，只是旋转因子变为 Wn−jkWₙ^{-jk}Wn−jk ，最后除以 nnn 为了达到 O(N2)O(N²)O(N2) 的时间复杂度，我将原代码中的 FFT 替换为 DFT/IDFT： 时间复杂度：O(N2)O(N²)O(N2) ACGO神机：请输入文本。