主页
首页 标签 归档 分类 Page

算法竞赛学习

2024-04-10

注意点

  • cin cout 换成 scanf printf
  • 用空间换速度：三层循环写成两层。https://www.acwing.com/problem/content/1223/
  • scanf 读字符容易包括空格回车，所以建议直接读字符串
  • 超过10 0000用scanf
  • 遇到sf用exit(0)二分查找错误
  • 整数类型大于4位用long long
  • while(x)只是判断不等于0
  • strlen(sc[i]+1)若字符串从第一个位置开始
  • #define x first
#define y second
typedef pair<int,int> PII
PII a[100];
a[1] = {1,2}
makepair

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    - 

    ![image-20230119105851793](image-20230119105851793-1679759988341-3.png)

    ## 函数

    ### < algorithm >中的函数

    ```cpp
    sort(a+1,a+n+1); 起始位置到终点位置。常与pair进行联合使用，先排pair的first再排pair的second

< sstream >

  • getline()
1
2
3
4
5
6
string line;
getline(cin, line); // 忽略掉第一行的回车

getline(cin,line);  //从标准输入流（即键盘）读取一行字符串，并将其存储到变量 line 中。在读取这一行时，以换行符为行的结束标志。
stringstream ssin(line); //把line放进流里(stringstream是C++中定义的一个类，代表了一个输入输出流)
while (ssin >> a[n]) n ++ ; //用输入流提取运算符将流中内容存入a[n]

<string.h>

1
void *memset(void *str, int c, size_t n)

< queue >

1
2
3
4
升序队列，小根堆
priority_queue <int,vector<int>,greater<int>> q;
降序队列，大根堆
priority_queue <int,vector<int>,less<int>> q;

< map >

1
2
3
map<typename1,typename2>mp; 
构造映射，键为typename1，值为typename2
会以键大小从小到大映射

可用于字符串统计

1
2
3
4
unordered_map<elemType_1, elemType_2> 
unordered_map<int, int> map;
map.insert({1,3})
map.empty()

输入

1
while(scanf("%d%d%d",&n,&m,&k) != -1)

所有区间的i

1
2
for(int i = 1; i <= n; i++)
       for(int j = i; j <= n; j++)

所有区间段

按区间大小从小到大枚举

1
2
3
4
5
6
for(int len = 2; len <= n; len++)
  for(int i = 1; i + len + -1 <= n; i++)
  {
    int j = i + len - 1;
    for(int k = i; k < j; k++)
  }

取整

上取整

  1. int(ce /ceil 返回double 类型 < cmath>
  2. a mod b = (a + b - 1) / b = (a - 1) / b + 1

排序

快速排序

image-20230113112501317

https://www.zhihu.com/search?type=content&q=%20%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

这个和Y总的代码实现不同，但思维是相通的

  • 当边界用i，边界点不能取q[l],例[0,1]会出现死循环
  • 当边界用j，边界点不能取q[r],例[0,1]会出现死循环
1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

image-20230113162330767

  • 对比

双指针

为了维护操作某一段区间

找单调性

设置i，j双指针，j经过每个循环+1，当不满足条件时，i++，直至满足条件。

树状数组和线段数

快速求前缀和（区间查询） O(logn)

在某个位置上的数加上一个数（单点修改）O(logn)

  • 线段数 完全包含 树状数组
  • 能用树状数组就用树状数组
  • 从1开始

树状数组

  • tr[x] 表示区间和是**(x-lowbit(x),x]**, 记住就行
  • add(x, k)让后面所有包含元素x区间和都增加k
  • query(x) 累加x前面全部的元素，每个i包含了（i-lowbit(i),i]的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//返回二进制的第一个非零的1
int lowbit(int x)
{
  return x & -x;
}

void add(int x, int k)
{
  for(int i = x; i <= n; i+=lowbit(i)) tr[i] += k;
}

void query(int x)
{
  int res = 0;
  for(int i = x; i; i -= lowbit(i)) res += tr[i];
  return res;
}

线段数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct node{
  int l,r; //左右区间
  int sum; //总和
}tr[N*4];

void push_up(int u) //利用两个儿子算当前节点信息
{
  tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum; //左儿子+右儿子
}


void build(int u, int l, int r) //当前节点编号，左边界，有边界
{
  if(l==r) tr[u] = {l,r,w[r]};  //如果已经是叶节点，直接赋值
  else
  {  
    tr[u] = {l,r};
    int mid = l + r >> 1;
    build(u<<1,l,mid);  //递归左儿子
    build(u<<1|1,mid+1,r); //递归右儿子
    push_up(u);  //做完儿子，更新当前节点信息
  }
}

int query(int u, int l, int r) //从根节点开始往下找对应的区间
{
  if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;//如果当前区间已经完全被查询包含，直接返回值
  int mid = tr[u].l + tr[u].r >> 1;
  //先判断和左边是否有交集
  int sum = 0;
  if(mid >= l) sum+= query(u<<1,l,r); //看一下区间中点和左边有没有交集
  if(r > mid) sum+=query(u<<1|1,l,r);
  
  return sum;
  
}

void modify(int u, int x, int v) //当前编号，修改位置，待修改的值
{
  if(tr[u].l == tr[u].r) tr[u].sum+=v; //若当前已经是叶节点，总和加上v
  else
  {
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid) modify(u<<1,x,v);
    else modify(u<<1|1,x,v);
    push_up(u);
  }  
}

for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);/*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */

二分和前缀和

整数二分

  • mid = (l + r + 1) / 2 ，若 mid = (l + r) / 2 有边界问题：若 l = r - 1，mid = l，边界还是 l 和 r 出现死循环。
  • mid = (l + r + 1) / 2 取上界，mid = (l + r) / 2 取下界。

image-20230118155655247

实数二分

  • 不用考虑边界

前缀和

image-20230119210729500

image-20230119210750851

一维差分

快速给某一个区间加上一个数，最终求每一个数的值。

核心操作：b[l] += x, b[r+1] -= x

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];

使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。

二维差分

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

Trie

高效存储和查找字符串集合的数据结构

题目限制一般在26个字母

image-20230120220047920

插入

1
2
3
4
5
6
7
8
9
10
11
12
void insert(char *str)
{
    int p = 0;  //类似指针，指向当前节点
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a'; //将字母转化为数字
        if(!son[p][u]) son[p][u] = ++idx;
        //该节点不存在，创建节点,其值为下一个节点位置
        p = son[p][u];  //使“p指针”指向下一个节点位置
    }
    cnt[p]++;  //结束时的标记，也是记录以此节点结束的字符串个数
}

查找

1
2
3
4
5
6
7
8
9
10
11
int query(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u]; 
    }
    return cnt[p];  //返回字符串出现的次数
}

并查集

将两个集合合并hi

询问两个元素是否在一个集合当中

  • 原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

    image-20230121112608329

  • 变形：找到需要维护的变量

1
2
3
4
5
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);  //find 函数不仅有找祖宗的功能，还把这个查找路径上所有节点直接变成了祖宗节点的孩子，即路径压缩
    return p[x];
}

堆

image-20230121145042183

  • 完全二叉树：除了最后一层节点，上面所有节点都是满的，最后节点从左到右排列。
  • 小根堆：每个点小于等与左右儿子，所以根节点是最小值。
  • 存储；down(X); up(x);
    image-20230121144349332

为什么从2/n开始down?

因为n是最大值，n/2是n的父节点，因为n是最大，所以n/2是最大的有子节点的父节点，所以从n/2往前遍历，就可以把整个数组遍历一遍

  • 理解heap_swap中的次序

    房间a中放有元素10，房间b中放油元素20。

    10（犯人1）是第一个插入的，20（犯人二）是第二个插入的。

    h[a] = 10, h[b] = 20 swap: h[a] = 20,h [b] = 10
    hp[a] = 1 ,hp[b] = 2 swap:hp[a] = 2 ,hp[b] = 1
    ph[1] = a ,ph[2] = b swap:ph[1] = b ,ph[2] = a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

数学问题

  1. 尽力分析
  2. 打表找规律 用dfs
  • a, b的最大不能组成的数：(a - 1) * (b - 1) - 1

动态规划

dp分析法：

  1. 状态表示

    集合：不重不漏

    属性：最大值，最小值，数量

  2. 状态计算：用集合表示，不重不漏

背包问题——最值、个数

  • 没有固定模板，核心在于状态表示和转移。
  • 0-1背包：物品只能选一次。一维二层枚举需逆序，因为f[ j ]需由f[ i-1 ][ j ]状态更新而来。
1
2
f[i][j] = max(f[i-1][j], f[i-1][j-v) + w) // 二维
f[j] = max(f[j],f[j-v] + w) //一维，二层循环需逆序，f[x][j-v)由上一层得到，j-v小于循环中的j，小的j的先被改变
  • 完全背包：物品可以用无数次。
1
2
f[i][j] = max(f[i-1][j], f[i][j-v) + w) // 二维
f[j] = max(f[j],f[j-v] + w) //一维，二层循环不用逆序, f[x][j]由上一层得到，f[x][j-v]由第i层得到
  • 多重背包：物品可以一次或多次。

法一：将多重背包拆解成01背包

法二：当数据量大，需通过二进制优化。

二进制优化：最少用几个数能表示小于等于k的所有数。可以将一个数拆成几个数，把一个问题拆成logn。

  • 分组背包：每一组选一个，最后可看成0-1背包问题

背包问题参考 https://blog.csdn.net/raelum/article/details/128996521

数位统计——==分情况讨论==

递归和递推

  • 递归将问题分为子问题
  • 递推由子问题推

枚举

  • 判断闰年：
1
int leap = year % 100 && year % 4 == 0 || year % 400 == 0;

距离公式

  • 曼哈顿距离

​ $d_{M}(P_1, P_2) = |x_1 - x_2| + |y_1 - y_2|$

  • 欧几里得距离

    $$ d(x_1,x_2) = \sqrt{\sum_{i=1}^n{(x_{1,i}-x_{2,i})^2}} $$

单调队列

  • 求窗口里面的最大最小值
  • 求离他最近比他小的元素或最大的元素

狄杰斯塔拉

不断选择距离最近的点

快速幂

快速求a * (b^x)

1
2
3
4
5
6
while(x)
{
	if(x & 1) a = a * b;
  b = b ^ 2;
  b >>= 1;
}

矩阵乘法

1
2
3
4
5
6
7
8
9
void mul(int res[][N], int a[][N], b[][N])
{
  int temp[][N]={0};
  for(int i=0; i<N; i++)
  	for(int j=0; j<N; j++)
      for(int k=0; k<N; k++)
        temp[i][j] =  temp[i][j] + a[i][k] * b[k][j];
  memcpy(res,temp,sizeof temp);
}

updated at 2024-04-10

# 算法竞赛
Previous Post
多台终端SSH无密码登录
Next Post
数学在算法中的运用