现在是 2022 年 7 月 28 日的凌晨，我刚刚结束 CCPC Final 2021。打铁是毫无疑问的，Final 本来也就是去图一乐，但是这一场比赛对我的算法竞赛历程极为重要吧。
它标志了我四年算法竞赛生涯的结束。回忆着几个小时前的比赛，我记得我还在和队友讨论 SG 函数、meet-in-middle、线性基和高斯消元。「到底是怎么实现的呢？这个思路又是怎么形成的呢？」即使我几周前就决定了我在这个赛季结束之后就退役，但是在退役的最后一场比赛，明知道自己以后可能再也不会想这些东西，却还是一直在思考着。现在我一个人坐在床上打字，仔细想想才明白，原来我已经在算法竞赛中太久了，这样的思考已经成为了我每一天的习惯了。
Continue reading →给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：
简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。
\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)
Continue reading →思博题，没什么好讲的。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll n;
scanf("%lld", &n), printf("%lld %lld\n", -n + 1, n);
}
return 0;
}
Continue reading → 有意思。之前做过一题是用矩阵树+高斯消元插值求本题的一维情况，本打算用继续这么做，后面发现 Lagrange 插值能做到 \(\Theta(n^5)\)，就学了一点新的东西。
首先，要认识到本题矩阵树出来之后可以得到一个二元多项式：
\[ \sum_{i = 0}^{n – 1} \sum_{j = 0}^{n – 1} a_{i, j} x^i y^j \]
Continue reading →如果你手上有一堆散点，然后你可以用这个公式拟合出一个函数：
\[ f(x) = \sum_{i = 1}^n y_i \prod_{j \neq i}^n \frac{x – x_j}{x_i – x_j} \]
Continue reading →