抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

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}
$$

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://www.jisuanke.com/contest/20871/challenges

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://www.jisuanke.com/contest/20844 B. So Easy1234567891011121314151617181920212223242526272...

分块

已知某函数$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$的前缀和。

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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 莫比乌斯反演狄利克雷卷积$$\begin{aligned}f(n)\circ g(n)=\sum_{d|n} f(d)\cdot g(\frac{n}{d})\end{aligned}$$...

前言

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

前置知识

代数系统,群论

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

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

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

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