普通视图

昨天以前Makerlife 的小站

2025-2026 赛季游记 && 退役记

作者 Makerlife

2025年9月20日 20:27

<div class="note note-info"> <a href="https://blog.makerlife.top/post/S25-record-private">私密版</a> </div><h2 id="Day-70-CSP-S-初赛">Day -70 CSP-S 初赛</h2>2025/9/20进场的时候在门口堵了 20 分钟。今年好像比较简单，但怎么 ccf 码风这么好看了。<h2 id="Day-33">Day -33</h2>2025/10/27怎么已经有三个人停课了，这么急。不知道为什么今天状态很差，whk 也不想学，oi 也不敢停课。<h2 id="Day-30">Day -30</h2>2025/10/30找班主任请假在机房待了一上午，对着 noi 大纲复健板子。顺便把没打完的游戏打了。先天 ub 圣体，前有关同步后混用 <code>read()</code> 和 <code>cin</code>，后有动态开点线段树用 <code>std::vector</code> 的 <code>emplace_back()</code> 之后迭代器失效。很害怕考场写 ub。我怎么下午还要去体测？怎么体测的地方跳远垫子这么滑？诶我怎么腿直接亲地上了？rp--然后成功一瘸一拐的去了日照。<h2 id="Day-29">Day -29</h2>2025/10/31去日照的高速好像已经走了五六年了，甚至那几个隧道和大桥名字都快背过了。去试机，刚进机房就发现有个电脑蓝屏了，还在想谁这么倒霉。结果过去一看是我电脑。然后就被安排到了对面备用机器。<img src="https://img.makerlife.top/data/202511021931246.jpeg" alt="蓝屏的电脑">本机 1s <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>4</mn><mo>×</mo><msup><mn>10</mn><mn>8</mn></msup></mrow><annotation encoding="application/x-tex">4\times 10^8</annotation></semantics></math>4×108 次取模，还没有虚拟机，那我 ub 怎么办。<h2 id="Day-28-CSP-S-复赛">Day -28 CSP-S 复赛</h2>2025/11/01CSP 比赛日。做梦好像梦到四个文件全没加文件读写，吓醒了。7 点多直接去吃早饭，然后对着电脑看到 11 点。解压密码好像是人杰地灵，膜 <code>Ren5Jie4Di4Ling5%</code>。开 T1，一看诶这不是个 dp 吗？开写！诶？我 dp 怎么是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^3\log{n})</annotation></semantics></math>Θ(n3logn) 的。哦是不是可以优化。并不是。哦观察样例发现好像最多的一列一定选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n}{2}</annotation></semantics></math>2n？这玩意显然不对啊。哦还真不对。算了去看 T2。上了个厕所然后一眼会了 40pts 暴力加边然后 kruskal，飞速打完。坏了 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">c\neq 0</annotation></semantics></math>c=0 咋做，不懂。直到考完也没想到那玩意是用来 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>k</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(2^k)</annotation></semantics></math>Θ(2k) 的。考完发现当时被降智了，本来对于一个被选的乡村 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c，直接加 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n 条边 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo>↔</mo><mi>e</mi><mo separator="true">,</mo><mi>e</mi><mo>∈</mo><mo stretchy="false">{</mo><mn>1</mn><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">c\leftrightarrow e, e\in\{1,\dots, n\}</annotation></semantics></math>c↔e,e∈{1,…,n} 即可。但是为啥我考场对节点两两连边，加了 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mrow><mi>n</mi><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n(n+1)}{2}</annotation></semantics></math>2n(n+1) 条边啊？？？？？读了一遍 T3 发现没看懂，语言学还是太厉害了！直接去 T4，写了个 8 分跑路。哦 T3 是不是就是 AC 自动机上随便搞点东西，但我已经不会 acam 了，有空现推，先把暴力哈希写了。坏了哈希写了 3k 还没过，红温。好像已经 <code>5:30</code> 多了，我要去推 T1。又去读了一遍题，突然发现是不是直接选每个最大的，如果最终有一列超过 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle displaystyle="true" scriptlevel="0"><mfrac><mi>n</mi><mn>2</mn></mfrac></mstyle></mrow><annotation encoding="application/x-tex">\dfrac{n}{2}</annotation></semantics></math>2n 就去调整对答案贡献少的人的选择，也许是对的？此时 <code>5:50</code> 多，感觉要写至少 3k 啊，不敢写了，写了如下注释遂跑路：<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 </pre></td><td class="code"><pre><code class="hljs cpp">// maybe greedy is right? choose the largest col for all, change the illegal // wrong? </code></pre></td></tr></table></figure>然后就开始想 T2 的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><mo mathvariant="normal">≠</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">c\neq 0</annotation></semantics></math>c=0，希望对正解有启发意义。结果啥也没想出来。最后 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mrow><mo fence="true">[</mo><mn>60</mn><mo separator="true">,</mo><mn>70</mn><mo fence="true">]</mo></mrow><mo>+</mo><mn>40</mn><mo>+</mo><mrow><mo fence="true">[</mo><mn>0</mn><mo separator="true">,</mo><mo stretchy="false">?</mo><mo fence="true">]</mo></mrow><mo>+</mo><mn>8</mn><mo>=</mo><mrow><mo fence="true">[</mo><mn>108</mn><mo separator="true">,</mo><mn>118</mn><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">\left[60,70\right]+40+\left[0,?\right]+8=\left[108,118\right]</annotation></semantics></math>[60,70]+40+[0,?]+8=[108,118] 遗憾离场。我是不是要停课了。<h2 id="Day-27">Day -27</h2>2025/11/02北斗已经有 SD 代码了，一看为啥 T1 挂 10pts，T2 还 MLE。为啥我感觉 T1 不简单于编辑字符串啊。为啥说这玩意比廊桥分配简单。这下真要停课了。<h2 id="Day-26">Day -26</h2>2025/11/03凌晨 <code>00:50</code>。躺床上没睡着想 T2，然后突然发现我好像会了。梦中惊坐起，去问 MrPython 做法，发现差不多对了。就在床上深度思考更睡不着了。<h2 id="Day-23-停课">Day -23 停课</h2>2025/11/06停课。<h2 id="Day-19-Day-5-集训">Day -19 ~ Day -5 集训</h2>2025/11/10 ~ 2025/11/24云斗集训，今年感觉还挺好的。打了前四场模拟赛，发现我怎么好多不会的。开始自己做题。<h2 id="Day-4-Day-2">Day -4 ~ Day -2</h2>2025/11/25 ~ 2025/11/27在机房打板子。机房甲流爆发，全天和 cpp xixisuper 苟在讨论室戴口罩。吓人。<h2 id="Day-1">Day -1</h2>2025/11/28出发去淄博，下午到北京路亚朵，在酒店启动打板子模式。打了 tarjan*2+hash*2+sgt*2，顺便把各种 log 数据结构和 lca 打了一遍。楼下吃的熙临居博山菜，感觉很好吃啊。去试机发现还是去年的同一个机房，windows 和虚拟机都有装好插件的 vscode，但是不知道为啥 <code>launch.json</code> 死活配不对，而且还莫名其妙死机一分钟，决定还是用 devcpp 写代码。取模 1s 5.5e8。晚上回到房间开始用 devcpp 随机写东西，结果发现完全不适应，自动补全完全没有，发现 xixisuper 有？？？这还有版本差异。在 22:20 成功清空任务列表，十点半多一点睡觉。<h2 id="Day-0-NOIP">Day 0 NOIP</h2>2025/11/29今年好像没有什么太大的反应了，面对距离退役还有 5 个多小时的事实已经释然了。心态从 06:50 到 12:00 左右都一直非常平静。从酒店一路堵到山理工，罪魁祸首是淄博实验。看人家学校校园还大，门还多，周六 8 点才到校，某学校学学人家。08:07 进场，先把缺省源和目录建好，然后就发压缩包密码了。开 T1，读一遍题发现这不是显然吗？于是乎马上码代码，大概 08:15-20 左右写完，思路大概是尽量多的选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 最大的，如果实在选不了了就按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 排序去选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 小的，对于一个 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 检查撤销上一步 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 那个对的选择是否不劣。大样例 6 没过，输出 81 比答案少 2。不懂为什么，尝试换了个思路写了个暴力错的更离谱了。然后整理了一下发现前半部分选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 最大的肯定是对的，问题是后面。直接去按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 从小到大排序，看如果把一部分 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 的选择换成一个 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 前缀是否会更优即可。从原来代码删删改改，使用 <code>res</code>, <code>cnt</code>, <code>cntdiff</code>, <code>last</code> 等意义不明的整型变量。大样例过了，开 T2。瞪了一眼觉得仍然是简单题啊，手模样例感觉就是总数减除以二之后产生的逆序对数量。上个厕所冷静一下然后 5min 简单实现发现错完了。决定打暴力，直接 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>n</mi></msup><mo>×</mo><mi>n</mi><mi>m</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(2^n\times nm)</annotation></semantics></math>Θ(2n×nm)，20pts 到手。开始思考特殊性质，对 A 性质闪过了一个答案为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">2^n</annotation></semantics></math>2n，但是因为不会证并且没大样例放弃了。开写 T2 之前看了 T3，一直没想到什么思路。写完 T2 暴力想了两个贪心策略但是一眼假，暴力实现难度略高。看 T4 的简单题意感觉暴力可做。然后就不知道怎么打出来了忘了是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>3</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^3\log n)</annotation></semantics></math>Θ(n3logn) 还是 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">Θ</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mi>log</mi><mo>⁡</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">\Theta(n^2\log n)</annotation></semantics></math>Θ(n2logn) 复杂度的暴力了，总之期望得分 5pts。甚至取模都没想到是 <code>unsigned long long</code> 直接用的 <code>__int128</code>。回到 T2，突然发现有贡献当且仅当两个 1 合并起来比 2 要小，然后就不会做了。最后 20-30min 比较辗转反侧，再多打一个 T3 暴力显然来不及，想任何一个题正解也想不完。在 T4 的文件末尾写下了：<figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 </pre></td><td class="code"><pre><code class="hljs cpp">// AFOed on 20251129 </code></pre></td></tr></table></figure>13:00 出场。下楼看见 xixisuper，直接问 T2 做出来了吗，T3 做出来了吗，T4 做出来了吗。他一脸懵逼说不会啊，不会啊，不会啊。于是去机房群里激情开喷。山理工路上碰到 cpp，问她 T2 会做吗，得到了一样的答案。群里伪人和 MrPython 自称全都不会。大家全都开始在群里激情开喷。<img src="https://img.makerlife.top/data/202511292229517.png" alt="激情开喷">但是某文化课了两个周的哥们会？？？直接场切紫题？折磨牛。结果在群里对 T1 大家思路全都不一样。对 T2 发现少拿 4pts。对 T4 发现暴力打丑了。自认为 T1 思路很对。洛谷是黄黑黑黑？黄嘿嘿嘿。下午直接回家，想测洛谷的 T1 民间数据。此时看到群里发了一个大样例全过洛谷得 80pts 的截图。打了一会 T1 打不动了，大脑停止工作。但是发现我考场代码好像按 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 排序的时候没有考虑有多组 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x+y</annotation></semantics></math>x+y 相同处理 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x 的情况。这下要随机挂分了。算了一下期望 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mo>+</mo><mn>20</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>5</mn><mo>=</mo><mn>125</mn></mrow><annotation encoding="application/x-tex">100+20+0+5=125</annotation></semantics></math>100+20+0+5=125，就看 T1 挂不挂了。AFO 还是很平静的。甚至以为第二天就要上学了，过单休过习惯了。我还是舍不得我的 oi 啊。

微积分学习笔记

Makerlife 的小站

作者 Makerlife

2025年10月2日 10:27

极限与导数

Core Code:

for(int i=1;i<=n;i++)
{
f[i][1]=max(f[i-1][2],f[i-1][3])+a[i];
f[i][2]=max(f[i-1][1],f[i-1][3])+b[i];
f[i][3]=max(f[i-1][1],f[i-1][2])+c[i];
}

AT_DP_K Stones

洛谷 Link

显然当一名玩家操作完成后石子数量为 $0$ ，则这名玩家必胜。

设 $f_i$ 表示剩余 $i$ 枚石子当前操作的人的输赢情况 ( $1/0$ )，可以发现当且仅当当前操作的上一步操作必输，当前操作才可以必胜，即如果有 $a_j$ 使得 $f_{i-a_j}=0$ ，则 $f_i=1$ 。

初始化 $f_0=0$ ，则有：

$f_i=\begin{cases}1,&a_j\leq i,f_{i-a_j}=0\\0 ,& \text{otherwise.}\end{cases}$

Core Code:

f[0]=0;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
if(i-a[j]>=0 && !f[i-a[j]]) f[i]=1;
}
}

TDPC_IWI イウィ

洛谷 Link

区间 DP，类似合并石子。

我们定义 $f_{i,j}$ 记录 $i$ 到 $j$ 能删掉多少字符，显然最后答案应除以 $3$ 。

因为答案计算的是最大的步数，那么对于一个大区间，在一般情况下的答案就应该是其分成的两个小区间的答案之和。考虑枚举这两个区间之间的分界点 $k$ ，答案取最大值即可。

本题还需要特判一种特殊情况。如果 $s_i$ 和 $s_j$ 为 i， $s_k$ 为 w，且中间的两个小段可以被完全删除。那么，当中间的被删掉之后，左右的 i 和中间的 w 就会拼在一起，也可以删掉，那么这个区间的答案就应该是它的长度，但显然直接相加有可能会出错。

Core Code:

for(int a=2;a<=len;a++)
{
for(int i=1;a+i-1<=len;i++)
{
int j=a+i-1;
for(int k=i;k<j;k++)
{
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
if(s[i]=='i' && s[j]=='i' && s[k]=='w' && f[i+1][k-1] == k-i-1 && f[k+1][j-1] == j-1-k)
{
f[i][j]=j-i+1;
}
}
}
}
write(f[1][len]/3);

ABC247F Cards

AT_DP_D Knapsack 1

<a href="https://www.luogu.com.cn/problem/AT2561">洛谷题目传送门</a> | <a href="https://atcoder.jp/contests/abc061/tasks/abc061_c">AT 原题传送门</a><h2 id="思路">思路</h2>桶的思想。用数组 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t 存储 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>a</mi></mrow><annotation encoding="application/x-tex">a</annotation></semantics></math>a 出现的次数，然后循环，用 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k 减每个数出现的次数，看在哪个数时满足 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>≤</mo><mn>0</mn></mrow><annotation encoding="application/x-tex">k \leq 0</annotation></semantics></math>k≤0 的条件，直接输出这个数的下标即可。注意不开 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext mathvariant="monospace">long</mtext><mtext> </mtext><mtext mathvariant="monospace">long</mtext></mrow><annotation encoding="application/x-tex">\texttt{long long}</annotation></semantics></math>long long 见祖宗<h2 id="代码">代码</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 </pre></td><td class="code"><pre><code class="hljs cpp">#include<cstdio> #include<iostream> #define ll long long using namespace std; ll n,k,a,b; ll t[100010],ans=0; int main() { scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld%lld",&a,&b); t[a]+=b;//t为桶，增加a的个数 } while(k>0)//当k<=0时跳出循环 { k-=t[++ans];//每次k自减t[++ans] } printf("%lld\n",ans); return 0; } </code></pre></td></tr></table></figure>