Acgo 竞赛积分系统

CSP复赛考试注意事项

CSP复赛在即，祝各位考生发挥最佳状态，RP+++！以下是考试注意事项，快来看看吧。 CSP复赛考试注意事项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 原文：CSP注意事项 考前准备 1. 考前注意检查身份证、准考证等证件，以及笔等基本工具。 2. CSP 允许带食品和饮料，可带一瓶水和巧克力等进入考场补充体力。 3. 比赛开始前调整屏幕分辨率至个人舒适大小。 4. 比赛开始前将编译器字体调整为平时惯用字体。 5. 在不影响视野的情况下，尽可能调大字号以方便查错，特别是模拟或搜索题目。 6. 比赛前多敲键盘，熟悉常用按键。 比赛时注意事项 1. 保持心态平稳，相信自己。对于题意不明确的情况，通读题面与样例，必要时询问工作人员。 2. 如果机器出现问题，不要慌，可申请加时并利用时间思考题目。 3. 如果感到紧张，可以尝试上厕所冷静一下。 4. 不要因为旁边人写得快而慌乱，每个人的解题速度不同。 5. 仔细读题，通读完后再开始深入思考。 6. 不要因为题目看似简单就急于写代码，先明确每一步要做什么。 7. 对于看似无解的题目，不要提前放弃，尝试几个例子可能找到解题思路。 8. 写题前先在纸上规划思路，判断可行性后再编写代码。 9. 认真计算时间复杂度，避免将低复杂度代码误算为高复杂度。 10. 不要浪费时间在大模拟或大搜索上，到一定程度即可。 11. 数学题或找规律题要在纸上写出来。 12. 充分利用时间，如果15分钟内没有思路就换题。 13. 先写暴力解，再写正解。 14. 时刻计算当前代码的复杂度。 15. 写完程序后，通读代码进行静态查错，注意变量调用、数组大小、变量类型等。 16. 通过样例后，自行设计数据测试程序，确保程序健壮性。 17. 出现问题时，分模块调试程序。 18. 可以使用 #include <bits/stdc++.h>，不需要背诵大量头文件。 19. 代码保存按照考场PDF指示，不清楚可询问监考老师。 20. 避免使用下划线开头的函数，除非自己定义。 21. 变量名避免使用完整单词或不清晰的命名方式。 22. 删除调试语句，定期保存代码。 23. 注意数据范围，合理分配内存空间。 24. 注意输出方式，如取模操作。 25. 自己手写 abs 函数。 26. 注意题目输出要求，如大写问题。 27. 整数指数时避免使用 pow 函数。 28. 注意 scanf 类型正确性。 29. 避免使用 floor 和 ceil 函数。 比赛结束前的注意事项 1. 比赛最后5至15分钟，不要再改动程序。 2. 检查文件名是否正确。 3. 检查是否正确处理文件输入输出。 4. 整理物品，离开时带走垃圾。 代码示例 以上是对考前准备、比赛时注意事项以及比赛结束前的检查事项的详细整理，希望对你有所帮助。 2024 CSP-J/S 第二轮缴费及系统使用说明流程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、赛事相关信息 📍 关于 CCF 2024 CSP-J/S 有关问题的解答 可先点击链接了解： 关于CCF CSP-J/S2024有关问题的解答 📋 关于 CCF 2024 CSP-J/S 各省特派员信息 点击链接查看各省负责人联系方式： CSP-J/S各省负责人联系方式 📆 CSP-J/S 2024第二轮报名通知 点击链接查看报名通知： NOI报名网站 二、第二轮认证时间 🕐️ 第二轮认证时间：2024年10月26日 * 入门级：8:30-12:00 * 提高级：14:30-18:30 三、第二轮认证参加资格 凡已参加 CSP-J/S 2024 第一轮认证，且成绩符合所在省市第一轮晋级第二轮认证规则者均可参加 CSP-J/S 2024 第二轮认证。 各省晋级规则将陆续公布在“NOI网站—各省新闻”中。 时间 8:30-12:00 14:30-18:30 2024年10月26日(周六) 入门级认证 提高级认证 未参加第一轮认证，或不符合本省参加第二轮认证晋级规则者均不能参加第二轮认证。 四、第二轮认证报名流程 CSP-J/S 2024 第二轮不需要认证者操作报名及指导教师进行审核，由各省负责人直接统一为本省具有晋级资格的认证者报名。 CSP-J/S 2024 第二轮报名流程及操作时间点具体如下 日期 时间 内容 角色 10月2-9日 全天 统一报名 各省负责人 10月10-18日 10月18日 15:00前 认证者审核状态为“请确认报名并缴费”后，认证者如确认参加活动，在报名页面进行交费 认证者 10月19-21日 10月21日 17:00前 生成准考证号、提交报名表、上传考点信息、CCF审核报名表 各省负责人,CCF管理员 10月22-26日 全天 下载准考证 认证者 10月26日 8:30-12:00 入门级认证 入门级认证者 10月26日 14:30-18:30 提高级认证 提高级认证者 👉 查看更多： 欢迎在留言区评论，畅所欲言！

互动｜#刷题必备神曲#

🚀话题#5｜ #刷题必备神曲# 😎大家写作业或者刷题的时候，是不是也有自己专属的“BGM”呢？是有超棒的歌曲想和大家分享，还是有那种因为听歌而发生的奇葩经历呢？不管怎样，都快来这里畅所欲言吧！ 🎵推荐分享 1. 适合刷题的神曲 * 我觉得《冰与火之歌》的主题曲非常适合，那种宏大的气势和神秘的氛围，就像代码世界里的未知挑战，凛冬将至的感觉也特别适合赶稿或者刷题的紧张氛围！你们有什么推荐呢🧐 2. 分享听歌经历 * 有一次光顾着听歌，结果稿都没写完，真是哭笑不得。 🎁 话题奖励 * 奖励设置：抽取3个人，获得ACGO盲盒。 🎁 话题时间 * 活动时间：本次话题活动从10月11日开始，到10月20日结束。在这个时间段内，大家都可以积极参与留言分享哦。 🎁 奖励名单 ID 昵称 3444749 ‮猫条一 2117063 Starsfocxy 3310442 key0213 快来分享你的刷题必备神曲吧😎

互动｜1024吐槽大会

🚀话题#6｜ 1024吐槽大会 😎 1024程序员节即将到来！大家在编程学习过程中，是不是有很多想吐槽的呢？比如学习中最难的算法，编程学习中遇到的最搞笑最或最崩溃的时刻，或者最最难的编程题，或者是ACGO的最难用的地方。不管是什么，都快来这里畅所欲言吧！ 🎁话题奖励 奖励设置：抽取3个人，获得ACGO盲盒1件。 🎁话题时间 活动时间：2024/10/21 -2024/10/30。 🎁获奖公告 ID 昵称 4347789 复仇者 4495551 VIVI 4156430 手持剑，刺锋芒 在这个时间段内，大家都可以积极参与留言分享哦，快来吐槽你的编程学习经历吧😎

互动｜ 我们2岁啦～参与掉落周年限定礼品

🎉🎉🎉 我们2岁啦！🎉🎉🎉 ACGO社区即将2周年啦！🎉这不仅是一段旅程，更是一段充满回忆的成长史。🎊亲爱的同学们，ACGO社区即将迎来它的2周岁生日（11月11日），在此，我们诚挚地邀请每一位同学，共同来庆祝这个特别的时刻！🎂 参与评论赢取周年限定礼品 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📅【活动时间】 从11月5日开始，一直到11月17日24点结束哦！🕙 🎁【如何参与】 * 方式1. 在评论区分享你与ACGO的小故事，快来告诉我们你是如何认识社区的，在社区发生过最难忘或最开心的一件事…… * 方式2. 分享你对ACGO社区的祝福。💕！在这个特殊的日子里，你又有哪些心里话想对ACGO说呢？🧐 🏆【活动奖励】 * 限定保温杯+2周年贴纸：我们会从大家分享的故事中，精心挑选出3-6篇最真实、最走心、最能打动我们的小故事，获得我们特别准备的2周年限定礼品！🥤 * 2周年限定贴纸：另外，我们还会在参与留言的同学中，随机抽取10位送上ACGO贴纸。🎁 💌【特别提示】 注意啦，我们会在活动结束后的一周内公布获奖名单哦，请大家耐心等待。😜 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 感谢每一位同学一直以来对ACGO社区的支持与陪伴。未来，让我们继续携手同行，在ACGO社区创造更多美好的回忆！✨

复仇者联盟の邀请！

欢迎您加入复仇者联盟！

Acgo 竞赛积分系统

概述 新版 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.9^i}{\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.81^i}}{\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_1^k g(RPerf_i) \times 0.9^i}{\sum_1^k 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のレート計算式 ↩︎

无聊的我雕了一个南瓜

Happy Halloween 🎃👻万圣节快乐！\textcolor{orange}{\textbf{\Huge \text{Happy Halloween 🎃👻}}}\\ \textcolor{orange}{\textbf{\Huge \text{万圣节快乐！}}} Happy Halloween 🎃👻万圣节快乐！ > 无聊的我雕刻了一个南瓜。 Trick or Treat 🍭👻\textcolor{purple}{\textbf{\Huge \text{Trick or Treat 🍭👻}}} Trick or Treat 🍭👻 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 游《温哥华》记 - 2024 Thanksgiving

排位赛#13题解

排位赛 #13 题解 写在前面 难了好多！第四题提交 2 次才 AC，呜呜呜，我菜得模拟都不会了。 个人评分：红红黄黄黄绿蓝紫。 T1 年龄分为今年之前的和今年之后的，直接处理比较麻烦。不妨将出生年移到今年，相应的下一场流星的时间也要修改，即 E←(E+B) mod 50,B←0E\gets(E+B)\bmod 50,B\gets 0E←(E+B)mod50,B←0。然后把寿命的起点移到下一场流星，也就是 L←L−E,E←0L\gets L-E,E\gets 0L←L−E,E←0。最后的答案当然就是 max⁡{0,⌊l50⌋+1}\max\{0,\lfloor\frac l{50}\rfloor+1\}max{0,⌊50l ⌋+1}。注意多测。 T2 因为这是一道不卡时间的字符串处理，所以我们可以使用 Python 解题。注意特判越界。 T3 首先是无解的情况：N≤KN\leq KN≤K，因为这样可以直接跳过去。 排除这种情况，我们考虑如何求出人数。发现“在每个长度 K+1K+1K+1 的连续区间内都有至少 PPP 个 TNT”是“至少 PPP 人可以通过”的充分必要条件，否则将不会有足够的 TNT 支撑玩家通过。因此，我们求出每一个长 K+1K+1K+1 的区间中 TNT 的数量，取最小值，这就是最多能成功通过 TNT 路径的玩家人数。 求数量的过程可以选择滑动窗口或前缀和，时空复杂度 Θ(n)\Theta(n)Θ(n)。 T4 典中典之，大模拟。。。特别坑！ 我们考虑把每一个牌用一个结构体存起来。存放点数时，我们按序用 map 映射点数，方便排序。然后，我们将牌按照第一点数，第二花色的顺序排序。最后按题意由优先级高到低判断——先判断三种顺子，如果不是顺子，就在桶排序后按照点数出现次数判断牌型。大坑：五张牌相同属于 High Card（高牌），而不是其它奇奇怪怪的牌型！被坑了一次提交23333。 代码可能比较抽象，凑合着看吧。 T5 如果 T4 是大模拟，这题就是小模拟。加一条边最多在两边各加一个小正方形，判断两边的正方形四边是不是都被加了即可。可以用简单的位运算技巧方便判断。注意分类讨论。 T6 直接看比较麻烦，因为答案似乎被两个维度所限制。但是我们观察式子： ∑i=1n((∣xi−x∣+∣yi−y∣)×ϵi)\sum_{i=1}^n((\left|x_i-x\right|+\left|y_i-y\right|)\times\epsilon_i) i=1∑n ((∣xi −x∣+∣yi −y∣)×ϵi ) 可以直接拆开： (∑i=1n(∣xi−x∣×ϵi))+(∑i=1n(∣yi−y∣×ϵi))\left(\sum_{i=1}^n(\left|x_i-x\right|\times\epsilon_i)\right)+\left(\sum_{i=1}^n(\left|y_i-y\right|\times\epsilon_i)\right) (i=1∑n (∣xi −x∣×ϵi ))+(i=1∑n (∣yi −y∣×ϵi )) 要使其最小，就要使加号左右最小，而两边均只关于 xxx 和 yyy。权值 ϵi\epsilon_iϵi 很碍眼，由于 ϵi\epsilon_iϵi 不大，不妨把每一个 (xi,yi,ϵi)(x_i,y_i,\epsilon_i)(xi ,yi ,ϵi ) 拆分成 ϵi\epsilon_iϵi 个 (xi,yi)(x_i,y_i)(xi ,yi )。设拆分后有 mmm 对坐标，则上式可改写为： (∑i=1m∣xi−x∣)+(∑i=1m∣yi−y∣)\left(\sum_{i=1}^m\left|x_i-x\right|\right)+\left(\sum_{i=1}^m\left|y_i-y\right|\right) (i=1∑m ∣xi −x∣)+(i=1∑m ∣yi −y∣) 要使加号左边最小，xxx 应该取什么呢？由绝对值性质得： ∣x−xi∣+∣x−xn−i+1∣≥∣xi−xm−i+1∣\left|x-x_i\right|+\left|x-x_{n-i+1}\right|\geq\left|x_i-x_{m-i+1}\right| ∣x−xi ∣+∣x−xn−i+1 ∣≥∣xi −xm−i+1 ∣ 代入 i=1,2,⋯ ,ni=1,2,\cdots,ni=1,2,⋯,n 得 {∣x−x1∣+∣x−xm∣≥∣x1−xm∣∣x−x2∣+∣x−xm−1∣≥∣x2−xm−1∣⋮∣x−xm∣+∣x−x1∣≥∣xm−x1∣\begin{cases} \left|x-x_1\right|+\left|x-x_m\right|&\geq\left|x_1-x_m\right|\\ \left|x-x_2\right|+\left|x-x_{m-1}\right|&\geq\left|x_2-x_{m-1}\right|\\ \vdots\\ \left|x-x_m\right|+\left|x-x_1\right|&\geq\left|x_m-x_1\right| \end{cases} ⎩⎨⎧ ∣x−x1 ∣+∣x−xm ∣∣x−x2 ∣+∣x−xm−1 ∣⋮∣x−xm ∣+∣x−x1 ∣ ≥∣x1 −xm ∣≥∣x2 −xm−1 ∣≥∣xm −x1 ∣ 求和得 2∑i=1m∣x−xi∣≥∑i=1m∣xi−xm−i+1∣2\sum_{i=1}^m\left|x-x_i\right|\geq\sum_{i=1}^m\left|x_i-x_{m-i+1}\right| 2i=1∑m ∣x−xi ∣≥i=1∑m ∣xi −xm−i+1 ∣ 等号成立，当且仅当 x⌊m/2⌋≤x≤x⌈m/2⌉x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}x⌊m/2⌋ ≤x≤x⌈m/2⌉ 。所以要使原式最小，xxx 的取值范围当然就是 x⌊m/2⌋≤x≤x⌈m/2⌉x_{\lfloor m/2\rfloor}\leq x\leq x_{\lceil m/2\rceil}x⌊m/2⌋ ≤x≤x⌈m/2⌉ 。 当然右边关于 yyy 也是一样的。所以代码实现很简单，时间复杂度为 Θ((∑ϵi)log⁡(∑ϵi))\Theta((\sum\epsilon_i)\log(\sum\epsilon_i))Θ((∑ϵi )log(∑ϵi ))。log 可以用 nth_element 求中位数去掉，当然直接排也没事。 T7 如果你比较熟悉 FJ，你应该对一道典题不陌生——Corn Fields，是状压 DP 的板题。而这道题类似于本题，区别在于 NNN 变大了（12→50012\to 50012→500），模数变了，同时不可以一只乌龟都不养。看起来 NNN 变大时间复杂度不行了，但是状压作法的复杂度略低于 O(n22m)O(n2^{2m})O(n22m)，nnn 变大的影响不大，所以还是状压板题。 设 fi,jf_{i,j}fi,j 是在第 iii 行，当前行状态为 jjj 时的方案数，0 为不放，1 为放。我们知道不合法的方案有：行内有连续的 1，有 1 出现在养殖设备的位置。如果该行合法，我们枚举状态 kkk。kkk 同样需要满足上述条件，同时 kkk 与 jjj 不能有同位 1，因为行间也不能有连续的 1。如果一切都符合规则，则可以转移：fi,j←fi,j+fi−1,kf_{i,j}\gets f_{i,j}+f_{i-1,k}fi,j ←fi,j +fi−1,k 。 别忘了边界条件：当 i=0i=0i=0 且 jjj 合法时，fi,j=1f_{i,j}=1fi,j =1。 细节看注释。 T8 一道毒瘤的数据结构题。（数据结构题！） 数据范围是 10510^5105，暴力显然不行，可以考虑 mnm\sqrt nmn 的分块作法或者 mlog⁡nm\log nmlogn 的线段树作法。如果您很强，那么还有可能用一堆树状数组以优雅的小常数完成此题，不过我不会。这里用线段树作法。 首先是线段树的每个节点要存什么。显而易见的是加法懒标记和区间立方和的值。除此之外，由于高次和需要低次和推导而来，所以我们需要再维护区间平方和与区间和的值。 然后是线段树的核心——懒标记下传。 设当前区间的长度为 lll，加法标记的值为 xxx，s1,s2,s3s_1,s_2,s_3s1 ,s2 ,s3 分别是修改前的 1,2,31,2,31,2,3 次方和，s1′,s2′,s3′s_1^\prime,s_2^\prime,s_3^\primes1′ ,s2′ ,s3′ 分别是修改后的 1,2,31,2,31,2,3 次方和。 从最简单的说起：区间和当然增加了 lxlxlx，也就是 s1′←s1+lxs_1^\prime\gets s_1+lxs1′ ←s1 +lx。 然后是平方和： s2′=∑(ai+x)2=∑(ai)2+2x∑ai+∑x2=s2+2xs1+lx2\begin{aligned} s_2^\prime&=\sum(a_i+x)^2\\ &=\sum(a_i)^2+2x\sum a_i+\sum x^2\\ &=s_2+2xs_1+lx^2\end{aligned}s2′ =∑(ai +x)2=∑(ai )2+2x∑ai +∑x2=s2 +2xs1 +lx2 最后是立方和： s3′=∑(ai+x)3=∑(ai)3+3x∑(ai)2+3x2∑ai+∑x3=s3+3xs2+3x2s1+lx2\begin{aligned} s_3^\prime&=\sum(a_i+x)^3\\ &=\sum(a_i)^3+3x\sum(a_i)^2+3x^2\sum a_i+\sum x^3\\ &=s_3+3xs_2+3x^2s_1+lx^2\end{aligned}s3′ =∑(ai +x)3=∑(ai )3+3x∑(ai )2+3x2∑ai +∑x3=s3 +3xs2 +3x2s1 +lx2 代码实现时，不要忘记上传节点信息的时候三种区间信息都要更新。为了防止负数出现，我们在输入的时候把所有负数取模成正数即可。 完整代码（稍有压行）。 尾 祝大家 CSP-J2/S2 rp++！

2024CSP-J&S江苏游记

DAYFOREVER(前言) 写在前面：作者这次状态极差，很多题都写挂了。无论如何，之前打OI的时光还是很值得留念的。 已AFO。2022.12.14~2024.10.27 DAY-1(2024/10/25) 听了一会歌，复习了一下模板，就去睡觉了，毕竟明天要考一天 睡得还行。但是我后来才知道，我应该是失眠了。 DAY1上午(2024/10/26) 幸好没有被分到南京去。 六点半起床，开半小时去苏州考场。到的时候已经七点半了，还算是比较早的，但是已经有很多人在站着了。天气是阴天。怎么考CCF的时候全是阴天啊喂 精神还行，没有很紧张，毕竟是J。但是怎么还有身高只有一米二的小朋友来考（记住这个小朋友，待会会考）。 分到的考场好闷。考场很小，几乎是挤在一块的。还有足足一个小时的时间开考，我也不急，先打了个Floyd模板试试手，测测运行时间。 大概8：24的时候，监考员下发了压缩包。什么？你跟我说有密码打不开？好吧雀氏打不开，但是可以预览文件。 看了四个文件名：chain?接龙？感觉是模拟。explore？探索？感觉是模拟。poker?扑克牌？感觉是模拟。sticks?火柴棒摆数字？感觉还是甜蜜的模拟。 随着我点开pdf的那一刻，我看到了第一题——poker。读完这题后，我随之感叹一句：J组的第一题水分又增加了114514%，真是滑天下之大稽。我用5分钟过了这道题。 第二题就是一个纯纯的模拟。感觉只有普及-的难度。狂写两分钟，结构代码debug半小时。无论怎样还是过了。 第三题火柴棒，果然猜对了：摆数字。一开始想着用贪心，但是不知道怎么了没有想出来。这时候看了一眼特殊性质：两个全部和7的倍数有关。我很快推出了两个性质，60分到手。然后我又去打表n≤20，打完之后很快发现这里有很明显的规律。 这时候突发事件来了，在整个刚才想的过程中，我的头越来越痛。感觉天旋地转，看到我有三只手。我觉得是机房太闷了，于是去上了个厕所。但是这种症状并没有减轻，差点躺在厕所里。那怎么办？硬抗。我当时这样想。 回来之后，感觉状态已经很差了。于是我朦胧找到的规律被我否决了，于是100分的机会没有拿到，只拿到了70分。 再看第四题。第一眼感觉要把他们连边。但是这样一来连的边就太多了。考虑dp。结果推了2个小时硬是没有推出来，我不会菜的连绿题都不会了吧。 还剩5分钟结束。我只能保存文件。估分100+100+70=270，这个分放在江苏估计连二等奖都拿不到。 考完的时候，那个小朋友说他AK了。wc真是天大的打击。问他了一下思路，也都差不多。 DAY1下午(2024/10/26) 在附近吃了个KFC。然后继续考S。不幸的是，状态仍旧不好，我的好手表竟然说我缺氧，tmd气死我了。 打开文件先看到第一题。哇这么水吗？我直接排序+O(n)遍历。10分钟的时候就写完了。 看到第二题。我勒个超速检测啊，他这次甚至还有公式。模拟了一遍之后很容易求出第一问。至于第二问，可以把检测到的摄像头看作区间，求最大交错区间，然后减去。但是这样的复杂度是O(n2)O(n^{2})O(n2)的，会被卡死。 看了一会，发现他们有单调性，那么两个东西都用二分，O(Tnlogn)O(Tnlogn)O(Tnlogn)解决。这题卡了我一小时。 这时候，脑子已经有点白热化了。 接着看第三题涂色。这题感觉很玄学啊，要用dp。本来要dfs的，后来看了一下数据，老实了。 dp[i][0]和dp[i][1]的转移卡了我有一个多小时。列了满满一草稿纸，算出一个很奇怪的转移方程。结果果然不对。但是思路应该没问题啊？？心态有点崩了。 顺便看了一下第四题，感觉有黑题。就先不做了。于是一直再调前面的题目。 后记(2024/10/27) 我怎么也没想到，3题全写挂？！70+0+5=75,对不起我要退役了。最后4勾的倔强。 这次也不能怪别人，不知道为什么状态出奇的差。也许最近压力太大了？我不知道，也许这就是OI的魅力。 比赛完，有人欢喜有人愁。漫步在校园里，远边夕阳早已落下，楼房灯火通明。或许，夕阳落下的，还有我的生涯吧。 AFOed.也许这条道路不适合我走，心中会有不甘，但是早已没有时间给我再来一次。 "总为浮云能避日，长安不见使人愁。"

ACL｜通用「树状数组」模板

前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 像使用 std::vector 一样，使用「树状数组」。 本文将介绍 AC(AtCoder) Library 中提供的 fenwick_tree 模版。 本文最后提供的 FenwickTree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。 树状数组简单来说即为支持在线求前缀和的一种特殊数据结构（请把复杂的功能交给「线段树」）。 使用树状数组，不需要知道树状数组的原理！ 当你需要一边「修改数组中单个元素」，又同时需要查询数组的「前缀和」时，那么不要犹豫，把此模版粘贴你的代码中去吧！ 然后就可以像使用 STL\tt{STL}STL 中的 std::vector，std::map 等容器一样使用「树状数组」啦！ 示例 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以下为使用 FenwickTree 和 Modint 后，挑战赛#10 的第 6 题，Ptorrweee 最后统计答案部分的代码。 可以看出，结合使用两个算法模板后，可以将最后的代码变得十分简洁。将「树状数组」封装，特别在题目需要有多个树状数组求解时尤其方便。 操作 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 构造函数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 定义一个长度为 nnn 的数组 a0,a1,⋯ ,an−1a_0, a_1, \cdots, a_{n - 1}a0 ,a1 ,⋯,an−1 。所有元素被初始化为 000。 注意 T 的类型为 int，long long，unsigned，unsigned long long 或 Modint 类型。 且 0≤n≤1080 \le n \le 10^80≤n≤108；构造函数的时间复杂度为 O(n)\mathrm{O(n)}O(n)。 2. ADD ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 执行 a[p] += x 操作。 要求 0≤p<n0 \le p \lt n0≤p<n；时间复杂度 O(log⁡n)\mathrm{O(\log{n})}O(logn)。 3. SUM ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 该方法返回 al,al+1,⋯ ,ar−1a_l, a_{l + 1}, \cdots, a_{r - 1}al ,al+1 ,⋯,ar−1 的和。 2. 该方法返回 a0,a1,⋯ ,ar−1a_0, a_{1}, \cdots, a_{r - 1}a0 ,a1 ,⋯,ar−1 的和。 以上方法要求 0≤l≤r≤n0 \le l \le r \le n0≤l≤r≤n；时间复杂度皆为 O(log⁡n)\mathrm{O(\log{n})}O(logn)。 FENWICKTREE.CPP ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------