「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

[Fortuna OJ]Aug 7th – Group A 解题报告

A – 小L的数列

这道题的式子跟 Codeforces 一道 F 题是一样的,让我误以为是 BSGS 之类的玩意,最后发现其实算是矩阵乘法的题。

考虑任意一个答案都是由\(\{f_n\}\)的幂的积组成的,由于\(k\)很小,所以我们可以考虑计算每一个\(f\)的指数,然后就可以用快速幂来计算这些东西。

继续阅读[Fortuna OJ]Aug 7th – Group A 解题报告

BZOJ2288:生日礼物题解

思路

其实这道题就是在求一个序列中最多\(M\)个(可相互重叠的)子序列的最大和。我们可以把序列中连续的正数和负数全部合并在一起:正数和正数合并,负数和负数合并。然后我把所有的正数全部加入答案之中,以他们的绝对值为关键字放入小根堆中,并且计个数,与此同时再创建双向链表结构。之后,我们可以以\(cnt>m\)作为循环条件,不停的取出队中的元素来进行处理。

继续阅读BZOJ2288:生日礼物题解

P1801:黑匣子题解

主要思路

我们可以考虑一个神仙结构:对顶堆。创建大根堆\(qmax\)和小根堆\(qmin\)。我们先用数组来储存这些数据。然后针对于某一次询问,我们要找整个序列前\(u(i)\)个数中第\(i\)小的的数字。每一次询问时,我们都把前\(u(i)\)个数放入大根堆中,如果大根堆中的元素数量等于\(i\)时,我们就把大根堆中最大的数(堆顶)放入小根堆中。最后,大根堆的元素个数为\(i-1\),然后我们要找的第\(i\)小的一定在小根堆的堆顶。

继续阅读P1801:黑匣子题解

POJ2442:Sequence 题解

思路与神奇操作

这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和,而次大和就是 \(n-1\)个序列的最大和一个头部值最小的序列的头部值 之和。所以,我们把视野缩小一些,讨论两个序列的合并。

继续阅读POJ2442:Sequence 题解