算法竞赛回忆录

现在是 2022 年 7 月 28 日的凌晨,我刚刚结束 CCPC Final 2021。打铁是毫无疑问的,Final 本来也就是去图一乐,但是这一场比赛对我的算法竞赛历程极为重要吧。

它标志了我四年算法竞赛生涯的结束。回忆着几个小时前的比赛,我记得我还在和队友讨论 SG 函数、meet-in-middle、线性基和高斯消元。「到底是怎么实现的呢?这个思路又是怎么形成的呢?」即使我几周前就决定了我在这个赛季结束之后就退役,但是在退役的最后一场比赛,明知道自己以后可能再也不会想这些东西,却还是一直在思考着。现在我一个人坐在床上打字,仔细想想才明白,原来我已经在算法竞赛中太久了,这样的思考已经成为了我每一天的习惯了。

继续阅读算法竞赛回忆录

「2021 CCPC 桂林」J – Suffix Automaton

简要题意

给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式:

  • 长度不同时,长度短的排在低次位。
  • 长度相同时,按字典序排序。

简单而言,长度是第一关键字,字典序是第二关键字。现在给定 \(Q\) 个询问,每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。

数据范围

\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)

继续阅读「2021 CCPC 桂林」J – Suffix Automaton

Codeforces Round #747 (Div. 2) – 解题报告

A – Consecutive Sum Riddle

思博题,没什么好讲的。

// 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;
}
继续阅读Codeforces Round #747 (Div. 2) – 解题报告

「GDOI2020模拟02.05」生成树 – 题解

主要思路

有意思。之前做过一题是用矩阵树+高斯消元插值求本题的一维情况,本打算用继续这么做,后面发现 Lagrange 插值能做到 \(\Theta(n^5)\),就学了一点新的东西。

首先,要认识到本题矩阵树出来之后可以得到一个二元多项式:

\[ \sum_{i = 0}^{n – 1} \sum_{j = 0}^{n – 1} a_{i, j} x^i y^j \]

继续阅读「GDOI2020模拟02.05」生成树 – 题解