基础算法学习笔记(C++)

简介: 基础算法学习笔记(C++)

筛法

素数又称质数:

指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

试除法判定质数

int is_prime(int x)
{
    if(x < 2) return 0;
    for(int i = 2; i <= x; i++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}

试除法分解质因数

void divide(int x)
{
    for(int i = 2; i < x / i; i++)
        if(x % i == 0)
        {
            int s = 0;
            while(x % i = 0) x /= i,s++;
            cout << i << ' ' << s << endl;
        }
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

埃式筛法

int primes[N], cnt; //primes[]存储所有素数
bool st[N];  //st[x]存储x是否被筛掉
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(st[i]) continue;
        primes[cnt++] = i;
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法

int primes[N], cnt; // primes[]存储所有素数 
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
          st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
#include<bits/stdc++.h>
#define pb push_back;
#define fi first
#define se second
#define pr printf
using namespace std;
typedef long long ll;
//对素数的理解
//实验时N=1e6
//素数的判断方法
//朴素筛法
//埃氏筛法极其终极版本
//欧拉筛法
inline bool isprime(int x)
{
    for(int i = 2; i <= x / i; ++i)
        if(x % i == 0) return 0;
    return 1;
}
int main(){
    //freopen("in.txt","r",stdin);
    int N; cin >> n;
    int count = 0;
    for(int i = 2; i < N; ++i)
    {
        if(isprime(i)) 
            count++;
            cout << count << "\n";
    }
    return 0;
}

埃式筛法


#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bitset<maxn> pri;
//4 = 2 * 2 
int main(){
    int N = 1e6, cnt = 0;
    double s = clock();
    
    for(int i = 2; i <= N; ++i)
    if(!pri[i])
            for(int j = i * i; j <= N; j += i) pri[j] = 1;
   for(int i = 2; i <= N; ++i) 
       if(!pri[i]) cnt++;
    double e = clock();
    printf("%d\ntime = %.01fms", cnt, e-s);
    return 0;
}

欧拉筛法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bitset<maxn> pri;//0为素数,1为合数(被晒除)
int primes[maxn],pp = 0;
//1 2 3 4 5 6 7 8 9 10
//primes
//让每一个素数只晒一次,欧拉筛选也叫线性筛
int main(){
    int N = 1e6, cnt = 0;
    double s = clock();
    
    for(int i = 2; i <= N; ++i){
    if(!pri[i]) primes[++ pp] = i; cnt++;
        for(int j = 1; primes[j] * i <= N; ++j){
            pri[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;//key
        }
    }
    double e = clock();
    printf("%d\ntime = %.01fms", cnt, e-s);
    return 0;
}

欧拉线性筛法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e8 + 10;
bitset<maxn> st;
int primes[maxn],pp = 0;
inline void ola(int x){
    for(int i = 2; i <= x; ++i){
        if(!st[i]) primes[++pp] = i;
        for(int j = 1; primes[j] * i <= x; ++j)
        {
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
    return;
}
int main(){
    int n, q; cin >> n >> q;
    ola(n);
    while(q--){
        int k; cin >> k;
        cout << primes[k] << endl;
    }
    return 0;
}

前缀和与差分

前缀和板子:

for(int i = 1; i <= n; ++i){
  cin >> a[i];
  pre[i] = pre[i] + a[i];
}

前缀积板子:

pre[0] = 1;//否则全部变成0了
for(int i = 1; i <= n; ++i){
    cin >> a[i];
    pre[i] = pre[i - 1] * a[i] % mod;
}
求[l, R]区间内前缀和
ans = pre[R] + inv(pre[l - 1]);

二维前缀和板子:

for(int i = 1; i <= n; ++i){
  for(int j = 1; j <= m; ++j){
  cin >> a[i][j];
    pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
    }
}
ans = pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];

一维前缀和代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kN = 1e5;
ll arr[kN],sum[kN];
int main(){
  int n; cin >> n;
    for(int i = 1; i <= n; i++){
    cin >> arr[i];
    }
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i - 1] + arr[i];
    }
    int m; cin >> m;
    while(m--){
        int l,r; cin >> l >> r;
        cout << sum[r] - sum[l - 1] << "\n";
    }
    return 0;
}

二维前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kN = 1e5;
ll arr[kN],sum[kN];
int main(){
  int n,m,q; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
          cin >> arr[i][j];   
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
      sum[i][j] = sum[i][j - 1] + sum [i - 1][j] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

优缺点

优点很显然,就是能快速求出区间或者矩阵的一些信息,例如和、积、疑惑等

缺点也很显然,就是不能在线操作 ,只能离线处理 ,遇到一个动态变化的就不能使用前缀和操作。

差分数组

差分数组的原理和特点

利用差分数组可以实现快速的区间修改,下面是将区间[l,r]都加上x的方法:

diff[l] += x;
diff[r + l] -= x;

在修改完成之后,需要做前缀和恢复为原数组,所以上面这段代码的含义是:

diff[i] += x表示将区间[l,n]都加上x,但是[r+1,n]我们并不想加x,所以再将[r+1,n]减去x即可。

但是注意,差分数组不能实现“边修改边查询(区间和)”,只能实现“多次修改完成后多次查询”。如果要实现“边修改边查询”需要使用树状数组、线性树等数据结构。

差分的实现

直接用循环O(n)实现即可,注意这里建议使得a[0] = 0,下标从1开始:

for(int i = 1; i <= n; i++)
    diff[i] = a[i] - a[i - 1];

将区间[l,r]都加上x:

diff[l] += x;
diff[r + l] -= x;

例题:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N], d[N];
void solve(int n, int m)
{
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
    
    while(n--){
        int l, r, v; cin >> l >> r >> v;
        d[i] += v, d[r + 1] -= v;
    }
    //复原前缀和
    for(int i = 1; i <= n; i++) a[i] = a[i + 1] + d[i];
    for(int i = 1; i <= n; i++) cout << a[i] << " \n";
}
int main()
{
    int n,m;
    while(cin >> n >> m) 
        solve(n,m);
    return 0;
}

枚举

枚举算法介绍

枚举算法 是一种基本的算法思想,它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来,并通过验证和比较 ,找到满足问题条件的最优解或者所有解。

枚举算法适用于问题规模较小、解空间可穷举 的情况。它的优点是简单直观,不需要复杂的数学推导,易于实现。但是,由于需要穷举可能的情况,对于问题规模较大的情况,枚举算法的时间复杂度可能会非常高,效率较低。

解空间的类型

解空间可以是一个范围内的所有数字 (或二元组、字符串等数据),或者满足某个条件的所有数字。

当然也可以是解空间树,一般可分为子集树和排列树,针对解空间树,需要使用回溯法进行枚举(搜索的知识点会讲到)

我们目前仅使用循环暴力枚举空间,具体的解空间类型需要根据题目来理解构造。

循环枚举解空间

  1. 首先确定解空间的维度,即问题中需要枚举的变量个数。
    例如当题目要求的是

例题:

小明对数位中含有2,0,1,9的数字很敏感(不包括前导0),在1到40中这样的数包含1,2,9,10至32,39,40,共28个,他们的和是574.

请问,在1到n中,所有这样的数的和是多少?

输入描述:

输入格式:
输入一行包含两个整数n(1<=n<=10^4^ )

输出描述:

输出一行,包含一个整数,表示满足条件的数的和。

代码如下:

#include<bits/stdc++.h>
using namespace std;
bool f(int x)
{
  while(x)
    {
        int y = x % 10;
        if(y == 2 || y == 0 || y == 1 || y == 9) 
            return true;
        x /= 10;
    }
    return false;
}
int main()
{
    int m; cin >> m;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
    if(f(i)) ans += i;
    }
    cout << ans << "\n";
    return 0;
}

高精度算法

思想

高精度算法本质上是用字符串模拟数字进行计算,再利用类似于数学里的竖式的形式,一位一位进行相关计算

处理

高精度计算中需要处理好以下几个问题:

(一)数据的接收方法存储方式

**数据的接收和存储:** 当输入的数很长时,可采用字符串方式输入,这样可输入位数很长的数,利用==字符串函数== 和操作运算,将每一位取出,存入数组中:
void init(int a[]){//传入数组
    string s; cin >> s;
    len = s.length();
    for(int i = 1; i <= len; i++)
        a[i] = s[len - i] - '0';//将字符串s转换为数组a,倒序存储
}

(二)进位、借位 的处理

//加法进位:c[i] = a[i] + b[i]
coed: if(c[i] >= 10){
        c[i] %= 10;
        ++c[i++];
}
//减法进位:c[i] = a[i] - b[i]
coed: if(a[i] < b[i]){
        --a[i+1];
        a[i] += 10;
}
//乘法进位:c[i + j - 1] = a[i]*b[j] + x + c[i + j - 1];
    x = c[i + j - 1]/10;
    c[i + j - 1]%10;

高精度加法

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    char a1[5005],b1[5005];//用字符存储数字
    int a[5005], b[5005], c[5005];//用c[i] 用来存储每位相加的结果
    int len_a, len_b, len_c = 1, x, i;
    
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    
    cin >> a1 >>b1;
    
    len_a = strlen(a1);
    len_b = strlen(b1);
    
    for(int i = 0; i < len_a; i++)
        a[len_a - i] = a1[i] - '0';
    for(int i = 0; i < len_b; i++)
        b[len_b - i] = b1[i] - '0';
    
    x = 0;//x进位
    while(len_c <= len_a || len_c <= len_b){
        c[len_c] = a[len_c] + b[len_c] + x;//两数相加,再加上前两个数进位的
         x = c[len_c] / 10; // 刷新进位
        c[len_c] %= 10; // 进位后剩下的
        len_c++; //位数加1
    }
    c[len_c] = x;
    if(c[len_c] == 0) { //判断首位是否为0
        len_c--; // 不输出此位
    }
 
    for(int i=len_c; i>=1; i--) {
        printf("%d", c[i]); //输出每一位的数
    }
 
    return 0;
}

高精度减法

#include <iostream>
#include <cstring>
 
int main() {
    int a[5005], b[5005], c[5005];
    int lena, lenb, lenc, i;
    char n[5005], n1[5005], n2[5005];
 
    std::memset(a, 0, sizeof(a));
    std::memset(b, 0, sizeof(b));
    std::memset(c, 0, sizeof(c));
 
    std::cin >> n1 >> n2; //输入被减数和减数
 
    lena = std::strlen(n1);
    lenb = std::strlen(n2);
 
    for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
    for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列
 
    i = 1;
    while(i <= lena || i <= lenb) {
        if(a[i] < b[i]) {
            c[i] = a[i] + 10 - b[i];
            a[i+1]--; //借位处理
        }
        else {
            c[i] = a[i] - b[i]; 
        }
        i++;
    }
 
    lenc = i;
    while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0,是需要输出的
        lenc--;   // 不输出首位0
    }
 
    for(i=lenc; i>=1; i--) std::cout << c[i];
 
    return 0;
}

高精度乘法

#include <iostream>
#include <cstring>
 
int main() {
  int a[105], b[105], c[10005];
  char n1[105], n2[105], lena, lenb, lenc, j, i, x;
 
  std::memset(a, 0, sizeof(a));
  std::memset(b, 0, sizeof(b));
  std::memset(c, 0, sizeof(c));
  
  std::cin >> n1 >> n2;
  
  lena = std::strlen(n1);
  lenb = std::strlen(n2);
  
  for(i=0; i<=lena-1; i++) a[lena - i] = n1[i] - 48; 
  for(i=0; i<=lenb-1; i++) b[lenb - i] = n2[i] - 48; // 倒序储存
  
  for(i=1; i<=lena; i++) {
    x = 0;
    for(j=1; j<=lenb; j++) {
      c[i + j - 1] = c[i + j - 1] + x + a[i] * b[j];
      x = c[i + j - 1] / 10; // 进位
      c[i + j - 1] %= 10; // 剩余
    }
    c[i + lenb] = x; // 进位的数
  }
  
  lenc = lena + lenb;
  while(c[lenc] == 0 && lenc > 1) {
    lenc--; // 删除前导0
  }
  
  for(i=lenc; i>=1; i--) {
    std::cout << c[i];
  }  // 输出每一位
     
    std::cout << std::endl;
  
  return 0;
}

高精度除法

高精度除以低精度

#include <iostream>
 
int main(){
    char n1[100];
    int a[100], c[100], lena, i, x = 0, lenc, b;
    
    std::memset(a, 0, sizeof(a));
    std::memset(c, 0, sizeof(c));
    
    std::cin >> n1 >> b;  
    lena = strlen(n1);
 
    for(i=1; i<=lena; i++) {
        a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
    }
 
//-------------------------初始化------------------------------
 
    for(i=1; i<=lena; i++) {
        c[i] = (a[i] + x * 10) / b;  // 算上上一位剩下的继续除
        x = (a[i] + 10 * x) % b; // 求余
    }
 
    lenc = 1;
    while(c[lenc] == 0 && lenc < lena) {
        lenc++;
    }
 
    for(i=lenc; i<lena; i++) std::cout << c[i];
 
    return 0;
}

高精度除以高精度

#include <cstdio>
#include <iostream>
#include <cstring>
 
using namespace std;
 
int a[50005], b[50005], c[50005], d;
 
void init(int a[]) {
  char s[50005];
  cin >> s;
  a[0] = strlen(s);   // 字符串存储,表示位数 
  for (int i=1; i<=a[0]; i++) {
    a[i] = s[a[0]-i] - 48;  // 正序储存
  }   
}
 
void print(int a[]) {     
  if (a[0] == 0) {
    cout << 0 << endl;
    return;  // 位数为0,输出0
  }
  for (int i=a[0]; i>=1; i--) {
    cout << a[i];  // 输出函数
  }
  cout << endl;
  return;
} 
 
int compare(int a[], int b[]) { 
  if (a[0] > b[0]) {
    return 1; // 被减数大于减数
  } 
  if (a[0] < b[0]) {
    return -1; // 被减数小于减数
  }
  for (int i=a[0]; i>=1; i--) { 
    if (a[i] > b[i]) {
      return 1;
    } 
    if (a[i] < b[i]) {
      return -1;
    }   // 位数相同,找到第一位不同的进行比较
  } 
  return 0;         
}
 
void numcpy(int p[], int q[], int det) {
  for (int i=1; i<=p[0]; i++) {
    q[i+det-1] = p[i]; //复制p数组到q数组从det开始的地方
  }
  q[0] = p[0] + det - 1;
}
 
void jian(int a[], int b[]) {   
  int flag = compare(a, b);    
  if (flag == 0)  {         
    a[0] = 0;
    return;
  }
  if (flag == 1) {        
    for (int i=1; i<=a[0]; i++) {
      if (a[i] < b[i]) {       
        a[i+1]--;     
        a[i] += 10;
      }
      a[i] -= b[i];
    }
    while (a[0]>0 && a[a[0]]==0) {
      a[0]--;         
    } 
    return; 
  }        
}  // 高精减法
 
void chugao(int a[], int b[], int c[]) {
  int tmp[50005];
  c[0] = a[0] - b[0] + 1;
  for (int i=c[0]; i>0; i--) {
    memset(tmp, 0, sizeof(tmp));  
    numcpy(b, tmp, i);// 清零
    while (compare(a, tmp) >= 0) {
      c[i]++;
      jian(a, tmp); // 用减法模拟    
    } 
  }
  while (c[0] > 0 && c[c[0]] == 0) {
    c[0]--;
  }
  return;
}
 
int main() {
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(c, 0, sizeof(c));
  
  init(a);
  init(b);
  chugao(a,b,c);
  print(c); 
  
  return 0;
}

二分

二分法的简介

二分法是一种高效的查找方法,它通过将问题的搜索范围一分为二 (两边具有明显的区别),迭代地缩小搜索范围,直到找到目标或确定目标不存在。

二分法适用于有序数据集合 ,并且每次迭代可以将搜索范围缩小一半

二分法的本质上也是枚举 ,但和暴力枚举不同,二分法利用数据结构的单调性 减少了很多不必要的枚举,从而极大提高了效率,一般可以将O(n)的枚举优化到O(logn)。

常见的二分类型有:

(一)整数二分

(二)浮点二分

(三)二分答案(最常见)

二分法简介- 解题步骤
  1. 研究并发现数据结构(或答案变量)的单调性
  2. 确定最大区间[1,r],确保分界点一定在里面,具体有一些细节:若以r作为答案,那么答案区间在[1+1,r],若以1作为答案,那么答案区间在[1,r-1]。
  3. 确定check函数 ,一般为传入mid(区间中某个下标),返回mid所属区域 或返回一个值,当check函数较简单时可以直接判断。
  4. 计算中点mid=(1+r)/2 ,用check判断该移动1或r指针 ,具体移动哪个需要根据单调性以及要求答案来判断。
  5. 返回1或r,根据题意判断

整数二分

整数二分就是在一个已有的有序数组 上,进行二分查找,一般为找出某个值的位置,或者是找出分界点。

这个数组肯定是开的下的,其数组大小一般在le6以内。

区域划分如下图:

整数二分模板

//找到升序数组a中的x第一次出现的位置
int l = 0, r = le9;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(l + 1 != r)
{
    int mid = (1 + r) / 2;
    
    //如果a为升序,说明mid偏大了,需要减小mid,就只能将r变小,即r=mid
    if(a[mid] >= x)  r = mid;
    else l = mid;
}
  cout << r << endl;

求大于等于所求值的最大值

int binary(){
    int l = 0,r =INF,mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid +1;
    }
    return l;
}

求小于等于所求值的最大值

int binary(){
    int l = 0,r =INF,mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid))  r = mid - 1;
        else l = mid;
    }
    return 1;
}

面对整数时的万能二分(近似万能)

int binary(int n){
    int l = 0,r =INF,mid,ans = 0;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

浮点二分

浮点二分不再是在有序数组上做二分查找,而是在某个实数范围内进行查找,因为实数域本身是单调的,所以也满足单调性,和整数二分的区别在于使用的变量类型、退出的判断条件不同。

浮点二分-模板

//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e - 6;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while(r - 1 >= eps)//eps是一个极小量,设置为1e-6较合适
{
    double mid = (1 + r) / 2;
    
    //f(x)单调递增,f(mid) >= 0,说明了mid偏大了,需要减小mid,就只能将r变小,即r = mid
    if(f(mid) >= 0) r = mid;
    else l = mid;
}
  //最后返回1,r差别不大
  cout << r << endl;

二分答案

常见模型:

二分框架(时间复杂度O(logm) + check函数(时间复杂度O(n)

一般情况下,我们会将答案进行二分,然后枚举在某个可能解后判断是否可以更优或者是否合法,从而不断逼近最优解

二分答案的题的特征:如果已知某个答案,很容易判断其是否合法或更优。某些贪心问题也可以转化成二分答案问题。

二分答案-模板

bool check(int mid)
{
    bool res = ture;
    //do something to check suthority of mid...
    return res;
}
int main()
{
    int l = 0,r = 1e9;
    while(l + 1 != r)
    {
        int mid = (1 + 2) / 2;
        //具体写法需要根据题意修改
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l << endl;
    //具体输出的内容需要根据题意判断
}

递归

递归的介绍

概念 :递归是指函数直接或间接调用自身的过程

解释递归的两个关键要素:

基本情况(递归终止条件):递归函数中的一个条件,当满足该条件时,递归终止,避免无限递归。可以理解为直接解决极小规模问题的方法。

递归表达式(递归调用):递归函数中的语句,用于解决规模更小的子问题,再将子问题的答案合并成为当前问题的答案。

递归如何实现

递归函数的基本结构如下:

返回类型 函数名(参数列表){
    //基本情况(递归终止条件)
    if(满足终止条件){
  //返回终止条件下的结果
    }
    //递归表达式(递归调用)
    else{
        //将问题分解为规模更小的子问题
        //使用递归调用解决子问题
        //返回子问题的结果
    }
}

实现过程:

  1. 将大问题分解为规模更小的子问题
  2. 使用递归调用解决每个子问题
  3. 通过递归终止条件来结束递归

设计时需要注意的细节:

  1. 确保递归一定能到递归出口,避免无限递归,这可能导致TLE(超时)、MLE(超内存)、RE(运行错误)。
  2. 考虑边界条件,有时候递归出口不止一个
  3. 避免不必要的重复计算,尽可能优化递归函数的性能(例如使用记忆化)

递归和循环的比较

递归的特点:

  1. 直观、简洁、易于理解和实现
  2. 适用于问题的规模可以通过递归调用不断减小的情况
  3. 可以处理复杂的数据结构和算法,如数和图的遍历
  4. 存在栈溢出风险(栈空间一般只有8MB,所以递归层数不宜过深,一般不超过1e6蹭

循环的特点:

  1. 直接控制流程,效率较高
  2. 适用于问题的规模没有明显的缩减,或者需要特定的迭代次数
  3. 适合处理大部分的动态规划问题

在部分情况下,递归和循环可以相互转化

例题讲解

斐波那契数列

已知F(1) = F(2) = 1; n > 3时,F(n) = F(n-1) + F(n-2)

输入n,求F(n), n <= 100000, 结果对1e9 + 7取模。

题解如下:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const ll p = 1e9 +7;
ll do[N];
ll fib(int n)
{
    if(do[n]) return do[n];
    if(n <= 2) return 1;
    return(fib(n-1) + fib(n-2)) % p;
}
int main(){
    int n; cin >> n;
    for(int i = 1; i < n; i++)
    cout << fib(n) << '\n';
    return 0;
}

时空复杂度

时间复杂度

尽可能让我们的程序运算规模控制在1额以内

空间复杂度

一般不会卡空间,会卡时间

离散化

离散化的简介

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

离散化 是一种将数组的值

离散化数组要求内部是有序(一般是去重的,当然也存在不去重的方法,但是比较少见)的,中可以直接通过离散化下标得到值,当然也可以通过值得到离散化下标(通过二分实现)。

下面是一个离散化的例子:

a(原数组)

不适用 3 1000 2 99999 2

L(离散化数组)

2 3 1000 99999

index(下标)

0 1 2 3 4 5


相关文章
|
3天前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
1天前
|
存储 算法 C++
【数据结构与算法】:带你手搓顺序表(C/C++篇)
【数据结构与算法】:带你手搓顺序表(C/C++篇)
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
编译器 C++
C++学习笔记(二开始学习C++)
C++学习笔记(二开始学习C++)
|
9天前
|
存储 算法 Cloud Native
C++ bcrypt算法 字符串加密,亲测有效
C++ bcrypt算法 字符串加密,亲测有效
|
16天前
|
缓存 负载均衡 算法
C++如何实现一致性算法
一致性哈希是一种用于分布式系统的负载均衡算法,旨在减少服务器增减导致的数据迁移。当有N台服务器时,通过哈希环将请求均匀分布到每台服务器,每台处理N/1的请求。若使用缓存如Redis,可进一步处理高并发场景。算法将哈希值空间视为环形,服务器和请求哈希后定位到环上,按顺时针方向找到第一台服务器作为负载目标。提供的C++代码实现了MD5哈希函数,以及一致性哈希算法的物理节点、虚拟节点和算法本身,以实现节点的添加、删除和请求映射。
17 1
C++如何实现一致性算法
|
23天前
|
算法 C++
c++算法学习笔记 (21) STL
c++算法学习笔记 (21) STL
|
23天前
|
算法 C++
c++算法学习笔记 (20) 哈希表
c++算法学习笔记 (20) 哈希表
|
23天前
|
算法 C++
c++算法学习笔记 (19) 堆
c++算法学习笔记 (19) 堆