什么是离散化？
离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；处理后：{3,4}，{2,6}，{1,5}；
例子：洛谷P1908，树状数组求逆序对时的应用
#include <iostream>
#include <cstdio>
using namespace std;
unsigned long long result = 0;
int a[500001] = {0};
int cache[500001] = {0};
void sort(int l, int r){
if (r <= l) return;
if(r-l==1){
if(a[l]>a[r]){
int temp = a[l];
a[l] = a[r];
a[r] = temp;
result++;
}
return;
}
int mid = (l + r) / 2;
//[l, mid] && [mid+1, r]
sort(l, mid);
sort(mid + 1, r);
int len = r - l + 1;
int x = l, y = mid + 1;
int pos = 0;
while(x<=mid && y<=r){
while (x <= mid && y <= r && a[x] <= a[y]) {
pos++;
cache[pos] = a[x];
x++;
}
if (x <= mid && y <= r && a[x] > a[y]){
pos++;
cache[pos] = a[y];
y++;
result += mid-x+1;
}
if(x>mid){
while(y<=r){
pos++;
cache[pos] = a[y];
y++;
}
break;
}
if(y>r){
while (x<=mid) {
pos++;
cache[pos] = a[x];
x++;
}
break;
}
}
for (int i = l; i <= r; i++){
a[i] = cache[i - l + 1];
}
}
int main(){
int n;
cin >> n;
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(1, n);
cout << result;
return 0;
}
#include <iostream>
#define MAXN 500001
using namespace std;
int n;
unsigned long long result = 0;
int a[MAXN] = {0};
int ft[MAXN + 1] = {0};
int lowbit(int x) {
return x & (-x);
}
void update(int index, int val) {
for (int i = index; i <= n; i = i + lowbit(i)) {
ft[i] += val;
}
}
int getSum(int index) {
int result = 0;
for (int k = index; k > 0; k -= lowbit(k)) {
result += ft[k];
}
return result;
}
class entry {
public:
int id, val, rank;
} m[500001];
// Last Update: 2020-12-30
/* Quick Sort With CMP Start */
// Sort the element between [a+left, a+right)
// You need to implement the "compare" function.
// You'd better implement a strict inequality in the set.
// An example is given in pseudocode.
/*
bool compare(T A, T B){
if(A precedes B){
return true;
}else{
return false;
}
}
*/
template <class T>
void quickSort(T* a, int left, int right, bool (*cmp)(T, T)) {
T pivot = *(a + right - 1);
int l = left, r = right - 1;
while (l < r) {
while (l < r && !cmp(pivot, a[l])) { // a[l] >= pivot then continue
l++;
}
while (l < r && !cmp(a[r], pivot)) { // a[r] <= pivot then continue
r--;
}
if (l != r) {
T temp = a[l];
a[l] = a[r];
a[r] = temp;
} else {
a[right - 1] = a[l];
a[l] = pivot;
quickSort(a, left, l, cmp);
quickSort(a, l + 1, right, cmp);
}
}
}
/* Quick Sort With CMP End */
bool compare1(entry a, entry b){
if (a.val < b.val) return true;
if (a.val > b.val) return false;
if (a.id < b.id) return true;
return false;
}
bool compare2(entry a, entry b){
if (a.id < b.id) return true;
return false;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
m[i].id = i;
m[i].val = a[i];
}
quickSort(m, 1, n + 1, compare1);
for (int i = 1; i <= n; i++){
m[i].rank = i;
}
quickSort(m, 1, n + 1, compare2);
for (int i = n; i >= 1; i--) {
update(m[i].rank, 1);
result = result + getSum(m[i].rank - 1);
}
cout << result;
return 0;
}
菜鸡没学过4-4，在微积分应用里面积面积和体积的时候有的草图画不出来…
图为$-4\pi \le t \le 4\pi, a=1$的图像.
周期为$2\pi$.
称两矩阵$A,B$合同，当且仅当存在可逆矩阵$C$，使得
称两矩阵$A,B$相似，当且仅当存在可逆矩阵$C$，使得
树状数组可以用于高效计算数列的前缀和，区间和等等。
它可以支持在$O(logn)$的时间内得到任意前缀和，以及在$O(logn)$时间内支持对区间单点值的修改。空间复杂度为$O(n)$。
如图所示。
$A[i]$代表原数组的元素，$C[i]$代表树状数组中的元素。
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
而其索引的二进制表示如下：
C[1] = C[0001] = A[1];
C[2] = C[0010] = A[1]+A[2];
C[3] = C[0011] = A[3];
C[4] = C[0100] = A[1]+A[2]+A[3]+A[4];
C[5] = C[0101] = A[5];
C[6] = C[0110] = A[5]+A[6];
C[7] = C[0111] = A[7];
C[8] = C[1000] = A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
我们可以找出规律，
也就是说，问题在于如何找出$i$的最低位$1$所代表的数值。
这里我们可以引入lowbit函数。
int lowbit (int x)
{
return x & (-x);
}
我们已经知道，对于整数表示，有
正数的补码是其本身；
负数的补码是在反码的基础上$+1$；
因此x & (-x)就可以满足我们对于查找最低位$1$的需求。
举个例子：
其反码为 $00101$ (2)
加 $1$ 后为 $00110$ (3)
上面准备工作都做好了，码就行了:(
#include <iostream>
#define MAXN 12
using namespace std;
int ft[MAXN+1] = {0};
int a[MAXN + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int lowbit(int x){
return x & (-x);
}
void generateTree(){
for (int i = 1; i <= MAXN; i++){
for (int k = i - lowbit(i) + 1; k <= i; k++)
ft[i] += a[k];
}
}
int main(){
generateTree();
return 0;
}
再把这张图拿过来：
如果我们要更改$A[3]$的值，那么我们知道，$C[3], C[4], C[8]$ 的值都会受到影响。
C[3] += temp;C[4] += temp;C[8] += temp;因此，我们只需要对所要更新的数据不断使其自增lowbit后，
使树状数组的对应索引增加 temp 值即可。
void update(int index, int val){
for (int i = index; i <= MAXN; i = i + lowbit(i)){
ft[i] += val;
}
}
假设现在我们要查询1~7的前缀和。
C[7] = C[0111] = A[7];
C[6] = C[0110] = A[5] + A[6];
C[4] = C[0100] = A[1] + A[2] + A[3] + A[4];
归纳可知，我们只需每次将索引减少i的lowbit，然后将对应的树状数组的值求和即可。
int getSum(int index){
int result = 0;
for (int k = index; k > 0; k-=lowbit(k)){
result += ft[k];
}
return result;
}
所以为什么要找一个背包图片当头图啊喂
有$N$件物品和一个容量为$V$的背包。每种物品仅有一件，可以选择放或不放。第$i$件物品的费用是$w[i]$，价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
设$f[i][v]$表示前$i$件物品(部分或全部)恰放入一个容量为$v$的背包可以获得的最大价值。则其状态转移方程便是：
我们可以将二维数组存储优化为一维数组存储。
在每次主循环中，如果我们以$v=V…0$的逆序推$f[v]$，这样就能保证推$f[v]$时$f[v-w[i]]$保存的是状态$f[i-1][v-w[i]]$的值。
伪代码如下：
for i = 1...N
for v = V...0
f[v] = max(f[v], f[v-w[i]]+c[i]);
其中$f[v]=max(f[v],f[v-w[i]]+c[i])$便与原转移方程等价。
有$N$种物品和一个容量为$V$的背包，每种物品都有无限件可用。第$i$种物品的费用是$w[i]$，价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
令$f[i][v]$表示前$i$种物品恰放入一个容量为$v$的背包的最大价值，于是可以按照每种物品不同的策略写出状态转移方程：
完全背包的特点恰是每种物品可选无限件，所以我们可以考虑“加选一件第$i$种物品”策略。因此我们可以使用可能已选入第i种物品的子结果$f[i][v-w[i]]$，于是我们必须采用$v=0…V$的顺序循环。
伪代码如下：
for i = 1...N
for v = 0...V
f[v] = max(f[v], f[v-w[i]]+c[i]);
考虑到第$i$种物品最多选$floor(\frac V {w[i]})$件，于是可以把第$i$种物品转化为$floor(\frac V {w[i]})$件费用及价值均不变的物品，然后求解这个0/1背包问题。
更高效的转化方法是：把第$i$种物品拆成费用为$2^kw[i]$、价值为$2^kc[i]$的若干件物品，其中$k$满足$2^kw[i]<V$。这是二进制的思想，因为不管最优策略选几件第$i$种物品，总可以表示成若干个$2^k$件物品的和。
有$N$种物品和一个容量为$V$的背包。第$i$种物品最多有$n[i]$件可用，每件费用是$w[i]$，价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本的方程只需将完全背包问题的方程略微一改即可，因为对于第$i$种物品有$n[i]+1$种策略：取$0$件，取$1$件……取$n[i]$件。令$f[i][v]$表示前$i$种物品恰放入一个容量为$v$的背包的最大价值，则：
循环时注意$v-k*w[i]$ 非负即可。
将第$i$种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为
且k是满足$n[i]-2^k+1>0$的最大整数。
例如，如果$n[i]$为$13$，就将这种物品分成系数分别为$1,2,4,6$的四件物品。
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价1和代价2，第$i$件物品所需的两种代价分别为$a[i]$和$b[i]$。两种代价可付出的最大值（两种背包容量）分别为$V$和$U$。物品的价值为$c[i]$。
费用加了一维，只需状态也加一维即可。设$f[i][v][u]$表示前$i$件物品付出两种代价分别恰为$v$和$u$时可获得的最大价值。状态转移方程就是：
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量$v$和$u$采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取$M$件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为$1$，可以付出的最大件数费用为$M$。
还有分组背包还有依赖背包但懒得写，源代码也有空再说8
诶mathjax怎么又炸了
附AC代码：
#include <iostream>
#include <cstdio>
using namespace std;
int v, n=0;
// i j k
int f[1001] = {0};
int max(int a, int b){
return a > b ? a : b;
}
void processTime(){
int a, b, c, d;
scanf("%d:%d %d:%d", &a, &b, &c, &d);
v = d - b + (c - a) * 60;
}
void tryItem(int cost, int value, bool inf){
if(inf){
for (int j = cost; j <= v; j++){
f[j] = max(f[j], f[j - cost]+value);
}
}else{
for (int j = v; j >= cost; j--){
f[j] = max(f[j], f[j - cost]+value);
}
}
}
void decompose(int cost, int value, int num){
int base = 1;
while(num>=base){
tryItem(cost * base, value * base, false);
num -= base;
base <<= 1;
}
if(num>0){
tryItem(cost * num, value * num, false);
}
}
int main(){
processTime();
int n;
cin >> n;
for (int i = 1; i <= n; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(c==0){
tryItem(a, b, true);
}else if(c==1){
tryItem(a, b, false);
}else{
decompose(a, b, c);
}
}
int result = 0;
for (int i = 1; i <= v; i++){
result = max(result, f[i]);
}
cout << result;
return 0;
}
如果会数学就好了
菜鸡不会打【P7108】，来补数学知识
给定一个正整数$m$，如果两个整数$a$和$b$满足$a-b$能够被$m$整除，即$(a-b)/m$得到一个整数，那么就称整数$a$与$b$对模$m$同余，记作。
对模$m$同余是整数的一个等价关系。
如果$p$是一个质数，而整数$a$不是$p$的倍数，则有。
因此，在计算$\frac{b^h-1}{b-1}$时，我们可以将其转化成$(b^h-1)*inverse(b-1)$计算。
long long invEl(int x)
{
return qpow(x, M - 2, M);
}
【黑人问号脸.jpeg】
散列表的相关概念和内容
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。
也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
这个映射函数称做散列函数，存放记录的数组称做散列表。
若采用求余的方法，采用质数可以在一定程度上解决冲突问题。
