数据结构和算法笔记

Intro

• 记录数据结构和算法题
• 笔记

背包dp

0-1背包

• 0-1背包指的是容量为W的背包，重量w[i]且价值v[i]的物品，每个物品只有两种状态，取或不取，怎样放入背包使背包中的物品价值最大。

• 二维数组解法，内存过大

>folded

#include<bits/stdc++.h>

using namespace std;

int w[1001];
int v[1001];
int dp[101][1001];

int main()
{
  int W, N;
  cin >> W >> N;
  for (int i = 1; i <= N; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 0; i <= N; i++) {
    dp[i][0] = 0;
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= W; j++) {
      if (j < w[i]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);        
      }

    }
  }
  cout << dp[N][W];
  return 0;
}

• 一维数组解法

>folded

#include<bits/stdc++.h>

using namespace std;

int w[1001];
int v[1001];
int dp[1001];

int main()
{
  dp[0] = 0;
  int W, N;
  cin >> W >> N;
  for (int i = 1; i <= N; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 0; i <= N; i++) {
    for (int j = W; j >= w[i]; j--) {
      if (j - w[i] >= 0) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    }
  }
  cout << dp[W];
  return 0;
}

• P1048 采药

完全背包

• 在01背包的基础上，每个物品都可以取任意数量

>folded

#include<bits/stdc++.h>

using namespace std;

long long w[10001];
long long v[10001];
long long dp[10000001];

int main()
{
  long long W, n;
  cin >> W >> n;
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= W; j++) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  cout << dp[W];
  
  return 0;
}

• P1616 疯狂的采药

并查集

• 并查集的实现是一个森林，其中每个节点1-n刚开始都是独立的树的根节点，通过维护一个父节点数组来体现哪些节点在一棵树上，一个最基本的带有find和unite操作的并查集实现如下

>folded

#include<bits/stdc++.h>

using namespace std;

struct dsu
{
  vector<size_t> pa;

  explicit dsu(size_t size) : pa(size) {
    iota(pa.begin(), pa.end(), 0);
  }


  size_t dsu::find(size_t x)
  {
    return pa[x] == x ? x : pa[x] = find(pa[x]);
  }

  void dsu::unite(size_t x, size_t y)
  {
    pa[find(x)] = find(y);
  }

};

• 并查集的两个常见优化是路径压缩和启发式合并，路径压缩在查询过程中将节点直接连接到根节点上，减少以后的查询时间，而启发式合并则维护两个集合的大小，总是把大集合的根节点作为小集合的根节点的父节点

• P1111 修复公路

树状数组

线段树

dfs & bfs

• dfs的常用方法在于维护一个全局数组，对访问过的节点标记处理，利用递归搜索，回溯后清除标记

小项

高精度

• 高精度计算利用字符串和竖式加减法实现大整数的四则运算

>folded

#include<bits/stdc++.h>

using namespace std;

static const int LEN = 1004;

int a[LEN], b[LEN], c[LEN];


void clear(int a[])
{
  for (int i = 0; i < LEN; i++) {
    a[i] = 0;
  }
}

void read(int a[])
{
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; i++) {
    a[len - i - 1] = s[i] - '0';
  }
}

void print(int a[])
{
  int i;
  for (i = LEN - 1; i >= 1; i--) {
    if (a[i] != 0) {
      break;
    }
  }
  for (; i >= 0; i--) {
    putchar(a[i] + '0');
  }
  putchar('\n');
}

void add(int a[], int b[], int c[])
{
  clear(c);

  for (int i = 0; i < LEN - 1; i++) {
    c[i] += a[i] + b[i];
    if (c[i] >= 10) {
      c[i + 1] += 1;
      c[i] -= 10;
    }
  }
}

void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

int main()
{
  read(a);
  read(b);
  add(a, b, c);
  print(c);
  return 0;
}

快速幂

• 快速幂是以$\Theta(log \space n)$时间复杂度计算高次幂的小技巧

>folded

#include<bits/stdc++.h>

using namespace std;

//递归
long long binpow(long long a, long long b)
{
  if (b == 0) {
    return 1;
  }
  long long res = binpow(a, b / 2);
  if (b % 2) {
    return res * res * a;
  } else {
    return res * res;
  }
}

//非递归
long long binpow(long long a, long long b)
{
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

gcd和lcm

• 最大公约数欧几里得算法

>folded

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

• 扩展欧几里得算法

常用stl库

排序 sort

>folded

int nums[100];

//定义不同的cmp函数可以得到不同的排序
bool cmp(int &a, int &b) {
  return a < b;
}

sort(nums, nums + n, cmp);

二分查找 lower_bound() upper_bound()

>folded

#include <algorithm>

//取得最小的下标i使 a[i] >= x
lower_bound(a,a+n,x)-a      //下标从0开始
lower_bound(a+1,a+n+1,x)-a  //下标从1开始

//取得最小的下标i使 a[i] > x
upper_bound(a,a+n,x)-a      //下标从0开始
upper_bound(a+1,a+n+1,x)-a  //下标从1开始

• 可以对比两函数返回值，若不同则找到了a[i] == x，差值即为x的个数

set & map

>folded

set<int> st;
for (auto i : st) {
  cout << *it << endl;
}

map<string, int> mp;
for (auto it = mp.begin(); it != mp.end(); it++) {
  cout << it->first << endl;
  cout << it->second << endl;
}