可能更好的阅读体验 link，优先更新这里
受到 AIerqwq and wcqwqk 的启发，打算写个题解记录做过的题。以下题目会先用口胡的形式呈现（注意不保证解法正确），后续可能会加上代码 and 正确思路。也欢迎各位大佬来指正我的口胡思路 awa。
部分题目出自题单：https://www.luogu.com.cn/training/9350
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P1095
本来写的是贪心，但这个做法会写成构式大分讨，还是老老实实写 DP 吧。
移动有三个优先级：
1. 直接魔法移动
2. 恢复魔法值后魔法移动
3. 跑步
不难发现，使用跑步的情况，要么是充能时间足够跑出去，要么就是剩余时间不足以进行第二轮充能。
定义 dpidp_idpi 为第 iii 秒所能移动到的最远距离。先按照上述优先级构建好 dpdpdp 数组。第二轮我们考虑可以在恢复魔法值时间内里开的情况，把所有休息替换成奔跑。如果到了终点直接输出即可。
代码(排班有点小问题，不用在意)：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P1462
开始是不会做的，看了下 tag 有一丢丢思路了。
发现题目要求经过城市单次交费最大值的最小值，考虑二分答案。其中的 check 函数就是最短路，如果可以跑完，那就往大了跑，否则就往小了跑。
代码：
咕咕咕
B4133
诶我咋跑过来做橙题了。
定义 dpidp_idpi 为从 111 到 iii 的最大字段和，显然转移方程为 dpi=max(dp[i−1]+a[i],a[i])dp_i=\max(dp[i-1]+a[i],a[i])dpi =max(dp[i−1]+a[i],a[i])。答案为 max(a1,a2...an)\max(a_1,a_2...a_n)max(a1 ,a2 ...an )。
代码：
P1439
乍一看 LCS，仔细一看确实 LCS。居然是绿题 /yiw。
不怼，这个数据怎么高达 10510^5105。
不管了先写部分分。
50%50\%50% 部分分
显然为朴素 LCS。定义 dpi,jdp_{i,j}dpi,j 为长度分别是 i,ji,ji,j 两串的 LCS。若 ai=aja_i=a_jai =aj 则 dpi,j=dpi−1,j−1+1dp_{i,j}=dp_{i-1,j-1}+1dpi,j =dpi−1,j−1 +1。否则 dpi,j=max(dpi−1,j,dpi,j−1)dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})dpi,j =max(dpi−1,j ,dpi,j−1 )。那么代码易得。
代码（我是码风切换大佬 awa）：
诶那你就要问了，100100100 分咋弄啊。这你就问对人了，我会用最直白，最不绕弯子的方式告诉你，我不会（。至少目前不会，满分做法请参考题解 awa
P1507
诶这不是 01 背包板子吗。
哦不对，要维护体积和质量两个参数。
考虑让 dpj,kdp_{j,k}dpj,k 维护质量，体积分别为 j,kj,kj,k 情况下所能取到的最大价值。转移方程为 dpj,k=max(dpj,k,dpj−W[i],k−V[i]+v[i])dp_{j,k}=\max(dp_{j,k},dp_{j-W[i],k-V[i]}+v[i])dpj,k =max(dpj,k ,dpj−W[i],k−V[i] +v[i])。其中 W,V,vW,V,vW,V,v 分别为物品的质量，体积与卡路里。
代码：
P3379
学的是 Tarjan 求 LCA。板子就不多讲了。
（雷霆码风
B3694
离散板子，但我为啥没做。
P14920
啥意思啊，这都是黄吗。
诶不是咋只有 60 pts。哦 kkk 有 10910^9109
那咋办。
转化一下，变成求提升攻击力所需要的最小金币数，只要这个值小于 kkk 即可直接输出。转移方程变为 dpj=min(dpj,dpj−ai+ci)dp_j=\min(dp_j,dp_{j-a_i}+c_i)dpj =min(dpj ,dpj−ai +ci )。然后记得别见祖宗。
代码：
P3431
前情提要：本题视频 link 的一定提示下。
42PTS 做法：
显然简单 dp 一下即可，不多讲了，复杂度 O(n×m)\mathcal{O}(n \times m)O(n×m)。
60PTS 做法
不难发现我们原本的转移代码是：
dpi,j=max(dpi−1,j,dpi,j−1)+w[i]dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+w[i] dpi,j =max(dpi−1,j ,dpi,j−1 )+w[i]
由于数组存不下，我们不妨转换下。定义 dpidp_idpi 为起点到第 iii 个点的最大值。我们发现地图里有很多滚木，所以我们只需要存有人的点即可。不难发现，这个点只能从他“左上方位”的点更新。则方程变为：
若有 i≠j,xj≤xi,yj≤yxi≠j,x_j \le x_i,y_j \le y_xi=j,xj ≤xi ,yj ≤yx ，则
dpi=dpj+widp_i=dp_j+w_i dpi =dpj +wi
其中 jjj 为符合以上条件的权值最大的点。
那不行啊，还是很难维护，那咋办。
看看能不能降下来一维，可以把 xxx 升序排序，所有 yyy 在当 xxx 相等的情况下升序排列，这样就可以减掉 xxx 的那个维度，接下来只用维护 yyy 就可以了。
转移方程变为：
满足 j<i,yj≤yij<i,y_j \le y_ij<i,yj ≤yi ，则
dpi=dpj+wjdp_i=dp_j+w_j dpi =dpj +wj
一样的，jjj 为所有满足以上条件的 dpdpdp 数组的最大值下标。
复杂度相较以前有了很大改善，为 O(k2)\mathcal{O}(k^2)O(k2)。
正解
你知道的，这题是数据结构优化 DP。
看看用什么优化。
发现对于更新 dpidp_idpi ，dp1...i−1dp_{1...i-1}dp1...i−1 肯定都被更新过了。转化一下，我们需要一个数据结构来维护 111 到 i−1i-1i−1 最大的值，也就是维护 yyy。区间查询单点修改，显然 BIT 码量与常数最小，可以胜任。那么在原代码基础上加上 BIT 维护即可。记得离散化。
代码：
时间复杂度 O(klogk)\mathcal{O}(k \log k)O(klogk)。
这道题或许可以算是我独立做的，看视频发现这道题，之后开始打部分分。40pts40pts40pts 的代码做完之后有事走了。路上一直在想方法，想到了 60pts60pts60pts 的做法。吃饭的时候想到了 100pts100pts100pts 的做法。在做之前看了一部分的视频，但我没看懂你信吗（
这个题大概率是我收获最大的题了，学会了排序降纬这个 trick，第一个数据结构优化 DP，第一次独立思考出青 DP。
P3908
我不更你们 P 什么。
口胡的，先说结论。
对于一个正整数 kkk，令 1⊕2⊕3...⊕k1 \oplus 2 \oplus 3... \oplus k1⊕2⊕3...⊕k 的值为 f(k)f(k)f(k)，则有：
f(k)={k,k≡0(mod4)1,k≡1(mod4)k+1,k≡2(mod4)0,k≡3(mod4)f(k) = \begin{cases} k, & k \equiv 0 \pmod{4} \\ 1, & k \equiv 1 \pmod{4} \\ k+1, & k \equiv 2 \pmod{4} \\ 0, & k \equiv 3 \pmod{4} \end{cases} f(k)=⎩⎨⎧ k,1,k+1,0, k≡0(mod4)k≡1(mod4)k≡2(mod4)k≡3(mod4)
然后没了。
::::info[至于我是怎么想到的]
搓一个打表代码：
然后观察输出，发现每隔三个输出就会出现一个 000，那么不难想到与 444 有关。
具体证明还是看题解吧，我太区了不会证明。
::::
LEETCODE NO.80
这不是随便做吗。
哦不对要原地去重。
发现遍历之后之前的值都没用了，所以考虑把去完重后的数组扔到先前已经遍历过的空间中。所以思路很简单了。
显然，因为数组是升序的，所以重复元素必然相连。题目要求我们保留两个数，只需要判断新数组倒数第二个元素是否与当前元素相等即可。如果相等则跳过，否则加入新数组。
ABC475 D
∣S∣≤7|S| \le 7∣S∣≤7
直接射！
解法 1
先筛出来所有质数，然后离散下原字符串。生成对于长度为 101010 包含字符 000 到 999 的排列，根据事先离散的数组取前 ∣S∣|S|∣S∣ 个数，转化为整数之后判断是否为质数，是的话直接输出。
解法 2
我怎么这都没想到，直接打表所有 PPP 就行了，我是啥比！！！
