音乐能激发或抚慰情怀，绘画使人赏心悦目，诗歌能动人心弦，哲学使人获得智慧，科学可改善物质生活，但数学能给予以上的一切。
年级：准初二
现就读于芜湖市第二十七中学
曾就读于芜湖市王家巷小学
有初中和一点点高中数学水平
2023 年中考（8 月完成，当时刚学完初中）124 分
2024 年中考（6 月完成）138 分（不该丢了 5 分）
大考游记见本博客。
mahaoming 0x7e6
密码：mhm2022。要共号的直接拿去共。每天晚上 23:00 左右更新，其实就是下线前更新。
缺省源：
1 | // Written by da_ke |
undo:
todo:
什么嘛，我想要留下美好的回忆有什么错！在自己消失之前，心怀上不像消失的愿望，希望让某个人记住我，希望留下羁绊。我这么希望着，又有什么不可以吗！——珂朵莉
最后 60 天，不管好坏都得退役了。也就是，CSP 结束的那一刻，可以和我说 GoodBye 了。
但是即使这样，我也想拼尽全力，不留遗憾。
其实呃呃呃。
今天颓了，跟小学生完了你画我猜，水了一黄就下了。
MO 自然是小蓝本。组合数学难，但有规律可循。
很不幸的是我过敏了，原因未知。手极度的酸，连代码都打不动。
下面说说晚上。
发现：https://www.luogu.com.cn/problem/AT_abc278_f 可做，刚学过状压。丢到几天后做。
竟然犇犇现场开导神犇：@Yun_Mengxi 这么强都得退役了，那我是啥？
AT_abc279_e，很难。
我糖了，b[a[i]+1] 写成
b[a[i]]+1，原因：显然。
写一下这题思路：实际上，不操作某个操作的结果：
根据题解理解，感谢 dl。
立马换 F，并查集板子（？）偷偷看题解确认一下。
你说的对，但怎么清空 \(y\) 的桶？！
开始看题解。21:52 懂了。思路是换点。
但是被 ub 搞到 22:43。还准备在写一题！
总结：数组太不安全，越界了连 RE 没有，我要学扶苏用
vector。
这个 abc280 C 太简单了，秒。
D 会，但是分解质因数应该有的。
【有关 MO】【OI 无关】：其实组合数学是有必要先囫囵吞枣的，但很多人认为没意义。
狂补作业ing，damn 读书记录，各种 sb 表。
没控制住，玩你画我猜到 20:00。
D，分解质因数，有公式：
对于 \(k\) 的因子 \(p\)，\(N!\) 有 \(N!/p^1+N!/p^2+\cdots+N!/p^k\)
牢记。
同时因为不开 long long
调了很久，因为最后有一个很大的因子。
过。
存一道题：https://www.luogu.com.cn/problem/AT_abc280_e
秒 ABC281 C。
9:00 刚开 D，看一下觉得爆搜？搜完 dp 就行，不知可不可行。
题解怎么比我想的复杂！！
我觉得有点像背包，写出来看假不假。
然后写废了，没调。
【OI 无关】贴一道组合数徐：
甲乙两人从 \(1,2,4,\cdots,2^{2024}\) 选数，甲先选。每选一个数，就将其减 \(1\)。如果哪个人操作后有负数，此人告负。问：谁必胜？
答案：甲必胜。原因：搞不懂。来源：《小蓝本》第 7 本，第 4 章习题 8。
大佬会的私信我。
感谢 Zelotz 的耐心查看，发现 1LL<<59 写成
1LL<59，警钟长鸣。
Zelotz 列为 Special Thanks。
随后 A 了。
写点闲话，我跟 cq_zry 什么关系。
这里 cq_zry 现在是 @CQ_Bob & @harmis_yz。
实际上，我们认识的日子就是 WOT 的生日。当时，cq_zry 回答了我的一个帖子，使得我关注他。然后我向他宣团，就是现在的 WOT，他加入了。
第二天，他问我团队里 【Wuhu 2002】飞行棋 他代码的问题，是用记忆化搜索的，我自然没看出来。
当时我很弱，非常菜，但是 cq_zry 不仅没有瞧不起我，还耐心地指导我。我们努力出了愚人节赛（T1 模拟，T2 博弈，T3 dp）。
他对我很耐心，他也很谦虚，我觉得这才是真正的大佬。相比最近一些嘲讽我的「dl」来说【】。
也是因为他，我才学习了 dp，而且相当一段时间，我做的题都是 dp。我也喜欢用记忆化搜索，直到今天也在用。
在我们努力下，我们又出了五一赛（T1 模拟，T2 贪心，T3 忘了 T4 随机 T5 数位 dp T6 卡常背包）
那个暑假发生了很多事。后来因为著名的联合公开赛，cq_zry 被封了（被小 L 盗号导致的），从此我跟他很长一段时间没有交往，后来 WOT 也解散了。
这是后来我重建 WOT 的时候，我去再次邀请他，他竟然出乎意料的回到了 WOT
后来我又拜他为师，他耐心地帮我调了很多代码。
其实 cq_zry 一直是我心目中最巨的大佬，不仅仅是因为他的学术水平强悍……
这里搞笑放一段 cq_zry 写的：
YT: 也许曾经喜欢过，但已不存在了。那时的我们，一起笑过，哭过，陪过。和妳一起的时光很短，分别的时光很长。就像一场龙卷风，在不经意的瞬间，卷走了妳，和我。分开的时候，是迷茫的，是沉默的。我好像并没有感情，又好像，只是没有说出来。就这样我们在那不知意的情况下，默默地、慢慢地分别。在梦里，在脑海里，在心里，都牵挂着妳。多少次莫名地心酸，多少次悄悄地哭泣，不知道，终是为何。是雨天，是晴雨天，是看不见的雨天。它倾盆地毫无保留地泼下来，淋湿了我，毫无遮挡的脸庞……
Bye,if you remember me...
cq_zry
2023.2.10
这里祝 @cq_zry NOI Au。
言归正传，19:00 准时开始做题，不准颓废！
存一道题：https://www.luogu.com.cn/problem/AT_abc281_e
ABC282 B 竟然橙 orz。看了一会儿，很简单，没写。
C 红，orz。随便写一下。
很好写的模拟题，19:18 写好了。
D 绿，orz。二分图？我还没学过呢！
https://oi-wiki.org ：节点集合由两个集合组成，且两个集合内部没有边的图，称为二分图。
呃这个，还是看不懂。Thus，题解！
虽然但是用 DeepL：
什么是二分图？当且仅当我们可以将每个顶点涂成黑色或白色以满足以下条件时，一个无向图被称为二分图。
- 没有边连接涂成相同颜色的顶点。
这场 ABC 是不是 shaber 场？要是我参加肯定掉大分。我是唐诗。
运用组合数学中染色的思想，我们将图而染色（不妨黑白）。
若一条还没有添加的边，满足两边颜色不同，可加。
枚举每个连通块，记黑白分别为 \(c_0,c_1\)，根据乘法原理共 \(c_0c_1\)，同时也可以和别的连通块中的点连，故 \(\sum c_0c_1+\sum (c_0+c_1)(N-c_0-c_1)/2\)
最后减去连边即可。
写了但是：https://atcoder.jp/contests/abc282/submissions/57205175
检查公式，发现加减写错，sb。
话说这样例也不能水这种程度？
然后又 WA：https://atcoder.jp/contests/abc282/submissions/57205323
先不调了，去切 Water 场。
ABC283 保卫战！
C，第一眼 dp，数据范围爆了。马上贪心，正确！但是即使这么简单也不妨碍我 sb 交了很多次。
D，只有橙吗？晕了，我竟然不太会。但是括号层数记一下，被标记层数记一下就做完了吧。由于字母只有 \(26\) 个故该条件应该是突破点。
更：ABC282D 开 long long，少错 2 个点。感谢 @baibaieee
水了犇，放松了一下，同时也获得了前面组合题的证明。感谢 @Ravener。
回来写题。大雾，为啥初值
x=1。A：原因是为访问过与第一层访问是有区别的。
E，是 dp 吗，数据这么诡异，不大不小。就算是也不会，太菜。
题解。
大概看了一下，是 dp，但暴力程度无法想象qwq。wssb。
可能丢一半明天写。
快开学了，先把 sb 表口胡了，还剩一个三结合，明天胡。
MO 颓了，悟净没颓。写点运动笔记
【高一物理】运动
先定义标量：只有大小而没有方向的量；矢量（数学中译作向量）：既有大小又有方向的量。
举例：如一物体沿 \((x-1)^2+y^2=1\) 这个圆走，从 \((0,0)\) 沿圆周走大 \((2,0)\)。其路程为 \(\pi\)，位移为 \((2,0)\)。这里用向量的方式表示矢量。
时刻：时间的节点。符号 \(t\)，是标量。
时间：两个时刻之间的部分（通俗）。符号：\(\Delta t\)，有时也即 \(t\)，是标量。
速度：符号为 \(v\)，\(v=\dfrac{\Delta x}{\Delta t}\)，是矢量。方向与位移方向一致。
速率：瞬间速度。符号 \(v\)，矢量。
加速度：匀变速直线运动中，速度-时间函数的斜率。
下面介绍这些的关系：
记时间为 \(t\)，开始速度为 \(v_0\)，加速度为 \(a\)。
\(v=v_0+at\)
位移的大小是速度-时间函数图像下方面积（通俗的讲是：开始时间的垂线、停止时间的垂线，函数图像，坐标系横轴所围成的面积）。
证明：这里记函数为 \(f(x)\) 将函数曲线分割成无限小长方形。每个长方形在横坐标轴上，其在横坐标轴上的边长为 \(\mathrm{d}x\)，其面积为 \(f(x)\mathrm{d}x\)，就是表示的是这个瞬间通过的位移大小。
由上面的结论我们可以推出一个推论：
如果我们用 \(v\) 表示结束时的速度，那么又有：
下面介绍函数关系：
由公式 \(x=v_0t+at^2\) 和 \(v=v_0+at\)，很难不发现，\(v=x'\)。
实际上，速度的变化实际上就是位移的瞬间变化率，这符合导函数的定义。
实际上，速度-时间函数是位移-时间函数的导函数，加速度-时间函数是速度-时间函数的导函数。
下面介绍考法：
实际上，各种问题，我们都可以将 \(v-t\) 图像转为 \(x-t\) 图像（积分）。这样我们就可以解决各种考题。
本人初学，有错私信。
写笔记写到 19:30，准备开始 OI。
今天可能需要补一些前面的题。
一上，https://lglg.top/913738 这个也能违规，这是人吗？！你谷现在 xxs 泛滥，天天讨论低质量内容，怎么来板块漂移就是 btd？？你谷真的是蒸蒸日上啊！
你谷 xxs tm 真可怕！我真的服了。其实我现在基本不用讨论区了，真的跟小学生对线对怕了！他们一个个号称比我强几百倍！说我 CTJ，说我菜，说我是 xxs。真的好想笑啊。其实你谷绿名是菜，xxs 很多都是绿名，但绿名只是是 xxs 的必要条件！不是充要条件！实际上也不是必要条件，因为橙名也有小学生。所以很多人看到我都以为是那种 xxs，都不看我主页都跟我对线，引战。
其实真正的大佬不是你们这些伪大佬的姿态的。可怕。xxs 一般具有几个特征：
主页冗长，含有滥用 \(\LaTeX\) 的垃圾内容、传送带图片、火柴人图片、你谷笑梗、游戏、iostream=100、各种打油诗等等垃圾内容。而大佬的主页都是什么 AtC Rating，CF Rating 之类的。
小学生你跟他说 ABC 都不知道是啥。他们没有 AT，CF。
小学生可以随便在求助帖里发诸如「666」「你调不出来就睡觉」之类的劝退的语气。
主要还是看主页。正如一位蓝勾巨佬跟我说的：主页就可以准确的看出一个人的年龄。
致远星了，看了 kkk 发的帖，sb，6 h 老铁，那我题目总版岂不是直接沉海！你谷讨论区密度小，而神贴密度比他更小，但学术帖密度很大，这是因为他又知识！！！那些 xxs 帖你觉得他又什么意义吗？这不是鼓励发水贴吗？
我去 LOJ 捞了（？），其实我是很反对各种规定的。实际上规定并不能约束人的思想。洛谷不是明明规定不能抄题解不还有人吗？他们难道不知道没有这条规定吗？这简直就是谬论！
惩罚实际上是一种比较低级的约束方式。虽然但是，LOJ 没有严格的规定也没有小学生嘛！
要么就严格要求。像 Codeforces，你去发个 qp 都不行。这强迫我们讨论学术内容。然而现在学术贴 1 年都没有一条回复，这是洛谷的初衷吗？？？！！
如今小学生泛滥的洛谷我觉得是无可救药了，自从 xht 搞毛，小粉兔休假以后就是密度一天比一天小，让知识都埋没在深处了。
洛谷就像一个大海，总是密度小的水贴上浮，显眼，甚至神贴永垂不朽；而密度大的求助帖下沉，还不给捞。
如果你认为我说的不对，别喷。只会喷人的人不是好人。
虽然但是如果你发帖缅怀李政道都是违规的，但是我看看管理员有没有胆量把他删了。
https://www.luogu.com.cn/discuss/880769
我觉得那些风纪志愿者也得停停停了，洛谷现状无法挽回。
开始看题了，边写边写点日记
sb dp，写了很久才写好。
sb AT，上了好久上不上去！
样例没过 #1
感谢 @ran_qwq 指出 AT_abc282_d 我取整的错误，orz。因边会在别的连通块中遍历到，所以不慌除以二。
发现问题：tm 又把 i,j,k 搞反，警钟长鸣。但是这竟然过了
16
组数据！
这次也算终于 A 了：https://www.luogu.com.cn/record/175306046
写一下想法：
\(dp(i,j,k,l)=min\{dp(i-1,k,l,0)+dp(i-1,k,l,1)\}+j\)
然后在 AT 的自带 IDE 上随便打了一道 C，直接交，没测样例，竟然直接 A。
明天开学报道了。
初一电脑班在 9 班，准备面积 ps。
谈谈大招在中考的应用：
图：天津 2024 中考，填空倒数第二题。
实际上这道题就是个裸体。
无需作任何辅助线的，但答案作了。
在 \(\triangle AED\) 中应用余弦定理，\(DE^2=AE^2+AD^2-2AE\cdot DE\cdot \cos \angle DAE=34\)。
然后应用斯特瓦尔特定理的特殊情况中线长定理，\(AF^2=\frac{1}{2}AE^2+\frac{1}{2}AD^2-\frac{1}{4}DE^2=\frac{\sqrt{10}}{2}\)。然后就结束了。
天津出题人脑瘫辣！
天津第 18 题一样脑瘫，但是有一个细节注意到：\(AE\) 是圆的直径。就结束了（应用小蓝本第 4 本「三角形内接三角形」中的结论即证）。
所以这里放几个大招：
余弦定理：
\(c^2=a^2+b^2-2ab \cos C\)，具体前提翻高中数学必修第二册。
正弦定理：
\(a/\sin A=b/\sin B=c/\sin C\)
斯特瓦尔特定理：
\(P\) 是 \(\triangle ABC\) 边 \(BC\) 上的点：
\(AB^2\cdot PC+AC^2\cdot PB=AP^2\cdot BC+PB\cdot PC\cdot BC\)
Menelaus 定理，塞瓦定理，托勒密定理。直接 bdfs 吧，这里不展开举例说明了。
堪称经典。
。。。。
今天没有日记，因为我去墨鱼了。
写了 E：LCM on the whiteboard。有一点没明白，故不写思路。
感谢 @枫原千叶 解答了我 4 个月的问题。
谷冥看法：https://www.luogu.com.cn/discuss/915331
投票:你如何看待姜萍事件(点击选项进行投票):
我支持姜萍。我认为她是一个自学成才的天才，她的成绩是真实的。
我不支持姜萍。我认为她是一个数学盲，她成绩可能是假的
今天入学。讲废话。乐子。
然后 ABC 事后诸葛亮了。赛时竟然只做了 A、B。赛后话好长时间做 C，但 D 秒了。qwq，掉大分！！！
wssb。
https://www.luogu.com.cn/discuss/916871 出题人是不是来吃饭的？！
这里讲一下 D 的做法（其实是个人就会。
一个暴力 dp：\(dp(i,j)=v(i)+\max\{dp(i,j),dp(i+1,dp(j+1))\}\)，其中 \(v(i)\) 是第 \(i\) 个所获价值。
其实我们并不关心 \(j\) 是多少，只关心奇偶性，故 \[dp(i,j)=v(i)+\max\{dp(i,j),dp(i+1,dp((j+1) \bmod 2))\}\]
然后你发现你就秒了。记忆化搜索即可，比 C 简单吧。
糖丸指数达 200，不水乐。
写了 ABC260 E，看官方题解的，一看马上秒懂，orz。
wssb。
先讲一点故事。其中【】不宜的内容，用【色，删】代替，自行领悟。
da_ke 准备和 public_sickle 面积。
众所周知，da_ke 的同桌是 lzx cp。
插叙：lzx 之前跟 da_ke 说过，说她有一个学弟，是 OIer，说 personality 非常像 da_ke。
插叙：cyh 跟 da_ke 说过，lzx 有一个小学 ng。
为下文做铺垫。
开端：
周一不引人注意，da_ke 去 709 问 fyy 谁无果。
周二不引人注意，同理。
发展：
事情在周三迅速发酵，因 da_ke 当 cyh 面给 public_sickle 写东西，引起注意。经多方商议、研究，确定路线，准备集体面积 public_sickle。同日，这件事被 lzx 知道了，因 da_ke 写信泄露到 lzx，悲。
cyh & lzx 每天都会传 QS（a letter to show love），周三 lzx 写的 QS 上有：
我 ng 就是 fyy （大意），他拉着【色，删】。
还有她的问题（以 lzx 的口吻，QS 原话）：
我帮 cyh 在 QS 上写了问题 1。
高潮：
周四上午，cyh & da_ke & 两位好心的保卫员，前往 709 面积 public_sickle。
保卫员和 cyh 大胆的询问到 ps，而 da_ke
却因为设死躲起来。
public_sickle 好帅！
da_ke 说了几句话就 go die 了。
结局：
既是高潮又是结局。
回来后，我发癫了：
我喜欢妳傅元一！
上午黄皮卷有一道题：
\(\triangle BDP,\triangle CPE\) 和四边形 \(ADPE\) 面积相等，求 \(CP/DP\)。
da_ke 向来不喜欢用正规方法解题。
对 \(\triangle BDP,\triangle BAE\) 应用 共角比例定理，
\[\dfrac{BC\cdot BP}{BA\cdot BE}=\dfrac{1}{2}\]
同理：
\[\dfrac{CP\cdot CE}{CD\cdot AC}=\dfrac{1}{2}\]
对 \(\triangle ADC\) 及截线 \(BPE\) 应用梅涅劳斯定理，
\[\dfrac{AC}{CE}\cdot \dfrac{EP}{BP}\cdot \dfrac{BD}{AD}=1\]
综合三式易得：
\[\dfrac{CP}{DP}=3\]
就是这么简单。
这是无脑做法，正规做法是连接 \(AP\) 设未知数，然后用类似于共边比例定理之类的也能得出结果。
但是思维难度大。
其实我做这种题的套路是：
按照这种套路你就无敌了。
OI：2023 S1 52 太菜。
无
累。没人理解我。
wssb。
纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。
唉。成人机了。
21:00 才上。
乐子。
A ABC 265 E，简单到爆。
略。
调试代码的好处
发现和修复错误：调试是找出并修复代码中错误的关键步骤。通过调试，开发者可以逐步跟踪代码执行过程，定位问题的根本原因，并及时修复这些错误，确保代码的正确性和可靠性。
提高代码质量：调试有助于发现代码中的逻辑错误、潜在的错误或者代码不规范的地方。通过逐行调试代码，开发者可以更加深入地理解代码的运行机制和细节，以及找出代码中的问题并进行修正，从而提高代码质量。
加快开发速度：调试可以帮助开发者快速定位问题，减少排查错误的时间，从而提高开发速度。通过调试，开发者可以逐步分析代码执行过程，并逐步排除错误，减少调试时间，加快代码开发的进度。
增强开发技能：经过长时间的调试实践，开发者可以积累大量的经验和技巧。不仅可以提高开发者的调试能力，还可以提高他们解决问题的能力和创新能力。
怎么样，是不是心动了，快试试吧！
0 分求调！
发帖用的（乐子。
无
只讲一下发生的重大事件呃。
在最后一节课前，当 cyh 去音乐教室时，我偷翻他的 QS，而且边看边笑，最后实在绷不住了。
被发现了qwq，cyh 要我道歉。
但是要求我向 lzx 3 鞠躬，还要叫她 mother。我强把后面一条删了，他也同意。
放学我见到 lzx 非常设死，并很不情愿的【】，然后迅速逃跑。瞟一眼，lzx 诡异笑容真可怕（
老胡发试卷故意拖延说废话和作业，害得 da_ke 和 cyh 直接犯癫痫，口念《临江仙·滚滚长江东逝水》，前面人以为我们要死了。结果试卷下确实死了。
老【】天天说要换座位，然后说今天必调（课后拖堂）。
老【】来过后，da_ke 非常【数据删除】，唱起了《送别》。
长亭外，古道边，芳草碧连天。晚风拂柳笛声残，夕阳山外山。天之涯，地之角，知交半零落。一壶浊酒尽余欢，今宵别梦寒。
感情深厚，虽然天天矛盾。但是没掉。
相信老【】调座位的就跟相信国足的一样。
崩。
下午我和 cyh 一人一张中考卷（由好心的 cyh 提供，从万维里面撕），他青海，我兰州。TM！
巨，然后我做到几何突然半角公式忘了，当场十分尴尬，然而他非常快的做完了，毕竟是青海，没难度。
\(\tan 2\alpha=(2\tan \alpha)/(1-\tan^2 \alpha)\)。
牢记。
遇到一点有趣的几何，用正弦定理边角转化即可，再加上三角恒，应该就杀了。
无，记在明天。
我眼神有点不好，没看见你们，sorry~
关于
非常帅
呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃………………………………………………………………………………………………………………
其实我都是睁一只眼闭一只眼，没逮任何人哦！
感谢！
下午没上课（喜）！
ABC 废了，ABD 一眼秒，唯独不知道 C 在说什么。上一丢丢分。
wssb。
我tm有邪恶微笑（（（（（））））））））））））））））
做题将题目一般化得到了点旋转公式：
\[X=x\cos \theta-y\sin \theta,Y=x\sin \theta+y\cos \theta\]
，很强。
ABC264F 非常好做的 DP，很经典，做了很多遍，我们用记忆化秒。
一遍过。
大雨，台风，晕。昨天晚上聊到好晚。
历险记
这几天一直发现有：
「您的 Windows 内部版本将于 XXXX 过期……………………」
一查发现，这玩也叫做「时间弹炸」。
介绍：是 Windows 8 以后内部版本安全性组成，其内部版本过期后将隔 2 个小时重启电脑，时间间隔不断减小，直至电脑报废。
我慌得一批，赶快 \(\texttt{bing}\) fs + luogu 提问。便去重装系统，想着 2 h 后电脑就要报废了，quick！！！！！！！！！！！！
镜像慢的要死，慌死了~
但是看到一篇救命博客，删掉 \(\texttt{System32/LicensingUI.exe}\) 即可，立即行动，发现寄了。需要 TrustedInstaller 权限。
真是长知识了，将我删除的经验写一下：
哇！！！！！！！！！！！！！！！！！！！！！有惊无险！！！！！！！！！！！！！！！！！！！！！
足足耗了我 1.h 服了。
后来说也不会重启了，自从 Windows 11，想想微软还是挺野蛮的啊。
https://www.luogu.com.cn/training/601675#problems
https://www.luogu.com.cn/discuss/927871
乐子。
1 |
|
乐子-》原：这份代码揭晓 Windows 和 Linux 有多大的区别。
然后发现我唐氏然后在 out.out
中间加了空格，警钟长鸣。
AC。
最难的 C。我的思路也很另类。
Stop learning other useless algorithms,go to solve problems,and learn how to use binary search. by Um_nik.
现在，有 \(N\) 个敌人的按顺序排成一行，记他们的生命值为：\(a_1,a_2,\dots,a_N\)，你有一个初始为 \(0\) 的量 \(T\)。
不断进行如下操作：
记目前最前面的敌人生命值为 \(a_i\)，满足 \(\forall j\in [1,i),a_j<1\)。
求让所有敌人生命值不大于 \(0\) 的最小操作次数。
暴力的方法的复杂度依赖于 \(\max a\) 的大小，是因为因为这种方法不断去枚举 \(T\) 导致的。
其实枚举 \(T\) 是没必要的，因为很多操作是重复的。其实复杂度的瓶颈就是在于有些 \(a_i\) 很大，你不断减 \(1\) 很浪费时间。
所以可以在枚举 \(i\in [1,n]\)，考虑将每个敌人「杀死」，这么做是 \(O(n)\) 的。但是个人觉得代码不太好写，我使用的是二分。
由于 \(T\) 可以很大，事实上 \(T\in [1,(\max a) \times N]\)，考虑如下：
若存在一个最小的操作次数 \(T_{min}\)。则定 \(\forall T>T_{min}\)，这些 \(T\) 都多做了一些操作；\(\forall T<T_{min}\)，这些 \(T\) 都无法杀死所有敌人。
显然这道题符合二分的定义。
二分方法如下（会的直接跳过）
定义区间 \([L,R]\) 为查找区间，查找目的为 \(L+1=R\)。
判断是否杀死的方法：
定义 \(x\) 为当前消耗的 \(T\) 值。
对于 \(i\in [1,n]\)，记 \(y=a_i\)。
如果 \(y<m\)，令 \(x\) 为 \(x+y\)。
如果 \(y\ge m\)，令 \(y\) 为 \(y-m-2\)，\(x\) 为 \(x+m\)。这里为了更好描述敌人的损耗。这是若 \(y\ge 0\)，则 \(i\) 已经死了。否则：设每轮 \(3\) 此共 \(5\) 伤害值的轮数 \(r=\lfloor\frac{x}{5}\rfloor\)，计算出 \(y\) 经过 \(r\) 轮伤害后的 \(y_1\)，同时更新 \(x\)。
具体思想是循环问题，每 \(5\) 个伤害为一轮，可仔细体会。
运用上面的方法，判断 \(i\) 次后是否满足 \(x\leq T\) 即可。
以上就是数学的描述，下面就是代码：
1 | // #define EXT |
代码中穿插了我写代码是举的例子，可仔细体会。
我觉得这次很难。
广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。
初赛巨难。但是应该能过吧。
答案：
1 | J: AACCA BBDDB DDCCD |
都过了。
这是我 OI 生涯的最后一场比赛，甚至游记都写不了就得退役了，故在考场上写。
密码公布了是：\(\texttt{Yi2Meng0Wei2Ma4}\)
上午 J 第一题很难，去看 T2。T2 是个线性 dp，对于我来说秒了。5 min 写好过了大样例。此时过去了 10 min。
回去看 T1，其实发现一些非常巧秒的东西。但只能得 70 pts。算了，去 T3。
T3 nortan 大模拟，叫我模拟某谷的积分功能，cao。直接宝马开干。
写了 1h，调了 30 min tm 终于搞完了。此时过去 2h。
T4 图论。竟然是个偏板子+暴力（？），不确定但写了。过了样例。
回看 T1，直接打了 70 pts。
估分：\(70+100+100(?)+50\)。
中午和 \(\texttt{\color{red}{public\_sickle}}\) 打了一会三国杀。
S 密码：\(\texttt{Bu4Fu2Shao0Hua2}\)
下午 S 更服。T1 类似于去年是思维题，虽然但是 0.5 h 终究想出来了部分分。
T2 算简单，但只会 40 pts。写完 T1 T2 过去 1h。
T3 大模拟，愤怒。爆肝了，调了很久，但过了样例，感觉会炸。因为样例强度太低。
T4 不可以总司令，希望可以通过 CCF 的脚造数据。
打完了还剩 30 min，我啥都不干了。因为这是我 OI 的最后 1800 秒。我检查 IO，并深度放松，尽情享受 OI 的最后 1800 s。
估分：\(30+40+50(?)+10=130\)
晚上看了解密。
出分了，但是退役了。
J：290，S: 120，都挂了。
祝我 Whk 顺利。正如密码所告诉我们的，以梦为马，不负韶华。
你可能以为是真的了，实际上这是假的，也许比这个好，也许比这个惨，但这的的确确是我ＯＩ的最后一场比赛了。
写本文章的目的是，我赛后真的没有游记了，于是用一个假的冒充一下，证明一下我也曾是一名 OIer。
希望在役的各位 OIer 珍惜每一天。
赛时被整懵了，赛后题解。
注意：一定是顺时针走。
记 \(i,j\) 的距离为 \(d(i,j)\)
暴力的做法是，枚举 \(\dfrac{d(i,j)}{M}\)，二分查找满足条件的点。
显然过不了，其瓶颈在于倍数的枚举。
不妨破环，记数组 \(a\) 为 \(a_1,a_2,\dots,a_{2N-1}\)，且使用前缀和。
事实上，\(d(i,j) \equiv 0 (\bmod \ M)\) 的充要条件是 \(\sum\limits^{i}_{k=1}a_k\equiv \sum\limits^{j}_{k=1}a_k(\bmod \ M)\)。
故对所有前缀和对 \(M\) 取模，若模相同，则满足题目要求。
但是考虑到一定是顺时针走，我们统计是只从前往后看的。换句话说就是，前面的只会看后面的，不会再往前看。这里的前后指的是下标的大小。
具体的，现有点 \(i,j\)。要从 \(i\) 走到 \(j\)。
我们看到第 \(i\) 个的时候只会向后看到第 \(i+N-1\) 个。因为这样我们才能保证我们即是方向正确的，又是两点的最短路径。
代码实现，我们采用了桶装的方法，因为对 \(M\) 取模的余数一定小于 \(M\)。
代码：
1 |
|
我觉得这个放在 D 虽然代码不长，但是有一定难度的。
参考资料：
广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。
题目已经翻译好了，故不提供翻译解释。
需注意：编号为 \(x\)
的球可以有很多个，赛场上因此痛吃罚时。
考虑到 \(x\in [1,10^6]\)，数据范围较小，故开一个桶：\(s_x\) 记录 \(x\) 出现的次数。
同时维护一个集合，记录目前还存在的球种类。考虑到我们只关心球种类的数量，故可将集合变为一个计数器。
代码很容易写出来。
时间复杂度 \(O(Q)\)，空间复杂度 \(O(\max x)\)。
但是如果 \(1\leq x \leq 10^{18}\)，那 \(x\) 肯定无法用桶去装了。这是因为数组一定是连续的，而事实证明根本不需要连续，因为很多数是没有出现过的。
但是 C++ 中的 STL
恰恰有这么一个非连续的数据结构
map。其使用方法与数组类似。
注意：map 在没有修改的键值对应值默认是
0，这里只举整数类型为例。
1 |
|
时间复杂度为 \(O(Q\log Q)\)。因为
map 一次查询的复杂度是 \(O(Q\log
Q)\) 的，且最多有 \(Q\)
个球会加入袋子。
空间复杂度 \(O(Q)\)，理由同上。
这道题作为 C 还是很水的，而且不必用 STL。
AC：https://atcoder.jp/contests/abc366/submissions/56635007
安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。
又是一道 dp 题……
先规定石头剪刀布的规则为：R 打败
S，S 打败 P，P 打败
R，出相同的字符视为平局。下简记三种出发为「手法」。
给出对方的 \(n\) 次出法的序列（一个长度为 \(n\) 字符串），要求你出一个对策，满足：
数据保证存在一种策略满足以上要求。
为什么不是贪心？
一种可能的思路是碰到对手一样的出发就隔一个赢一次，但是很幸运的没有过第 3 个样例。
各种分类后发现根本没有通用的方法，故采用 dp。
众所周知 dp 很多都是将暴力指数级算法优化成很多维的算法。但这道题只允许线性或 \(O(n\log n)\) 的算法通过，故确定复杂度且确定为线性 dp。
若出了手法 \(s\) 出了下一个就不能 \(s\)，只能出不同于 \(s\) 的另外两个，不妨设另外两个为 \(s_1,s_2\)。
故转移为：\(dp(i,s)=dp(i+1,s_1)+dp(i+1,s_2)\)
其中 \(i\) 表示决策到了第 \(i\) 次，其他的如上文所述。
放代码：
1 |
|
实现采用了思路比较清晰的记忆化搜索。
然后就愉快的 AC 了：https://www.luogu.com.cn/record/171653457
类似于博弈、游戏等题目不能局限于贪心或一种方法，可以大胆开拓新的思路。
安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。
当场没做 D 来做 E 是明智的，D 根本想不到的。
翻译一下：
高桥准备 \(n\) 个菜，每个菜肴有甜味值 \(a_i\) 和 咸味值 \(b_i\)。高桥可以按任意顺序排放这些菜肴。Snuke 按排放的顺序吃，当吃的总甜味值大于 \(X\) 或总咸味值大于 \(Y\) 时停止。求吃的菜肴总数的最大值。
这道题和 C 题如出一辙，但仔细一看发现未必。这题求的是最大值。
数据范围是 \(n\le 80\) 且 \(X,Y\le 1000\) 显然 dp。
对比 P2240 和 P1048，发现其实和分别这次 C 题和 E 题道理相同。
一眼类似于背包的 dp，不难设计状态转移：
\(dp(i,x,y)=\max\{dp(i+1,x,y),1+dp(i+1,x-a_i,y-b_i)\}\)。
其中 \(i\) 表示考虑了前 \(i\) 个菜肴，\(x,y\) 分别表示能承受的甜味、咸味值还剩余多少，\(t\) 表示已经选了 \(t\) 个菜肴。
事实上，\(x\) 确定了 \(y\) 就确定了，故记忆化时忽略 \(y\)。否则空间肯定开不下。代码中的
cnt 是为了方便编写，实则不必计入状态。
同时不难写出类似于这样的代码（读者别急着写类似于这样的代码）：
1 | // 赛时代码 |
同：https://atcoder.jp/contests/abc364/submissions/56045157
很可惜，这样的思路是有漏洞的！
比赛的时候碰到这种情况一定冷静！
显然，该程序并未考虑顺序问题。
0-1 背包中物体选的顺序是不考虑的。但题目中特别说了：
高桥可以按任意顺序排放这些菜肴。
反例：不妨只考虑甜味值，假设咸味值远远还没有达到极限。假设选的菜肴中有一个菜的甜味值为 \(p\)，另一个在它之前的菜肴甜味值为 \(q\)。假设除去这两个菜肴以外已经选了甜味值 \(m\)，且 \(m+p+q>m+q>X>m+p>m\)。
按照我们之前的方案，最大的甜味值被认为是 \(m+q\)。然而将 \(p\) 和 \(q\) 交换就得到最大甜味值 \(m+p+q\)，所以最大的菜肴数也比原来多 \(1\)，故原方法有漏洞。
很容易想到用排序法修复 Bug。
这是我们将咸味值加进来。我们不妨只考虑其中两个临项 \(i\) 和 \(i+1\) 的情况。列表得：
| 项（菜） | 已选甜味 | 已选咸味 |
|---|---|---|
| \([1,i)\) | \(x\) | \(y\) |
| \(i\) | \(x+a_i\) | \(y+b_i\) |
| \(i+1\) | \(x+a_i+a_{i+1}\) | \(y+b_i+b_{i+1}\) |
反之：
| 项（菜） | 已选甜味 | 已选咸味 |
|---|---|---|
| \([1,i)\) | \(x\) | \(y\) |
| \(i\) | \(x+a_{i+1}\) | \(y+b_{i+1}\) |
| \(i+1\) | \(x+a_i+a_{i+1}\) | \(y+b_i+b_{i+1}\) |
若 \(x+a_{i+1}>X>x+a_{i}\) 且 \(y+b_{i+1}>Y>y+b_{i}\) 这时一定有 \(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。也就是说，符合条件的满足：\(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。那我们可以将 \(a_i+b_i\) 从小到大排序。
补充：不妨考虑满足 \(x+a_{i+1}>X>x+a_{i}\) 但不满足 \(y+b_{i+1}>Y>y+b_{i}\)，这时交换后会出现和交换前一样的现象。
在基础上改一下就可以得到：
1 | // 赛时代码修改 |
代码中 mem 数组中 cnt
的维度同样可以略去不计。
当场肯定不能像写题解一样考虑，一般来说是用直觉做的（也有一眼看穿证明的）。
这个思路阶梯是我当场真实体验。所以希望大家考虑全面。
但是本题解给出的方法只是思考的时候用的，并不是证明。有疑问或证明欢迎评论！
难度评级：绿或蓝。
WOT 2024 第 1 期日报 27中七下期中游记
Time flies.转眼又考试了.
前两次应该说还好,这次不会炸吧?
2023期中: 286.5 rnk校=(20,30)
2024七上期末: 776 rnk校=19(18?)
题外话,教你们一个查排名的办法: F12. 点击红旗->检查->百分比即排名
切入游记正题.
呃呃.
晚上押作文.去年湖南长沙考了「平凡的XX」XX不记得了.
晚上睡不着,早上起来爆物理(初三第一课).
烦死了,中午也不凡则睡.
下午去的有点晚.天还下着雨,还不小,看着就有不详的预感.
进入考场更是的.每次「请考试将与学科有关的物品...」唯独我一个不出去放——我不临时抱佛脚的.
老师很磨叽,卷子不提前发.开卷第一件事看作文,结果真押对了..qwq.
我暗自庆幸,但事实并不如我所料.默写很顺利.语段顺利.啊?名著题什么东西?wc三空3pts一个不会!全靠蒙!
假设我三个都蒙对,但是...顺序!这样算了只有 \(\frac{1}{6}\) 的胜率!
先空着吧.
什么东西?对联又坑人!经我犹豫填对了.阅读古文不想说,愿无锅吧!
最后是作文.作文真是对的题,但不是特别手到擒来的题.我想了很久才开始写,也尝试写「工整美观」.
时间一分一秒过去.什么?只剩15min了!我我我我!还有100字!
拼命了!我去!结果最后的字迹略微草率.唉总算好了.
我记得去蒙前面的题...qwq
估分120很险.很难.
出来跟lyc交流了一下,ta也说难.
啊!我3空全错你!我暗想:我错,人家也错...qwq
好吧,我家长又要聊天了qwq....
有两个家长,我简记为:小M家长,小N家长.小M成绩在「重点班」(其实是骗子)rnk2,很自以为是;小N是我同学,差的.大概小M比我低1档,N比我低2档,一档10人(我觉得在一个班)
一过了,小M,N就开始...
小N家长:简单!
小M家长:三空我家都对了.
小N家长还拍了TA在watch TV的视频.wc!都觉得简单是吧.我不禁大骂:小心乐极生悲!(我们班主任口头禅)您能想象我的愤怒啊!
废了,被一顿训...qwq你隔着屏幕可以想象的.
人狂必有祸,后来小N默写错!
我劝说我家长:语文炸了,day2&3不一定不会翻盘呢?
家长:反正你rnk班1没了.
没用自己知道行了.sb
补充: 小N是一个非常要面子且吹牛的人,他平时数学[120,130],你知道他水平了.但他每次都说他满分,sb!
数学,我的天下.
上午先秒杀AH2020疫情中考,成功150.我的信心得到鼓舞下午力争翻盘!
下午是个好天气,阳光明媚(天气真不是我造的,我不是那些没脸的文学家)
还有难度,选择压轴细节,填空有一道我开始没想出来后来1s解决的,大题均设分类讨论,最后一题外角定理秒杀.
我先跟lyc对了一下,wow!150~
我洋溢着喜悦回班见老慈(班主任)
小N: 简单 我心中暗骂:sb 结果他估分140,我们拭目以待.
小M: 150.
我们也拭目以待.他们说话很有水分.我就不..............(此处省略100字qwq)
明天英语继续哦~
补充:
今天,我听有人说「拔剑特训」上有原题,而小M不就是做嘛!结果ta根本不承认.后来在我逼迫下承认的.qwq
是个阴天.进考场发卷子就狂风大雨.
做完一题不会,估分119-作文[1,2].
对答案,一份不挂.好耶!还是119-作文
上电脑班拿伞被骂nj...qwq
小N: 115-作文
小M: 118-作文
班上同学有点悬,好像有点失误吧他们.
这不就翻盘了吗?
但是没小M高aaa.qwq人家小M是女生qAQ.
中午手机炸了.
查得,390 rnk校=42.
卧槽,小M直接397rnk=8我去他们班一号.
唉,小N就是在吹牛,就360qwq.
啊啊啊,这次怎么被小M整了?
后来,zyz都393就我最差是吧??qwq
没事没事,这次数学英语发挥稳定,语文略有失误.况且这次对题海很友好.qwq
达克.
\(\sum\limits^{n}_{j=1}a_j\)
\[\Phi \Pi \times\]
\[E=mc^2\]
| 1 | 2 |
|---|---|
| A | A |
1 | ohaaaaaaaaa! |
OH YEAH!
AH Wuhu Jinhu 27 mid
33256
