KeBlog

有生之年。

233. Rubik's Rectangle

给定一个 \(H \times W\) 的网格，每个网格有个数字，每次操作可以翻转某行或某列，求一组合法操作使得该网格的数字排好序。

时间复杂度：\(O(HW(H+W))\) 。

初赛到了考场才真实地认识到一个新的赛季又开始了，不过我已经精神退役了，所以考的比较佛。

初赛

10.09 才知道初赛日期是 10.11 ，没啥感觉，10.11 就跟过去裸考了。

湖南大学好热闹，但是没人和我面基。

不过碰到个小哥哥（应该是湖南大学的学生）问我这么多人是干啥，了解了一波情况后给我说了加油。

考试的时候那个字符串的题目把我整懵了，猜了几个结论糊弄过去。

考后发现 nth_element 那题还错了一个，看懂是个 nth_element 后就没仔细看实现了，没注意到它的实现有缺陷。

update: 膜拜我校高一选手初赛 AK ！

本来装好 deepin.com.qq.im 后就可以愉快使用了，但是在某次滚动更新后突然发现 QQ/TIM 都中文乱码，困惑了很久都没找到解决方案。

在失败和重新尝试的断断续续的反复循环中，今天终于解决了。

其实就是下载 simsun.ttc 和 simsun.ttf 放到 .deepinwine/Deepin-QQ/drive_c/windows/Fonts 里头。

可能还要写个 zh.reg ，像下面这样，然而 deepin-wine 自带的 deepin-regedit 用不了，把 /usr/lib/deepin-wine/wine 拷贝到 /usr/lib/i386-linux-gnu/deepin-wine/wine 后似乎就好一点，但还是用不了，因此我并没有注册，但好像也还可以。

美食家

题目大意

给定一张 \(n\) 点 \(m\) 边的有向图，边有不超过 \(w\) 的长度。现要求从点 \(1\) 出发经过长度恰为 \(T\) 的路径回到点 \(1\) ，每到达一个点就会获得等于该点点权的愉悦值。特别地，有 \(k\) 个美食节，形如“于时刻 \(t\) 到达点 \(x\) 会额外获得 \(y\) 的愉悦值”。最大化获得的愉悦值总和。

做法 1

考虑 \(k = 0\) 的情况，也就是忽略美食节。

不难得到这样一个 DP ：设 \(f_{i,j}\) 表示在时刻 \(i\) 到达点 \(j\) 的最大愉悦值，转移枚举 \(j\) 的出边即可，复杂度 \(O(T(n+m))\) 。

做法 2

做法 1 的 DP 中转移与 \(i\) 无关，可以想到把 \(f_i\) 看做一个向量，用 max+ 矩阵描述转移，但是由于边有不等的长度，需要把连续 \(w\) 个时刻的状态合并为一个向量，这样一来就可以用 max+ 矩阵描述转移，使用矩阵快速幂，复杂度 \(O(m + (wn)^3 \log T)\) 。

做法 3 （正解）

现在考虑美食节，称有美食节的时刻为关键时刻，两个相邻的关键时刻之间是不受美食节影响的，可以套用矩阵快速幂的做法。那么就以关键时刻把时间轴分为 \(k+1\) 段，每段用矩阵快速幂，在关键时刻把美食节的影响加到状态上即可。这里矩阵快速幂不能每次暴力矩阵乘矩阵，需要预处理矩阵乘积的幂次，然后用向量乘矩阵的方式处理每一段。复杂度 \(O(m + (wn)^3 \log T + k (wn)^2 \log T)\) 。

想出一道不一般的积性函数前缀和的题，题没出出来，倒是发现不少有意思的东西。

一些定义

有些定义是我胡扯的。

对于积性函数 \(f\) ，称其特征函数 \(F\) 为 \(f\) 关于质数 \(p\) 的函数，准确来说 \(F\) 是 \(f\) 的特征函数当且仅当对于任意质数 \(p\) 有 \(F(p) = f(p)\) ，可以发现 \(F\) 并不是唯一的，但是我们只考虑最简单的那个，例如对于任意质数 \(p\) 有 \(f(p) = p + 1\) ，不妨令任意 \(x\) 有 \(F(x) = x + 1\) ，可以发现 \(F\) 并不一定是积性函数。

记积性函数 \(I_m(x) = x^m\) 。

对于数论函数 \(f\) ，其前缀和函数记为 \(S_f\) ，满足 \(S_f(n) = \sum_{i=1}^n f(i)\) 。

记 \(B(n) = \lfloor \sqrt{n} \rfloor\) ，\(n / i = \lfloor \frac{n}{i} \rfloor\) 。

就呆机房考试了一上午，写个屁游记啊。

边打 APIO 边写游记，这感觉很妙啊。

我已经菜到只能刷板题了 QwQ 。

愈发意识到，会和熟练是两码事，熟练与不熟练的差距真的很大。

直奔主题

直接举例子吧，考虑这样一个问题：给定一个长为 \(n\) 的数列，要选恰好 \(k\) 个不交的子段使得选择的子段总和最大。

朴素 DP

朴素 DP 是设 \(f_{i,j,0/1}\) 表示考虑前 \(i\) 个选择 \(j\) 段最后一个有没有选的最大收益，时间复杂度 \(O(n^2)\) ，必须有一维 \(j\) 处理“恰好”这个限制。

有没有更优秀的复杂度呢？

士别三日，当刮目相待。

跳过瞎扯，进入正题

备考期

省选一结束就被搞过去准备学考。学考结束后又开始停课。

不过是最后一次了，只有一个月，就要迎来 NOI 了。

Part1

07.14 - 07.16

主要是做了做 SNOI2020/ZJOI2020 的几道题，但没有什么具体的计划，效率很低。

Part2

07.17 - 07.22

cy 把我拉去谈话，说要我先花一两周整理复习知识点，要复习后做到以下两点：

• 具备做出每道题的可能（即考察的知识点都会）
• 只要能想到就能写出来

我觉得挺有道理，但一两周感觉太多了，占了整个备考计划近一半的时间，于是列出详细的计划表，在计划里开了六天时间。