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 手持剑，刺锋芒 在这个时间段内，大家都可以积极参与留言分享哦，快来吐槽你的编程学习经历吧😎

规则怪谈《你让我张三遵守规则》第二十二章

简介：【惊悚+诡异++爽文+国运=正经小说】 阅读规则： 1、请不要在镜子前阅读本书。 2、阅读本书时，如果听到身后传来脚步声，请放下手机或电脑笔记本，不要回头！千万不要回头！ 3、晚上1点到4点，请不要阅读本书。如果不小心阅读本书，请务必在4点44分前，放下手机或电脑笔记本，准备睡觉。 4、每周至少要阅读本书三次，如果忘记，请保持镇定，并将本书推荐给你的朋友。 5、本书永远无法阅读完，如果看到最新章，请保持理智，在心里默念：读者很帅，作者更帅！ 6、本书不存在1星到4星的评价，如果看到非5星价，请假装没看到，并给出5星评价。 7、如果发现自己的手机或电脑笔记本没有本书，请假装什么都没发生过，并在心里默念：我是人类。然后，你就会醒来。 第22章 妈妈纸条的真相 “啊——” “你……你……你是……” 穿着白色连衣裙刚刚回到家里的妈妈，看到儿子卧室的门口站着一个手持大斧子的壮汉，吓得腿都软了。 整个人扶着墙，差一点儿就要因为站不稳而摔倒在地上。 壮汉朝着妈妈瞪了一眼，吓得妈妈马上捂住嘴，不敢继续出声。 “女人！我劝你安静一点儿！” “老子只是来求财的！” “你家的猫值钱，将猫给我，我就走！” “否则的话……” 壮汉说着，手中的斧头朝着卧室的房门上狠狠地劈下去。 咔嚓一声！ 房门被瞬间劈开，露出更大的窟窿。 而张三此时也能清晰地看到刚刚从外面回来的妈妈。 此时，张三又看了一眼卧室里钟表上的时间。 23点55分。 “只要你不伤害我的孩子，我什么都给你！什么都给你！” 女人说着，小心翼翼地走进客厅，朝着在卧室里的张三温柔地说道：“孩子，不要怕！有妈妈在！” “听妈妈的话，将猫猫给他！” “给他猫猫，咱们就安全了。” 壮汉一脸狰狞地看着房间里的张三，沉声道：“没错！我只是为了求财，不想造成不必要的伤害！” 张三看了一眼时间。 23点56分。 张三抱着猫猫，从床上下来，走到了卧室的门口，看了一眼在门口手持斧子的壮汉。 刚想要将猫猫交出去的一瞬间，张三猛然想到了什么，但却又有些想不清刚刚闪过自己脑海之中的那一句 至关重要的话是什么。 精神净化！ 下一个瞬间，刚刚似乎被某种力量影响而忘却的那句话，再次出现在张三的脑海之中。 门口放钥匙托盘下面压着的那张纸条上的第4条。 如果遇到无法化解的危机，可以牺牲猫猫。 没错！ 猫猫是可以牺牲的。 但，猫猫真的是可以牺牲的吗？ 张三朝着站在客厅里的妈妈看了一眼，忍不住问道：“妈妈，门口的那张纸条，是你写的吗？” “是啊！” 妈妈看向张三，眼神之中充满了关切与疼爱。 妈妈轻轻蹲在地上，保持着和此时只有八岁男孩高的张三平视。 这世上，只有妈妈和孩子说话的时候，才会如此温柔吧。 “孩子，你要知道，对妈妈来说，这世上没有什么比你对我更重要！” “当初妈妈十月怀胎，挺着大肚子连晚上睡觉都难受。” “可就算这样，妈妈还是忍受着痛苦，将你生下来，将你养大。” “你爸爸家暴我，还在外面欠赌债，甚至我都被追债的人毒打过。” “可就算这样，妈妈离开那个男人的时候，还是没忘记带着你。” “因为在这个世上，只有是**妈的骨肉血亲。” “没有人比你对妈妈更重要。” “所以……所以妈妈宁愿当单亲妈妈，忍受别人异样的目光，忍受一个人支撑整个家庭的坚辛，妈妈能承 受一切，只要你能快乐长大。只要……” “只要你能一直在妈妈身边。” 这一刻，直播间里的所有网友，无不动容。 这世上，最初的也是最伟大的，就是母爱吧。 她不管自己多苦多累，都会将你哺育长大。 因为你对她来说，在是这世上最最重要的珍宝。 “孩子，听妈妈的话，将猫猫给他。” “只要将猫猫给他，你就安全了。” “妈妈就能和你，一直在一起了。” 此刻，不少在看直播的网友，早已泪如雨下。 这世上，还有什么能比妈妈更值得你去爱呢？ 张三听到这里，也低下了头，轻轻抚摸着怀里的猫猫。 “没错。对妈妈而言，孩子对自己更重要。” “就算是牺牲自己，也不愿意让孩子受到伤害。” “是吗？” 妈妈轻轻点头。 而在卧室门口的壮汉，也放下手中的斧头，准备接过张三递过来的猫猫。 然而，就在下一个瞬间，张三却是猛然转身，回到了卧室的床上。 壮汉见到这一幕，不由得一愣。 客厅里的妈妈，也是一脸愕然。 甚至连直播间的所有网友都懵了。 “张三这是在干嘛？” “把猫猫给他，就通关了啊！” “这个时候，张三不会想要将这个猫猫卖给对方吧？” “为什么他总是这么多骚操作啊！” 此刻，所有人看向张三，都充满了疑惑和不解。 甚至一些刚刚因为感动而泪流满面的人，看着张三都有些想要骂街。 你特么到底在干嘛！？ 妈妈朝着卧室里的张三喊道：“孩子，快把猫猫给他啊！” “将猫猫给他，妈妈和你就可以一直在一起了！” 壮汉往前迈了半步，朝着卧室里的张三伸出双手。 “我保证，只要你将猫猫给我，我就马上离开！绝不会伤害你！” 不少网友也在疯狂发弹幕。 “此处播放BGM《听妈妈的话》！” “为什么这熊孩子就这么不听话呢！” “这张三到底在想什么？将猫猫给对方，一切就都结束了啊！” “人家只是求财！一只猫猫而已啊！” “之前看日落王国的那个动保女孩，我觉得离谱！现在我看张三，感觉他更离谱！” 而就在直播间的画面里，妈妈一声声呼唤，壮汉也举起双手保证不会伤害张三的时候。 张三看了一眼卧室里的钟表。 23点57分。 继续拖延时间，应该是来不及了。 不过，还有三分钟的时间，应该足够了。 下定决心之后，张三朝着门口的壮汉，还有在客厅的妈妈冷冷地看了一眼。 “你们，别演了！”

原创猜谜-第五期

我曾挑衅西方，是故事 我守护万家，只是为垄断 倡导绿色，一尘不染 加号是我的底气 亦是能够吓退恶势的标志 我来自东方 来自正在苏醒的巨狮

ACGO名人专访第一期macw

建议萌新食用 首先我在这里预祝所有ACGO的同学们拥有一个幸福快乐的国庆小长假！ 对Macw07大佬致以最诚挚的慰问，祝他在加拿大也能有一个美好的假期Macw07没有长假哈哈哈 就在两天前（9月27日）我突然心血来潮，想做一个关于ACGO里名人de采访，然后就找到了我们ACGO的镇站之宝Macw07绝不是因为他很帅 他以ACGO的饲养员成功吸引了我直接无敌了好吧，我有幸加到了他的QQ，与他展开了深刻的关于软件编程的探讨~~他其实很好相处的，虽然有点邪恶（排位赛13直接难爆了）~~接下来，我们看看我与他谈论了啥吧！ 我们的大神依旧是稳定发挥，超级低调不是呀，两年前才接触信奥，实力太恐怖了呀让我这个蒟蒻默默留下了自尊心的泪水，虽然我认为Macw07有所保留，没把真实时间告诉我，绝对不是说他想装13但我们尊重他的回答。继续下一个环节 大神的思考方式就是不一样！认为学习编程是他生活中不可分割的部分，看看我，对编程并没有强大的内驱力支撑每天上编程课跟上刑一样，啊！差距啊！ 这个方法对我来说：非常的有用只不过是把web换成了python的小项目而已绝对没有玩过游戏（自欺欺人） 这一点和我的想法相同，因为封装对手速慢的同学来说真的非常不友好，而且如果你的编程水平较差，很有可能封装都会错像我当然不会啦，在编程比赛中，时间紧，任务重，还是建议多一事不如少一事，避免封装，除了要重复很多次，要用到函数以外（python） 很好，被狠狠的欺骗了，py的各项方法根本用不了，😔，说多了都是泪，你们自己去看我分数。 知州所众，我们ACGO做大做强大部分功劳都在我大部分功劳都在背后的程序猿和老板还有我们亲爱的用户们，而这些改进我一听到后直接开心的跳了起来米小圈。包括我们很希望的深色模式也狠狠的钉在了日程上，我们就一起期待吧！ 这个问题非常重要macw的回答为java党和python党吃下了一颗定心丸，当然c一直都不是最方便，最简洁的语言，包括我在学c的时候就像上刑一样，认为c的代码冗长，没有意义。这些都是正常的，对我们来说也是非常致命的，一旦我们对变成彻底失去兴趣，再有趣的语言也不在有意义，c的前景也不是一片昏暗，真要我总结一下的话，那就是：想要学历学c++，想要有趣和项目选java和python。 没想到macw也有考前综合症，我们就祝贺他考零蛋祝贺他考100吧！ 最后说一下ai测评不是我不想更，是没时间

关于限制使用人工智能工具的新规定

> This article cites the latest regulations of Codeforces 关于限制使用人工智能工具的新规定 看起来神经网络正在创造技术奇迹。不久前，它们在我们的比赛中甚至连最简单的任务都难以完成，但现在它们正在达到无法忽视的新高度。 我们有理由相信这一进步将继续下去，并且可以期待神经网络在编程竞赛领域中取得进一步的发展。 因此，我们明确限制使用基于 AI 的系统（例如 GPT、Gemini、Gemma、Llama、Claude 等模型）来解决编程问题。 不过，我们也认识到 AI 可以作为学习和编程辅助的有用工具，因此我们希望为其使用设立明确的界限。 本规则的适用范围： 此规则严格适用于比赛期间的参赛者。如果一轮比赛是非排位评级的的，并在比赛公告或规则中明确指出，该规则也将适用。在比赛之外，AI 工具可以自由用于练习、学习或非竞赛性质的问题解决。 允许的 AI 使用方式： * 翻译题目：你可以使用基于 AI 的系统来翻译题目，但必须确保系统不对题目进行解释或总结。仅允许直接翻译。 * 代码补全工具（例如 Copilot）：可以使用基于 AI 的代码补全系统，但仅限于语法和小的代码建议。不得用于生成解决问题的核心逻辑或算法。 禁止的 AI 使用方式： * 你不得将题目、题目摘要、任何部分或子问题输入 AI 系统，来获取现成的代码或解决方案的自然语言描述。 * 禁止使用 AI 来根据系统反馈诊断或解决错误（例如，在收到“测试 1 运行时错误”等判定后，不得请求 AI 系统帮助修复问题）。任何替代你自身推理的 AI 辅助问题理解、逻辑创建或决策的使用方式都是严格禁止的。 正确使用 AI 的指导： * 允许使用 AI 生成简单的模板代码（如输入/输出函数）。 * 严禁依赖 AI 生成算法逻辑或关键解决方案。 * 如果你不确定某种 AI 使用方式是否违反规则，请咨询比赛 出题人/ AC君。 作弊检测： 这一规则使我们可以像 AI 时代之前一样继续识别作弊行为。我们也会通过检测某一位用户的历史提交记录的代码风格变化并比对比赛时的代码来做出进一步裁决。更进一步地，如果两位参赛者的代码相同，并且在比赛前这些代码没有公开在互联网上，这将被视为作弊的证据。这一方法确保 AI 工具不会被不当使用以规避个人努力，维护公平竞争的完整性。 我们将密切关注 AI 技术的发展，并在平衡公平竞争与 AI 辅助学习的优势时，适时调整规则。

复仇者联盟 10月排位赛 の邀请

比赛链接 赛制：IOI 邀请码：BTNA 本次第一名直升管理员！\COLOR{RED}{本次第一名直升管理员！}本次第一名直升管理员！【【改名为“复仇者_XXX”后】】 排行榜： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次奖励——《逆行人生》或《探索新境》（1到12集）\color{orange}本次奖励——《逆行人生》或《探索新境》（1到12集）本次奖励——《逆行人生》或《探索新境》（1到12集） 《探索新境》 《逆行人生》 【参加比赛后，告诉我你要的是哪个，我会告诉密码哦~】 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 下期预告： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 彩蛋： 【被N多个自己的“顶”顶上热搜...】

ACGO排位赛#13 - 题目解析

ACGO排位赛#13 - 题目解析 > 感谢大家参加本次排位赛！ T1 - 纪元流星雨 题目链接跳转：点击跳转 也没有特别大的难度，手动模拟一下就可以了。 解题步骤 1. 先计算出这个人一生中第一次看到流星雨的日子：(E+B)mod  50(E + B) \mod 50(E+B)mod50 。 2. 计算出剩余一生中可以看到流星雨的年份 YYY。 3. 答案就是 Y50+1\dfrac{Y}{50} + 150Y +1。 代码实现 本题的 C++ 代码如下： 本题的 Python 代码如下： T2 - MARCONCATENATE 题目链接跳转：点击跳转 根据题目模拟就可以了，没有什么难度。 代码实现 本题的 C++ 代码如下： 本题的 Python 代码如下： T3 - TNT接力 题目链接跳转：点击跳转 > 这道题是本次比赛的第三道题，但是许多参赛选手认为这道题是本场比赛最难的题目。 解题思路 1. 滑动窗口：使用滑动窗口技术，先在前 KKK 个方块中计算有多少个空气方块。接着，随着窗口向右滑动，我们移除窗口左端的一个方块，并加入窗口右端的一个方块，更新空气方块的数量。 2. 最大空气方块数量：我们维护一个变量 mx，表示在当前窗口中最多有多少个空气方块。 3. 计算答案：每次计算答案时，使用 K−最大空气方块数量K - \text{最大空气方块数量}K−最大空气方块数量 来表示最小的 TNT 方块数量，这表示需要多少步才能避免 TNT 的塌陷。如果 K≥NK \geq NK≥N，表示玩家可以直接跳过整个桥，输出 −1-1−1 。 时间复杂度 每次处理一个序列的时间复杂度是 O(N)O(N)O(N)，其中 NNN 是方块序列的长度。整体复杂度为 O(T×N)O(T \times N)O(T×N)，其中 TTT 是测试用例的数量。关于本体，还可以用二分来进一步优化。本文不过多陈述。 代码实现 本题的 C++ 代码如下： 本题的 Python 代码如下： T4 - 小丑牌 题目链接跳转：点击跳转 解题思路 也是一道模拟题，但需要注意以下几点： 1. 同一个点数可能会出现五次，那么此时应该输出 High Card（如题意）。 2. 如果有一个牌型符合上述多条描述，请输出符合描述的牌型中在规则中最后描述的牌型。 3. 牌的数量不局限于传统的扑克牌，每张牌可以题目中四种花色的任意之一。 代码实现 本题的 C++ 代码如下： T5 - VERTEX VERSE 题目链接跳转：点击跳转 直接模拟情况就可以了，但是细节比较多需要注意一下。 时间复杂度 其中 work 函数会在每次迭代中被调用 444 次，每次的复杂度是 O(E)O(E)O(E)。因此，对于每个输入的 qqq 对点，总的时间复杂度是 Θ(4×q×E)\Theta(4 \times q \times E)Θ(4×q×E)，即O(q×E)O(q \times E)O(q×E)。但在最坏情况下，图中的边数 EEE 可以接近 O(n×m)O(n \times m)O(n×m)，因此总时间复杂度是 O(q×n×m)O(q \times n \times m)O(q×n×m) 。 代码实现 本题的 C++ 代码如下： 另一种写法如下： T6 - 最优政府大楼选址-2 题目链接跳转：点击跳转 解题思路 本题有好多解决方法，可以使用带权中位数写 N=105N = 10^5N=105 ，为了考虑到朴素的模拟退火算法，本题的数据范围被适当降低了。如果学过模拟退火算法做这道题就非常的简单，把模板的评估函数改成计算意向程度的函数即可。 时间复杂度 模拟退火算法的时间复杂度约为 Θ(k×N)\Theta(k \times N)Θ(k×N)。其中 kkk 表示的是在模拟退火过程中计算举例的 F2 函数的调用次数。NNN 表示数据规模。 代码实现 本题的 C++ 代码如下（模拟退火）： 使用加权中位数算法的 C++ 代码： T7 - 乌龟养殖场 题目链接跳转：点击跳转 前置知识： 1. 了解过基本的动态规划。 2. 熟练掌握二进制的位运算。 > 至于为什么放了一道模版题，原因是因为需要凑到八道题目，实在凑不到了，找了一个难度适中的。 题解思路 这是一道典型的状压动态规划问题。设 dpi,jdp_{i, j}dpi,j 表示遍历到第 iii 行的时候，当前行以 j(base2)j_{(base2)}j(base2) 的形式排列乌龟可以构成的方案数。 对于每一行的方案，我们可以用一个二进制来表示。例如二进制数字 101001010010100，表示有一个横向长度为 555 的场地中，第 1,31, 31,3 号位置分别放置了一只小乌龟。因此，每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。 首先，我们预处理出横排所有放置乌龟的合法情况。根据题意，两个乌龟不能相邻放置，因此在二进制中，不能有两个 111 相邻。如何预处理出这种情况呢？我们可以使用位运算的方法： 如果存在一个二进制数字有两个 111 相邻，那么如果我们对这个数字 xxx 进行位运算操作 (x << 1) & x 的结果或 (x >> 1) & x 的结果必定大于等于 111。我们通过把这种情况排除在外。同时，我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉，如果网箱在第 iii 一个格子中不能放置乌龟，那么在枚举所有方案数的时候直接忽略掉第 iii 位为 111 的情况即可。 接下来如何保证上下两行的乌龟不冲突？假如上一行的摆放状态是 yyy，当前行的摆放状态为 jjj，如果 i & j 的结果大于等于 111，也可以证明有两个数字 111 在同一位置上。因此我们也需要把这种情况排除在外。 综上所述，我们可以得出状态转移方程：dpi,j=dpi,j+dpi−1,kdp_{i, j} = dp_{i, j} + dp_{i-1, k}dpi,j =dpi,j +dpi−1,k 。其中，jjj 和 kkk 表示所有横排合法的方案。答案就是 ANS=∑j=02M−1dpN,j\mathtt{ANS} = \sum_{j=0}^{2^M-1}{dp_{N, j}}ANS=∑j=02M−1 dpN,j 。 状态的初始化也很简单，另 dp0,0=1dp_{0, 0} = 1dp0,0 =1 ，表示一只乌龟都不放有一种摆放方案。 时间复杂度 通过观察上述代码，在枚举所有状态和转移状态的时候有三层循环，分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 O(n×2M×2M)=O(n×2M2)=O(n×4M)O(n \times 2^M \times 2^M) = O(n \times 2^{M^2}) = O(n \times 4^M)O(n×2M×2M)=O(n×2M2)=O(n×4M)。但由于合法的摆放数量远远少于 2M2^M2M，因此实际情况下程序运行的速度会快许多。 代码实现 本题的代码实现如下。在输出的时候需要减一，因为不放置也是一种合法情况，根据题目要求需要把这一合法情况排除。 本题的 Python 代码如下，Python 可以通过本题的所有测试点： 再提供一个暴力解法用于对拍： T8 - 数据中心能耗分析 题目链接跳转：点击跳转 本文仅针对对线段树有一定了解且并且有着较高的程序设计能力的选手。本文的前置知识如下： 1. 线段树的构造与维护 - 可以参考文章 浅入线段树与区间最值问题。 2. 初中数学 - 完全平方和公式和完全立方和公式。 3. 取模 - 之如何保证对所有整数取模后的结果为非负整数 - 可以参考本题的 说明/提示 部分。 > 原本出题的时候我并不知道这道题在许多 OJ 上是有原题的，so sad（下次再改进）。 题目本身应该非常好理解，就是给定一个数组，让你设计一个程序，对程序进行区间求立方和和区间修改的操作。但本题的数据量比较大，N,MN, MN,M 最大可以达到 10510^5105，对于每一次修改和查询都是 O(N)O(N)O(N) 的时间复杂度，显然用暴力的方法时间复杂度绝对会超时，最高会到 O(N2∗M)O(N^2 * M)O(N2∗M) （大概需要 115115115 天的时间才可以搞定一个测试点）。当看到区间查询和维护操作的时候，不难想到用线段树的方法，在线段树中，单次操作的时间复杂度约为 O(log2N)O(log_2 N)O(log2 N)，即使当 NNN 非常大的时候线段树也可以跑得飞起。 解题思路 不得不说，这是一道比较恶心的线段树区间维护的题目。不光写起来比较费劲，而且维护操作运算量比较大。稍有不慎就会写歪（因此写这道题的时候要集中注意力，稍微一个不起眼的问题就容易爆 000）。 本题的主要难点就是对一个区间内进行批量区间累加的操作。很容易就想到跟完全立方公式的联系：(a+b)3=a3+3a2b+3ab2+b3(a+b)^3 = a^3 +3a^2b + 3ab^2 + b^3(a+b)3=a3+3a2b+3ab2+b3。区间累加操作也只不过是对区间的所有数字都进行该操作，并对所有操作的结果求和就是该区间进行操作后的立方和。化简可得： ANS=∑i=1n(ai+x)3=(a1+b)3+(a2+b)3+⋯+(an+b)3=(a13+3a12b+3a1b2+b3)+(a23+3a22b+3a2b2+b3)+⋯+(an3+3an2b+3anb2+b3)=(a13+a23+⋯+an3)+3b(a12+a22+⋯+an2)+3b2(a1+a2+⋯+an)+nb3=∑i=1nai3+3b∑i=1nai2+3b2∑i=1nai+nb3\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^3}\\ &= (a_1+b)^3+(a_2+b)^3+ \cdots + (a_n+b)^3 \\ &= (a_1^3 + 3a_1^2b + 3a_1b^2 + b^3) + (a_2^3 + 3a_2^2b + 3a_2b^2 + b^3) + \cdots + (a_n^3 + 3a_n^2b + 3a_nb^2 + b^3) \\ &= (a_1^3 + a_2^3 + \cdots + a_n^3) + 3b(a_1^2 + a_2^2 + \cdots + a_n^2) + 3b^2(a_1 + a_2 + \cdots + a_n) + nb^3 \\ &= \sum_{i=1}^{n}{a_i^3} + 3b\sum_{i=1}^{n}{a_i^2} + 3b^2\sum_{i=1}^{n}{a_i} + nb^3 \end{align} ANS =i=1∑n (ai +x)3=(a1 +b)3+(a2 +b)3+⋯+(an +b)3=(a13 +3a12 b+3a1 b2+b3)+(a23 +3a22 b+3a2 b2+b3)+⋯+(an3 +3an2 b+3an b2+b3)=(a13 +a23 +⋯+an3 )+3b(a12 +a22 +⋯+an2 )+3b2(a1 +a2 +⋯+an )+nb3=i=1∑n ai3 +3bi=1∑n ai2 +3b2i=1∑n ai +nb3 综上所述，我们只需要用线段树维护三个字段，分别是区间的立方和、区间的平方和以及区间和。在维护平方和的过程中与维护立方和类似，根据完全平方公式 (a+b)2=a2+2ab+b2(a+b)^2 = a^2 + 2ab + b^2(a+b)2=a2+2ab+b2。经过累加和化简可得： ANS=∑i=1n(ai+x)2=(a1+b)2+(a2+b)2+⋯+(an+b)2=(a12+2a1b+b2)+(a22+2a2b+b2)+⋯+(an2+2anb+b2)=(a12+a22+⋯+an2)+2b(a1+a2+⋯+an)+nb2=∑i=1nai2+2b∑i=1nai+nb2\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^2}\\ &= (a_1+b)^2 + (a_2+b)^2 + \cdots + (a_n+b)^2 \\ &= (a_1^2 + 2a_1b + b^2) + (a_2^2 + 2a_2b + b^2) + \cdots + (a_n^2 + 2a_nb + b^2) \\ &= (a_1^2 + a_2^2 + \cdots + a_n^2) + 2b(a_1 + a_2 + \cdots + a_n) + nb^2 \\ &= \sum_{i=1}^{n}{a_i^2} + 2b\sum_{i=1}^{n}{a_i} + nb^2 \end{align} ANS =i=1∑n (ai +x)2=(a1 +b)2+(a2 +b)2+⋯+(an +b)2=(a12 +2a1 b+b2)+(a22 +2a2 b+b2)+⋯+(an2 +2an b+b2)=(a12 +a22 +⋯+an2 )+2b(a1 +a2 +⋯+an )+nb2=i=1∑n ai2 +2bi=1∑n ai +nb2 以上三个字段可以在构造线段树的时候一并初始化，之后的每次更新直接修改懒标记就可以了。一切都交给 push_down() 函数。在每次区间查询和修改之前都进行懒标记下放操作，对区间进行维护。具体维护操作如下： 注意事项 1. 请注意取模，为了保证答案正确性，请在每一步操作的时候都对结果取模。 2. 开 long long，不然的话只能过前三个测试点（出题人还是挺好的，留了三个小的测试点骗粉）。 3. 在维护立方和、平方和以及和的时候，请注意维护的顺序。应当先维护立方和，再维护平方和，最后再维护区间总和。 4. 注意线段树数组的大小，应当为 4×N4 \times N4×N。 5. 建议使用读入优化，直接使用 cin 的效率比 std 慢约 100%100\%100% 。 时间复杂度 线段树单次查询和修改的复杂度约为 O(log2N)O(log_2 N)O(log2 N)，初始化的时间复杂度为 Θ(N)\Theta(N)Θ(N)，因此本代码的整体时间复杂度可以用多项式 Θ(N+M⋅log2(N))\Theta(N + M \cdot log_2(N))Θ(N+M⋅log2 (N)) 来表示，整体代码的时间复杂度就为 O(M⋅log2(N))O(M \cdot log_2(N))O(M⋅log2 (N))。在极限数据下，程序只需要 160ms160ms160ms 就可以完成暴力一整年所需的工作。 代码实现 1. 代码使用了宏定义，方便后期进行调式。 2. 以下代码与普通的线段树无太大区别，但请着重关注 push_down() 下放操作。 以下是本题的 Python 代码，但由于 Python 常数过大，没有办法通过所有的测试点：

排位赛#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++！