为什么用并查集做AC不了

全网最详细赌罐头教程重磅来袭！

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ rt。 > 此贴持续更新中，每十天会更新一次总概率 作为一个已经赌过25次罐头的人，我认为有必要写一篇教程，造福人类，让大家不当守财奴！ 本人已经买过25次“AC之神的祝福”，得出数据如下： 我的收益：901⇒2567\color{red}我的收益：901\Rightarrow2567我的收益：901⇒2567 收益率：约为185%\color{red}收益率：约为185\%收益率：约为185% 注：以上数据包含我每日点赞、评论、做题得到的罐头，但去掉后收益率也不低于170%170\%170% 以下是详细数据： 25次中： 66：222次，8%8\%8% 99：555次，20%20\%20% 199：121212次，48%48\%48% 399：333次，12%12\%12% 888：333次，12%12\%12% 可以看出，概率排名为： 199>99>399=888>66 但是！根据我的经验，不止这么简单，于是我们分析我每天的收益： DAY 1 199三个+399一个+888一个，总收益889，收益率89%89\%89% DAY2 66一个+99四个，总收益-533，收益率−53%-53\%−53% DAY 3 199五个，总收益0，收益率0%0\%0% DAY4 66一个+199两个+399一个+888一个，总收益756，收益率76%76\%76% 需要说明的是，我这次是先买了四个，开完后又买了一个\color{red}需要说明的是，我这次是先买了四个，开完后又买了一个需要说明的是，我这次是先买了四个，开完后又买了一个 DAY5 99一个+199两个+399一个+888一个，总收益789，收益率79%79\%79% 需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完\color{red}需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完需要说明的是，我这次是先买了三个并开完，开完后又买了两个并开完 经过分析，可以发现： * 第一天收益极高，接近90%90\%90%，且稳赚不赔，有888 * 第二天收益低，全部亏完 * 第三天收益为0，不亏不赚 * 第四天以一批全赚，且有888 * 第四天第二批亏 * 第五天第一批有赚有亏，有888 * 第五天第二批小赚 于是，我总结出几条规律： 1. 各个结果的概率绝非均等，也没有规律，只与购买批次有关系！\color{red}各个结果的概率绝非均等，也没有规律，只与购买批次有关系！各个结果的概率绝非均等，也没有规律，只与购买批次有关系！ 2. 如果一批中有888，则那一批大概率全赚\color{red}如果一批中有888，则那一批大概率全赚如果一批中有888，则那一批大概率全赚 3. 如果上一批大赚，则这一批会亏或小赚\color{red}如果上一批大赚，则这一批会亏或小赚如果上一批大赚，则这一批会亏或小赚 4. 如果上批亏，则这批收益率为正 5. 收益率若为正，则必大于70%70\%70% 6. 399常伴随888 注：一批是指购买的一批，即只买一个就是单独成批 因此，可以给出建议： 1. 如果一批中有888，那么果断开完\color{red}如果一批中有888，那么果断开完如果一批中有888，那么果断开完 2. 如果上一批大赚，那么这一批少买，来抵消会亏的debuff\color{red}如果上一批大赚，那么这一批少买，来抵消会亏的debuff如果上一批大赚，那么这一批少买，来抵消会亏的debuff 3. 如果上批亏，则这批大胆全买，吃满buff\color{red}如果上批亏，则这批大胆全买，吃满buff如果上批亏，则这批大胆全买，吃满buff 4. 如果连亏两次，就把剩下的留到第二天开\color{red}如果连亏两次，就把剩下的留到第二天开如果连亏两次，就把剩下的留到第二天开 5. 出了888千万别上头，不要有“乘胜追击”的心态\color{red}出了888千万别上头，不要有“乘胜追击”的心态出了888千万别上头，不要有“乘胜追击”的心态 注：我还没有试过一次买五个以上，留到第二天开，因此不要轻易尝试 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY6 今天我分两批买，2+3 第一批199+66，第二批888+399+66，总收益623，收益率63%63\%63% 再次验证了399常伴随888出现 创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！\color{purple}创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！创作不易（成本巨大），留个赞吧，我们一起拿罐头，双赢！

官方题解 | 挑战赛#27

挑战赛27题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的矩形 入门 T2 午枫的字符串移动2 入门 T3 午枫打砖块 普及/提高- T4 午枫的子序列之和 普及/提高- T5 午枫的星星树 普及- T6 午枫的数字华容道 普及/提高- T1 午枫的矩形 题目大意 给定一个矩阵，判断这个矩阵的任意子矩阵是否满足 左上角的数+右下角的数≤左下角的数+右上角的数左上角的数+右下角的数\leq 左下角的数+右上角的数左上角的数+右下角的数≤左下角的数+右上角的数 。 解题思路 由于数据范围只有 1≤n,m≤501\leq n,m\leq 501≤n,m≤50 ，所有直接四层循环嵌套枚举左上角和右下角，同时也能知道左下角和右上角的坐标，直接计算判断即可。 参考代码 T2 午枫的字符串移动2 题目大意 给定一个字符串，可以进行左移和右移的操作任意次，找到所有可以得到的字符串中字典序最小以及最大的字符串。 解题思路 因为可以操作任意次，所以只要单独往一个方向不断移动并且更新字典序最小和最大的字符串即可。 这里可以直接使用 string 类型进行移动的操作，并且也可以使用 min 和 max 函数进行比较字典序大小。 参考答案 T3 午枫打砖块 题目大意 给定 nnn 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 ddd ，并且将这 ddd 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。 解题思路 这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。 参考答案 T4 午枫的子序列之和 题目大意 给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。 解题思路 首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。 枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。 参考代码 方法一：map 方法二：离散化 T5 午枫的星星树 题目大意 给定一棵树，问是否存在一个点与其他所有点直接相连。 解题思路 记录所有点的度数，判断是否存在一个点的度数为 n−1n-1n−1 即可。 参考代码 T6 午枫的数字华容道 题目大意 有 999 个点 mmm 条边的无向图，其中有 888 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 1∼81\sim 81∼8 分别放在顶点 1∼81\sim 81∼8 上的最少操作次数。 解题思路 我们可以将 999 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 111 存放数字 222 ，顶点 222 存放数字 555 ，依此类推，特殊地，数字 000 表示该点为空。那么终点就可以用 123456780 表示。 由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 bfsbfsbfs 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。 参考代码

AC罐头商店使用说明

AC罐头商店 使用说明 💰 一、罐头获取方式 刷题赚罐头 🎯 获取方式 罐头奖励 说明 攻克新题 1-7罐头/题 每成功攻克一道自己未AC的官方题目，根据题目难度获得罐头：• 入门：1罐头；• 普及-：2罐头；普及/提高-：3罐头；• 普及+/提高：4罐头；• 提高+/省选：5罐头；• NOI/CTSC级别：7罐头；每日上限：5题（即每日最多通过5道新题获得罐头） 题目首杀 5-35罐头/题 首位攻破“零通过”的官方题目，根据题目难度获得• 入门：5罐头；• 普及-：10罐头；• 普及/提高-：15罐头• 普及+/提高：20罐；• 提高+/省选：25罐头；• NOI/CTSC级别：35罐头 ；每日上限：5题（即每日最多通过5道首杀获得罐头） 首次竞赛报名 20罐头 用户第一次报名ACGO的官方竞赛时获得 排位等级晋升 100-800罐头/级 排位等级从上一级晋升到下一级时获得（每个等级仅奖励一次）：• 青铜→白银：100罐头；• 白银→黄金：200罐头；• 黄金→铂金：300罐头；• 铂金→钻石：400罐头；• 钻石→大师：600罐头；• 大师→王者：800罐头 天梯闯关过关 1-200罐头/关 每通过一关天梯闯关即可获得罐头，奖励金额随关卡难度递增，具体以关卡实际显示为准 活跃赚罐头 🎪 获取方式 罐头奖励 每日上限 每日点赞 1罐头/次 5次（5罐头） 每日评论 1罐头/次 5次（5罐头） 每日收藏题单 1罐头/次 5次（5罐头） 帖子被点赞 1罐头/次 10次（10罐头） 题单被收藏 5罐头/次 10次（50罐头） 每日活跃罐头上限：75罐头（5+5+5+10+50） 运营与贡献 🏆 获取方式 罐头奖励 说明 管理员手动发放 50-5000罐头 适用于以下场景：• 参与各类赛事并按赛事规则分配奖励；• 贡献优质题解、技术分享等内容被官方采纳；• 为社区发展提供特殊贡献等 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⏰ 二、罐头过期说明 滚动过期规则 AC罐头采用 【滚动过期】 方式管理： 1. 过期时间：每个自然年年底（12月31日23:59） 2. 过期范围：上一个年度获得且未消耗的罐头 3. 过期示例： * 2024年获得的罐头，将在2025年12月31日23:59过期 * 2025年获得的罐头，将在2026年12月31日23:59过期 * 以此类推... 过期提醒服务 * 提醒时间：每年12月1日开始 * 提醒方式： * 站内信通知 * 平台置顶帖子公告 * 提醒内容：“您有XXX罐头即将在12月31日到期，请尽快兑换！” 过期应对策略 1. 及时消费：不要过度囤积罐头，看到心仪商品及时兑换 2. 年度规划：每年11月开始规划罐头使用，避免年底过期浪费 3. 关注提醒：每年12月注意查看站内信和公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 三、重要提醒 1. 罐头与账号绑定，不可转让、不可交易 2. 商品一经使用，概不退换，请确认后再购买 3. 请合理安排罐头使用计划，避免过期造成浪费 每年年底记得清空旧罐头，迎接新一年的赚罐头之旅！ 🎉

非官方题解 | 嘻哈赛#1题解

WOC榜10了，感谢各位大佬观看，点赞的全家健康，长命百岁，比赛次次都AK 出了商城功能以后，凡是在我这个帖子里随便发几条评论、点个赞都能拿罐头！ 求官方批准@AC君 求点赞 点个赞吧 求你了求你了求你了求你了求你了求你了求你了求你了求你了 狗友们真是太6了！ 一起冲破榜一 回归正题： 非官方题解 | 嘻哈赛#1题解(C++&PYTHON) 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 可爱表情 入门 T2 自我介绍 入门 T3 生日祝福 入门 T4 比价格 入门 T1 可爱表情 题目大意： 直接输出5行表情： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T2 自我介绍 题目大意： 直接输出3行自我介绍的内容： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T3 生日祝福 题目大意： 按照以下固定格式： 注意：标点符号要使用中文标点 解题思路： c++版： 首先定义一个字符串用string和cin输入，在把祝福语和变量连接起来用cout一起输出 python版： 首先input()函数进行输入一个变量，在用printd的固定格式输出(如f格式化输出.....) 注意：标点符号要使用中文标点!!! 参考代码： c++版： python版： T4 比价格 题目大意： 同一本书，比较两家书店的价格，从中找出价格最低的输出那个价格 解题思路： c++版： 首先定义两个整数用int和cin输入，在用cout输出min比较两个数谁大谁小大结果 python版： 首先input()函数进行输入两个整数，在用print输出min比较两个数谁大谁小大结果 参考代码： python版： 团队传送门（你敢不敢加入此团队？） 如果要团队合作，请私信。

我的作文为什么才得了30分？！谁能帮Me

求评论和指点 老师到底是咋想的啊！！！ 《找回纯真》 著：墨白渊 记忆在时光的长河中流过，其中就有我找不回的星光。 一年级前，我还是那个爱穿彩色衣服、笑容透亮的孩子。可我现在却活成了曾经那个另厌恶的模样。波斯菊我没能留住，圣洁的土地上也开出了鲜红的黑玫瑰。 新学期开始前的周末，最好的朋友小墨为了庆祝，硬拉着我去了游乐场，说要陪我玩新出的项目。我本不想出门，却拗不过他的热情。毕竟，我与世界之间，隔着一层厚厚的玻璃。我能看见所有的热闹，但所有的声音都是闷响，所有的温度都无法传导。而他确实那束例外的光。谁料过马路时，一辆汽车失控冲来，小墨为了护我。。。温热的鲜血飞溅在我的脸上，我的大脑一片空白，耳朵一阵轰鸣，我多么希望这是一场梦，梦醒了，小墨就又会出现在我面前。 我开始封闭自己，把彩色衣服全锁进柜子，只穿黑白灰。我学着变得“黑心”，低价收商品再高价倒卖，成了大家口中的“奸商”；见同学犯错就肆意嘲弄，看着他人窘迫的模样，心里反倒多了一丝病态的安全感；我信奉基督教，却用虚伪的微笑掩饰恶意。——哪怕。。。知道这不行。 转机在一个周末的游乐场出现。我陪着亲戚去旧地，心情自然十分糟糕，无意间看见两个小孩：瘦小的男孩摔倒了，另一个小孩立刻跑过去，小心翼翼扶起他，还把自己的棉花糖分给他，眼里满是纯粹的善意。这一幕像钥匙，打开了尘封的回忆——从前我和小墨，也是这样的。 我站在原地，黑白衣服仿佛透着寒意。可是，失去的太多，黑山羊的河流把他们都带走了，已经找不回来了。嘴角一丝苦笑，转身，向着远方走去。 实际上——早就不指望救赎了——深渊底部的黑暗，比任何星光都更适合我。 上帝啊。。。 https://www.acgo.cn/team/2004842565258547200

海淀信息奥赛游记

woc榜十了，感谢各位大佬观看，点赞的全家健康，长命百岁，比赛次次都AK 榜七了，啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，感谢感谢 1.24 666一觉醒来榜六了 点个赞吧 求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了求你了 年龄：11岁，六年级 身份：GESP五级79分的蒟蒻，男 角色介绍：牢孙（男，同班同学），牢白（女，隔壁班的） 考试全名：海淀区中小学生信息学奥林匹克竞赛 这样适合装b 先给大家展示一下考试 时间有点久，网上找的图，请见谅 目标：我不到啊，上次我第一赛段就趋势了 第一赛段 考前：看真题，信心满满，必须拿下好吧 考试时：被AI技术的题喂饱了 考完：在小绿书上查答案，估分80左右 出成绩：72?????，同班同学（不知名姓孙的物种）才64，压力！ （分数线62） 第二赛段 考前：复习2024年真题，感觉误闯天家了，啥也看不懂啊。疯狂补习排列组合ing 考试时：被排列组合喂饱了，还好复习了。 遇到会做的选择题： 不会做的： 考完：依旧小绿书，发现自己没救乐，基本错了一半啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 出分53 等待分数线处刑ing 牢孙微信告诉我他考了43，心情瞬间舒畅了 分数线出了，分数线43！ 不过我好像高兴不起来是为什么 致敬传奇压线王牢孙 彩蛋：由于牢白被嘲笑了，于是牢孙被牢白线下真实了 主包在旁边吃瓜看戏加油呐喊，也是很爽。主包非常有用 这句话运用了删除线的手法，体现了主包诚实的品质 赛后采访牢孙：男厕是个好东西 第三赛段 考前：ok啊也是来到我最擅长的上机编程了，必须1=的好吧（幻想自己1=ing） 考试时：6道题，满分600！看到前两道题，感觉稳了，输入输出是人都会啊。 看到T3~T6的我： T3~T6直接输出样例都提交了 考完：T1，T2应该AC了……吧，牢孙和牢白自认为做出了3道，主包被狠狠地嘲笑了 漫 ~ 长 ~ 的 ~ 等 ~ 待 ~ 出 ~ 分 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 %%%疯了 我230，T1 T2AC T4 T5各骗15分，爽！ 牢孙190，他是怎么做到的？ 请看VCR： 牢孙T1：颗秒题 牢孙T2：做的太快颗秒自己（就得了80） 牢孙T3：不会 牢孙T4：苦思冥想ing 我会了！（结果因为没加max(1,ans)被紫菜了）10分 牢孙T5，T6：不会 等等，聪明的你可能会问，不会输出样例吗？ 没错，牢孙不会 牢白分数至今也是未解之谜，问她就说我知道也不告诉你（像个类人） 等待分数线中…… 1.23 顺带一句期末考试发卷了，我语文98.5，数学100，英语100 发奖状了，我一等奖！！！！！！！！！！！！！！！！！！ 牢孙二等奖，哈哈哈哈哈哈 666可恶的牢白一等奖 %%%被牢白线下紫菜了 爽死了

【GeOI-M1】赛时答疑帖

此贴完结。 【GEOI-M1】赛时答疑帖 比赛基本内容 这里是 2026 GeOI Math Round 赛时答疑帖，你可以在此处提出问题或报名比赛，比赛时间为 2026/1/16 12:00 至 2026/1/31 00:00，剩余时间为赛后补题，不计入获奖名单。 这里是 比赛链接，邀请码为 HXmj。 这里是 作弊名单，第一周每日更新，剩余时间三日更新一次。 答疑情况 * T2 没有错误数据 赛时公告栏 截止于 【END】，比赛报名人数 117117117，有提交人数 333333，AK 人数 000，rk1 @we go! 得分 250+0+175=425250+0+175 = 425250+0+175=425。 信息 * [2026/1/16 13:06] 验题完成 * [2026/1/18 00:21] 恭喜 @𝓐𝓘𝓮𝓻 首杀 A 题！ * [2026/1/25 17:15] 恭喜 @we go! 首杀 C 题！ * [2026/1/26] 已有 100100100 人报名比赛！ * [2026/1/31 12:00] 比赛结束 欢迎加入 GEOI！ * ACGO link * 洛谷 link * 加入要求（请先通读，然后申请加入并主动私信给出符合条件）

互动｜期末玄学许愿指南

🎒 期末倒计时！你的玄学能量储备好了吗？ 在刷题、背诵、焦虑、抓狂的边缘反复横跳…… 别怕！期末许愿池2.0 限时返场！ 用宇宙的能量，换考场的奇迹—— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌟 许愿通道正式开启 请严格按以下格式，留下你的神圣考前愿望： 🎯 我希望： __________ 💀 我愿意为此放弃： __________ 🔮 如果灵验，我将回来还愿并： __________ 🌟 优质示范： > 🎯 我希望： 数学期末考能稳定发挥，大题不崩 > 💀 我愿意为此放弃： 一周的峡谷夜游，专心刷题 > 🔮 如果灵验，我将回来还愿并： 在社区分享我的错题笔记+给AC君点爆100个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 许愿者专属福利 所有按格式完整许愿的用户，均可参与能量池抽奖！ AC君将随机抽取 5位 天选锦鲤与点赞最高TOP1，送出AC狗拼图冰箱贴随机1片。 > ⏰ 活动时间：即日起 - 1月31日 23:59 > 🎉 开奖日期：2月2日（考完正好来还愿✨） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 许愿池使用说明 1. ✅ 愿望越具体、越真诚，宇宙接收信号越强！ 2. ✅ 放弃的代价要真实可执行（比如“放弃一周游戏”比“放弃呼吸”更靠谱） 3. ❌ 禁止许愿他人挂科（反向能量会反弹！） 4. 💫 互相点赞、评论加油的愿望，实现概率+99% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌌 来自宇宙的回复 > “你刷的每一道题，背的每一个知识点， > 都会在考场上变成让你稳住的底气。 > 许愿不是魔法，而是给自己一个仪式感的承诺—— > 期末考试月，我们一起把它变成奇迹发生的土壤。” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👇 评论区已开放许愿通道，你的愿望，宇宙正在收听！ 转发给并肩作战的搭子，一起接收好运能量！ 🔮 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

一个新的寻找二次函数顶点的方法？

首先，形如 ax2+bx+cax^2+bx+c ax2+bx+c 的柿子 要变为 k(x−l)2+r (k,l,r不含x)k(x-l)^2+r\ (k,l,r不含x) k(x−l)2+r (k,l,r不含x) 先化简原式 k(x−l)2+rk(x-l)^2+r k(x−l)2+r =k(x2+l2−2xl)+r=k(x^2+l^2-2xl)+r =k(x2+l2−2xl)+r =kx2+kl2−2kxl+r=kx^2+kl^2-2kxl+r =kx2+kl2−2kxl+r 那么你就会发现 (因为 (k,l,r不含x)(k,l,r不含x)(k,l,r不含x) ) {k=abx=−2kxlkl2+r=c\left\{\begin{matrix}k=a \\bx=-2kxl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=abx=−2kxlkl2+r=c 若 x=0x=0x=0 ，则 y=cy=cy=c 嗯对。。。 否则 {k=ab=−2klkl2+r=c\left\{\begin{matrix} k=a \\ b=-2kl \\kl^2+r=c \end{matrix}\right.⎩⎨⎧ k=ab=−2klkl2+r=c 将 k=xk=xk=x 代入方程组 {b=−2alal2+r=c\left\{\begin{matrix}b=-2al \\al^2+r=c \end{matrix}\right. {b=−2alal2+r=c 单独求解①式，得： l=−b2al=-\frac{b}{2a} l=−2ab 将其带入②式 a×b24a2+r=ca\times \frac{b^2}{4a^2}+r=c a×4a2b2 +r=c b24a+r=c\frac{b^2}{4a}+r=c 4ab2 +r=c 所以 r=c−b24ar=c-\frac{b^2}{4a} r=c−4ab2 所以 {k=al=−b2ar=c−b24a\left\{\begin{matrix}k=a \\l=-\frac{b}{2a} \\r=c-\frac{b^2}{4a} \end{matrix}\right. ⎩⎨⎧ k=al=−2ab r=c−4ab2

数状数组/线段树 代码存档

UPDATE: 决定把这个做成较为详细的笔记 UPDATE: 骗你的，做不下去了，只做了树状数组 排版很乱，见谅哈。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.树状数组（BINARY INDEXED TREE,BIT,二叉索引树） 简介：可以处理区间修改，查询区间和/差等问题（仅支持前缀可减的操作）。 问题：给出一个数组 {an}\{a_n\}{an }，请在 log⁡n\log{n}logn 的时间复杂度内执行区间修改或区间查询操作。 关于树状数组，我们从一个很聪明的函数讲起： lowbit(x)=x&(−x)\tt{lowbit(x)=x\&(-x)}lowbit(x)=x&(−x) 指 xxx 与 −x-x−x 按位与的结果。 可以发现，当 xxx 是奇数时，lowbit(x)=1\tt{lowbit(x)=1}lowbit(x)=1，反之 lowbit(x)=\tt{lowbit(x)}=lowbit(x)= 二进制下的 xxx 从左往右出现的最后一个 111 及其后面的 000 组成的数的十进制。这么听着有点绕，例如 lowbit(6)\tt{lowbit(6)}lowbit(6)，(6)10=(110)2,(6)_{10}=(110)_2,(6)10 =(110)2 , 取 101010，得 (10)2=2(10)_2=2(10)2 =2，所以 lowbit(6)=2\tt{lowbit(6)=2}lowbit(6)=2。当然这个只是铺垫后面的内容，听不懂也没关系。你只需要知道 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值一定是 222 的幂次，前提 x≠0x\ne 0x=0。 关键在于我们按 lowbit(x)\tt{lowbit(x)}lowbit(x) 的值将每个数分层并连边，居然神奇的出现了一棵二叉树！（如下图） 这棵二叉树非常神奇，对于节点 iii，如果他是左子结点，他的父节点为 i+lowbit(i)\tt{i+lowbit(i)}i+lowbit(i)，否则他的父节点为 i−lowbit(i)\tt{i-lowbit(i)}i−lowbit(i)。因此我们可以利用 lowbit\tt{lowbit}lowbit，对区间段进行前缀和计算。 构造一个辅助数组 c[]c[]c[]，定义 cic_ici 为覆盖节点 iii 及其左子树的区间和，即： ci=∑i−lowbit(i)+1iaic_i=\sum_{i-lowbit(i)+1}^i a_i ci =i−lowbit(i)+1∑i ai 这时我们回归问题。 修改 观察 cic_ici 的定义，修改一个节点的值，只需要同步修改在其右上方的祖先的值即可。 查询 只需要将所有其左上方的祖先及其本身的值即可。 对于区间修改问题，由于 query\tt{query}query 本质上是前缀和，所以差分一下即可（换句话说，区间修改问题必须有可差分性） 模板题，上模板。 例题： * 股票 提醒各位初学者，本题虽然不必离散化，但是你拿 aia_iai 建的树状数组就需要注意阈值上限是 max⁡ai\max a_imaxai 不是 nnn 了。可能你们会觉得这句话很糖。 * 逆序对 由于 aia_iai 达到了 10910^9109，我们无法直接按照 aia_iai 的值建树状数组，因此考虑离散化： * 1.复制 aaa 数组存入 ttt，将 ttt 排序。 * 2.将 ttt 用 unique\tt{unique}unique 函数去重。 * 3.用二分找原 aia_iai 在 ttt 中的位置。 这样我们就得到了 aia_iai 的相对大小顺序，把值域缩到了 5×1055\times 10^55×105 之内，可以建树状数组了。 2.线段树/(LAZY_TAG) 没写完。 3.权值线段树 洛谷我没找到板（没有给权值线段树の标签），自己放一个草题。 题目描述 给出 n,{an}n,\{a_n\}n,{an }，约定 b1=a1b_1=a_1b1 =a1 。对于 2≤i≤n2\le i \le n2≤i≤n： bi=min⁡j=1i−1∣aj−ai∣ b_i=\min_{j=1}^{i-1}|a_j-a_i| bi =j=1mini−1 ∣aj −ai ∣ 求出 {bn}\{b_n\}{bn }。 输入 给出 n,{an}n,\{a_n\}n,{an } 输出 {bn}\{b_n\}{bn } 输入 111 输出 111 1≤n≤105,1≤ai≤1071\le n \le 10^5,1\le a_i\le 10^71≤n≤105,1≤ai ≤107 无需离散化&动态开点 Code:\tt{Code:}Code: 回转寿司,luogu5459,绿 九转大肠有没有食欲 发现与区间和有关，套上前缀和 sumsumsum。 考虑列不等式 L≤sumr−suml−1≤RL\le sum_r-sum_{l-1}\le RL≤sumr −suml−1 ≤R，直接维护这个是 n2n^2n2 的肯定不现实。 考虑变换得 sumr−R≤suml−1≤sumr−L(l<i)sum_r-R\le sum_l-1\le sum_r-L(l<i)sumr −R≤suml −1≤sumr −L(l<i)，考虑枚举 sumisum_isumi ，那么我们只要找出满足条件的 suml−1sum_{l-1}suml−1 的数量，就是对于 sumisum_isumi 的选择。 于是我们使用权值线段树维护 sumsumsum 的值，也就是要计算的 [sumi−R,sumi−L][sum_i-R,sum_i-L][sumi −R,sumi −L]，那把小于 iii 的 sumjsum_jsumj 全部丢进权值线段树即可。 需要注意的是，本题阈值很大，记得动态开点处理。