<!DOCTYPE html><html lang="zh-CN"><head><meta charSet="utf-8"/><meta name="viewport" content="width=device-width, initial-scale=1"/><meta name="robots" content="follow, index"/><title>ACGO讨论社区-信息学编程算法训练动态最新发布-ACGO题库</title><meta name="keywords" content="ACGO讨论社区,编程算法训练,ACGO题库,编程算法训练动态"/><meta
name="description" content="ACGO(Acgo.Cn)是专业的编程算法训练平台，ACGO致力于为参加CSP-J/S、GESP、NOIP、NOI、ACM、CSP、CCPC、ICPC竞赛的选手提供清爽、快捷的编程训练刷题体验。适合初级小白C++编程入门训练，包含CSP入门级提高级赛前集训、提高组普及组训练，ACM区域赛前多校训练营，是学习noip等竞赛时理想的网站。"/><meta name="next-head-count" content="6"/><meta charSet="UTF-8"/><meta http-equiv="X-UA-Compatible"
content="IE=edge,chrome=1"/><meta name="force-rendering" content="webkit"/><meta name="renderer" content="webkit"/><link rel="shortcut icon" href="/favicon.ico"/><meta name="theme-color" content="#0f1a2b"/><link rel="stylesheet" href="/fonts/iconfont.css"/><meta name="msvalidate.01"
content="A033AD016D4920E0C8C8C392882AB7E7"/><link rel="preload" href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/673fff6033cd8283.css" as="style"/><link rel="stylesheet"
href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/673fff6033cd8283.css" data-n-g=""/><link rel="preload" href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/15c519a62d8d8244.css" as="style"/><link rel="stylesheet"
href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/15c519a62d8d8244.css" data-n-p=""/><link rel="preload" href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/655da26446d11c6d.css" as="style"/><link rel="stylesheet"
href="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/css/655da26446d11c6d.css" data-n-p=""/><noscript data-n-css=""></noscript><script defer="" nomodule=""
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/polyfills-c67a75d1b6f99dc8.js"></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/webpack-8a37d0098e2aca36.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/framework-4f2e43b303c5fc23.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/main-e9c10f40a4b15e4f.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/pages/_app-b2d22ed376ef87e1.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/c97c1b85-8530c761b544d963.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/175675d1-2e83d953ef4808b3.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/29107295-af7ba304cbca5b2d.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/5074-eeda164bbca0c63d.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/6154-f46c78e70b1e76b4.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/2054-64ad3aa5eb00e1ce.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/1966-7ab1e615c7e333f1.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/2979-90809b183519b961.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/1844-ef1832017233f9f3.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/545-637fa8b733761b5e.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/2365-45c53e7b6f19f995.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/967-2a683ff85e72fab5.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/chunks/pages/discuss-5f24b4ee616d9454.js" defer=""></script><script
src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/qHnIb2wlwEJXij7KLQY5l/_buildManifest.js" defer=""></script><script src="//xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/1.0.0/prod/_next/static/qHnIb2wlwEJXij7KLQY5l/_ssgManifest.js"
defer=""></script></head><body><div id="__next"><div class="index_page__988oe"><header class="index_header__mmxqW"><div class="index_headerContent__EClqO"><nav class="index_nav__fufhn"><a class="index_logoWrap__Rq9HN index_navLink__JpW60" href="/"><span
style="box-sizing:border-box;display:inline-block;overflow:hidden;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;position:relative;max-width:100%"><span
style="box-sizing:border-box;display:block;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;max-width:100%"><img style="display:block;max-width:100%;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0" alt="" aria-hidden="true"
src="data:image/svg+xml,%3csvg%20xmlns=%27http://www.w3.org/2000/svg%27%20version=%271.1%27%20width=%27101%27%20height=%2728%27/%3e"/></span><img alt="acgo题库" src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" decoding="async" data-nimg="intrinsic"
class="index_logo__M_tF9" style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%"/><noscript><img alt="acgo题库"
srcSet="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Flogo.png&w=128&q=100 1x, /_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Flogo.png&w=256&q=100 2x"
src="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Flogo.png&w=256&q=100" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%" class="index_logo__M_tF9" loading="lazy"/></noscript></span></a><ul
class="index_navList___gEoz"><li class="index_navItem___pOt1"><a href="/" class="index_navLink__JpW60">首页</a></li><li class="index_navItem___pOt1"><a href="/problemset/" class="index_navLink__JpW60">题库</a></li><li class="index_navItem___pOt1"><a href="/collection/"
class="index_navLink__JpW60">学习</a></li><li class="index_navItem___pOt1"><a href="/contest/" class="index_navLink__JpW60">竞赛</a></li><li class="index_navItem___pOt1"><a href="/discuss/" class="index_navLink__JpW60">讨论</a></li><li class="index_navItem___pOt1"><a href="/ranking/"
class="index_navLink__JpW60">排行</a></li><li class="index_navItem___pOt1"><a href="/team/" class="index_navLink__JpW60">团队</a></li><li class="index_navItem___pOt1"><h4 class="index_navLink__JpW60 ">备赛专区</h4><div class="index_secondNavList__OOGUp"><div class="index_menuWrap__uFHG9"><p
class="index_menuWrapTitle__HWEZQ">竞赛</p><ul><li class="index_menuItem__ALFW0"><a class="index_menu__mVXvG " href="/practice/info?matchSourceId=1&subjectType=3">CSP-J/S</a></li><li class="index_menuItem__ALFW0"><a class="index_menu__mVXvG "
href="/practice/info?matchSourceId=8&subjectType=3">蓝桥杯</a></li></ul></div><div class="index_menuWrap__uFHG9"><p class="index_menuWrapTitle__HWEZQ">考级</p><ul><li class="index_menuItem__ALFW0"><a class="index_menu__mVXvG " href="/practice/info?matchSourceId=2&subjectType=3">GESP</a></li><li
class="index_menuItem__ALFW0"><a class="index_menu__mVXvG " href="/practice/info?matchSourceId=3&subjectType=3">CPA</a></li><li class="index_menuItem__ALFW0"><a class="index_menu__mVXvG " href="/practice/info?matchSourceId=4&subjectType=3">电子学会考级</a></li></ul></div></div></li></ul></nav><div
class="index_login__kBpS6"><div class="index_btn__GOyBf">登录</div><div class="index_btn__GOyBf">注册</div></div></div><div class="index_headerBg__AqdOm"><div class="index_headerInnerBg__5UzB6"></div></div></header><main class="index_main__8vV6G"><section class="index_body__DC_Oj"><aside
class="index_typeAside__qArfe"><a class="index_link__9h58o index_active__oQRIP" href="/discuss/?tab=undefined"><div class="index_linkIcon__zUkjx"><span
style="box-sizing:border-box;display:inline-block;overflow:hidden;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;position:relative;max-width:100%"><span
style="box-sizing:border-box;display:block;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;max-width:100%"><img style="display:block;max-width:100%;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0" alt="" aria-hidden="true"
src="data:image/svg+xml,%3csvg%20xmlns=%27http://www.w3.org/2000/svg%27%20version=%271.1%27%20width=%2716%27%20height=%2716%27/%3e"/></span><img alt="图标" src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%"/><noscript><img alt="图标"
srcSet="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_quanbu.png&w=16&q=100 1x, /_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_quanbu.png&w=32&q=100 2x"
src="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_quanbu.png&w=32&q=100" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%" loading="lazy"/></noscript></span></div>全部板块</a><a class="index_link__9h58o "
href="/discuss/study/?tab=undefined"><div class="index_linkIcon__zUkjx"><span style="box-sizing:border-box;display:inline-block;overflow:hidden;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;position:relative;max-width:100%"><span
style="box-sizing:border-box;display:block;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;max-width:100%"><img style="display:block;max-width:100%;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0" alt="" aria-hidden="true"
src="data:image/svg+xml,%3csvg%20xmlns=%27http://www.w3.org/2000/svg%27%20version=%271.1%27%20width=%2716%27%20height=%2716%27/%3e"/></span><img alt="图标" src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%"/><noscript><img alt="图标"
srcSet="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_xueshu.png&w=16&q=100 1x, /_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_xueshu.png&w=32&q=100 2x"
src="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_xueshu.png&w=32&q=100" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%" loading="lazy"/></noscript></span></div>学习讨论</a><a class="index_link__9h58o "
href="/discuss/depot/?tab=undefined"><div class="index_linkIcon__zUkjx"><span style="box-sizing:border-box;display:inline-block;overflow:hidden;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;position:relative;max-width:100%"><span
style="box-sizing:border-box;display:block;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;max-width:100%"><img style="display:block;max-width:100%;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0" alt="" aria-hidden="true"
src="data:image/svg+xml,%3csvg%20xmlns=%27http://www.w3.org/2000/svg%27%20version=%271.1%27%20width=%2716%27%20height=%2716%27/%3e"/></span><img alt="图标" src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%"/><noscript><img alt="图标"
srcSet="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_zhanwu.png&w=16&q=100 1x, /_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_zhanwu.png&w=32&q=100 2x"
src="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_zhanwu.png&w=32&q=100" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%" loading="lazy"/></noscript></span></div>站务中心</a><a class="index_link__9h58o "
href="/discuss/rest/?tab=undefined"><div class="index_linkIcon__zUkjx"><span style="box-sizing:border-box;display:inline-block;overflow:hidden;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;position:relative;max-width:100%"><span
style="box-sizing:border-box;display:block;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0;max-width:100%"><img style="display:block;max-width:100%;width:initial;height:initial;background:none;opacity:1;border:0;margin:0;padding:0" alt="" aria-hidden="true"
src="data:image/svg+xml,%3csvg%20xmlns=%27http://www.w3.org/2000/svg%27%20version=%271.1%27%20width=%2716%27%20height=%2716%27/%3e"/></span><img alt="图标" src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%"/><noscript><img alt="图标"
srcSet="/_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_guanshui.png&w=16&q=100 1x, /_next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_guanshui.png&w=32&q=100 2x"
src="/next/image?url=https%3A%2F%2Fxmcdn.oss-cn-shanghai.aliyuncs.com%2Fcpp_community%2Fimages%2Fpost_guanshui.png&w=32&q=100" decoding="async" data-nimg="intrinsic"
style="position:absolute;top:0;left:0;bottom:0;right:0;box-sizing:border-box;padding:0;border:none;margin:auto;display:block;width:0;height:0;min-width:100%;max-width:100%;min-height:100%;max-height:100%" loading="lazy"/></noscript></span></div>灌水池塘</a></aside><div><div
class="index_bodyContainer__1BwsV"><div class="index_header__QGUmc"><div class="index_tabWrap__B8tK index_headerLeft__eecVm"><div class="tabHead"><div class="tabItems"><div class="tabItem"><a href="/discuss/" target="_self" class="">最新回复</a></div><div class="tabItem"><a href="/discuss/?tab=public"
target="self" class="">最新发布</a></div><div class="tabItem"><a href="/discuss/?tab=essence" target="self" class="">精华帖</a></div></div><div class="tabUnderLine"></div></div><div style="display:none"></div><div style="display:none"></div><div style="display:none"></div></div><div
class="index_headerRight__93s7"><div class="index_searchWrap__mmgps index_search__3Kd_a"><input type="text" class="index_inputField__83fj7" placeholder="搜索帖子标题、内容" maxLength="30" value=""/><button type="button" class="index_searchBtn__717kh"><i class="iconfont icon-sousuo"></i></button></div><button
type="button" class="index_btn__geTJ6 index_primary-btn__iXCPn index_default-shape-btn__aYK7 ">发起讨论</button></div></div><div class="PostList_wrap__6xXep "><ul><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/study/60434"><h2 class="PostList_title__yZMjf"><span>官方题解 | 欢乐赛#58题解</span><span
class="PostList_greatLabel__X00F9">精华</span><span class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。
题目编号 题目名称 题目难度 T1 音频计算 入门 T2 排队时间 入门 T3 作业检查 入门 T4 立体炸弹 入门 T5 三好学生 普及- T6 产量预测 普及-
T1 音频计算
题目大意
题目给出了关于音频文件大小的计算方法和文件大小单位的转换规则，这里读题时注意采样频率的 HzHzHz 是单位，按照提示中的计算公式计算时并不会影响结果。
题解思路
本题本质为格式化输入输出，按照提示的公式计算后进行单位转换即可，注意使用 double 类型进行计算，输出要使用 printf 方法保留 444 位小数。
误差不到 10−310^{-3}10−3 的结果均视为正确。
参考代码
T2 排队时间
题目大意
题目给出了 nnn 位患者的等待时间，然后才给出当前刚轮到的患者序号 xxx 和阿北的序号 yyy，要求求出所需的等待时间。
题解思路
本题本质为一维数组的使用，按照题目要求循环遍历序号在 x∼yx\sim yx∼y 之间的每个数组元素进行统计即可。根据题目描述，这里包含序号 xxx 但不包含序号 yyy。
由于序号输入是后置的，所以数据输入必须存储于数组中，在先给出编号的题目中也可以直接进行统计。
这里求区间和的要求也可以考虑使用前缀和的模版代码实现。
参考代码
T3 作业检查
题目大意
题目给出了一个标准字符串和多个待检查的字符串，要求按顺序找出有错误的字符串并标出错误位置。
题解思路
本题本质为字符串的遍历，由于可能存在多个错误位置，所以直接遍历整个字符串进行对比即可。注意要标记一下每位同学是否出错，第一次发现出错时要先输出当前同学编号，后续发现错误时只需要输出位置即可。题目描述中对缺少字符和多余字符的位置也视为错误，需要注意循环条件。
字符串的题目在输入部分要检查是否正确输入，尤其需要关注数输入后的空格和换行符，检查后续的字符串输入是否正确进行。
参考代码
T4 立体炸弹
题目大意
题目给出每艘船的炸弹数量、装甲上限、作战时间、炸弹伤害和维修效率，要求计算所需维修装置的最小数量。
题解思路
本题本质为题目信息的理解与模拟，通过循环的方法模拟炸弹和维修装置的运行过程。由于规律难以获得并且数据范围较小，这里使用嵌套循环的方法，外层循环枚举维修装置的数量，内层循环模拟时间范围内的运行情况。
由于同秒内的维修生效在炸弹之后，所以需要先计算炸弹效果，未被炸毁时再计算维修效果，维修时注意装甲不能超出原有的装甲上限。
当超出时间后，仍在运行中的炸弹和维修装置仍会继续完成当前轮次的运行，这里在模拟时需要多模拟一轮并注意后续不再开启。
参考代码
T5 三好学生
题目大意
题目给出积分记录，根据记录累积每位同学的总积分，最后再按积分比例计算总积分。
题解思路
本题本质为结构体排序，每位同学存在多个分数和多条记录，并且总积分需要进行排序，所以采用结构体进行存储与排序。
需要注意的是，题目并没有说明编号是从 1∼n1\sim n1∼n，所以需要对整个可能的编号范围 1∼20001\sim 20001∼2000 进行遍历统计并标记有记录的同学编号，在排序时将是否有记录作为第一关键字进行排序。
另外对于总积分的输出格式，从样例中可以发现是输出实际的有效位，如果结果是整数就输出整数，如果结果存在小数部分则按小数实际大小输出。这里只存在一位小数和整数的两种情况，样例中都有包括。
参考代码
T6 产量预测
题目大意
题目给出了从 P0P0P0 开始加工到 P4P4P4 的转化情况，要求从零开始计算一段时间后的各级产品数量。
题解思路
本题本质为对题目信息的模拟，按照时间顺序模拟各级工厂的运行情况。这里工厂的开工时间比较统一，所以可以优化为对每 151515 分钟的时间节点进行模拟操作，不需要按每分钟进行模拟。
工厂的消耗与产出过程非常相似，所以可以将每级工厂的运行都总结为函数进行，在每个时间点按低级到高级的顺序依次模拟运行。由于同级工厂会统一开工，所以要注意标记当前是否有工厂在运行并记录运行工厂的数量。每轮运行时要注意先产出上一轮的产品，将记录的运行工厂数清空后，然后再考虑新一轮的运行情况。最后的一个整点同样要注意计算产出并消耗材料启动新一轮流程。
极限情况下可能存在 P0P0P0 产品数量超出 int 范围的情况，所以要注意使用 long long 类型变量。
参考代码
这里因为工厂运行的模式非常相似，所以代码可以考虑复制粘贴后再修改，也可以在函数内部使用循环进行不同级工厂的运行。</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/4451596"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7"
style="width:28px;height:28px;padding:0px"><div class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/07666f94d02449c280a29ba61b76d879.jpg" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">Sherry</p></a><div
class="AuthorInfo_identityWrap__RM_Zw"><div class="AuthorInfo_badgeList__5ortF"><img src="https://attach.acgo.cn/picture/4011a0b1893d4082b39f2db5c16605a4.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="出道萌新"/><img
src="https://attach.acgo.cn/picture/5cf406ac0e0847d5b6ad7811c6f61508.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="时空双修者"/><img src="https://attach.acgo.cn/picture/50ca801425254c9aab4d164d36c0f4bb.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="快乐小狗"/><img src="https://attach.acgo.cn/picture/66a3482736ec474f9b9687dbc5472f69.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="管理员"/></div></div></div><div
class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>7</span><span>阅读</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>0</span><span>回复</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>0</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/rest/58654"><h2 class="PostList_title__yZMjf"><span>#创作计划 浅谈树状数组</span><span class="PostList_greatLabel__X00F9">精华</span><span
class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>先说一个东西，本文连同潘子涵的文章我认为才是一篇创作计划该有的样子，有长度，有内容，有可以让大家知道自己不知道的东西的部分。
UPD：更新了树状数组倍增求 kkk 大值，并修改了有序表问题。
前言
本文主要在洛谷发布，且本文非常完善，涵盖了你知道和不知道的东西。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
强烈谴责某些用户写的树状数组文章纯纯误导我这种蒟蒻！
注：下文中的 ccc 数组即为树状数组，aaa 为原数组。
概念
完了有点忘了怎么办。
本质就是将一个长度为 nnn 的数组用特别的方法分成不超过 logn\log nlogn 段区间，用这些区间的已知信息做合并来拼凑出询问的信息，大概长下面这个样子：
其中，被标成蓝色的点就是管辖了其子节点所有信息的点。
那么该怎么分每个节点管辖的信息呢？
这是被定义的，定义如下：
设 ckc_{k}ck 是树状数组中下标为 kkk 的节点，那么它管辖的区间就是原数组中 [k−k′+1,k][k-k^{\prime}+1,k][k−k′+1,k] 内的元素的信息，其中，k′k^{\prime}k′ 是 lowbit(k)，而 lowbit(k) 的意思是 kkk 在二进制表示中最低位的 111 及其后面的所有 000 所构成的数值，比如 lowbit(5) 的计算方法就是先将 555 转化为二进制，为 (110)2(110){2}(110)2 ，然后取出右边开始第一个 111 及其右侧的所有 000 组成的数值，即 (10)2(10){2}(10)2
，转化为十进制就是 222，在代码中，lowbit(x) 函数被实现为 xxx 与 −x-x−x 做 & 运算，具体为什么在此不多赘述，可以自行查询位运算相关知识。
基本用法
终于到了激动人心的基本用法讲解！
写在前面
首先，你要了解树状数组查询区间信息的本质——差分。
因此，普通的树状数组不能维护区间最大值等等不可差分的信息！
区间求和
注意：树状数组每次只能查询形如下标在 111 到 kkk 的区间前缀和，所以真正的区间和需要运用前缀和知识进行拼凑。
假设我们要查询区间 111 到 kkk 的前缀和（下文中设 lowbit(k) 为 ppp，且 p′p^{\prime}p′ 等表述意为 kkk 在减去先前一个 ppp 之后的数做 lowbit 运算的值）。
首先，我们已经有了 ck=∑i=k−p+1kaic_{k}=\sum_{i = k-p+1}^{k}a_ick =∑i=k−p+1k ai ，那么，为了继续找到我们所求答案的下一个部分，我们需要继续查询 ∑i=k−p−p′+1k−pai\sum_{i=k-p-p{\prime}+1}{k-p} a_{i}∑i=k−p−p′+1k−p ai 的值并累加到答案中，注意到这个值就是 ck−pc_{k-p}ck−p ，那么以此类推，每次都用上述一样的思想就可以得出查询的方法是将
ck,ck−p,ck−p−p′,ck−p−p′−p′′c_{k},c_{k-p},c_{k-p-p{\prime}},c_{k-p-p{\prime}-p^{\prime\prime}}ck ,ck−p ,ck−p−p′ ,ck−p−p′−p′′ 一直到 c1c_{1}c1 这些值全部相加，就拼凑了原数组中下标在 111 到 kkk 的和。
之后，在求出了 111 到 l−1l-1l−1 的和 sl−1s_{l-1}sl−1 与 111 到 rrr 的和 srs_{r}sr 后，就可以根据前缀和的知识得知 lll 到 rrr 的和为 sr−sl−1s_{r}-s_{l-1}sr −sl−1 。
代码：
单点修改
如果要修改 axa_{x}ax 的值，那么就需要在 ccc 数组中更新所有管辖了 axa_{x}ax 值的节点。
观察最初的图，可以发现 xxx 号有色节点的父节点编号是 x+px+px+p（ppp 为 lowbitx(x)），那么就可以通过不断从 xxx 往上“跳”，每次都跳到当前节点的父节点，更新跳到的每个节点即可。
代码：
TIPS
注意，一般情况下，树状数组中的初值就是在原数组对应的位置存上对应的值！
练习
现在，你学习了树状数组的基本用法，那么，你就可以完成 P3374 了！
小进阶
1. 区间修改，单点查询
结合普通的差分数组，我们就可以实现区间修改，单点查询！
实现：
1. 求出原序列的查分数组 bbb，并将其按照下标作为键值存入树状数组。
2. 利用原本树状数组“单点修改”的特性与差分性质，修改 blb_{l}bl 与 br+1b_{r+1}br+1 即可实现“区间修改”。
3. 利用原本树状数组“区间查询”的特征与差分性质——对差分数组求前缀和就可以获得原序列可得，查询的第 xxx 个数的值相当于求出 111 到 xxx 在树状数组上的和。
代码（存储初值）：
代码（修改）：
代码（查询）：
练习 2
接下来，完成 P3368 吧！
2. 区间修改，区间查询
其实当我们掌握了基本方法，做任意理论上可以实现的查询都可以通过“推式子”得出。
由上个部分的查分数组做考虑组合出答案。
首先，ai=∑j=1ibja_{i}=\sum_{j=1}^{i}b_{j}ai =∑j=1i bj ，那么：
∑i=1rai=∑j=1r∑k=1jbk=r∑l=1rbl−∑d=1r(d−1)bd\sum_{i=1}{r}a_{i}=\sum_{j=1}{r}\sum_{k=1}{j}b_{k}=r\sum_{l=1}{r}b_{l}-\sum_{d=1}^{r}(d-1)b_{d} i=1∑r ai =j=1∑r k=1∑j bk =rl=1∑r bl −d=1∑r (d−1)bd
那么这个式子可以分别维护左半部分和右半部分，开两个树状数组即可，一个存储普通的数值，一个存储 (i−1)×bi(i-1)\times b_{i}(i−1)×bi 。
代码（存储）：
代码（修改）：
代码（查询）：
练习 3
使用树状数组完成 P3372。
正经进阶
来点进阶的！
1. 权值树状数组
本质上，权值树状数组就是将原本用下标作为键值的树状数组改为了用一个数值作为下标！
他有什么用呢？
他可以相当于将树状数组变成一个“数轴”，因为使用值域作为下标，那么原本在一个位置加上一个数的操作就相当于在一条数轴上标记一个点。
值得注意的是，这种方法受空间限制（总不能开 10910^{9}109 大小的数组吧），所以通常搭配离散化来进行操作！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如果我们要统计一个数组中 ai≤aja_{i} \leq a_{j}ai ≤aj 的数量，我们该怎么做？
根据上文的描述，我们可以将这些值全部作为点存进“数轴中”，假设为下图。
其中，红色数字代表树状数组中的“下标”，蓝色的数字表示这个数字出现的次数，那么，如果我们想要统计比 666 小的元素有多少个，那么我们只需要求得“下标”在 [1,5][1,5][1,5] 间所有蓝色数的和即可，对应到树状数组上就是查询区间 [1,5][1,5][1,5] 的和，也就是 Query(5)，如果要查询比某个数大的元素个数，也只需要求得这个数右侧的下标对应的蓝色数的和即可。
代码（加点，其中求 rkrkrk 的部分是离散化后的结果）:
练习 4
好了，再结合离散化，你就可以完成：
1. SP32899（通常情况下，“加点”操作都要按照顺序一个一个来，不能一次性全部加进去，因为这样会导致对下标的要求混乱，比如你要求所有的 suml≤sumrsum_{l} \leq sum_{r}suml ≤sumr 为了保证 l,rl,rl,r 的关系，你需要按照顺序加点）。
2. P1908（本题中因为逆序对也要求了下标的顺序，注意控制“加点”的顺序与查询的细节）。
3. 全局第 KKK 大值。
再次考虑权值树状数组。
问题相当于：在权值树状数组上找到一个 xxx，满足 111 到 xxx 的前缀和 <k\lt k<k，111 到 x+1x+1x+1 的前缀和 ≥k\geq k≥k，那么，x+1x+1x+1 就是第 kkk 大值。
二分 xxx 结合权值树状数组查询即可，复杂度 O(log2n)O(\log^{2} n)O(log2n)，慢了。
考虑更高效的“跳”来找到 xxx。
想到倍增，从大到小枚举一个 iii，记录一个变量 xxx 初始为 000，每次跳 2i2^{i}2i 步，尝试将 [x+1,x+2i][x+1,x+2^{i}][x+1,x+2i] 的前缀和加入一个初始为 000 的数 SSS 中，如果加入后 S<kS \lt kS<k，那么说明可以继续往后跳，将 xxx 更新为 x+2ix+2^{i}x+2i，依次类推，最后会找到最大的 xxx 使 S<kS \lt kS<k，那么 x+1x+1x+1 就是答案。
由于 [x+1,x+2i][x+1,x+2^{i}][x+1,x+2i] 的前缀和其实就是 cx+2ic_{x+2^{i}}cx+2i ，可以每次 O(1)O(1)O(1) 查询，于是这种方法的复杂度降至了 O(logn)O(\log n)O(logn)，优秀。
其次，修改操作只要在权值树状数组对应的映射上进行加减操作即可。
3. 二维树状数组
顾名思义，二维树状数组就是对一个矩阵进行操作的数据结构。
先给个代码感受下：
具体讲解可以看作者的这篇题解。
习题 5
1. SP1029。
2. P4514。
鸽了
1. 维护不可差分信息
不可差分的信息树状数组可不可以维护呢？
行！但就是很慢，是单次 O(log2n)O(\log^{2} n)O(log2n) 的，不如线段树。</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/4772459"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7"
style="width:28px;height:28px;padding:0px"><div class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/5cea92a962554376935bb28318a50811.png" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">Lyzc0dr</p></a><div
class="AuthorInfo_identityWrap__RM_Zw"><div class="AuthorInfo_badgeList__5ortF"><img src="https://attach.acgo.cn/picture/4011a0b1893d4082b39f2db5c16605a4.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="出道萌新"/><img
src="https://attach.acgo.cn/picture/52847ba4a0b643c58546822b1cf108a1.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="时间刺客"/><img src="https://attach.acgo.cn/picture/8255ead013964310a4eab7a6defbe55c.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="倔强青铜"/></div></div></div><div class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>129</span><span>阅读</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>28</span><span>回复</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>4</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/rest/59853"><h2
class="PostList_title__yZMjf"><span>互动#25｜#1024吐槽节</span><span class="PostList_greatLabel__X00F9">精华</span><span class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>💥 #1024吐槽节# 盛大开幕！
嘿，AC狗友们！🧑💻
又到了一年一度，咱们程序员的专属节日——1024！
（没错，ACGO也有自己的小传统了，仪式感拉满 😎）
所以，我们决定如期举办那个 “让人又爱又恨” 的活动——
#1024吐槽节#
今年的规则，简单到令人发指：
> 看ACGO哪里不顺眼？大胆开麦！
是题库太阴间？测评机日常抽风？
还是社区功能用起来像在考古？
或者，你单纯想对我们AC君喊一句：
“你们这个功能是祖传的吗？能不能动一动！”
没问题！今天你说了算！🫡
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
💡 来来来，指条明路（欢迎自由发挥）：
* 「功能篇」：题库、测评机、排行榜、编辑器… 哪个让你血压飙升？
* 「社区篇」：氛围、活动、推荐机制… 哪里让你想“原地退站”？
* 「运营篇」：希望我们多整活？多发福利？还是… 少整点烂活？🤣
一句话：今天我们不开夸夸团，专心 “Debug ACGO”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
✨ 参与姿势：
1️⃣ 带话题 #1024吐槽节# 发帖或直接评论本帖
2️⃣ 尽情输出你的“血泪体验” + 你心目中的完美改进方案
3️⃣ 支持各种形式：小作文、段子、表情包、灵魂拷问… 越真实，越有力！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
🎁 而我们，郑重承诺：
* 所有高赞、走心的吐槽，我们保证逐字阅读，跪着回复！
* 那些闪闪发光的金点子，将直接进入 「ACGO优化清单」 （是真的会排期的那种！）
* 被我们“盯上”的优秀吐槽官，还会收获一份 “忍住别哭” 的小惊喜 🎁
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
🎁 活动礼品：
高赞奖：点赞最高的前三位，送上ACGO钥匙扣盲盒
金点子奖 ：我们将选2-5名，送上AK吧唧
优秀吐槽官奖 ：我们将选选2-5名，送上ACGO周边定制笔
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
🗓 活动时间：10月14日 至 10月26日
💬 活动主旨：吐槽是门手艺，进步需要勇气。
毕竟——
ACGO的bug或许会迟到，但我们想修好它的心，永不缺席！ 🛠️
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
👉 往期话题</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/36482"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7" style="width:28px;height:28px;padding:0px"><div
class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/86bef79ccff04644903237e864defff0.png" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">AC君</p></a><div class="AuthorInfo_identityWrap__RM_Zw"><div
class="AuthorInfo_badgeList__5ortF"><img src="https://attach.acgo.cn/picture/8255ead013964310a4eab7a6defbe55c.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="倔强青铜"/><img src="https://attach.acgo.cn/picture/66a3482736ec474f9b9687dbc5472f69.png"
class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="管理员"/></div></div></div><div class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>1347</span><span>阅读</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>368</span><span>回复</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>63</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/study/58203"><h2 class="PostList_title__yZMjf"><span>#创作计划#
Tarjan 学习笔记</span><span class="PostList_greatLabel__X00F9">精华</span><span class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>TARJAN 强连通分量学习笔记
可能更好的阅读体验
前言
> 声明：跳过本部分的阅读并不影响您学习算法。
其实笔者老早一段时间就已经接触到连通一系列问题了，当时是在洛谷网校听的，老师讲的很好，就是我当堂并没有听懂。
大概是在一两周后吧，我去查了很多资料，还发帖求助过，不过越查越乱。我发现基本上每个博客甚至是教辅，都有对 Tarjan 不同的解释。就以对图边的分类来讲吧，OI-wiki 上分成了四种边，洛谷网校上分成了三种边，《算法竞赛》上分成了两种边，《信息学奥赛一本通》上甚至没有分类。类似于上述的例子还有很多。
于是我就决定先放一放。
几天前碍于 csp，决定重新学一学，通过更广的学习面，于是有了本篇博客。旨在想用蒟蒻的更好理解的语言，为大家讲清这个“庞然大物”。与其说是写给自己的学习笔记，不如说是给后人的“避坑指南”。
记录
> 如果您还能看到这段话，代表笔者还打算继续更新。
> 目前计划：更新边双点双（会重新写一篇博客）。
* upd 2025.09.24 构思好了介绍强连通分量的框架，同时手搓（手写）了一份“小博客”。
* upd 2025.09.27 更新完了除例题外的所有部分。
* upd 2025.09.29 写完了所有部分。
* upd 2025.10.06 发现了一处笔误。
强连通分量
概念理解
* 强连通：在一个有向图 GGG 中，如果存在两个节点 u,vu,vu,v 是互相可达的，即从节点 uuu 开始，存在一条路径到达节点 vvv，同时节点 vvv 也存在一条路径到达节点 uuu，则称 uuu 和 vvv 是强连通的。
* 强连通图：如果一个有向图 GGG 中，所有节点互相强连通，则称 GGG 是强连通图。
* 强连通分量（Strong Connect Component，下文直接将其称为 SCC）：对于一个有向图 GGG，如果 ta 不是强连通图，那么必然可以将其分为多个强连通子图（一个点构成的图也是强连通图），如果每个强连通子图都是极大的，那么我们认为这些“极大的强连通子图”即为强连通分量。
其中极大的意思是无法在扩张了，满足对于一个 SCC，不存在一个不属于该 SCC 的节点与该 SCC 中所有节点互相强连通。
以上图举例，我们认为 {a,b,c,d,e}{a,b,c,d,e}{a,b,c,d,e} 属于同一个 SCC，而并非两个 SCC。
算法讲解
让我们先画一个图。
为了引出算法，让我们再画一个 DFS 搜索树。
由于笔者太垃圾了，并不会对边进行上色，就将就着看吧（（（。
假设按照 {a,b,d,c,f,e}{a,b,d,c,f,e}{a,b,d,c,f,e} 的顺序进行 DFS。我们讲所有指向未被搜索的边叫做树边（如图中黑色边，且必须由父亲指向儿子），而指向已被搜索的边叫做非树边（如图中黄色边）。
好，接下来让我们直接推出一个定理。
* 不存在两个节点 uuu 和 vvv，满足两点不为祖孙关系，且在 uuu 和 vvv 的子树中有非树边互相连接。换句话说，如果在 uuu 的子树中有一个点由一条非树边指向 vvv 的子树的某个点，那么 vvv 的子树中就一定没有一个点由一条非树边指向 uuu 的子树的某个点。
证明：
> 因为两个点访问顺序必然有一个先后，当访问其中一个节点的子树时，必然会顺着那条所谓的非树边访问另外一个未被访问的节点的子树的某个节点，那么那条非树边就成了树边了，证毕。
为了方便后面的表述，我们引入一个数组 dfn，为时间戳，表示每个节点被 DFS 搜索到的顺序。
一般用代码这么实现：
然后再定义一个 SCC 中的根为其中 dfn 最小的节点。
让我们再引出一个定理：
* 一个 SCC 中的所有点必然出现在其的根的子树中。
证明：
> 使用反证法。
> 如果一个 SCC 中的点 xxx 不在根的子树中，而是根的祖先，那么 xxx 的 dfn 必然小于 SCC 的根，矛盾。
> 如果一个 SCC 中的点 xxx 与根没有关系（指不是祖孙关系），那么想要与根强连通，必然需要来回的两条非树边，这样就违背了前面的定理。
> 故证毕。
至此，你已经理解了在强连通分量中，Tarjan 算法的主要应用。
那么如何判断在根的子树中那些节点属于 SCC 呢。我们需要引入一个新的数组 low，也就是通过最多一条非树边能到达的 dfn 最小的祖先的 dfn。
只要当存在一个节点 xxx 满足 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么它必然是 SCC 的根。
上述的定理可能会很无厘头，甚至荒谬，笔者并没有水平可以证明它（如果您有证明过程，欢迎在评论区给出），但是我可以保证你举不出反例。
或许你会觉得很晕，让我们回到最开始的图来举例吧。
在上述图中，SCC 有三个，分别为 {f},{e},{a,b,c,d}{f},{e},{a,b,c,d}{f},{e},{a,b,c,d}；其中，按照 {a,b,c,d,e,f}{a,b,c,d,e,f}{a,b,c,d,e,f} 的顺序，dfn 值分别为 {1,2,4,3,6,5}{1,2,4,3,6,5}{1,2,4,3,6,5}，low 值分别为 {1,1,1,1,6,5}{1,1,1,1,6,5}{1,1,1,1,6,5}。正好符合我们的“猜测”。
让我们看看 low 的更新步骤。
* 如果节点 uuu 可以通过一条边访问一个未被访问的节点 vvv，那么该边为树边。我们需要先搜索节点 vvv，然后更新 lowu=min{lowu,lowv}\text{low}_u=\min{\text{low}_u,\text{low}_v}lowu =min{lowu ,lowv }，因为树边并不影响我们对于“经过最多一条非树边”的限制。
* 如果节点 uuu 可以通过一条边访问自己的祖先 vvv，那么该边为非树边。我们更新 lowu=min{lowu,dfnv}\text{low}_u=\min{\text{low}_u,\text{dfn}_v}lowu =min{lowu ,dfnv }。注意必须得用 dfnv\text{dfn}_vdfnv 更新，因为已经消耗了“最多一条非树边”的限制。
*
* 如果节点 u,vu,vu,v 没有祖孙关系，那么什么也不做。
然后是回溯，我们需要再引入一个栈辅助。每个节点 xxx 在被访问时就先压栈，当其把所有边都访问完之后开始回溯。判断如果 dfnx=lowx\text{dfn}_x=\text{low}_xdfnx =lowx ，那么该节点必然为 SCC 的根，我们只需一直弹栈直至弹出节点 xxx，中间的所有节点均为同一个 SCC。
怎么样，很神奇吧。同样的，无法证明其正确性，但是可以很轻易的证明所有不为同一个 SCC 的点 vvv，一定会在此之前先被弹栈。因为如果 vvv 与 xxx 不强连通，那么必然是 lowv\text{low}_vlowv 为一个大于 dfnx\text{dfn}_xdfnx ，小于等于 dfnv\text{dfn}_vdfnv 的数（因为节点 xxx 是一定可以通过树边直达 vvv 的），既然时间戳比根 xxx 晚，所以就能很轻易的得出时间戳为 lowv\text{low}_vlowv 的节点会在 xxx 回溯之前将 vvv 弹栈。
上述推导建议自己再多举几个例子，稍微理解后再往下看，如果还有疑问，可以直接提出。
为了更加实际些，我将给出模板代码以加深印象（Tarjan 模板形式很多，建议选择一种自己最喜欢的背下来，今后就不要改了）。
例题讲解
P2863 [USACO06JAN] THE COW PROM S
传送门
一个很板很板的题，再弹栈的时候判断一下 SCC 的元素即可。
具体请见代码。
P3387【模板】缩点
传送门
首先我们要知道一个关于 SCC 的定理。
* 一个点必然可以通过若干条路径遍历完 SCC 内的所有点并回到起点。
这个很好证明，强连通嘛，过去回来。
那么一条贪心策略就呼之欲出了。
> 每到一个点，就将其 SCC 内的所有点都遍历一次。
不仅白白更新了答案，又回到了起点，稳赚不赔。
然后我们就引出了连通性中一个最常见的分支，也就是缩点。
在本题中，缩点实际上就是通过将每个 SCC 缩成一个点，将原图化简成一个 DAG（有向无环图）。
DAG 能干的事可多了，因为它可以进行拓扑排序，这样我们就可以进行 DP 了。
回到这道题中，我们可以将每个 SCC 缩成一个点，同时将权值累加，最后跑一个类似于 LIS（最长上升子序列）的 DP 即可。
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
传送门
"牛牛 OJ"的题还是不错的。
容易发现，“喜欢”其实就是可达罢了。同样是因为 SCC 互相可达的性质，这题依旧可以缩点。
缩完点之后，我们可以保证最多只有一个“点”满足所有点均可达。因为如果存在两个点，那么就出现环了。
但是考虑到我们找这个“点”不是很方便，可以考虑到这个“点”的另外一个性质，那就是出度为 000。同样的理由，如果出度不为 000，那么就有环了。
于是我们可以写出这个一份代码：
但是这样并不能直接 AC，我们犯了一个很容易忽视的细节，那就是出度为 000 的点不一定只有一个，因此还需要特判，当存在多个出度为 000 的点时直接输出 000。
参考资料
《深入浅出》，《算法竞赛》，《信息学奥赛一本通》，《算法竞赛进阶指南》，OI-wiki，Link。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本文共计 994099409940 个字符，从构思开始共计花了 555 天，每天码字时间大于 111 小时，制作不易，求赞 awa。</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/4244987"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7"
style="width:28px;height:28px;padding:0px"><div class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/566db0c9aace43dfbd8ee03b0491c84b.jpg" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">ppl 大帝</p></a><div
class="AuthorInfo_identityWrap__RM_Zw"><div class="AuthorInfo_badgeList__5ortF"><img src="https://attach.acgo.cn/picture/f5787266f7a44bc58908980cff5854cf.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="传道者"/><img
src="https://attach.acgo.cn/picture/7c07775d2f984a44a57e612ec87703cd.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="题解仙人"/><img src="https://attach.acgo.cn/picture/a91de3ca599e4ba29b72706eb2c133e4.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="CSP-J一等奖"/><img src="https://attach.acgo.cn/picture/7f8de6100b7247fdb9c93939ccff2fc2.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="尊贵铂金"/><img
src="https://attach.acgo.cn/picture/7508aafdf4844ceaa04087efe6c657a8.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="出题人"/><img src="https://attach.acgo.cn/picture/9555b5f84d5f48d189e986d0cf82937c.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="代码纠察员"/></div></div></div><div class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>447</span><span>阅读</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>115</span><span>回复</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>31</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/depot/34702"><h2 class="PostList_title__yZMjf"><span>ACGO
公开赛申请指南</span><span class="PostList_greatLabel__X00F9">精华</span><span class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>> 本帖为 ACGO 官方团队公开赛申请渠道。欢迎各大 AC 狗友积极投稿公开赛。
> 我们欢迎任何有想法的用户都可以为社区贡献出自己的一份力量。
有关于公开赛的任何疑问可以加群进一步沟通：群聊链接。
2025 年 Q1 比赛档期安排
场次 比赛日期 COCR 入门赛#1 2025 年 1.1 - 1.5 日 COCR 提高赛#1 2025 年 3 月 1 日 COCR 普及赛#1 2025 年 4 月 12 日
出题人权益
资金支持与赞助
出题主办方会得到来自 ACGO 官方团队的资金赞助，包含：
1. 固定礼品奖励：每场赛事将赠送盲盒和勋章作为奖励，这部分费用由社区承担，无需额外费用。
2. 出题人资金奖励：每场赛事为出题团队提供 300 元预算，团队负责人可以提供礼品清单，由 @AC君 负责采购。奖励可以用于额外奖励优秀参赛者，或者用于团队成员的奖励，以此激励团队的积极性和创作热情。
3. 赛事题目归属：赛事中的题目完成后，题目所有权归 ACGO 平台所有。ACGO有权使用这些题目在后续赛事中，或将其纳入平台内容中，推动平台的发展。如果放弃出题人资金奖励，可以保留出题人的题目所有权。
全员参与
公开赛是一种面向全站用户开放的比赛模式，任何用户均可自由参与。
以 COCR 公开赛为例，比赛累计报名人数达到 704 人，其中实际参与答题的人数为 260 人。这种开放形式不仅鼓励更多用户体验比赛的乐趣，也为社区营造了积极的竞争氛围。
推荐位
可以通过 Banner 宣传比赛，吸引更多人参与。
冠名权
1. 赛事的名称和封面均支持自定义设置。
2. 在赛事说明的显著位置，将对出题人进行鸣谢，并附上个人主页的超链接，以便其他用户了解更多信息。
3. 此外，在题面中也会包含出题人的简介，进一步推广出题人。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
申请公开赛具体方法
提交方法
1️⃣ 访问该链接填写表单 ACGO 公开赛申请
2️⃣ 请至少提前一个自然月提交申请，审核将在 10 个工作日左右完成（由于最近 Yuilice 频繁出差，审核速度显著变慢，见谅）。加急请另说明理由。⏳
⚠️ 注意事项
为避免占用公共资源，个人/团队在最近三个月内如果累计被拒绝达到两次，则将暂时无法提交新的申请，需等待三个月后方可继续申请。如果未达到两次拒绝记录，则可正常申请。
请严格按照下述要求提供完整的材料，否则可能会影响申请进度或申请结果。恶意申请可能导致站内禁言、封号等处罚。🚨
个人申请要求
✅ 近六个月内未发生任何违规行为。
✅ 排位赛段位达到铂金级别及以上，或 CSP-J 一等/CSP-S 二等及以上或对等资质（包括但不限于 USACO，CCC，ACSL 等竞赛成绩）。
团队申请要求
✅ 申请人须为题目的主要负责人。
✅ 必须由团队管理员（题库管理员及以上）以团队名义申请。普通成员无法以团队名义申请。
✅ 主要负责人排位赛段位需达到铂金级别及以上，或 CSP-J 一等/CSP-S 二等及以上或对等资质（包括但不限于 USACO，CCC，ACSL 等竞赛成绩）。
整体要求
1️⃣ 题目应当符合核心价值观和公序良俗🌟。
2️⃣ 每道题应当都有独立的出题人和验题人。
3️⃣ 有任何问题请在站内或 QQ 私信沟通 ACGO 相关负责人（AC 君，Yuilice，Macw）💬。
申请文件链接：ACGO 公开赛申请（所有所需要的内容都在这里面，请详细阅读！）
可以寻求的独立验题人
下列用户并没有义务帮忙验题，具体选择权在他们自己手中
1. @MuktorFM CSP-J&S2024 银牌，3 年C++算法学习经验；
2. @亚洲卷王 AK IOI CSP-J&S2024 银牌，洛谷提高题刷题量高达 164；
3. @不会C++的noah CSP-J2024 金牌，数学能力强大，数论知识丰富；
4. @pipilong CSP-J2024 金牌，洛谷等级分 1238；
5. @复仇者_帅童 CSP-J2024 金牌，ACGO 等级分 1668 第 1；
6. @双面人 蓝桥杯国赛二等奖。
7. @Macw07 USACO Platinum with Certified Score, CCC Senior G. Distinction, OUCC High Distinction R1, OUCC China National Merit R2. (Not always available because there is miscellaneous work that needs to be done by Macw07)
提交前的审核清单（自查表）
项目 必要性 阅读并熟悉 “规范使用 Markdown 排版” 必要 阅读并熟悉 “ACGO 题目排版要求” 必要 填写完整的申请表格 必要 打包题目数据 必要 创建邀请赛（或提供题目的链接） 必要 完整的题目解析 Markdown 必要 阅读并熟悉 “数据合法性检验” 必要 算法正确性审查 Markdown 必要 数据合法性检验 C++ Code 必要 比赛 Logo，用于宣传以及将品定制 必要 比赛 Banner，用于站内宣传 非必要 赛时答疑帖链接 非必要，但推荐提供 比赛描述详情页 Markdown 非必要，但推荐提供</p></div></a></div><div
class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/929871"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7" style="width:28px;height:28px;padding:0px"><div class="index_avatarInner__aBS59"><img
class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/66bc98e519344dfea860db3e12ff291f.jpg" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">Macw07</p></a><div class="AuthorInfo_identityWrap__RM_Zw"><div class="AuthorInfo_badgeList__5ortF"><img
src="https://attach.acgo.cn/picture/4011a0b1893d4082b39f2db5c16605a4.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="出道萌新"/><img src="https://attach.acgo.cn/picture/7f8de6100b7247fdb9c93939ccff2fc2.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="尊贵铂金"/><img src="https://attach.acgo.cn/picture/69b3408be92b4141b2bb86b39f93e3e7.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="USACO"/><img
src="https://attach.acgo.cn/picture/7508aafdf4844ceaa04087efe6c657a8.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="出题人"/><img src="https://attach.acgo.cn/picture/24c9828e7ed049b5acb58cbe340b45d5.png" class="BadgeItem_img__3DOJK
BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="AC狗饲养员"/></div></div></div><div class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>2528</span><span>阅读</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>147</span><span>回复</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>33</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/depot/30544"><h2 class="PostList_title__yZMjf"><span>Acgo
竞赛积分系统</span><span class="PostList_greatLabel__X00F9">精华</span><span class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>概述
新版 Acgo\tt{Acgo}Acgo 竞赛分系统参考了 AtCoder\tt{AtCoder}AtCoder 平台的 AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00[1]。
该积分系统基于 Logistic Distribution\tt{Logistic\ Distribution}Logistic Distribution（或 Sigmoid Function\tt{Sigmoid\ Function}Sigmoid Function），类似于 Elo\tt{Elo}Elo 评分系统，但进行了许多修改。
新版竞赛分系统上线后，用户参加 Acgo\tt{Acgo}Acgo 的所有比赛将会有 Rated\tt{Rated}Rated 和 Unrated\tt{Unrated}Unrated（即「评分」与「不评分」）两种状态。
正常情况下参加比赛的选手状态为 Rated\tt{Rated}Rated，状态被评为 Unrated\tt{Unrated}Unrated 包含但不仅限于以下情况：
1. 参加本场比赛前竞赛分超过本场比赛的 Rated\tt{Rated}Rated 分数线限制（RATEDBOUNDRATEDBOUNDRATEDBOUND）；
2. 比赛中作弊，被取消比赛成绩；
3. 本场比赛因不可抗力因素导致无法正常进行的将参与本场比赛的所有用户设置为 Unrated\tt{Unrated}Unrated。
对于 Rated\tt{Rated}Rated 的选手，在每场比赛中，会获得一个「表现分」。这个值代表了你在比赛中的表现如何。
粗略地说，你的每场比赛后的竞赛分为「表现分」的加权平均值（最近的比赛权重更高）减去 f(x)f(x)f(x)（xxx 为 Rated\tt{Rated}Rated 比赛的参与次数），其中 f(1)=1200f(1) = 1200f(1)=1200，且 fff 随参加的 Rated\tt{Rated}Rated 比赛的次数增加而逐渐减小并趋于零。
这意味着如果你持续获得 XXX 的表现分，你的竞赛分将从 X−1200X−1200X−1200 开始，并逐渐趋近于 XXX。
请不要担心在第一场比赛中获得很低的竞赛分，如果你参加更多比赛，分数很可能会迅速上升。当参加 101010 场比赛后，你的竞赛分将会非常接近于你的真实实力。
计算表现分
在系统内部有两种类型的「表现分」：PerfPerfPerf 和 RPerfRPerfRPerf（修正后的 PerfPerfPerf） 。
首先，对于每个参赛选手，我们计算出他们的 APerfAPerfAPerf（平均表现分）。
令 Perf1,Perf2,⋯ ,PerfkPerf_1, Perf_2, \cdots, Perf_kPerf1 ,Perf2 ,⋯,Perfk 为一位参赛选手的历史 PerfPerfPerf。其中 Perf1Perf_1Perf1 是最近参加的一场比赛，PerfkPerf_kPerfk 是最早参加的一场比赛，这位选手的 APerfAPerfAPerf 被定义为：
APerf=∑i=1kPerfi×0.9i∑i=1k0.9i\begin{equation} APerf = \frac{\sum_{i=1}^{k}Perf_i \times 0.9i}{\sum_{i=1}{k}0.9^i} \end{equation} APerf=∑i=1k 0.9i∑i=1k Perfi ×0.9i
所有第一次参与 Acgo\tt{Acgo}Acgo 的 Rated\tt{Rated}Rated 比赛的选手的 APerfAPerfAPerf 将会被设置为 CenterCenterCenter。
CenterCenterCenter 和每一场 Rated\tt{Rated}Rated 比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND（即 Rated\tt{Rated}Rated 上限）有关。
Center=RATEDBOUND×0.4Center = RATEDBOUND \times 0.4Center=RATEDBOUND×0.4。
令 nnn 为一场比赛中所有的 Rated\tt{Rated}Rated 的参赛选手的数量，令 APerfiAPerf_iAPerfi 为第 iii 个选手的 APerfAPerfAPerf。那么比赛的 Rated\tt{Rated}Rated 榜单中，排行第 rrr 名选手的 PerfPerfPerf 被定义为满足以下公式的唯一的 XXX：
∑11+6.0(X−APerfi)/400.0=r−0.5\begin{equation} \sum\frac{1}{1 + 6.0^{(X - APerf_i) / 400.0}} = r - 0.5 \end{equation} ∑1+6.0(X−APerfi )/400.01 =r−0.5
这个 XXX 可以使用二分来计算得出。
请注意，以上的排名是所有并列名次的平均值。例如，如果有四个人并列第 333 名至第 666 名，那么这些人的排名为 4.54.54.5。
除此之外，为了避免在第一场比赛中的「表现分」方差过小，Acgo\tt{Acgo}Acgo 使用新竞赛分系统的第一场比赛（这里指 排位赛#4）的表现值会被放大处理，具体如下：
Perf=(Perf−Center)×1.5+Center\begin{equation} Perf = (Perf - Center) \times 1.5 + Center \end{equation} Perf=(Perf−Center)×1.5+Center
最终，对于每个用户其 RPerfRPerfRPerf 使用以下方式计算：
RPerf=min{Perf,RATEDBOUND+100}\begin{equation} RPerf = \min{{Perf, RATEDBOUND + 100}} \end{equation} RPerf=min{Perf,RATEDBOUND+100}
其中 RATEDBOUNDRATEDBOUNDRATEDBOUND 对于不同的比赛是不一样的，每场比赛的 RATEDBOUNDRATEDBOUNDRATEDBOUND 会在竞赛说明中给出。
计算竞赛分
定义 FFF 为：
F(n)=∑i=1n0.81i∑i=1n0.9i\begin{equation} F(n) = \frac{\sqrt{\sum_{i=1}^{n} 0.81i}}{\sum_{i=1}n 0.9^i} \end{equation} F(n)=∑i=1n 0.9i∑i=1n 0.81i
定义 fff 为：
f(n)=F(n)−F(∞)F(1)−F(∞)×1200\begin{equation} f(n) = \frac{F(n) - F(\infin)}{F(1) - F(\infin)} \times 1200 \end{equation} f(n)=F(1)−F(∞)F(n)−F(∞) ×1200
定义 ggg 为：
g(X)=2.0X800\begin{equation} g(X) = 2.0^{\frac{X}{800}} \end{equation} g(X)=2.0800X
该函数可以给更好的表现赋予更多的权重。因此，极好表现与较好表现之间的差异会非常大，而重大失误与一般失误之间的差异则不会那么大。
这样可以使得当参赛者在比赛中打出了超出水平的发挥时，会增加更多的竞赛分；当参赛者在比赛中打出了远低于自己水平的表现分时，不会减少太多的竞赛分；
令 RPerf1,RPerf2,⋯ ,RPerfkRPerf_1, RPerf_2, \cdots, RPerf_kRPerf1 ,RPerf2 ,⋯,RPerfk 为一位参赛选手的历史 RPerfRPerfRPerf，其中 RPerf1RPerf_1RPerf1 为当场比赛的 RPerfRPerfRPerf。那么本场比赛结束后，其竞赛分为：
Rating=g−1(∑1kg(RPerfi)×0.9i∑1k0.9i)\begin{equation} Rating = g{-1}(\frac{\sum_1k g(RPerf_i) \times 0.9i}{\sum_1k 0.9^i}) \end{equation} Rating=g−1(∑1k 0.9i∑1k g(RPerfi )×0.9i )
然后考虑公式 (6)(6)(6) 的 fff 函数对竞赛分的影响，定义以下函数[2]：
mapRating(r)={400exp(400−r400)r≤400rr>400\begin{equation} mapRating(r) = \begin{cases} \frac{400}{\exp{(\frac{400 - r}{400})}} &{r \le 400}\ r & {r \gt 400}\ \end{cases} \end{equation} mapRating(r)={exp(400400−r )400 r r≤400r>400
最终 RatingRatingRating 计算出来为：
TrueRating=mapRaing(Rating−f(n))\begin{equation} TrueRating = mapRaing(Rating - f(n)) \end{equation} TrueRating=mapRaing(Rating−f(n))
其中 nnn 为已经参加的 Rated\tt{Rated}Rated 的比赛场次（包括本场）。
本文档的版本记录
* 10/29/2024 Ver. 1.00: 第一版。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. AtCoder Rating System ver.1.00\tt{AtCoder\ Rating\ System\ ver. 1.00}AtCoder Rating System ver.1.00 ↩︎
2. AtCoderのレート計算式\tt{AtCoderのレート計算式}AtCoderのレート計算式 ↩︎</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/4197450"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7"
style="width:28px;height:28px;padding:0px"><div class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/75f550b3811e4944a09043cf6b064c22.png" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">アイドル</p></a><div
class="AuthorInfo_identityWrap__RM_Zw"></div></div><div class="ReadonlyActionBtns_readonlyActionBtns__57QyK "><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>5346</span><span>阅读</span></div><div class="ReadonlyActionBtns_viewBox__h8Ydj"><span>136</span><span>回复</span></div><div
class="ReadonlyActionBtns_viewBox__h8Ydj"><span>72</span><span>点赞</span></div></div></div></li><li class="PostList_itemCard__9PSc5"><div><a href="/discuss/study/19493"><h2 class="PostList_title__yZMjf"><span>ACGO社区帮助手册</span><span class="PostList_greatLabel__X00F9">精华</span><span
class="PostList_label__ZbVqn">置顶</span></h2><div class="PostList_cardBody__k67S1"><p>📋 ACGO社区帮助手册
🌟 站务汇总
* 站务汇总
🏆 赛事信息
* 巅峰排行榜规则介绍
* 排位分机制揭秘
🗨️ 讨论区指南
* 发帖规范
* 删帖原因
团队招募帖子通常不应发布在“学习讨论”板块；
发布无意义内容；
发布违反社区规范的内容；
发布格式混乱，难以阅读的题解，不符合题解规范的题解。
📘 格式手册
* LaTeX数学公式语法
* Markdown语法教程
🤔 提问与解答
* 提问的智慧
* 题解编写技巧
🤖 AC助手使用指南
* AC助手的正确食用方法
🧠 知识点精华贴
* 知识点精华贴</p></div></a></div><div class="PostList_cardFooter__NVcJI"><div class="AuthorInfo_authorInfo__4sFXu undefined"><a target="_blank" href="/person/36482"><div class="index_avatar__P9HW8 AuthorInfo_avatar__1KKd7" style="width:28px;height:28px;padding:0px"><div
class="index_avatarInner__aBS59"><img class="index_avatarImg__Z6rbG" src="https://attach.acgo.cn/picture/86bef79ccff04644903237e864defff0.png" alt="userId_undefined" loading="lazy"/></div></div><p class="AuthorInfo_nickname__zn45a">AC君</p></a><div class="AuthorInfo_identityWrap__RM_Zw"><div
class="AuthorInfo_badgeList__5ortF"><img src="https://attach.acgo.cn/picture/8255ead013964310a4eab7a6defbe55c.png" class="BadgeItem_img__3DOJK BadgeItem_activeImg__oakXy AuthorInfo_badgeImg__xZUCw" alt="倔强青铜"/><img
