nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
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顶多浪费两倍空间
两倍的空间算不上啥，除非这是唯一的优化点，否则不会优化到这个数据结构上来
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接https://codeforces.com/contest/1555
1. A. PizzaForces1.1. 题意6元15个物品，8元20个物品，10元25个物品
现在需要买至少n个物品，问需要多少钱
1.2. 做法首先看单价，发现他们都相同，然后就是尽量不要多买了。
如果n比15,20,25的最小公倍数的两倍还要大，则多出的这一部分，可以考虑直接购买6元的，剩下的小范围dp即可
核心思想： 大范围贪心，小范围dp
notes: 注意一定是至少两倍以上才能贪心
阅读全文
fightinggg
8月 01, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接https://codeforces.com/contest/1551
1. A. Polycarp and Coins1.1. 题意给你一个数n，你要把他拆为$c_1+2c_2$的形式，你需要最小化$c_1$和$c_2$的差
1.2. 做法对模3的余数进行分类讨论
1.3. 代码123456789101112131415161718192021222324#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; } }}
阅读全文
fightinggg
7月 24, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
比赛链接VK Cup 2021 - Elimination (Engine)
1. A. Binary Decimal1.1. 题意给你一个十进制数，你要把它拆成多个只由0和1组成的十进制数之和，问最少拆几个。
1.2. 做法答案就是十进制数每个位上的数中的最大值
1.3. 代码1234567891011121314151617181920#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; }}
阅读全文
fightinggg
7月 18, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
题目大意：你需要计算有多少对满足长度为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}$$
阅读全文
fightinggg
7月 16, 2021
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
分块已知某函数$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
前言关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？
前置知识代数系统，群论
环环是一个具有两个二元运算的代数系统。环$\lt R,+,\circ\gt$满足
$\lt R,+\gt$构成交换群， 即$+$满足封闭性、结合律、单位元、逆元、交换律
$\lt R,\circ\gt$构成半群， 即$\cdot$满足封闭性、结合律、单位元
$\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$
阅读全文