从零开始的 DP（不止）学习记录

_WRYYY_ · 2023-11-23 22:05:19 · 个人记录

为了补上我dp的短板（其实说真的dp约等于没学过，板都没有的那种），也为了以后复习dp不会再忘记dp怎么写，dp的各种思想是怎么来的，从零开始学习 dp ，并记录在此博客。

因为要补的东西也挺多的，就不多开文章了，直接在这里记录了。

当然也会记录日常生活

大概是首发于洛谷博客，可能会同步到博客园，以后搭了个人blog就会同步到个人blog。

因为我博客园的主题默认是暗色，所以有些图可能看不清，可以点开来看或者手动切换到亮色。

有一些题目加上了 <\text{trick}> 标签方便以后复习技巧找，使用 Ctrl+F 即可

洛谷blog指路

博客园指路

个人blog指路（暂无）

于 2023.11.23 22:00

今日写了 洛谷题单 - 动态规划的引入 思维导图里的题

虽然是基础题，但基础不牢，地动山摇，更何况我是真的有题不会（没错就是基础题不会）

纸币问题1：没什么好讲的我都写的出 要用一些不同面值的纸币凑出一个金额，每种纸币无数张，问最少用多少张可凑出。

如果要求最少使用张数，我们可以知道最后这个金额肯定是要从前面某个金额的最小使用张数+1而来，那么就可以从1枚举到最后金额，求出每个金额的最小使用张数一个个转移就是。

数字三角形：这是真的没什么好讲的了。

纸币问题2：不讲题面了

题目说了顺序不同也算一种方案，那么我们就可以从1转移到最后金额，当前金额方案数等于前面所有可以通过加上某个面值后等于当前金额的金额的方案数的和

纸币问题3：

现在顺序不同不能算贡献了，考虑外层枚举面额，内层枚举1到w的金额，dp_{i,j} ，表示算到第 i 个面额，金额 j 有多少个方案，因为面值个数是作数的，所以从当前面额扫到 w ，这样就可以看作是一个面额算了多次，因为 dp 数组只跟 i-1 ，即上一层有关系，所以可以滚掉 i 这一维，贴一下关键代码：

for (int i = 1; i <= n; i++)
        for (int j = val[i]; j <= w; j++)
            dp[j] =(dp[j]+ dp[j - val[i]])%MOD;

采药：每个物品有一个花费和一个贡献值，要求总花费小于 T 的情况下最大化贡献。

考虑每一个物品，设 dp_{i,j}，表示限制选前 i 个物品在总花费为 j 时的最大值，我们知道在同一区间内物品可提供价值是一样的，所以不用考虑最后花费为不到 T 的情况。接着就可以写出转移方程 dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-cost_i}+val_i) 表示在选前 i-1 个物品当前总花费 j 减去这个物品的花费后最大的贡献是多少，再加上当前物品的贡献，与自身取个 max 就可以得到自身的最大值，这里采用记搜的思路会更好理解一点

我们发现 dp_{i,j} 只和 i-1 有关，可以滚掉 i 这一维，其实做了这题后，我终于理解了为什么有些转移是从后向前有些是从前向后，重点在于滚掉一维后，按某种顺序会影响到后面求值，而不是像二维那样可以不用管，当然这只是其中之一，还有就是本身求值就是和当前物品前面的求值挂钩的要按特定顺序。而且滚掉一维实际上是有常数优化的，如果有时候时空复杂度都是没错的，就是因为没有滚掉一维被卡常数了，当然我觉得这样的情况发生的概率特别特别小，没有人会去卡这点常数罢。

于 2023.11.26 14:00

也是动态规划的引入

滑雪：雪啊，食雪啊

有些时候dp好写，有些时候记忆化好写，但这两个东西的本质是一样的，这题适合记忆化，考虑将高度从低到高排序，直接记忆化搜索即可。

最大食物链计数：这真的算dp吗？

最大子段和:

考虑直接 dp，这里直接给柿子 ans=\max(sum+x,x,ans) ，ans 初值为负无穷。

整数划分没找到。那么动态规划的引入就写完力。

于 2023.11.28 22:20

昨天出分了，本来以为自己垫底稳了，没想到还有【数据删除】帮我垫底，快乐多了

sakana 还有 WQ最大fAKer 在和 THOTH 商量 WC 的事情，我 CSP 考太烂了，只能自娱自乐了。

写了会 whk 作业，研究了一下 tuple，搞完已经没多少时间写 dp 了。

导弹拦截：还没写，自己只能想出来 n^2 的第一问和 n\log_2n 的第二问，看了题解，感觉第一问的优化有点神奇，我觉得这算个上位黄了。

于 2023.12.2 15:20

今天把片剪完了，累死我了，想要做出好东西来得要多学点。

有一说一，我妈不知道是什么原因开始对我 OI 像对我 whk 一样了，虽然我不太喜欢这样，我还是喜欢自己搞，但至少比之前有大进步了，估摸着还是班主任说的话有用，得亏班主任支持啊，对于初中班主任我就只能 流汗黄豆——差不多得了 的态度。

接着导弹拦截：

首先第一问 n^2 的方法是好想的 dp_i=\max\left \{1,max_{1\le j<i,h_i\le h_j}dp_j\right \} ， ans=\max_{1\le i\le n}{dp_i} 我觉得显然，第二问 n\log_2 n 的也是好想的，我们令可重集合 S 为当前所有已部署的拦截系统所能拦截的最高高度的可重集合，当遭受一个导弹攻击时，我们选择高于当前导弹的拦截最高高度最低的系统对他拦截，如果没有就新开一个系统，并加入 S ，显然，答案是 S 的大小，使用二分就可以在 n\log_2 n 时间内解决。

关键在于第一问的 n\log_2 n ，其实只要知道了结论就很简单，先给出结论：

记 f_i 表示「对于所有长度为 i 的单调不升子序列，它的最后一项的大小」的最大值。特别地，若不存在则 f_i=0 ，而且随 i 增大，f_i 单调不增。

证明有点绕，但是光看结论还是比较显然，感性理解一下就是了，证明链接。

然后就可以对 f 进行二分，找出满足最大的 1\le j\le maxlen 使 f_j\ge h_i 即可，接着对 maxlen 进行更新，答案即为 maxlen。

于 2023.12.5 19:00

今天听新闻听到关于明年的新闻了，想了想才发现时间过的好快啊，转眼就快要到明年了，只剩 26 天了。

今天继续写洛谷题单。

打鼹鼠：有一说一，我还一开始真不知道怎么下手，思考无果就去看了题解，发现自己是个若至，一看方程我就懂了，脑子还是没转过那个弯来。

我们将每个鼹鼠的出现时间排序，虽然说题目已经给我们排好序了，dp_i 表示到第 i 只鼹鼠最多能打几只鼹鼠，转移方程为 dp_i=\max_{1\le j<i}(dp_i,dp_j+1) ，条件是 time_j+|x_i-x_j|+|y_i-y_j|\le time_i 时间复杂度为 m^2 ，因为我们在当前鼹鼠的最大值肯定是从之前的鼹鼠转移过来的，所以如此设计转移方程。

琪露诺:这个我会，但是 n^2 ，范围 2e5 ，虽然但是，O2 艹过去了。数据有点氵。

直接给方程了，我发现这些题如果不写优化都一个套路。

于 2023.12.7 22:00

本来可以写两题的，写个英语作业写了好久，都是英语害得的

今天继续

大师：这我只会 n^2v ，还是菜了。看了题解，发现确实是自己菜。

自己的解释就放代码里：

for (int i = 1; i <= n;i++){
        for (int j = 1; j < i;j++){
            dp[i][h[i] - h[j] + v] += dp[j][h[i] - h[j] + v] + 1;
            //表示由第 j 项与它们二者之间的高度差转移而来
            dp[i][h[i] - h[j] + v] %= MOD;
            ans += dp[j][h[i] - h[j] + v]+1;
            //因为 dp 数组中存的是以 i 结尾的等差数列长度 - 1 
            //而当前的方案数应为等差数列的长度，所以 + 1
            ans %= MOD;
        }
    }

题解写的比我好多了，再放一份题解的：

"

以 i 结尾且上一个数是 j 的公差为 k 的等差数列数量是以 j 结尾公差为 k 的等差数列数加一

转移的过程中直接计数，顺便把数字数为一的区间加上

注意第二维数组开二倍将负数右移即可

这样只需要 n^2 的转移就可以了

"

于 2023.12.9

md，写了一上午WC2018结果看不懂样例，导致暴力寄掉，最ex的是我手%的和我程序算的一样，换了种理解方式再算一遍发现和样例不一样，难受，艹。

火大，继续。

快速求和：

luogu月赛，启动！

小丑了，对着 1A 大眼瞪小眼瞪了一下午，最后烦躁的要死没写一道题，乐

于 2023.12.12 22:00

今天出了省队名额，JX 6个名额

md，这下多切一题都没队进了。

THOTH 找了 Sakana 和 WQ最大fAKer 谈话，叫他们不要太功利，我不一样，菜到没办法功利。

写了一会网络流，没有给初始流量赋初值卡了20分钟，md。

快速求和：昨天就写完了，忘记写了，有一说一，我觉得这数据是有点氵的，题解那种限制数字位数到11的做法实在是不可取，于是我进行了一下修改，而且打算出一个 HACK ，当然也有咕咕咕的可能性。（如果看到我还没有去hack就踢下我） HACK 完成于 2023.12.14

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    ll n, len;
    cin >> s >> n;
    len = s.size();
    for (int i = 0; i < s.size(); i++)
    {
        a[i + 1] = s[i] - '0';
    }
    for (ll i = 1; i <= len; i++)
    {
        num[i][i] = a[i];
        for (ll j = i + 1; j - i <= len - 1 && j <= len; j++)
        {
            if ((num[i][j - 1] * 10 + a[j] <= n))
                num[i][j] = num[i][j - 1] * 10 + a[j];
            else
                num[i][j] = INT_MAX;
        }
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0][0] = 0;
    for (ll i = 1; i <= len; i++)
        for (ll k = 1; k <= len - 1; k++)
            if (i >= k)
                for (ll j = num[i - k + 1][i]; j <= n; j++)
                    dp[i][j] = min(dp[i][j], dp[i - k][j - num[i - k + 1][i]] + 1);
    if (dp[len][n] > len)
        cout << -1;
    else
        cout << dp[len][n] - 1;
    return 0;
}

石子合并（弱化版）： 漏了合并后贡献卡了一会，10 分钟氵了。

最长上升子序列（LIS）: 2 分钟氵了。

于 2023.12.14

【数据删除】 去【数据删除】了，周六才能回。不知道【数据删除】的人怎么看待【数据删除】的人。

今天大概就可以结束这个题单了，明两天换题单写

子串：写完了，没时间来写记录了，过几天来补。

于 2023.12.16

写区间dp咯。

回文字串：这是区间dp吗？

考虑求出最长回文子串，然后用原串长度减去最长回文子串长度就是最后的答案，求最长回文子串可以将原串翻转，然后用翻转串和原串做最长公共子序列就可以求出了。

考虑感性证明，我们求出了最长回文子串，那么我们有两种情况，一是该子串长度为奇，那么就以这个字符为回文串的中点，只要是回文子串里的字符都会对称分布，如果回文子串中两个字符在原串是隔开的，那么就可以把隔开他们的字符加到回文子串对应的另外两个字符间，这样我们就可以保证他们在原串是回文的，而且被加过去的字符也刚好回文了；如果长度是偶，那就在直接按照定过中点后的方法做。

Zuma:脑子转过弯来就是板题了。

考虑给基础的转移加上一个语句，我们知道如果 a_l=a_r，那么会有：

因为若 a_l=a_r，那就可以直接从夹在 l 和 r 的这个区间转移从而达到不需要额外贡献直接消除 l 和 r，但是还是要进行一层转移，因为通过下一层转移而来的值是完全有可能会更小的。

合唱队：居然是罕见的 n^2 区间 dp 口牙

设 dp_{i,j,k},k\in [1,0] 表示，在区间 [i,j] 上最后一次操作是从前 (0) 插入，还是从后（1）插入，那么显然我们就有 4 种转移可能，分别是

1. 从前插入

   1. 前一次操作是从前插入
   2. 前一次操作是从后插入

2. 从后插入

   1. 前一次操作是从前插入
   2. 前一次操作是从后插入

对应到转移方程就是：

if(a[i]<a[i+1])
    dp[i][r][0] += dp[i + 1][r][0];
if(a[i]<a[r])
    dp[i][r][0] += dp[i + 1][r][1];
if (a[r] > a[i])
    dp[i][r][1] += dp[i][r - 1][0];
if(a[r]>a[r-1])
    dp[i][r][1] += dp[i][r - 1][1];

初始状态为一个数从前插入的方案为 1，从后也行，但不能二者皆有。

最后答案即为 dp_{1,n,0} + dp_{1,n,1}。

环状最大两段子段和：还没做，这题绿低了罢，怎么着也得是蓝罢。

今天不写了，滚去写建模题了。

于 2023.12.19

双子序列最大和：下一题的前置，5分钟氵了。没必要放方程。

环状最大两段子段和：<\text{trick}>

是我菜了，sakana 教过就会乐，(TヘTo)

类似于反悔贪心的做法

基础和上一问一样，正着扫一遍，反着扫一遍，此时求出最大双子段和，然后对整个序列取反，再求一遍最大双子段和，用原序列的总和减去这次所求的，再和第一次求的最大双子段和取个 max 就求出答案来了。

取反后选择的两段

用 sum 减去后等同于

相当于在环形上求最大双子段和。

今天开始推树上与图上 dp 。

二叉苹果树：裸的树形背包。脑袋卡壳了花了点时间。放一下转移方程。

设 dp_{x,k} 表示在节点 x 保留 k 个树枝

则

注意倒着扫就是了。

跑路：这题其实没有说有什么 dp 罢，主要还是倍增，真要说 dp 难道是 floyd ？

一开始本来直接过了，结果因为初值赋太大导致 floyd 跑得时候越界了，这里要记住 memset(f,0x7f,sizeof f) 时，2f 会越界，memset(f,0x3f,sizeof f) 不会。

于 2023.12.21

今天只看日期是回文日awa。

明天考试，后天考试，笑死我了。

今天继续树图dp

绿豆蛙的归宿：拓扑板题，期望知识没过关，卡了一会，实际上很氵，直接 PASS。

采蘑菇：个人认为难度不高，就是这个抽象缩点重赋点权重建图图上拓扑序转移dp，看起来很难实际上不会，就是恶心。还没写完。先写思路。

显然先缩点，然后将每个强连通分量里的所有边权压成点权，然后重新建图，按着拓扑序直接转移就是了，感觉不如环状最大两段子段和。

于 2023.12.25

笑死，月考爆炸了，物理写太慢导致没写完，前面还把正确的改成错误的；数学也没写完，因为三角函数算错值导致图像画好久耽误了时间，前面有一个没注意cos的取值导致从选择全对变成扣5分；语文意外作文上了40,有点惊讶，但这次还是差 3 分及格；英语也就那样了；生物差1分及格，结果这次不赋分，小丑了；化学也就那样了，要不是那个方程没配出来，不然就上70了，居然比 WQ最大fAKer 高一分；总分成信息组最丢脸的了（除去【数据删除】）。生物【数据删除】那边改出来59，我们这边改出来64。XD

听 THOTH 说又要停课了，不知道怎么搞，whk这边说好看罢，在班上排挺后的，说不好看罢，在年级里又还算比较前的。

有点难办啊。

于 2023.12.26

一年又要过去力，不知不觉又到了一年的末尾呢，想我开始拥有使用竞赛机房的权利还是在今年年初，那个时候才真正成为了一个正式竞赛生吗？但也已经过了一年了，时间好快啊，明年我16岁生日一过就是省选了，不知道自己能不能给自己一个最好的生日礼物呢，大抵是有点困难的，毕竟真的打不过那些怪物啊，希望能让17岁时的我把16和17的礼物都拿到手。

续采蘑菇：拓扑序转移有点问题，起点可能不是 0 入度点，而且不太好搞掉其他 0 入度点的影响，所以改写最长路。

md，m 写成 n 调了1个小时。

火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了。

于 2023.12.28

CCF NOI 2024江西省队选拔赛报名通知

（2）省选正式参赛资格：
NOIP 2023成绩高于150分（含）；
或
NOIP2023女生赛江西省获奖选手。

这下我开心了，直接去不了省选了，直接线上全真 VP 。

火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了

很难受，写不动题了，虽然说还有一年，虽然比我强很多的学长都放下了，但是，但是，但是，唉。

md。年轻人复活甲叠的就是快，老子复活了，明年再战就明年再战，ctmd。

于 2023.12.29

我今天的烦躁程度远超我想象，看来还是有点难受，我现在就一个念想，那就是不正式参赛也要到省选赛场上比一比，就只有这个是我最希望的了，虽然能正式参赛就更好就是了。

明两天又是待在学校集训，说实话我真的因为这个事情动力减少了很多，但是没办法，就算是为了高二的省选做准备了。

高情商：

这是眼光长远地为高二省选做准备。

低情商：

就是菜。

接下来的计划就变更了，我可以开始准备更为长远的数学学习了，OI 上也可以开始放长线学习计划了，首先 dp 是不可以断的，因为本来就菜，后面看一下是先去搞各类数据结构还是先去搞图论，如果有余力的话还是要出出题，毕竟这也是提升实力的重要途径，也可以体验当毒瘤的感觉，还有搞点什么黑科技，不能总局限于已有的东西，虽然这个的优先级肯定是最低的了，毕竟我还是很菜，还有就是要搞 dark♂ 模拟，代码实现能力要拉上去。

就这样罢，明天开始进状压 dp 了，后面就是各种 dp 优化。

于 2023.12.30

今日状压 dp

依旧是按着题单走

互不侵犯：

很容易可以想到状压，每个位置选与不选可以让每行组成一个二进制数，一下就想到了。

一开始我设的状态有四维 dp_{i,j,k,c} 表示第 i 行第 j 列已经选了 k 个并且当前行的选择情况为 c，然后发现状态重合了，因为 c 的大小已经可以表示是在第几列了，所以就改成三维 dp_{i,j,k} 表示第 i 行，选择情况为 j，已经选了 k 个。

然后就可以想到转移方程为

上式中 c 表示总选择状态，num_j 表示选择情况为 j 时有多少个被选了，若 num_j=-1 则该选择情况不合法。

上式可以执行当且仅当 num[z] == -1 || (z & j) || (z & (j << 1)) || ((z << 1) & j) 该式为假时可以执行。

边界条件为 dp_{1,i,num_i}=1 其中 i 为所有满足条件的选择情况。

循环时注意边界即可。

啊啊啊不想写dp乐，我已经很长时间没有接触过 dp 以外的题乐，开始营养不良乐。

于 2024.1.2

新年快乐！（虽然迟到了

啊，已经是 2024 了啊，虽然农历还没到，时间过的好快啊。

不多讲了，继续 dp。

今天还是在状压 dp。

关灯问题II：

原题的操作有点绕弯子，这里直接翻译成人话。

有 m 个按键，n 个灯。每个按键按下后会对这 n 个灯进行调整。按下 i 按键对于第 j 盏灯，是下面 3 中效果之一：若 a_{i,j}=1 则将该灯调整为关；若 a_{i,j}=-1 则将该灯调整为开；若 a_{i,j}=0 则不调整。初始所有灯都是开的，求最少按多少次按键可以关掉所有灯，若无论怎样都无法关闭所有灯，则输出 -1 。

事实证明乱搞可以过。

首先考虑压缩状态，灯的状态就不需要说了，正常压缩，接下来考虑按钮带来的影响的状态

我们考虑压两个数字，第一个数字代表所有的 a_{i,j}=1，第二个数字代表所有的 a_{i,j}=-1，我们令 val_1=2^n-1,val_2=0，对于每一位若 a_{i,j}=1 则 val_1 的该位变为 0，若 a_{i,j}=-1 则 val_2 的该位变成 1 这样转移的时候就可以从状态 i 转移到状态 i\&val_1|val_2 这样就做到了 O(1) 的转移，然后考虑所有按键都按 T 遍能不能转移到 0 ，时间复杂度 O(T2^nm) 我取的 T=100 因为考虑到他有 100 个按键所以跑 100 应该就可以得出最终解，虽然我觉得这样可能不太正确，但或许没办法卡掉（至少我不会。

while (T--)
{
    for (int i = anx; i >= 0; i--)
    {
        if (dp[i] != inf)
            for (int j = 1; j <= m; j++)
            {
                to = i & cg[j][0] | cg[j][1];
                dp[to] = min(dp[to], dp[i] + 1);
            }
    }
}

事实证明因为数据过氵 T=2 就可以直接过所有数据，T=1 过不了 hack。

这里我想到了实际上的证明方法，也就是说不会被卡掉，而且可以优化复杂度。令 T=m，那么复杂度就变成了 O(2^nm^2)，是十分优秀的复杂度，他的范围再大点都没关系。

考虑将问题转化为图上问题，从每个状态开始，看从这个状态按下每个按键可以转移到哪个状态，然后连一条有向边，最后跑一遍最短路就行乐，我这样子写就类似于跑 floyd，是吗？是的罢后面看一下找个时间 hack 了。

为什么我从开始写状压 dp 后写的就越来越长了啊。

A Simple Task：不会写，不知道这种东西怎么转移的，看了题解懂了，想起了 CSPRO 的闪耀巡航。

写完了，过几天补一下笔记。

破 500 行庆祝！

于 2024.1.4

今天你校英语节，被二五仔背刺了。

接 A Simple Task：

状态压缩方式就不多说，选与不选的压。

类似于 floyd 的，令当前状态为 t 则起点为 lowbit(t)，一步步中转最后看能否走到起点即 lowbit(t) 若能，则加入答案中，若目前不是起点，则转移贡献到当前点。

宝藏：

md帮人调费用流调红温了。

后面补，还不会写。

于 2024.1.5

今天 WQ 最大 fAKer 和 sAKana 去外培了，我太菜了，打不了省选，伤心。

于 2024.1.6

宝藏：

写完了，还是看了题解，这东西的压缩方式我还以为会很复杂，因为觉得存在树异构的情况，只压已选点无法知道树的结构，也就无法求出树的总代价。所以我一开始是往用一种方式来表达一个树的结构然后压缩，并在这个树上进行换根 dp 以求出该结构的最小代价进而求出全部树的最小总代价，但是复杂度实在有点高，没去写，而且没想到怎么优化。

看了题解就知道了实际上完全不用考虑异构的问题。

正常压缩。

设 dp_{s,h} 为点集为 s 时树最大高度为 h，令 \sout{G_s} 为 \sout s 可扩展出的所有集合的并，s_0 为 s 的非空真子集。

初始状态为 dp_{1<<i,0}=0,0\le i< n，其余均为极大值。

转移方程为：

其中 cost 计算方式如下：

令 \large g=\complement_s s_0 即使用位运算的 g=s \oplus s_o，w_i=\min dis_{i,j}，sum=\sum w_i 其中 i\in g,j\in s_0

则 cost=sum\cdot h

注意到我们的计算方式是对于点的集合而言的，也就是计算方式本身就没考虑树异构的情况。

现在解释为什么不用考虑树异构的问题。（当然是有一点感性理解在里面的

首先我们规定了高度是多少，那么相对而言树的结构是有一定的确定性的，如果对于 s_0，其加入的边不是全部与该子集的某一结构的最大深度点相连，那么从这个子集转移一定会更劣，最终想要的结构一定可以从另一个子集转移而来，并且所连边接在最大深度点上。

至于时间复杂度，由于我比较菜，不会证明，只知道是 O(3^nn^2)。

啊啊，今天的 dp 就到这里罢。有点想念数据结构和网络流了。

于 2024.1.7

下午三点就被抓来学校了，难受QAQ。

于 2024.1.9

BJWC2018 那题过段时间写，因为不会杨表之类的，也不太像是能用状压过的去的题，后面实力更强一点再去写，顺便可以写写题解。

一双木棋：<\text{trick}>

这道题压状态的方式好巧妙啊，这就是轮廓线 dp 吗？学到了学到了。

也学了一下 min-max 搜索，还不错，这是我第一个学会了的博弈相关算法。

先讲一下状态压缩，我们知道整个棋盘有足足 100 个格子，每个都压进去的话大小是可想而知的，不仅空间过不去，时间更不可能过去。然后注意到我们所下的棋所构成的图形一定是个连通块，每行棋子是连续的，且满足 num_i\le num_{i-1}，num_i 表示第 i 行的已下棋子数，也就是众多题解所说的“锯齿形”。

本来仔细写了状态为什么不会重叠的问题，但因为没有保存，然后使用 desmos 不当导致浏览器崩溃，所以没了，这里就简略写一下。当 \sum_i^nsum_i 为奇时，一定是先手下到的状态；为偶时一定时后手下到的状态，所以状态不会重叠。

最后写一下如何求解，实际上本题难点就在于如何进行状态压缩，懂了如何进行状态压缩就是裸的 min-max 搜索，根据计算，有效状态不多，可以使用 map 存下每个状态的值，然后视先手为最大化价值，后手为最小化价值，输出根节点即 0 状态的答案即可。

花园：

是我菜了，不会融汇贯通，先不谈矩阵加速，只谈暴力，这个不只是压缩状态然后直接进行转移，还要按像以前写的 dp 一样一步一步转移到 n。还没写，瞥了一眼题解，看后面自己想能不能想出来。

于 2024.1.16

emmmm 过了挺久的，虽然不是没写题，但没写 dp，在自己出题，有点耗时，毕竟是第一次出题，虽然出的是氵模拟。

在加上前几天状态不是很好，晚上还有点失眠，就没写多少，尽在那里氵了，THOTH 说我在迷茫，我到底是不是在迷茫呢？我说不清。

今天继续写 dp，看能不能把思维导图里的题写完。

还是花园：

呃呃还是菜的，不会写，还是看了题解。

写这题顺带复习了一下矩阵。

考虑将第 i 位的前面 m 位进行压缩。

令 dp_{i,j} 为第 i 位的前面 m 位 的状态为 j，\text{bitcount(i)} 表示 i 有多少位是 1。

转移方程如下：

条件为：

啊啊，不想写了，直接进构造矩阵。

对于任意状态 i 可以转移到状态 con 的，令 A_{con,j}=1，其余为 0。

正常矩阵快速幂。

显然单调队列优化，令 x 为单调队列队头元素，则转移方程化为：

完事

于 2024.1.27

The Bakery：

应该是经典线段树优化 dp 了罢。

状态设计不会难，令 dp_{i,k} 表示到第 i 位，已经分了 k 段，val_{i,j} 表示从 i 到 j 有多少个不同的数。

最最最朴素的是 O(n^3k)

外层 i,k，内层 j 和每一次求 val 都扫一遍 O(n)

乘起来 O(n^3k)

考虑将扫一遍内层 j 的过程与求 val 的过程合并，倒着扫，就可以依次求出 val，不需要再扫一遍。

优化为 O(n^2k)。

for (int i = 1; i <= n; i++)
{
    for (int j = 2; j <= k; j++)
    {
        vis.reset();
        vis[val[i]] = 1;
        cnt = 1;
        for (int z = i - 1; z > 0; z--)
        {
            dp[i][j] = max(dp[i][j], dp[z][j - 1] + cnt);
            cnt += (!vis[val[z]]);
            vis[val[z]] = 1;
        }
    }
}

显然还是过不去。

考虑再对其进行优化。

我们再换个角度思考，将原本在更里层的 k 和在更外层的 i 交换，即先求完 [1,n] 的分 k 段的值，再接着求 [1,n] 分 k+1 段的值，而不是先求完 i 的所有分 [1,k_{max}] 段值再转移到 i+1。

如果这样做我们就会发现所有的分 k-1 段的值都是已知的，我们只要考虑怎么求出 val 对其的影响。

可以发现 dp_{j,k-1}+val_{j+1,i} 本质上就是将已经求好的在区间 [1,i-1] 上的 dp 值，再拼接上一段，最后找到最大的从而转移到 dp_{i,k}。

首先求最大可以很容易想到线段树；然后所有分 k-1 段的值都是已知的，所以我们对每个 k 都基于 dp_{i,k-1} 建一颗线段树；因为是再拼接上一段 [j+1,i] 所以可以想到扫的时候可以把在 [j+1,i] 上出现的不同数值的贡献直接加到 dp_{j-1,k-1} 上，这样就符合转移的方程，所以线段树每个叶节点的值是 dp_{i-1,k-1}，但是如何确定数值的贡献呢。考虑令 fr_i 表示在 i 上的数值上一次出现的地方加一，我们可以在扫的时候直接将在 [fr_i,i] 上的 dp 值加一，这样就不会因为是同一个数字重复加入，也不会因为后面的 dp_{i,k} 因为转移的 j 大于当前的 i 而错误记入。

时间复杂度 O(nk\log_2n)

天天爱打卡：

来了，断送我省选的题目，现在的我已经会了当初不会的 52pts 做法，后面再继续搞，你是我的重点对象

于 2024.1.29

天天爱打卡：

md，52pts 做法挂成 44 分做法了，我这个好像是 O(m^2) 的。

于 2024.1.30

今天第一次打 USACO，ak 铜组，可惜没时间写银组了。

天天爱打卡：

OHHHHHHHHHHHHHHHHHHHHH！

写出来力！！！！！

第一次自己写出线段树优化 dp，而且实际上写法基本和所有题解都不一样。

甚至我认为的大常数代码都不需要卡常。

虽然调的很难受，但总算是解决了这个重点对象。

有点晚了，过几天再补。

于 2024.1.31

今天打了云斗，还是自己菜了，只会一两题，不过可喜的是我能把暴力 dp 写出来乐，大抵是有钱拿的。

补一下天天爱打卡。

考虑最基础的 O(nmk) 的做法。

设 dp_i 表示第 i 天不跑所得的最大能量是多少。

转移方程为：

其中 sum_{j,i} 表示从第 j 天到第 i 天有效的挑战所提供的贡献和。

代码如下：

for (ll i = 1; i <= n+1; i++)
{
    sum = 0;
    for (ll j = i - 1; j >= max(i - k - 1, 0ll); j--)
    {
        for(auto px:val[j+1])
            if(i-1>=px.first)
                sum += px.second;
        dp[i] = max(dp[i], dp[j] - d * (i - j - 1) + sum);
    }
    ans = max(ans, dp[i]);
}

其中 val_i 存储的是在第 i 天开始的挑战的结束日期以及所能提供的能量值。

考虑优化。

我们发现有用的天数只有各个挑战的端点值，所以可以将各个挑战的左右端点离散化出来。

考虑离散化后的数组 ch_i，ch_i 中对于挑战的左端点 first 存储他的开始日期减一，second 存储他的终止日期，third 存储完成这个挑战可获得的能量值。而右端点，first 存储他的结束日期加一，second 不存储，但为了方便，我们存为极大值，third 也不存储，但为了方便，存为 0。接着对 ch 排序，那么我们就得到了离散化的数组。

其他地方小改一下就可以了，时间复杂度 O(m^2)，但是根据数据强度，上界会比较松，可以得到 44pts。

代码：

for (int i = 0; i < ch.size(); i++)
{
    x = ch[i].first;
    sum = 0;
    for (int j = i - 1; j >= 0 && x - ch[j].first - 1 <= k; j--)
    {
        x1 = ch[j].first;
        if (x == x1)
            continue;
        y = ch[j].second.first;
        w = ch[j].second.second;
        if (x > y)
            sum += w;
        dp[i] = max(dp[i], dp[j] + sum - (x - x1 - 1) * d);
    }
    if (i)
        dp[i] = max(dp[i], dp[i - 1]);
    ans = max(ans, dp[i]);
}

继续考虑优化，我们发现 (x - x1 - 1) * d 可以转化为随着 x 不断增加，在区间 [1,x_1] 上不断减去 (x-x_1)*d 其中 x_1 表示上一个 x。

面对这种区间问题，很显然可以用线段树优化。

这样我们就解决了不同天数导致要减去的能量不同的问题。

再根据我们存储挑战的方式，我们可以知道只有当前天数大于挑战结束日期，且转移天数小于挑战开始天数才能得到挑战的能量。但是我们用线段树维护 dp 值，加入贡献早了或晚了都会影响 dp 的转移。于是我们考虑将挑战加入优先队列当中，以结束天数为关键字按小根堆入队。当我们到了第 i 个离散化端点，对优先队列进行处理，如果堆顶的值小于当前离散化端点的天数，就把这个挑战的贡献加入到线段树的 [1,begin-1] 也就是 1 到该挑战的开始天数减一，因为我们要对线段树进行访问的区间是 [x-k-1,x]（未离散化时），所以即使加到了前面也不会影响求值，毕竟访问不到。

还有一个问题就是就是怎么确定离散化后的区间，这个好想，直接二分左边界，然后我们知道端点是会重复的，所以还要二分右边界，因为没二分右边界卡了好久。

代码。

这下终于搞完了，这道断送省选的题切掉力！

然后刚打完云斗比赛，30￥到手了，最后几分钟老吓人了，真的会有人在最后几分钟狂爬排名啊。

于 2024.2.2

任务安排：

一道斜率优化板题。

考虑暴力 dp（伪）。

已知 s 只会对后面的任务产生影响，我们就把 s 的贡献单独拉出来，为 s\times \sum_i^n c_i。

令 dp_i 表示完成到第 i 个任务，sumt 和 sumc 分别为时间和价值的前缀和。

然后就可以知道转移方程：

时间复杂度 O(n^2)。

后面懒得写了。

序列分割：

还是斜率优化板题，甚至比上面的还要板，不写。

找到了一个新的 OJ，加拿大的 DMOJ （大妈OJ），打了一下他的比赛，只能说没有油猴插件太难过日子了。

于 2024.2.2

小年了。

New Year and Original Order：<\text{trick}>

超级抽象数位 dp，没接触过类似的东西恐怕这辈子都想不出来，后面写。

于 2024.2.4

可能是因为快假期了，虽然有在做，但是懒得写了。

今天打了比赛，洛谷的那场有点火大，ARC 那场我只会 A，属实是菜了，一点不会写啊啊啊啊啊啊啊啊，难受。

PTA-Little Bird：

单调队列优化半板子题。挺氵，不写。

瑰丽华尔兹：

单调队列优化，懒，看着补。

于 2024.2.5

股票交易：

单调队列优化题，有一说一这题的状态也就那样，但是转移方程有点不好想，一开始推了个 O(n^2) 的转移，和外面两层遍历叠起来时间复杂度到了惊人的 O(n^4)，想都不用想肯定有锅（虽然正确性没锅），总不可能里一个单调队列优化一个 n，外一个单调队列优化一个 n 直接优化到 O(n^2) 罢。

然后去翻了题解，发现题解比我多一个 dp_{i,k}=\max (dp_{i,k},dp_{i-1,k}) 的转移，然后就发现这样就可以不用再去把前面的所有的 j\in[1,i) 扫一遍了，因为这个转移已经把前面的都归到 dp_{i-1,k} 上了。

这里就少一个 n。

然而我还是没想到怎么用单调队列去优化剩下的那一个 n。

又去翻了翻题解，发现自己没想出来是因为自己写的有点抽象，一点看不出来。

我自己写的转移是长这样的：

for (int j = 0; j <= min(as[i], k); j++)
    dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][k - j] - j * ap[i]);
for (int j = 0; j <= min(bs[i], maxP - k); j++)
    dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][k + j] + j * bp[i]);

把转移对象用一个柿子表达在 dp 里面，把转移产生的贡献直接搞上去。

而题解的转移大抵长这样：

for (int k = 0; k <= maxP; k++)
    for (int j = max(k - as[i], 0); j <= k; j++)
        dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][j] - (k-j) * ap[i]);
for (int k = maxP; k >= 0; k--)
    for (int j = min(k + bs[i], maxP); j >= k; j--)
        dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][j] + (j - k) * bp[i]);

直接把转移对象放里面，把转移产生贡献用一个表达式写出来后再搞上去。

而题解的转移是可以拆的，可以拆成：

其中 k\times ap_i 是常数可以直接提出来，所以只要维护 dp_{\max(i-W-1,0),j}+j\times ap_i 就可以了，而我们知道 j 的范围长这样 \max(k-as_i,0)\le j\le k，很可以联想到单调队列，只不过维护的是 j 而且维护单调队列的表达式是 dp_{pos,j}+j\times ap_i，而一般写的是直接维护 i，并且表达式只含有 dp_{i,j}，所以我会感到有点新奇，可能还是做的少了。

破千行庆祝！✿ヽ(　ﾟ▽ﾟ)ノ✿

于 2024.2.17

新年快乐！

其实昨天就被抓来学校乐，只是没有写。

[MtOI2018] 衣服？身外之物！：<\text{trick}>

观察数据范围，一眼状压。但是第一眼没看出来怎么压，想了想应该不是用二进制而是别的进制，但还是不会写。翻了翻题解发现有两种压的方式，第一种是压 7 位四进制的，另一种是压 4 位七进制的，我想到了第二种，但是不会写转移。然后发现实际上由 dp_{i-1,j} 推出来 dp_{i,j} 即使用类似 dp_{i,j}=dp_{i-1,j_1}+... 的不好想，很难想出怎么正常转移，而写成这种 dp_{i+1,j_1}=dp_{i,j}+... 形式的就还是很好想的 ，因为知道填哪个衣服就可以由状态 j 直接对应到一个确定的要转移的状态 j_1，但同样的情况下被转移的 j_1 不能对应一个确定的 j，虽然可以枚举，但终究没前者来的顺畅。

转移方程如下:

其中 nt 值为 nxt(j),+ct_k\times sp_k。

第三条的 k 位模式串的任一 border（周期） 长度，因为可能会有要填的前缀与前面填过的后缀重叠，所以可能直接填模式串进去不如填模式串的一部分来的更优，但是这样就要保证前面的一部分必须要填上模式串，所以要从 f_{i-len+k,1} 转移。

至于 f_{i,1} 的转移，则可以通过跳前缀函数的方法进行转移，这部分时间复杂度上限显然不超过 O(|t|)。

其转移为：

于 2024.4.9

今天月考。

语文作文实在是有点太抽象了。

于 2024.4.10

月考寄了。

于 2024.4.25

好久没写了，今天也没时间了，过几天补。

P9352 [JOI 2023 Final] Cat Exercise：

有意思的题。

于 2024.4.27

P9352 [JOI 2023 Final] Cat Exercise：

因为只有在猫猫所在的架子放障碍物猫猫才会离开这个架子，所以明显的是猫猫一旦进入某个节点 x 的任一子树，她就没办法进入 x 的其他子树了。

所以一个显而易见的方程是 dp_x=\max(dp_{pos_y}+dis_{x,y})。

其中 S 为可选集合，根据每条线段纵坐标改变。

我们发现这是个复杂度为 O(t\times c_{\max}) 的 dp，而 t\in[1,10^{18}]，显然不可以直接做。

但我们也发现了这个方程只和它的前一位有关，而且 c\in[0,15]，所以我们考虑一下矩乘优化。

我们把所有高度的 dp 值都放进一个向量里面，然后乘上不同的转移矩阵就 ok 了，转移矩阵也比较基础，不多赘述。

还是比较简单的。

于 2024.7.16

这几天还是在考试考试考试考试考试。

不同的是补完题后还是有事干了，在写 JOI 的题，比较难受的是我每次都看出来该怎么写了，但是每次都会写挂，烦内。

尤其是昨天开的一道 dp，我一看就知道这是线段树优化，然后直接开码，结果发现挂了。

然后我就改改改，然后突然发现一个很严重的问题，我想不到一个比较好的方式来满足题中的一个限制，然后就想想想，好不容易想到了，写出来又假了，迫不得已只能征求网络意见了。

最后终于写出来了。

蓝题 dp 爆写 3 个数据结构。

于 2024.7.23

也是又一周没写了，因为一直在考试考试补题补题，最近的考试变难了一些，从之前场均切两题到现在切一题算幸运。

今天也是正式紫题破百道了，并且第 100 道是正式的第一道 Ynoi，虽然之前写过一道 Ynoi，但是那时候我刚好在学欧拉函数，写了上帝与集合的正确用法，然后第二天%你赛就考了那道题，也是直接会做了。

嘛，因为我认为那道题的题解没有人解释的比较清楚，而且使用了不必要的后缀和，导致我看题解看了很久没看懂，最后还是我自己想出来了，所以我要记录一下。

P5309 [Ynoi2011] 初始化 ：

首先比较容易想到的是当 x\ge \sqrt{n} 时，此时修改的次数不会超过 O(\sqrt{n}) 可以直接暴力修改。

最主要的问题是当 x<\sqrt{n} 的情况。

考虑到因为这样的 x 不超过 \sqrt{n} 个，y\le x，而且对于一个确定的 x，它分出来的整块标记每段都相等，我们只需要知道散块的大小即可，所以我们又可以对每个询问用不同 x 进行分块进行求解，对于每个 x，把 y 处产生的贡献做前缀和，这样标记分块就可以做到打 tag O(\sqrt{n})，然后每个标记块的区间查询根据整块都相等，散块前缀和就能做到 O(1)，总共又有 O(\sqrt{n}) 个 x，总的单次查询就是 O(\sqrt n)，原序列分块也是根号的，总时间复杂度 O(n\sqrt{n})。

然后就是注意卡常，使用快速读入以及用 long long 存储答案，最后输出的时候再取模就不会 TLE。

于 2024.7.24

早上吃了感冒药导致困到接近九点，药效疑似有点大了。

不困了之后就开始写之前写的 JOI 的某题。

JOI 2024 Final 马拉松比赛 2：

一开始就是经典的 JOI 题必看错一次题面，我还说怎么这么简单，为什么有 dp 的 tag，明明直接爆码一个线段树就可以了。

结果发现是要把所有的球都拿上再去终点，而不是从起点到终点每个球都拿上就行了，卒。

遂重想，看了一下数据范围，感觉没什么可做的方法，因为每次询问都是改变的，询问的次数高达 5\times 10^5，这代表我们每次回答都要在 O(\log_2 n) 以下，感觉一点都不可做。

再想了想好像可以把拿球的状态压起来，求出在每个地点的最小花费，但点数一大，询问一多就没有前途了，遂罢。

想来想去写不出来，只能看题解了。

看题解发现这里又是有与圣诞树那题相近的转化，都是把状压转了区间，但是这题更抽象一点，因为圣诞树转化之后就可以直接过了，但这题的数据范围一眼不能支持区间，然后就是非常短时赛（CF&AT）的观察性质了，通过观察可知，当对位置去重后，若去重后的位置依旧超过了 10^3，那么就是全部无解，直接让区间变得可行起来，只能说确实是自己菜了。（你说的对，注意力涣散导致的）

首先我们会发现，离终点越远的点被先拿是更优的，正确性显然，因为你不会抱着一堆球减缓自己的速度再去捡最远的球再走相同的路跑回来，肯定是捡完最远的接着在原路返回的过程中再来捡更近的。

于是就可以把状压方程转为区间方程，因为有用的状态都可以被区间表示，令 f_{l,r,1/0} 表示拿完在区间 [1,l)\cup(r,n] 的球后在左区间或是在右区间的最快是多少秒，转移显然。

但是我们的方程还是会跟起点终点相关，所以还是要对每个询问重新 dp，时间复杂度 O(n^2Q) 太大了。

只能想办法让方程不更起点终点相关了，比较好的想法就是再设一个 g_{l,r,1/0} 但是起始与 f 不一样，这样就可以根据起点终点来调整我们答案的取值。

具体可以看题解，懒得写了。┌|*´∀｀|┘

于 2024.8.5

今天开始回学校坐牢。

上午依旧是考试，只会 T1，因为某个变量没赋初值爆扣 100，险些爆零，给我唐完了。

下午开始补题，最后补了两道，完成率达到 75\%，还差一题没写，今天不太在状态，看也没几个人写了，遂作罢。

想着要出点题，但是没灵感，加上我可能要求又比较高，所以想了很久也没想出到底要出什么样的题。

想着要找些灵感，又看了看旁边我买的高数，于是开看。

我当初买的原因主要是想学线性代数加上点微积分，当我拿到后翻几眼就知道我好像买错书了，反正以后也有用，所以留了下来。

八月份的计划也就那样，写题写题，考试考试，补题补题，想出题，学些新知，要把通过数拉到 850+，如果能有逆天效率的话我希望能到 900（这意味着我要在八月份写 100 多题，所以比较逆天）

就这样罢。

于 2024.8.6

今天。。。挺日常的。

上午考试考的还不错，主要是 T2 我做过（虽然当时也场切的所以就算没做过也做得出来就是了），后面看 T3 感觉会是个很抽象的做法所以直接写了可观的部分分，T4 乱搞。

下午就是自己写题了，照常写 JOI，现在我还是很不理解为什么那道题有人可以二分图匹配过，太不科学了。

明天是订正日，看一下把这几天的题都补了。

于 2024.8.12

今天是坠机日。

考场怒挂 200分，挂分率高达 86.95\%

无敌了。

今天四道题，T3 炒鸡柿子题。

来个军火展示：

前式：

后式：

今天还从【数据删除】那边得知了一个重要消息：

【数据删除】的人觉得【数据删除】的机房里全是婻酮。

WTF？

属实是被抽象到了。

于 2024.8.13

今天是起飞日。

因为 T2 又是做过所以场切两题，怒夺第 6。

没有拿更高分纯粹因为去做 T3 的煞笔数据结构了，调了我三分之二个下午以及一节晚自习才调出来，无语了。

明天补题日，我估计又要做一大堆蓝桥杯，实在不想做计数，上次布置的七题有五题计数，差不多得了。

一想到我这周还要写圆锥曲线就头大。

不至于罢。

于 2024.8.15

今天考了一场不是人考的%你赛。

炸了。

签到是你的谎言

弓长队薄纱T2

SG在T3游荡

数学在T4咆哮

丸辣！

今天复习一下AC自动机就不想做事了。

破防。

于 2024.8.16

签到依旧是你的谎言。

今天的题比昨天的好多了，要是签到真的是签到就更好了，最大的败笔就是在考场上做了一个半小时 T1。

T2 要是我把做 T1 的时间挪过来就做完了，T3 我只能说二分做法太帅辣！

T4 一开始我以为我的状压被卡了，我还说凭什么卡我状压，但：

for (int j = tcon ^ con;; j = (j - 1) & j)
{
    dp[i][j | con] = (dp[i][j | con] + dp[i - 1][j]) % MOD;
    if (!j)
        break;
}

子集枚举写错了。

丸辣！

于 2024.8.22

我要发表暴论正论：所有需要打 pushdown 的平衡树都不是真正的平衡树，是线段树邪恶入侵，强盗式领土扩张！

于 2024.8.23

今天是不知道什么日子，但明天是 0824。

今天考的不好，但【数据删除】考的比我还烂。

马上开学了，啊不我已经开学了艹。

八天暑假你值得拥有！

于 2024.8.28

前面的区域以后再来探索罢

md吓死我了草神外号及其来源一览。

于 2024.8.28

今天是正常场。

因为明天回家，所以从下午开始效率就不断降低，如果明天不考试的话我估计明天上午就直接清空了。

难得的双休。

说实话，我一直想建立一个我自己的博客，博客园这种技术型的有些东西不太方便往上面发，但是碍于种种原因，我估计直到我获得新电脑都无法做到了。

今天写题捞了 HACK 还没人理我，气。

昨天学了一下数位 dp，捣鼓了一下终于有点明白卡上下界是什么鬼了。

明天一过，这长达两个月的集训就结束了，两个月都把我的交换空间都占满了，睡觉只能是充电，周末也只能清理部分交换，内存和缓存，我需要一段时间减少与 OI 的接触，再热爱的东西，几乎天天接触超过 14 个小时每天长达两个月，也得稍微休息一会了，我需要消耗一段时间补充燃料，开学后上一段时间 whk，换换脑子，再接着停课学 OI，到时候重燃应该就更学得进去，效率也会更高。

两个月的集训给我带来了很多，实力应该是有一个比较大的上升罢，最主要的是校内人太少，没办法感知自己的提升，和外面开始联考也算是大致知道了自己的水平（虽然不太完全）。

今天也是完成了我八月集训开始时设定的目标，做题量到 850+，当然是只算 luogu 上的。

和上个月做的数量差不多，因为这会基本没学什么新东西。

前几天还得知因为【数据删除】比较社牛，所以我们这边的情况基本抖出来了，难绷，直接被迫让别人成功将我的网名和真名建立双射关系了，艹。

其实今天也就差不多是集训总结了，有日常的，规划的，总结的，这两个月也基本是当作日记来写这个记录，什么时候再写下一篇的做题记录还是未知数。

就酱罢！

于 2024.9.3

开学考。

坠机了，目前语文倒二，化学，生物倒数，物理数学又爆炸，英语更不用说了，两个月停完课回来完全变成 dinner 了。

寄。

今天晚上 VP 了一场 CF，秒A 然后卡B，卡C，不会D，无敌了。

C 题还是很有趣的，可能会写一下题解。

于 2024.9.26

其实这周刚开始就停课了。

现在处于半文化半竞赛状态，但是只上化学生物，并且有考试就不上，物理随机补课。

接着就是被联考遗忘了，连续两次都不在分组里，今天才加入，绷。

今天直接考破防了。

T1 直接被撞完了，下次再也不偷懒了。

T2 考场想到了 dp 方程，但是忘记斜率优化了，O(n^3k) 的方程让我如何相信你能过！

结果真能过，甚至跑得还挺快，破防。

唐。

于 2024.9.28

昨晚打了 CF，但是因为 11 点之前必须要回寝室，所以没打完，只写完了 ABD，写完的时候排名 496，今天早上一看居然还有 1214？

再让我继续写应该是可以维持在前 500 的。

今天晚上有 ABC，认真打一场，看我摆脱棕名。

下午打了 MX 的比赛，差一点 J 组 AK。

sbE题，棕名摆脱失败。

我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?我这差的四分E你哪里给我补啊?

悲惨记录。

于 2024.9.29

今天我发现了，我错过了人生中第一次 AK 的机会，一个简单的判断条件更改，就让我与 AK 失之交臂，要是我当初写了对拍，AK 就是唾手可得。

唉，无语了。

于 2024.10.10

月考爆炸。

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

要受到双重压力了。

回家就被父母 whk 压力。

自己又不想放弃竞赛。自己又给自己压力。

后者实际上还没什么，我总是能看得开的，不然我也不会坚持到现在。

主要是前者。压力我 whk 就算了，还要来影响我竞赛，真的受不了。

这方面我真的很感谢我的班主任，真的感谢他能一直支持我，不然我的压力会更大。

于 2024.10.16

火大。

上午直接随机区分题拼上一场集训队训练组合成了一场 CSP-S 模拟赛，点燃一天的火大。

估计是火神组的模拟赛才会让我这么大火。

不过还是有收获的。

<\text{trick}>

遇到选 x 挑不重合路径求最值可以选择使用费用流限源汇流量为 x 来获得一个还算快速的暴力。

于 2024.10.17

调题无限火大。真的无语死了。

打错变量名真的是唐完了。

今天把插头 dp 的模板写了，然后在 dd 被卡了，使用神奇打表大法成功通过。

我的压缩方式不太一样，直接使用最后一位来表示是否形成回路，理论上来讲应该要更快一点的，但是出了神奇问题没跑过去，可能是 STL 或者 pb_ds 的问题。

下午直接变量名打错怒调 2h。

于 2024.10.20

感觉这几天在智商正弦曲线的最低点，希望考试的时候可以振作起来，马上就要退役了啊啊啊。

于 2024.10.22

今天《想吃掉我的非人少女》动画化官宣了。

虽然一个月前就有消息了，但是官宣和亲眼看到 pv 还是很激动的。

毫不夸张的说，这件事直接扫空了我一周的压力，并且给了我一个勇往直前的 buff，刚听到的时候真的是兴奋到感觉我已经无人能挡了。

但是和 THOTH 商量外培携带设备失败，有点难受。

不过还有几天，我为了我的心理健康一定会胜利的。

于 2024.10.23

我真的想把那些闲的没事乱敲别人机房窗户的人的头拧下来。

然后今天一天没见到 THOTH，我不想疯掉啊啊啊。

明天最后一天？

于 2024.11.15

两天获得了三道题的最劣解，服了。