图论（基础）学习笔记

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

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 666登上榜一了 > 此贴持续更新中，每十天会更新一次总概率 作为一个已经赌过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 存储从起点状态到达所有状态结点的最短路径长度。 参考代码

互动｜「寒假生存实录」开播中！

🌟「寒假生存实录」开播中！ 寒假模式已启动！你的生活主页面，从【教室】切换到了哪里？ 是燃系励志番、日常搞笑番，还是“摆烂”治愈番？ 这个假期，#寒假生存实录# 专属频道持续开放！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📮 参与指南：两种方式，任你选择 🎬 方式一：评论打卡 · 速记名场面** 懒得开新帖？直接在 本帖评论区，用一句话或一张图，晒出你当日的“高光/崩坏瞬间”。 📖 方式二：深度连载 · 开启个人剧集** 欢迎 单独发帖，进行连载或深度记录。只需： 1. 在讨论区发布帖子； 2. 在 帖子标题开头 带上 #寒假生存实录# 话题，即视为成功参演。 ⏰ 放映期间：即日起 ~ 2月28日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 互动奖励 🏆 人气打卡奖（TOP8瓜分奖池） 在 本帖评论区 打卡互动。活动结束后，符合评论要求&点赞数超过20的用户，将共同瓜分2016罐头！ ✨ 深度连载奖（优质内容激励） 在讨论区发表 #寒假生存实录# 主题的深度帖子。我们将根据内容的真实性、趣味性和故事性，评选出优质连载，送出稀有道具 「AC之神的祝福」 一张！ 🍀 随机幸运奖（全员参与抽奖） 所有有效参与者（包含评论打卡与发帖连载），均自动加入抽奖池！我们将随机抽取10位幸运儿，每人赠送 「昵称变色卡」 道具一张！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题 你的寒假日常，就是最真实的原创剧集。 快在评论区抛出你的“今日更新”，或开启你的专属连载吧！期待看到你的精彩“放映”。🎉

【获奖公告】挑战赛#27

【获奖公告】挑战赛#27 用户ID 用户昵称 获奖 4699151 @梦里初晴 拼图X1 +盲盒X1+1500罐头 4480835 @Su0710 拼图X1 +盲盒X1+600罐头 2901632 @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ 拼图X1 +盲盒X1+600罐头 3621376 @🥥 拼图X1 +盲盒X1+600罐头 4244987 @Gragher 拼图X1 +盲盒X1+600罐头 494973 @不会C++的一只屑生姜 拼图X1 +盲盒X1+300罐头 1371791 @复仇者_天之神_银色子弹 拼图X1 +盲盒X1+300罐头 3099184 @༺ཌༀ诺崽的树(互关)ༀད༻ 拼图X1 +盲盒X1+300罐头 4753295 @枫岚 拼图X1 +盲盒X1+300罐头 3640785 @肖越腾 拼图X1 +盲盒X1+300罐头 4784858 @195****3060 拼图X1 +盲盒X1+300罐头 5346770 @Micheal Jordan 拼图X1 +盲盒X1+300罐头 4221310 @༼ つ ◕_◕ ༽つ(ˉ﹃ˉ)‏ 拼图X1 +盲盒X1+300罐头 4997640 @Srobot 拼图X1 +盲盒X1+300罐头 4057292 @沈思邈 拼图X1 +盲盒X1+300罐头 3298235 @yanghongzheng 拼图X1 +盲盒X1+300罐头 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 获奖信息填写 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 前100名违规名单 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 72 名用户存在疑似 AI 生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 用户ID 用户昵称 3751693 @神-爸爸 5205870 @༺ཌༀ༒AC王者༒ༀད༻ 3614898 @RuiDaShuai2025 4592666 @𝓐𝓘𝓮𝓻 4326899 @狐夏聆哲_Anarilune. 5212050 @༺ཌༀ`§☯༺ཌ༒༺☯§′ༀད༻ 5134294 @黑妞 5320353 @181****9763 5439864 @Eric 3861543 @云雾星海 3431448 @得吃鼠鼠 5085318 @deepseek 4958203 @WA?不存在的 5034831 @一只开挂的蒟蒻 5347557 @we go! 4921199 @wwh 3708542 @徐梓铭 3361566 @12岁巅峰学生（互关） 5396059 @Lucky 5080911 @dvf 4960039 @请输入文本 4578820 @666 4609559 @老杨 4950030 @土豆（灿） 4963362 @我的世界老玩家（互关，专攻难题） 3455548 @十万暴击 3477229 @EasonDai 3809107 @AC 5205437 @里昂熠熠 5205370 @TLE君（自闭中） 4955240 @夏绍智(必回关) 5403433 @栖月 4126504 @༺ཌༀ◎真仙◎ༀད༻ 5433579 @༺ཌༀཉ༒ 砚辞 ༒ༀད༻ 4321981 @Minecraft 3460964 @终极主宰大神（求关注必回） 4790834 @异雷-彩色庆祝版 5431616 @134****0429 5345022 @Phantom_73 2454098 @i闪天天开心 5206173 @Google Chrome 5402041 @liuziang250 5401663 @whistleblower 1362696 @大刚 3249248 @陈羿然 4752030 @SD_xm 4976685 @实验小学乔子航 3644432 @黑皇 5216253 @133****8755 4307593 @Dog 5439994 @xjsmsms 4770844 @宇浩 ~-HAPPY 果 4390455 @𝓔𝓣𝓗𝓐𝓝 4909644 @ 4815042 @明月清风（互关） 3050135 @136****7366 5089157 @DAX-CC 4440554 @Ad-梵高无人识 4937905 @王普驿 5371339 @谈damn 5339471 @6AG3 4966462 @哪吒与敖丙 3745777 @Kevin Durant 4768854 @血战狂龙——血虐修罗之骜の流星尾 5194566 @周豫才 5415015 @chf 768428 @AC考试王乾瑄 4938384 @195****3768 4958204 @穷涂墨鹿、 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 申诉机制 请在2月8日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核 ：@Gragher，@cjdst 📎 ACGO 官方赛事公平审核规则 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 用户ID 用户昵称 累计历史违规次数 4963362 @我的世界老玩家（互关，专攻难题） 9 3751693 @神-爸爸 8 3455548 @十万暴击 8 4592666 @𝓐𝓘𝓮𝓻 6 3361566 @12岁巅峰学生（互关） 5 4440554 @Ad-梵高无人识 4 4955240 @夏绍智(必回关) 4 4326899 @狐夏聆哲_Anarilune. 3 5206173 @Google Chrome 3 4950030 @土豆（灿） 3 4126504 @༺ཌༀ◎真仙◎ༀད༻ 3

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. 请合理安排罐头使用计划，避免过期造成浪费 每年年底记得清空旧罐头，迎接新一年的赚罐头之旅！ 🎉

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

首先，形如 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=ak=ak=a 代入方程组 {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

【学习笔记】拉格朗日插值入门

同步发布于 我的 cnblogs 这篇应该比较简单（） LAGRANGE 插值 > 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi ,yi ) 满足 xi≠xjx_i\neq x_jxi =xj ，可以唯一确定一个 n−1n-1n−1 次多项式 y=f(x)y=f(x)y=f(x) 过上述所有 nnn 个点。 > > 现在给出 kkk，求 f(k)f(k)f(k) 的值。 一个简单的想法是直接 Gauss 消元，可以 O(n3)O(n^3)O(n3) 解出这个 n−1n-1n−1 次多项式每一项的系数。 这里介绍一下用 Lagrange 插值的解法： * 构造 nnn 个函数 fi(x)f_i(x)fi (x) 表示该函数过点 (xi,yi)(x_i,y_i)(xi ,yi )，对于任意 j≠ij\neq ij=i 都过点 (xj,0)(x_j,0)(xj ,0)。容易发现令 f(x)=∑i=1nfi(x)f(x)=\sum\limits_{i=1}^nf_i(x)f(x)=i=1∑n fi (x) 就可以得到一个满足条件的函数 f(x)f(x)f(x)。 * 然后考虑构造因式分解：对于每个 fi(x)f_i(x)fi (x) 多项式构造一项 x−xj(i≠j)x-x_j(i\neq j)x−xj (i=j)，然后凑一个系数 aia_iai 满足 fi(xi)=yif_i(x_i)=y_ifi (xi )=yi ，容易解方程得到 ai=yi∏j≠i(xi−xj)a_i=\dfrac{y_i}{\prod\limits_{j\neq i}(x_i-x_j)}ai =j=i∏ (xi −xj )yi 。 * 于是有：f(k)=∑i=1nfi(k)=∑i=1nyi∏j≠ik−xjxi−xjf(k)=\sum\limits_{i=1}^nf_i(k)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}f(k)=i=1∑n fi (k)=i=1∑n yi j=i∏ xi −xj k−xj ，可以在 O(n2)O(n^2)O(n2) 的时间复杂度内求解。 :::success[O(n2log⁡n)O(n^2\log n)O(n2logn) 解法] ::: :::success[O(n2)O(n^2)O(n2) 解法] ::: 001. P5667 拉格朗日插值2 根据上面的理论，容易得到： f(m+k)=∑i=0nyi∏j≠im+k−ji−jf(m+k)=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j} f(m+k)=i=0∑n yi j=i∏ i−jm+k−j 可以 O(n2)O(n^2)O(n2) 时间复杂度求解。 考虑对这个东西进行优化。注意到 kkk 的取值是连续的一段，所以从这里突破： f(m+k)=∑i=0nyi∏j≠im+k−ji−j=∑i=0nyi∏j≠i(m+k−j)∏j≠i1i−j=∑i=0nyi(m+k)!(m+k−n−1)!(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0nyi(−1)n−i1i!(n−i)!(m+k−i)=(m+k)!(m+k−n−1)!∑i=0n[1i!×yi×(−1)n−i1(n−i)!]×1m+k−i\begin{aligned} f(m+k) &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{m+k-j}{i-j}\\ &=\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}(m+k-j)\prod\limits_{j\neq i}\frac1{i-j}\\ &=\sum\limits_{i=0}^ny_i\frac{(m+k)!}{(m+k-n-1)!}(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{i!(n-i)!(m+k-i)}\\ &=\frac{(m+k)!}{(m+k-n-1)!}\sum\limits_{i=0}^n\left[\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!}\right]\times \frac1{m+k-i} \end{aligned} f(m+k) =i=0∑n yi j=i∏ i−jm+k−j =i=0∑n yi j=i∏ (m+k−j)j=i∏ i−j1 =i=0∑n yi (m+k−n−1)!(m+k)! (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n yi (−1)n−ii!(n−i)!(m+k−i)1 =(m+k−n−1)!(m+k)! i=0∑n [i!1 ×yi ×(−1)n−i(n−i)!1 ]×m+k−i1 记 Pi=(m+i)!(m+i−n−1)!,Ai=1i!×yi×(−1)n−i1(n−i)!,Bi=1m+iP_i=\frac{(m+i)!}{(m+i-n-1)!},A_i=\frac1{i!}\times y_i\times(-1)^{n-i}\frac1{(n-i)!},B_i=\frac1{m+i}Pi =(m+i−n−1)!(m+i)! ,Ai =i!1 ×yi ×(−1)n−i(n−i)!1 ,Bi =m+i1 ，则可以用 NTT 求出 C=A⊙BC=A\odot BC=A⊙B 即 CCC 为 A,BA,BA,B 两个序列的等差卷积，而 PiP_iPi 显然可以线性递推。 但是这真的对吗？？？把卷积形式写出来之后发现其形如：Ck=∑iAiBk−iC_k=\sum\limits_iA_iB_{k-i}Ck =i∑ Ai Bk−i （0≤i≤n0\le i\le n0≤i≤n），这怎么还出来负数下标了（）不过解决这个问题也是简单的，重新记 Bi=1m+i−nB_i=\frac1{m+i-n}Bi =m+i−n1 ，此时有 Cn+k=∑i=0nAiBn+k−iC_{n+k}=\sum\limits_{i=0}^nA_iB_{n+k-i}Cn+k =i=0∑n Ai Bn+k−i ，将其写成卷积的形式只需要对所有 i>ni>ni>n 都记 Ai=0A_i=0Ai =0 就可以扩展为 Cn+k=∑i=0n+kAiBn+k−iC_{n+k}=\sum\limits_{i=0}^{n+k}A_iB_{n+k-i}Cn+k =i=0∑n+k Ai Bn+k−i 的形式。 一次 NTT 卷积即可求出 C=A⊙BC=A\odot BC=A⊙B 这个等差卷积。 因此总时间复杂度为 O(nlog⁡n+m)O(n\log n+m)O(nlogn+m)，分段打表阶乘可以把后面的 O(m)O(m)O(m) 省去。 跑了 973ms，喜提最劣解（没事至少这个能过） :::success[Code] ::: 006. CF622F THE SUM OF THE K-TH POWERS 通过作差可以发现答案是一个 k+1k+1k+1 次多项式的形式，因此想到 Lagrange 插值。将 xi=ix_i=ixi =i（0≤i≤n0\le i\le n0≤i≤n）带入，有： ∑i=0nyi∏j≠ix−ji−j=∑i=0nyi(∏j=0i−1x−ji−j∏j=i+1nx−ji−j)=∑i=0nyi(∏j=0i−1(x−j)∏j=i+1n(x−j)∏j=0i−11i−j∏j=i+1n1i−j)=∑i=0nyi(−1)n−i1x!1(n−x+2)!∏j=0i+1(x−j)∏j=i+1n(x−j)\begin{aligned} &\sum\limits_{i=0}^ny_i\prod\limits_{j\neq i}\frac{x-j}{i-j}\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}\frac{x-j}{i-j}\prod\limits_{j=i+1}^n\frac{x-j}{i-j})\\ =&\sum\limits_{i=0}^ny_i(\prod\limits_{j=0}^{i-1}(x-j)\prod\limits_{j=i+1}^n(x-j)\prod\limits_{j=0}^{i-1}\frac1{i-j}\prod\limits_{j=i+1}^n\frac1{i-j})\\ =&\sum\limits_{i=0}^ny_i(-1)^{n-i}\frac1{x!}\frac1{(n-x+2)!}\prod\limits_{j=0}^{i+1}(x-j)\prod\limits_{j=i+1}^n(x-j) \end{aligned} === i=0∑n yi j=i∏ i−jx−j i=0∑n yi (j=0∏i−1 i−jx−j j=i+1∏n i−jx−j )i=0∑n yi (j=0∏i−1 (x−j)j=i+1∏n (x−j)j=0∏i−1 i−j1 j=i+1∏n i−j1 )i=0∑n yi (−1)n−ix!1 (n−x+2)!1 j=0∏i+1 (x−j)j=i+1∏n (x−j) 后面这两个 ∏\prod∏ 一看就很能预处理，而前面的显然可以直接算。时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。注意到 iki^kik 是积性函数，所以使用线性筛可以将其优化至严格 O(n)O(n)O(n) 求解。 007. P4593 [TJOI2018] 教科书般的亵渎 设 S(n,k)=∑i=1nikS(n,k)=\sum\limits_{i=1}^ni^kS(n,k)=i=1∑n ik，则容易观察到该题要求的答案为：∑i=0mS(n−ai,m+1)+∑i=0m∑j=i+1m(aj−ai)m+1\sum\limits_{i=0}^mS(n-a_i,m+1)+\sum\limits_{i=0}^m\sum\limits_{j=i+1}^m(a_j-a_i)^{m+1}i=0∑m S(n−ai ,m+1)+i=0∑m j=i+1∑m (aj −ai )m+1。后半部分可以暴力快速幂求解，而前半部分是 CF622F，直接套用上面的公式求解即可。

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

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 全部丢进权值线段树即可。 需要注意的是，本题阈值很大，记得动态开点处理。

非官方题解 | 嘻哈赛#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版： 团队传送门（你敢不敢加入此团队？） 如果要团队合作，请私信。

海淀信息奥赛游记

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可恶的牢白一等奖 %%%被牢白线下紫菜了 爽死了