0. 前置知识

需要提前有字典树的知识

1. 双数组字典树介绍

双数组字典树英文名为DoubleArrayTrie，他的特点就是使用两个数组来表示一颗字典树，这里有比较有趣了，两个数组是怎么表达出字典树的呢？

2. 双数组介绍

顾名思义，有两个数组，一个是base，另一个是check。

首先介绍数组的下标，数组的下标代表字典树上节点的编号，一个下标对应一个节点。

其实base数组的作用是用来记录一个基础值，这个值可以是随机值，只要不产生冲突就可以了，所以这个值可以用随机数算法获取，当然这样效率不高，高效的做法应该是使用指针枚举技术，ok，现在你已经明白了，base数组是一个不产生冲突的随机数组。

最后，check数组，check数组与base数组相互照应，如果base[i]=check[j] 则说明j是i的儿子，而且i到j的边权恰好为j-base[i]，也可以写作j-check[j]好好理解这句话

从另一个方面而言，双数组字典树的base数组，应该是一个指针数组，他指向了一个长度为字符集大小的数组的首地址，而check数组是一种hash碰撞思路，由于base数组疯狂指向自己，导致产生了很多碰撞，但是由于字典树是一个稀疏图，导致儿子节点指针利用率低，所以base数组疯狂复用这段空间，最后必须要依赖check来解决冲突，

双数组字典树相比于传统字典树，仅仅只在内存方面于增删改查占有优势，但是唯一不好的地方就是删和改会导致base数组内存分裂，难以回收，删和改如果占大头，那么传统字典树的内存效率更高

由于搜索领域几乎不涉及到删和改，所以这个数据结构很nice，字符集多大，就节省了多少倍的空间

数据结构很棒，但是在现在这个内存不值钱的时代，这些指针的储存用hashmap直接无脑顶掉，空间占用也高不了多少，hashmap顶多浪费两倍空间

两倍的空间算不上啥，除非这是唯一的优化点，否则不会优化到这个数据结构上来

比赛链接

https://codeforces.com/contest/1555

1. A. PizzaForces

1.1. 题意

6元15个物品，8元20个物品，10元25个物品

现在需要买至少n个物品，问需要多少钱

1.2. 做法

首先看单价，发现他们都相同，然后就是尽量不要多买了。

如果n比15,20,25的最小公倍数的两倍还要大，则多出的这一部分，可以考虑直接购买6元的，剩下的小范围dp即可

核心思想： 大范围贪心，小范围dp

notes: 注意一定是至少两倍以上才能贪心

比赛链接

https://codeforces.com/contest/1551

1. A. Polycarp and Coins

1.1. 题意

给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差

1.2. 做法

对模3的余数进行分类讨论

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int step;
    cin >> step;
    while (step--) {
        int n;
        cin >> n;
        if (n % 3 == 0) {
            cout << n / 3 << " " << n / 3 << endl;
        } else if (n % 3 == 1) {
            cout << n / 3 + 1 << " " << n / 3 << endl;
        } else {
            cout << n / 3 << " " << n / 3 + 1 << endl;
        }
    }
}
 

比赛链接

VK Cup 2021 - Elimination (Engine)

1. A. Binary Decimal

1.1. 题意

给你一个十进制数，你要把它拆成多个只由0和1组成的十进制数之和，问最少拆几个。

1.2. 做法

答案就是十进制数每个位上的数中的最大值

1.3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();

    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int mx = 0;
        while (x) {
            mx = max(mx, x % 10);
            x /= 10;
        }
        cout << mx << endl;
    }
}

题目大意：

你需要计算有多少对满足长度为n的排列$p$和$q$，满足$p$字典序>$q$ 且 $inv(p)<inv(q)$，答案取模

$inv$ 为逆序对个数

做法：

设$f(i,j)$为长度为$i$、逆序对个数为$j$的排列的个数 , 考虑第一个数字为$t$

$f(i,j) = \sum_{t \in [1,i]} f(i-1,j-t+1)$

一个填$u$，另一个填$v$ $u<v$

$$
\begin{aligned}
ans[i] \&= i * ans[i-1] + \sum_{1<=u<v<=i, x+u>y+v} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>v-u, 1<=u<v<=i} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>d, 1<=d<i} (i-d)*f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x,y} f(i-1,x)\cdot f(i-1,y) \cdot \sum_{x-y>d, 1<=d<i} (i-d)
\end{aligned}
$$

分块

已知某函数$f(x)$对于$x\in[l,r]$，有$f(x)$关于$x$单调，且$f(x)$值域远小于$x$的定义域。

现在要你求$\sum_{x=1}^n g(x,f(x))$

那么我们就可以根据$f(x)$对$g$进行分块，在这一块中，始终有常数$y=f(x)$，然后对$h(x)=g(x,y)$统计$x$的前缀和。

最终我们就能很快的计算答案。

前言

关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？

前置知识

代数系统，群论

环

环是一个具有两个二元运算的代数系统。环$\lt R,+,\circ\gt$满足

• $\lt R,+\gt$构成交换群， 即$+$满足封闭性、结合律、单位元、逆元、交换律

• $\lt R,\circ\gt$构成半群， 即$\cdot$满足封闭性、结合律、单位元

• $\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$