c7w
文章13
标签12
分类0
2020-01 日记

2020-01 日记

【■■■ - 请输入密码继续访问 - ■■■】
密码保护文章测试

密码保护文章测试

【■■■ - 请输入密码继续访问 - ■■■】
数据的离散化

数据的离散化

数据的离散化处理

什么是离散化

离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。

通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:

  • 原数据:1,999,100000,15;处理后:1,3,4,2;

  • 原数据:{100,200},{20,50000},{1,400};处理后:{3,4},{2,6},{1,5};

例子:洛谷P1908,树状数组求逆序对时的应用

洛谷 P1908 求逆序对

洛谷 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$.

双纽线

r4VeSK.png

笛卡尔心形线

r4ZSht.png

其它曲线

r4ZeNn.png

r4Zu90.png

r4ZK3V.png

r4ZMcT.png

Reference

合同矩阵与相似矩阵

合同矩阵与相似矩阵

合同矩阵

定义

称两矩阵$A,B$合同,当且仅当存在可逆矩阵$C$,使得

性质

  1. 合同关系是等价关系.
  • 自反性: $A$与$A$本身合同
  • 对称性: $A$合同于$B$, 则$B$合同于$A$
  • 传递性: $A$合同于$B$, $B$合同于$C$, 则$A$合同于$C$.
  1. 合同矩阵的相同。

相似矩阵

定义

称两矩阵$A,B$相似,当且仅当存在可逆矩阵$C$,使得

性质

  1. 相似关系是等价关系.
  • 自反性: $A$与$A$本身相似
  • 对称性: $A$相似于$B$, 则$B$相似于$A$
  • 传递性: $A$相似于$B$, $B$相似于$C$, 则$A$相似于$C$.
  1. 相似矩阵具有一系列相同的特点.
  • 两者的秩相等;
  • 两者的行列式值相等;
  • 两者的迹相等;
  • 两者拥有同样的特征值,但相应的特征向量一般不同;
  • 两者拥有同样的特征多项式;
    (我们可以利用这些必要条件来判断两个矩阵是否相似)
  1. 相似矩阵具有相同的可逆性,当它们可逆时,则它们的逆矩阵也相似。
树状数组-入门

树状数组-入门

Basic Concept

树状数组可以用于高效计算数列的前缀和,区间和等等。

它可以支持在$O(logn)$的时间内得到任意前缀和,以及在$O(logn)$时间内支持对区间单点值的修改。空间复杂度为$O(n)$。

数组存储方式

rD8IfS.png

如图所示。

$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

这里我们可以引入lowbit函数。

int lowbit (int x)
{
    return x & (-x);
}

我们已经知道,对于整数表示,有

  • 正数的补码是其本身;

  • 负数的补码是在反码的基础上$+1$;

因此x & (-x)就可以满足我们对于查找最低位$1$的需求。

举个例子:

  • 二进制数 $11010$ (1)
  • 其反码为 $00101$ (2)

  • 加 $1$ 后为 $00110$ (3)

  • 将(1)(3)两者相与便得到最低位的 $1$ 所表示的数值

树状数组的建立

上面准备工作都做好了,码就行了:(

#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;
}

单点更新

再把这张图拿过来:

rD8IfS.png

如果我们要更改$A[3]$的值,那么我们知道,$C[3], C[4], C[8]$ 的值都会受到影响。

  • $3(011)$ => C[3] += temp;
  • $lowbit(3) = 001$, $3 + lowbit(3)= 100 = 4(100)$ => C[4] += temp;
  • $lowbit(4) = 100$, $4+lowbit(4)=1000=8(1000)$ => 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;
}

Reference

动态规划的背包问题

动态规划的背包问题

所以为什么要找一个背包图片当头图啊喂

0/1 背包问题

有$N$件物品和一个容量为$V$的背包。每种物品仅有一件,可以选择放或不放。第$i$件物品的费用是$w[i]$,价值是$c[i]$。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

设$f[i][v]$表示前$i$件物品(部分或全部)放入一个容量为$v$的背包可以获得的最大价值。则其状态转移方程便是:

0/1背包的空间优化

我们可以将二维数组存储优化为一维数组存储。

在每次主循环中,如果我们以$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]);

另一种解法:转化为0/1背包问题

考虑到第$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]$ 非负即可。

转化为0/1背包问题

将第$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怎么又炸了

Practice

附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】

Reference

Hash Table(散列表)

Hash Table(散列表)

  散列表的相关概念和内容  

散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。

​ 也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。

​ 这个映射函数称做散列函数,存放记录的数组称做散列表

基本概念

  • 关键字为$k$的值存储在$f(k)$的存储位置中,称映射$f$为散列函数,按照这个思想建立的表称为散列表
  • 对不同的关键字可能得到同一散列地址,即$k_1 \neq k_2$,而$f(k_1) = f(k_2)$,这种现象称为冲突(Collision)。具有相同函数值的关键字对该散列函数来说称做同义词
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

构造散列函数的方法

​ 若采用求余的方法,采用质数可以在一定程度上解决冲突问题。

处理冲突的方法

  • 开放定址法
  • 避免聚集:
    • 单独链表法
    • 再散列

Reference