首页 > 编程语言 >算法基础课笔记

算法基础课笔记

时间:2024-05-03 21:57:55浏览次数:27  
标签:idx int res scanf 笔记 ++ 算法 基础课 AcWing

二分

整数二分

有单调性一定可以二分,二分不一定有单调性

数的范围

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    
    while(m --)
    {
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(q[mid] >= x) r = mid;//找绿色边界,验证是不是满足绿色的要求,也就是q[mid]是否 >= x,满足的话,更新右边界
            else l = mid + 1;
            
}
        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';
            int l = 0 , r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l = mid;
                else r = mid - 1;
}
            cout << l << endl;
}
}
    return 0;
}

数的三次方

#include <iostream>
using namespace std;
int main()
{
    double x;
    cin >> x;
    double l = -10000, r = 10000;
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
        
    }
    printf("%lf\n", l);
    return 0;
}

前缀和与差分

双指针

核心思想

for(i = 0, j = 0; i < n; i ++)
{
    while(j < i && check(i, j)) j ++;
}

最长连续不重复子序列

#include <iostream>
using namespace std;
const int N = 1e5 + 10;//数的范围,一共有n个整数,整数的范围是N
int n;
int q[N], s[N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    // 存数组
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++)
    {
        s[q[i]] ++;//
        while(j < i && s[q[i]] > 1)    
            s[q[j ++]] -- ;
        res = max(res, i - j + 1);
    }
	cout << res << endl;
    return 0;
}

判断子序列

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i ++ ;
        j ++ ;
    }

    if (i == n) puts("Yes");
    else puts("No");

    return 0;
}

位运算

lowbit(x)返回x的最后一位1

离散化

区间合并

单调栈

单调队列

kmp

Trie

Trie字符串统计

#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

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];
    }
    cnt[p] ++ ;
}

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

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/45282/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

哈希表

模拟散列表

字符串哈希

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;//字符串长度,询问次数
char str[N];//字符串
ULL h[N], p[N];

ULL get(int l, int r)//求l和r之间的哈希值,公式计算出结果
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1] * P;
    }

    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/45313/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

DFS深搜

排列数字

#include <iostream>

using namespace std;

const int N = 10;//给n是什么范围就把这个N先定义了

int n;//存输入的值
int path[N];//保存的是路径
bool st[N];
void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);//path[i]??
        puts("");
        return;
    }
    for (int i = 1; i <= n; i ++ )
        if(!st[i])
        {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            path[u] = 0;//可去掉
            st[i] = false;
        }
}

int main()
{
    scanf("%d", &n);

    dfs(0);

    return 0;
}

回溯?为什么要回溯,回溯完,下一次循环难道不会得出和上一次一样的结果吗???

  • 不恢复现场的话,在最深的一层也就是即将要输出的时候,1 2 3 全部被用过了,递归到倒数第二层的时候因为3已经被用过了,所以不能出现1 3 _这种情况,所以算法也就失败了。所以最后一层的时候要恢复现场,同理可以推得,如果倒数第二层的时候不恢复现场,那么第一层的时候需要的2 _ _也被用过了,所以算法失败。所以每层都要恢复现场

n皇后


BFS宽搜

走迷宫


八数码

1、状态表示复杂

2、如何记录每个状态的距离


树与图的深度优先遍历

树和图的存储

树是特殊的图,所以只讲图

邻接表(拉链法)

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;//头,边

void add(int a, int b)//插入a指向b的bian
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    st[u] = true;//标记是否已经搜过了
    //遍历u的所有出边
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//当前链表里的节点对应的图里边的编号是多少
        if(!st[j]) dfs(j);//j如果没搜过,就继续搜
    }
}

int main()
{
    memset(h, -1 ,sizeof h);
}

邻接矩阵(稠密图)

树的重心

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;//idx当前已经用到了的b
bool st[N];

int ans = N;//最小的最大值

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//返回以u为根的子树中点的数量
int dfs(int u)
{
    st[u] = true;//初始化的时候全是未被
    int sum = 1, res = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果没被搜索过
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}

int main()
{
    cin >> n ;
    memset(h, -1, sizeof h);//全部初始化为-1
    for(int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a,b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

树与图的广度优先遍历

AcWing 847. 图中点的层次

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int h[N], e[N], ne[N], idx;//头,边,下一节点,索引
int d[N], q[N];//距离,数值

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
}
    return d[n];
}
int main()
{
    cin >> n ;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
}
    cout << bfs() << endl;
    return 0;
}

拓扑排序

有向图才有拓扑序列(起点在终点前面

有向无环图:拓扑图

AcWing 848. 有向图的拓扑序列

Dijkstra

AcWing 849. Dijkstra求最短路 I


AcWing 850. Dijkstra求最短路 II


bellman-ford

存边方式非常随便

image-20240111204147678

AcWing 853. 有边数限制的最短路

spfa

AcWing 851. spfa求最短路


AcWing 852. spfa判断负环

dist[]最短距离

cnt[]边数


Floyd

三重循环,把邻接矩阵转成最短路矩阵

AcWing 854. Floyd求最短路


Prim

AcWing 858. Prim算法求最小生成树

Kruskal

AcWing 859. Kruskal算法求最小生成树

染色法判定二分图

AcWing 860. 染色法判定二分图

匈牙利算法

AcWing 861. 二分图的最大匹配

质数

判定:试除法

AcWing 866. 试除法判定质数


快速幂

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

区间问题

Huffman树

排序不等式

绝对值不等式

推公式

标签:idx,int,res,scanf,笔记,++,算法,基础课,AcWing
From: https://www.cnblogs.com/wswtc/p/18171682

相关文章

  • 时间序列预测模型对比——视频笔记
    Autoformer他的特点是加入了自动相关,代替原来的自注意力机制,因为作者认为数据不能简单由数值来判断,而应该根据趋势来判断。他与Dlinear一样,都是用到了decomposition,这个拆分(快速傅里叶变换FFT)基于STL(季节性,趋势性),数据=趋势性数据+季节性数据(周期)+余项auto-correlation代替注意力......
  • uboot-uboot介绍-学习笔记
    源码目录编译配置......
  • uboot-学习笔记
    uboot引导程序的作用不同bootloader的对比系统启动自举过程阶段iROM读取流程......
  • 代码随想录算法训练营第10天 | 栈和队列 232.用栈实现队列 225.用队列实现栈
    leetcode232.用栈实现队列题目232.用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现MyQueue类:voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的......
  • 网课-概率论学习笔记
    基本概念贝叶斯公式\[\becauseP(AB)=P(A|B)P(B)\]期望方差......
  • raft算法和etcd代码解析-5.应用模块的启动
    Node接口Node是raft应用模块在节点上的抽象,也是应用模块和算法模块交互的入口应用模块持有Node作为算法模块的引用,通过调用Node接口的API与算法模块通信,通信方式是通过若干个Channel异步完成的。//Noderepresentsanodeinaraftcluster.typeNodeinterface{ //告知......
  • Unity 热更--AssetBundle学习笔记 1.0【AB包资源加载工具类的实现】
    工具类封装通过上文中对AB包加载API的了解和简单使用,对AB包资源加载的几种方法进行封装,将其写入单例类中,如代码展示。确保每个AB资源包只加载一次:在LoadAssetBundleManager单例工具类中,首先提供基本的AB包及其AB包依赖包的加载方法,为保持AssetBundle只加载一次,使用DIctionary......
  • 读天才与算法:人脑与AI的数学思维笔记16_音乐图灵测试
    1.      艾米1.1.        人工智能作曲家1.1.1.          分析机可能会生成任意复杂程度、精细程度的科学的音乐作品1.1.1.1.           阿达·洛夫莱斯1.1.2.          巴赫的作品是大多数作曲家开始学习创作的起点,也是......
  • 随机森林Adaboosting算法与Python实现(二)
    AdaBoost是Freund和Schapire于1996年提出的一种集成学习方法。它的核心思想是通过迭代训练一系列弱分类器,每次调整样本权重以便更好地拟合被前一轮分类器错误分类的样本,从而构建一个强分类器。最终的模型是基于这些弱分类器的加权组合。AdaBoost广泛应用于二分类和多分类问题,尤其......
  • 网课-线性代数学习笔记
    线性一个函数\(f(x)\)是线性的,当且仅当:\(f(x+y)=f(x)+f(y),f(kx)=kf(x)\)其中\(c\in\mathbf{R}\),\(x,y\)为某种可运算的元素。向量纵向的列表。\[\begin{bmatrix}a\\\vdots\\c\end{bmatrix}\]线性函数:\(c_1x_1+c_2x_2+\dots+c_nx_n\)线性变换:定......