本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-15 19:10:45

弹弦高唱声回环，千羽驻林间。

12.18

提交了申请。

1.2

申请通过了，然而第一次填的时候试图选不参加看下面的问题还在不在，结果最终忘了填的是啥了，所以又填了一次，被 Iceturky 嘲笑了。

1.3

订了 $30$ 个徽章，因为 $30$ 个起包邮。发现 Iceturky 没注意导致 $25$ 个比我还贵，嘲笑回去了。

1.13-Day0

早上的火车，十一点就到北京了。下午去报道排了两个小时队，冷，但是通过面基群里的消息认出了一些大神。去试机发现不会用 Linux 和 VSCode，不会编译，只写了 A+B 就跑了。

试完机坐地铁逛了一圈，吃了饭以后回酒店临阵突破研究了一下编译，把去年 T1 写了写就睡了。

1.14-Day1

进场，开场前就发了一个面包一瓶水俩士力架，然而我不喜欢吃士力架。开场看题，T1 线段树优化 DP，好写好写！一个小时过了。T2 好神秘，推了挺长时间，四维限制还猜过 CDQ，但是不会。用线段树维护次大写了 $43$ 的 $z\le2$，诶是不是类似就能全做完，好像不能，跳。T3 故障机器人，怎么是塔。猜了一个很神秘的关于括号序列的结论，用这个写了 $36$ 暴力结果全过了？哦好像能证，挺好。最后看 T4 只会 $20$ 暴力 DP，写了。

这时候拿了 $199$ 分，还有一个多小时。开始吃面包，并且看了看其他的部分分。发现只会 T3 的 $9+17$ 分特殊性质了，感觉也不太难写，开写。结果 $17$ 分的写到一半发现假了，$9$ 分的写完了但到最后也没调出，$199$ 遗憾离场，但感觉也没有太差。

考完去操场合照，几百人在北京的寒风中站了十多分钟，冷。然后吃饭，吃得还不错，但是五十还是有点贵，~感觉不如 wfyz 食堂~。吃饭的时候也见到初三的 syy 了，以前只知道但没说过话，认识了一下，互相拍了个照，然后也一块行动了。

下午学科嘉年华是一堆 AI 科技展示，逛了一圈感觉没啥好玩的。玩完以后在 THU 某个校门等了半个多小时大巴才来，冷。晚上去紫光园吃了烤鸭和据说很好吃的酸奶，但是感觉就是普通老酸奶，没有特别惊艳。然后回酒店颓了会就睡了。

1.15-Day2

早上看群好像 D1T2 就是类似维护次大值，线性的？恐怖，不管了。听说 Day2 是工程题，以前从没写过，有点慌。

进场，又发了跟前一天一样的物资。开题，题面十多页，大概是写一个大语言模型还是啥的，从最简单的部分开始写，一共七个题。T1 水，然而是零下标，后来看到公告才改过。T2 根据提示把矩阵乘法的一个矩阵转置一下卡常就过了。然后 T3-T5 就是给了一堆奇怪的张量矩阵乘法之类的公式，根据题面里的式子一个一个套上就行，都一遍过了。

此时还有俩小时，优势在我！结果读 T6 读懵了，好多式子，式子还很混乱，不懂啊。读了一个小时大概明白了，中间也看了一眼 T7 是要把前面六个题的东西拼一起，还是得先写 T6。然后开写，还有半个小时的时候写完了，交！只有 $8$ 分，后来也看出来一个错改了，但是最后也没过，只有 $8.64$ 分。

出场发现好像人均 $508$，难绷。之后面基群里说有一个操作需要对矩阵的每一行分别做，而不是对整个矩阵一起做，题面没写清楚，难评。之后还发现题面有好多很不清楚歧义的地方，难视。

下午开幕式，然后听讲座，两个清华教授讲了一些 AI 相关，感觉还挺有意思的。然后闭幕式，应该是发纸，结果改成发牌了。据说原一等二等是金，三等是银，我拿银了，但是金只有 $110$ 个，这下接受了，没打铁就挺好。

晚上会坐卧铺回家，然后过两天再去绍兴 WC。总之首先是社恐导致进了面基群但啥也没干，最终徽章就只给了两个认识的同学。还有感觉 Day2 的工程题还是很有意思的，如果题面写得严谨一点或许体验会更好。好玩，下次能来还想来。

食粮满篮水满罐，今生复何求。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 15:52:12

做了几道搜索，记一下。

Gym - 100825C. KenKen You Do It?

减和除直接 $O(n^2)$ 枚举即可，对于加和乘考虑搜索，朴素的搜索一位一位枚举即可，剪掉行列中的相同数以及不可能达成目标的状态，但时间还是很紧张。

考虑把搜索过程分为两部分，一部分只搜出每个数各出现多少次，比如设 $c_i$ 表示 $i$ 填的次数。此处不考虑是否真的能填进去，而是凑出 $t$ 来即可。

把一组 $c_i$ 跑出来后，考虑计算其填进格中有多少种不同方式。我们发现 $i$ 的取值已经不重要了，重要的只是有多少相同数出现。所以给 $c_i$ 排个序，计算排序后的次数序列有多少中出现的可能即可。

对于每种出现次数的计算，可以在前面预处理出来，像朴素搜索中一样搜出来，但复杂度大致由 $O(m^n)$ 降至阶乘，因为只考虑出现次数，每次只可能多开一种。把跑出来的所有情况放 map 里，在前面用到时在 map 里查一下即可，这样就跑过了。

CF293B. Distinct Paths

Sol.1 搜索 + 剪枝（同类搜一次）

根据抽屉原理，$k$ 种颜色只能不重复地放到 $k$ 个格子里，若路径上的格子总数 $n+m-1$ 超过了 $k$，则一定无解。所以数据范围实际上是 $n+m-1\le10$，考虑搜索。

朴素的搜索也就是开 $v_{i,j}$ 表示以 $(i,j)$ 为右下角，$(1,1)$ 为左上角的矩形内出现过的数，状压存一下就行。每一位先记录下 $v_{i,j}=v_{i-1,j}\cup v_{i,j-1}$，然后枚举其中没有的一项填上再继续往下搜即可。可以加的剪枝是其中没有的项数不足 $(n-i+m-j+1)$ 时一定无解，但是这样复杂度还是高。

考虑把相同的东西放到一块搜，发现填到 $(i,j)$ 时，所有在已填过的区域和题目规定的限制中均未出现过的数本质上是等价的，也就是不管在这填哪一种，后面接着填的方案数相等。那么第一次出现这样的数就搜下去记一下，后面再出现直接加上标记就行。判断是否是这样的数只需要开个数组记录是否出现过即可。

Sol.2 状压 DP（容易超时）

考虑一格一格填，发现若 $(k,l)$ 填 $x$ 导致后面填 $(i,j)$ 时不能填 $x$，当且仅当 $k\le i$ 且 $l\le j$。由于 $k\le i$ 一直满足，重要的就是前面填过的 $x$ 中列数最小的那个 $l$。所以把 $k$ 种颜色的这个列数在 $16$ 进制下状压，用 map 存一下，每次取出来找 $l\le j$ 的转移一下即可。

这份代码用了一些剪枝，把开头和结尾的颜色剪掉了，剩了 $8$ 个颜色跑，但还是跑不到 $1$ 秒内，不知道是不是我实现的问题。

AT_icpc2012autumn_b. Texas hold 'em

发现从剩余的 $45$ 张牌里选两张的方案数为 $\frac{45\times44}{2}=990$，每个人从七张牌中选五张的方案数为 $\frac{7\times 6}2=28$，总共需要处理的牌型有 $990\times28\times2=55440$ 种，所以直接暴力搜出每一种即可。

另外还有一些处理牌型时能注意到的点：

• 每张牌是什么花色不重要，只需要知道五张牌是否同花色即可。
• 任意两种有区别的牌型均能分出大小。
• 所有比较均是先比较类型，再以某些牌的大小为关键字比较。

因此想到如果能把每种牌型都压成一个数，会更方便比较。所以代码中把牌的类型作为高位，其他关键字依次作为低位压成了一个数。而且这里只需要保证同种类型的牌型处理时位置对齐即可，不同类型之间已经由于最高位不同分出大小了。

另外可以用函数判断区间相等，用函数把关键字压成一个数等，可以简化代码。

CF525D. Arthur and Walls

从宏观看到微观，发现只要是矩形，在 $2\times 2$ 的格子里就一定会有 $0,1,2,4$ 个点，反之若有三个点，则另一个必须也变成点才能形成矩形。因此初始把本来是三个点的位置放到队列里，BFS 搜索，每次修改后再判断修改处有关的四个 $2\times 2$ 区域是否变为三个点，再放到队列里一直处理，直到队列空为止，此时一定恰好全部变为矩形。

由于每个 $2\times2$ 区域最多被找到四次，时间复杂度 $O(4nm)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-08 23:48:46

记录

AG 还没做，C 没处理好方案输出，D 没判 $1\times 1$ 的边界，E 式子写错了，其他的没啥问题。

题解

A. New Adventures of the Wolf of Wall Street

待补。

B. Choosing a Vertex To Remove

树形换根 DP，设 $siz_u,sum_u,f_u$ 分别表示子树大小，子树权值和以及 $u$ 的所有子树贡献和，也即 $\sum_{v\in son_u}siz_v\times sum_v$，一遍 DFS 就能求出。

那么删掉根节点的答案即为 $f_{rt}$，然后进行换根 DP，计算 $v$ 答案时给 $f_v$ 加上其父亲的那颗子树，也即 $(n-siz_v)(tot-sum_v)$，其中 $tot$ 为所有节点的权值和。对所有的 $f_i$ 取最大值即可。

C. Space Expedition

二维 $01$ 背包，考虑像一维一样设 $f_{j,k}$ 表示两种容量分别为 $j,k$ 的最大代价，转移时也是倒序枚举 $j,k$，更新 $f_{j,k}=max(f_{j,k},f_{j-a_i,k-b_i}+v_i)$ 即可，最终答案为 $f_{A,B}$。

但是如果直接记 $p_{j,k}$ 表示 $f_{j,k}$ 最后使用的物品，直接输出答案的话，会出现重复的情况。因为最终的 $f_{j,k}$ 是考虑了所有元素的，可能同一个物品既会给 $f_{j,k}$ 更新，同时也会给 $f_{j-a_i,k-b_i}$ 更新，而对结果的影响是用倒序枚举消掉的，但方案就会炸掉。

所以改设 $f_{i,j,k}$ 表示前 $i$ 个物品给 $j,k$ 容量的最大价值，有 $f_{i,j,k}=\max(f_{i-1,j,k},f_{i-1,j-a_i,k-b_i}+v_i)$，这里用 $v_{i,j,k}$ 记录一下是从哪个转移来的，最后输出方案时从 $(n,A,B)$ 一直按照 $v_{i,j,k}$ 转即可，最后正序输出。

D. A Giraffe Travels and Munches

DP，设了两种状态，第二种要注意处理一下不用走，也就是 $n=m=1$ 的情况，不然会寄。

Sol.1

设 $f_{i,j}$ 表示最终停在 $(i,j)$ 的最大价值，用 $\frac{i+j-2}{k+1}$ 计算出走的次数以确定系数，若不能整除就到不了这格。然后从 $f_{i-k,j-1}$ 或 $f_{i-1,j-k}$ 转过来再加上这格的收益即可。最终答案为 $f_{n,m}$。

Sol.2

设 $f_{i,j}$ 表示走了 $i$ 次，其中 $j$ 次是向下 $k$，向右 $1$ 的最大价值，可以计算出最终的奇偶性。然后可以从 $f_{i-1,j}$ 或 $f_{i,j-1}$ 转移过来，最终枚举终点是 $(n,m)$ 的 $i,j$ 来更新答案即可。

E. Petya and Dice

发现只需要记录下有多少字符已经复原即可转移，设 $f_{i,j}$ 为操作 $i$ 次后 $j$ 个字符已复原的方案数，$f_{0,cnt}=1$。有以下分类转移:

• $f_{i,n}=\sum_{j=0}^{n-1}f_{i-1,j}$（全变对）
• $f_{i,0}=\sum_{j=0}^n f_{i-1,j}\times (25^n-[j=0])$（全变错）
• $f_{i,j}=f_{i,j}+24(n-j)f_{i-1,j}+(n-j+1)f_{i-1,j-1}+25(j+1)f_{i-1,j+1}$（修改）

滚动数组优化一下空间，少取模优化一下时间就能过。

F. Lottery

考虑把 $b_i$ 需要的次数求出来作为花费，$c_i$ 作为收益，就能转化为 $01$ 背包问题。设 $f_i$ 为变出 $i$ 需要的次数，初值 $f_1=0$，那么可以枚举 $j<i$，求出可用 $z$ 的范围为 $(\frac{j}{i-j+1},\frac j{i-j}]$，若有整数则可以转移 $f_i=\min(f_i,f_j+1)$。

这样就可以做 $01$ 背包了，但是复杂度 $O(nk)$ 达到 $10^9$，考虑减小 $k$，发现 $i$ 在 $10^3$ 之内的 $f_i$ 最大只有 $12$，那么全都变好至多也就 $1.2\times10^4$。所以把 $k$ 与所有 $f_{b_i}$ 的和取较小值即可，复杂度优化到 $10^7$ 级别。

G. Evolutionary Tree Weights

没讲，待补。

I. Sum of Path Lengths

把贡献拆到边上，那么点 $v$ 连到父亲的边的贡献为 $siz_v(n-siz_v)$，用树形 DP 处理出 $siz$ 数组后计算求和即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-12 10:59:33

记录

A-E 切了，F 想了一会困了就睡了，没做出。

题解

A. Only Pluses

枚举所有加的情况直接算即可，或者有数学结论，但我没想。

B. Angry Monk

由于最后要合到同一段，那么在最终合并之前只能剩最多一段非 $1$ 的，显然要剩下最大的那段。总代价为所有其他段的 $2a_i-1$ 之和。

C. Gorilla and Permutation

要最大化 $f$ 同时最小化 $g$，显然要把不小于 $k$ 的放在最前面，不大于 $m$ 的放在最后面。另外为了让大数在 $f$ 里多贡献，在 $g$ 里少贡献，前面要递减放，后面要递增放，中间无所谓。

D. Test of Love

DP，设 $f_i$ 表示到达 $i$ 所需的最少游泳格数，如果第 $i$ 格是地面，更新 $f_j=\min(f_j,f_i),f_j\le i+m$。如果是水，更新 $f_{i+1}=\min(f_{i+1},f_i+1)$，最后判断 $f_{n+1}$ 是否不超过 $k$ 即可。

E. Novice's Mistake

设 $n$ 的长度为 $l$，考虑枚举最后保留的位数 $i$，可以算出保留部分的数字大小 $k$。那么有以下式子：

• $na-b=k$
• $la-b=i$

解得 $a=\frac{k-i}{n-l}$，求出 $b$，判断 $a,b$ 是否合法即可。

当且仅当 $n=1$ 时 $n-l=0$，会 RE，特判出来有 $9999$ 种 $b=a+1$ 的方案即可。

F. Valuable Cards

考虑贪心，也就是从左到右依次分出极长合法子段。先预处理出 $x$ 的所有因数 $dx_i$，用 unordered_map 维护已经能构成的因数集合，每到 $a_j$ 就枚举所有因数 $k\in dx$，看是否能新构成这个因数，也就是 $a_j\mid k$ 且 $\frac {k}{a_j}$ 出现过，直到 $x$ 能构成就把 $j$ 分到下一段即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 17:41:51

记录

ABC 正常，D 猜结论过了？E 用的笛卡尔树不太会，再说。

题解

A. Split the Multiset

注意到每次操作最多把数增加 $(k-1)$ 个，那么由 $1$ 个变为 $n$ 个需要的最少次数为 $\lfloor\frac{n-1}{k-1}\rfloor$。

B. Make Majority

发现可以把一段 $0$ 变为只剩一个，然后判断 $01$ 个数大小即可，只有 $1$ 的个数严格大于 $0$ 时可以最终变成 $1$。

C. Increasing Sequence with Fixed OR

先把给的数转成二进制，只需要考虑为 $1$ 的 $k$ 个位。根据题意，相邻的两个数不能有一位两者都为 $0$。同时贪心地想最大数一定为 $n$。倒着填时每次都要符合条件且尽可能大，那么每次都只去掉一个 $1$ 即可，这样的 $k+1$ 个数一定最优。

D. The Omnipotent Monster Killer

发现如果有次数上界 $k$，那么直接树形 DP 设 $f_{u,i}$ 表示 $u$ 子树内 $u$ 第 $i$ 轮删的最小花费，$f_{u,i}=ia_u+\sum \min_{j\ne i}f_{v,j}$ 直接转即可。问题在 $k$ 最大能取到多少。

最初感觉取到 $3$ 即可，但是挂了。考虑如果原树 $n$ 个点需要 $k$ 次删完，那么给每个点都连上一个极大值点，也就是加上 $n$ 个点就能让其多一次操作。所以操作数上界为 $\log n$。正式证明我不太会，只会感性理解。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-19 15:19:48

记录

ABCD 切，E 不会，后来发现是结论题。（上紫了啊）

题解

A. Diverse Game

显然把每个数增加 $1$，$nm$ 变成 $1$，除 $n=m=1$ 外均有解。

B. Fun Game

首先发现只用一位去修改 $s_x$ 影响最小，所以先找到 $s$ 中第一个 $1$ 的位置 $p$。那么对于所有 $x>p$ 的 $s_x$ 都可以通过选以其为结尾的 $p$ 个字符来单点修改，最后 $s_p$ 也可以通过选前 $p$ 个来变成 $1$。所以当且仅当 $s$ 中与 $t$ 不同的位置均在第一个 $1$ 之后就合法，否则非法。

C. Hungry Games

考虑枚举 $l$，求出答案非零的 $r$ 数量。那么设 $f_i$ 表示以 $i$ 为 $l$ 时后面答案为 $0$ 的 $r$ 数量，则 $f_i=f_{nxt_i+1}+1$，其中 $nxt_i$ 表示从 $l$ 开始取到这一位正好大于 $x$，而取到上一位不大于。这个东西在前缀和上二分一下就行，对所有的 $n-i+1-f_i$ 求和即为答案。

D. Funny Game

倒着考虑，也就是从 $n-1$ 一直到 $1$。发现 $i\mid (a_u-a_v)$ 等价于 $a_u \equiv a_v\mod i$，而对 $i$ 取模的结果有 $i$ 种，此时有 $i+1$ 个连通块，根据抽屉原理一定能连出一条边。所以倒着考虑的时候暴力找到一对不连通的合法点连起来即可。

赛时对每一种余数分别平方找的，时间复杂度好像 $O(n^3)$，但跑得很快。其实如果对于每一组，若第一个与其他的都在同一连通块就可以跳出了，这样复杂度就是 $O(n^2)$ 的了，150ms 减到了 100ms。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-20 22:31:22

要看到题目之间的联系，更要看到联系之间的联系。

[ABC155F] Perils in Parallel

考虑把区间操作变成单点操作，那么区间 $[l,r]$ 取反相当于在前缀异或值上取反 $l$ 和 $r+1$。那么对整个序列求前缀异或值，可以同时修改某两个位置，求是否能够把序列变为全 $0$（原序列和前缀序列均是），$l$ 和 $r$ 可以离散化二分求出。

那么把 $l$ 和 $r+1$ 连边，生成一张无向图。考虑若要同时取反 $x$ 和 $y$，只需任选图上一条 $x,y$ 之间的路径，使用路径上的边操作即可。那么找一个生成森林即可进行操作。

考虑对于每个需要取反的点 $x$ 都把 $x$ 到所在树根 $rt$ 路径上的边状态全部取反，那么两个点的路径即可由 $rt$ 相连构成一整条路径从而实现取反。如此若 $rt$ 最终的状态不符合题意则无解，否则求一下每条边是否被选即可。

[CF1994F] Stardew Valley

重要性质：一张图有欧拉回路当且仅当每个点的度均为偶数。

那么把重要边的对每个点的度数奇偶性记录下来，非重要边可以同时取反两个点的奇偶性，跟上一道题一样做，最后跑欧拉回路即可。

所以题目之间会有很多相似的部分，关键在于做过的题要理解每一部分并能运用，而不同的部分需要经验性质之类解决。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-21 12:45:34

记录

AB 过了以后，C 卡了五发不过，D 赛后一分钟写完，掉 100 分，寄。

题解

A. Submission Bait

发现所取数量的奇偶性会影响到最终的胜负，而所取数量取决于先手第一次取的 $x$ 及以上的个数，所以对桶数组做后缀和，只要有奇数就可以必胜。

B. Array Craft

考虑把 $[y,x]$ 内全赋为 $1$，那么这个区间内肯定是 $a_x$ 前缀最大，$a_y$ 后缀最大。只要在 $[1,y-1]$ 和 $[x+1,n]$ 交错填上 $1$ 和 $-1$，使所有值不大于要求值，所以 $x,y$ 就是满足下标条件的位置。

C. Mad MAD Sum

发现一次操作后变成递增，两次操作后除了最后一段其余长度均大于 $1$。把这两次暴力操作，后面就是前面的段不变，同时最后一段消失。那么可以直接处理贡献。

D. Grid Puzzle

发现长度大于 $4$ 的行一定是直接全涂，用这些行分段，对每一段分别 DP，设 $f_{i,0/1,0/1}$ 表示第 $i$ 行是否选 $1,2$，是否选 $3,4$ 时把前 $i$ 行全涂白的最小代价，转移一下即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-13 01:45:57

请你打开电视看看

多少人 为生命在努力勇敢的走下去

我们是不是该知足

珍惜一切 就算没有拥有

今天 B 站首页推了一首枯久伪合唱稻香，推出来肯定是因为我比较关注方舟 up 主。重新听这首歌，勾起了我的回忆，也给我带来了很多感触。我循环了半天，也听着写下了这篇鲜花。

去年暑假，初中举办歌唱比赛，我们班选了这首歌。记得化学老师让我们拿了纸飞机，最后扔到了台下。那是我初三生活第一个美好回忆，当时真的有一种忘却烦恼的感觉。

当时我最大的烦恼就是高中。我拿到了去市一中的资格，面临着去不去的抉择。我很犹豫，留在县里没有什么资源，而我又不想放弃 OI；可我在初中又有很多很好的朋友，离开又很舍不得，也很想留下，内心一直在挣扎。

那段时间，我时不时翻看我们班的照片，还有我们当时唱《稻香》的视频，边感慨边思考着这个重要的抉择。我很珍惜这份友谊，无论以后能不能一直拥有，我都很珍惜。

还记得 你说家是唯一的城堡

随着稻香 河流继续奔跑

微微笑 小时候的梦我知道

不要哭 让萤火虫带着你逃跑

乡间的歌谣 永远的依靠

回家吧 回到最初的美好

我最后还是决定离开，决定继续在 OI 的路上奔跑，追逐我自己的梦。联系上一中教练那天，我在自己的洛谷主页留了一句话，这也是我认知上自己 OI 生涯的开始。

让我很感动的是，我离开初中的消息传开时，有几个同学在朋友圈里发文送别，很多老师也给我发消息祝福。这时我明白，即使我离开了，我们已经结下的情谊也不会消失，能让我一直拥有，一直珍惜。

下半学期里，我只因为考试和毕业回了几次初中，与故人重逢半天再离开。每次回去之前，我还是会听我们一起唱的《稻香》。我能感受到，这对我来说就是回家；而这份情谊，就是那最初的美好，也会是我永远的依靠。

不要这么容易 就想放弃 就像我说的

追不到的梦想 换个梦不就得了

为自己的人生鲜艳上色

先把爱涂上喜欢的颜色

来了一中以后，我很快发现自己之前学的东西太少了，自己的水平很低。同时我也深刻认识到了 OI 之路的艰难，也考虑过是否要坚持学下去。

后来，随着水平逐渐提高，我也慢慢想通了，决定尽力去尝试一把。成功也好不成功也罢，尽力就好。顶多是之后学文化课困难点，我也不怎么怕。

如今看来，这种想法在歌词里似乎也有体现。“换个梦不就得了”，不是直接放弃，而是不在意最终结果的豁达。只要不放弃地追逐梦想，这个过程本身就足够美好。

笑一个吧 功成名就不是目的

让自己快乐快乐 这才叫做意义

童年的纸飞机 现在终于飞回我手里

到了暑假外出集训，SDSC 有不少讲座，我几乎全听了。讲座经常提到对 OI 的兴趣，我自认为是有的，这也是我在多次抉择中都选择继续的最大原因。

正如歌词所说，虽然“功成名就”也是目的之一，但真正的意义还是在于兴趣带来的“快乐”。这歌词的回旋镖就像纸飞机一样，似乎在这时飞回了我手里。

对这个世界 如果你有太多的抱怨

跌倒了 就不敢继续往前走

为什么 人要这么的脆弱 堕落

还有，某次讲座开始前，旁边的学妹问我：“你今年能进省队吗？”我答道：“我想进啊，但是……

当我想说“我真正学的时间不长，水平不够高”之类的话时，她打断我说：

“想，那你就去做啊。”

我好像被什么东西击中一样沉默下来。这句话我听过，但从来没有这样触动过我。是啊，心之所向，不管有多少困难，努力去追求即可。如今重听《稻香》，它也告诉我，不管跌倒几次，都要继续往前走。

我很感谢那位学妹，她让我明白了很多。某种意义上，她已经是我的老师了。

想完了。该开始做了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-15 17:48:41

[ABC299F] Square Subsequence

考虑求 $S$ 中有多少种本质不同的子序列，需要保证 $f_i$ 不会同时转移到 $S_x=S_y$ 的 $x,y$ 才能避免算重。那么处理出 ${nxt}{i,c}$ 表示在 $[i+1,n]$ 中最小的 $j$ 使得 $S_j=c$， $f_i$ 只向 ${nxt}{i,c}$ 转移即可，也即 $f_{nxt_{i,c}}=f_{nxt_{i,c}}+f_i$，答案为 $\sum_{i=1}^n f_i$。

那么推广到前后出现两次的子序列数量，首先需要枚举断点 $r$，为了避免算重，定义 $r$ 为第一个子序列的结尾并枚举 $r$。每轮设 $f_{i,j}$ 表示第一个子序列结尾为 $i$，第二个子序列结尾为 $j$ 的方案数，初值 $f_{0,r}=1$。那么 $f_{nxt_{i,c},nxt_{j,c}}=f_{nxt_{i,c},nxt_{j,c}}+f_{i,j}$，其中 $f_{i,j}$ 的 $i\le r,j\le n$。每轮给答案累加上 $\sum_{i=r+1}^n f_{r,i}$ 即为答案。

[ABC320F] Fuel Round Trip

发现油箱容量 $H$ 跟 $n$ 同级，考虑设进状态。先考虑弱化版，也就是只需要从 $0$ 走到 $n$ 的最小代价。那么设 $f_{i,j}$ 表示走到 $i$ 且剩余油量为 $j$ 的最小代价，转移即可。

那么如果需要来回，就设 $f_{i,j,k}$ 表示到第 $i$ 个去时剩余油量为 $j$，返回时剩余油量为 $k$ 的最小代价。由于前后只能加一次油，所以需要同时考虑两次的加油情况，因此倒序枚举 $i$ 并转移即可。设 $dis$ 表示 $x_{i+1}-x_i$，$s_i$ 是题意中的 $F_i$，有如下转移：

• 不用：$f_{i,j,k}\leftarrow f_{i+1,j-dis,k+dis}$。
• 第一次用：$f_{i,j,k}\leftarrow f_{i+1,\min(H,j+s_i),k+dis}+p_i$。
• 第二次用：$k<H$ 时，$f_{i,j,k}\leftarrow f_{i+1,j-dis,k+dis-s_i}+p_i$；$k=H$ 时，$f_{i,j,k}\leftarrow f_{i+1,j-dis,l}+p_i$，其中 $l\in[H+dis-s_i,H]$。

另外要注意的是 $n-1$ 与 $n$ 之间要特殊处理初始状态，可以令 $s_0=H,p_0=0$，答案即为 $\min f_{0,0,i}$。

[ABC366F] Maximum Composition

考虑排好顺序以后 DP，需要有判断条件。考虑 $k$ 先后使用第 $i$ 和第 $j$ 个应该怎么排序，如果先使用第 $i$ 个，则最终为 $a_j(a_ik+b_i)+b_j$，先使用第 $j$ 个最终为 $a_i(a_jk+b_j)+b_i$，以此排序后设 $f_{i,j}$ 表示前 $i$ 个中使用 $j$ 个的最大收益即可。

同样的思路在 AT_DP_X 里也用到了，即先排号所有操作的顺序再进行 DP。