算法笔记

笔记仅为个人总结模板和理解。。。

快速幂：

    while (n) //n为多少次方{
        if (n & 1)
            k = k * x % mod;
        n >>= 1;
        x = x * x % mod;
    }
    return k ;
}

差分：

    for(int i=1;i<=n;i++)
    {
        int t,c;
        cin>>t>>c;
        int l=max(0,t-k-c+1);
        int r=max(0,t-k);
        s[l]++;
        s[r+1]--;
    }
    for(int i=1;i<=200010;i++)s[i]+=s[i-1];

“差分是前缀和的逆运算”，只是感觉是有点像，可能还得再理解理解

筛质数：

bool finds(int n)
{
    if(n<=1)return false;
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0)
        return false;
    }
    return true;
}

发现这种筛质数方法好像更节约时间

dfs(深度优先搜索)/bfs（广度优先搜索）：

    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>0&&ty>0&&tx<=n&&ty<=m&&!maps[tx][ty])
        {
            maps[tx][ty]=1;
            dfs(tx,ty);
            maps[tx][ty]=0;//应对路径进行回溯
        }
    }

搜索中，部分题需要回溯；以及部分题不需要重开标记数组，直接在原数组上修改即可

邻接表：

  vector<ll>v[100010];//多维数组，邻接表的初始化
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 int dfs(int step,int t)//邻接表的遍历
{
    if(a[step])t++;
    else t=0;
    if(t>m||vis[step])return 0;
    vis[step]=1;
    int ans=0;
     if (step > 1 && v[step].size() == 1) return 1;
    for(int i=0;i<v[step].size();i++)
    {
        ans+=dfs(v[step][i],t);
    }
    return ans;
}

进制转换：

string s;//十转高进制
char a[16] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 65, 66, 67, 68, 69, 70};
int main() {
    ll n;
    cin >> n;
    while (n) {
        s = s + a[n % 16];
        n /= 16;
    }
cout<<s;

并查集：

   while(n--)p[n]=n;//初始化
。。。。。。。。。//缺少并的过程
  int find(int x)//查找
{
    if(p[x]!=x)p[x]=find(p[x]);//其中x为子节点，f[x]为父亲节点；
    return p[x];
}

记录不同斜率直线数量（避免爆精度）

                  map<pair<int,int>,int>maps;//初始化，建立map容器存储分子分母
        pair<int,int>ans;//以下为核心代码
        ans.first=k1/gcd(k1,k2);//利用欧几里得算法求最简形式
        ans.second=k2/gcd(k1,k2);
        if(maps[ans]==0)
        {
            maps[ans]=5;
            res++;
        }

哈希：

unordered_map<char,int>mp;//初始化
    char ch;//和谐算法
    ll ans=0;
    while(cin>>ch)
    {
        mp[ch]++;
    }
    for(int i='0';i<='9';i++)
    {
        ans+=(ll)mp[i]*mp[i];
    }
    cout<<ans;

dp(动态规划）

#include <bits/stdc++.h>//完全背包问题
using namespace std;
typedef long long ll;
int v[1010], w[1010] ;
int dp[1010][1010];
int main() {
    int n, vv;
    cin >> n >> vv;
    for (int i = 0; i < n; i++)
        cin >> v[i] >> w[i];
    for (int i = 0; i <n; i++) {
        for (int j = 1; j <= vv; j++) {
            if (j <v[i]) {
                dp[i+1][j] = dp[i][j];
            } else {
                dp[i+1][j] = max(dp[i][j], dp[i+1][j - v[i]] + w[i]);//判断向左和上一级
            }
        }
    }
    cout << dp[n][vv];
}
注：
01背包问题中的判断从上一级添加物品，即i-1；
dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);
完全背包可以从同一级添加物品即：i
dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]);

dp真难，不算总结，多看看学会

杂类算法及注释：

1.vector中pair的排序

vector<pair<int ,int> >v;
sort(v.begin(),v.end());//排序以v.first为准

2.全排列函数的运用（全排列yyds）

#include <iostream>
#include<algorithm>
using namespace std;
 
int main(int argc, char** argv) {
    int a[4]={1,2,3,4};
    sort(a,a+4);
    do{
        //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
        for(int i=0;i<4;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation(a,a+4));
    return 0;
}

3.gcd（欧几里得算法）//求最大公约数

 int gcd(int a,int b)
 {
     while(b)
     {
         int t=a%b;
         a=b;
         b=t;
     }
     return a;
 }

补充

1.最小公倍数求法为：两数相乘除以最大公约数

2.分数最简形式：分子/最大公约数

分母/最大公约数  

4.注意！

t*=k%mod不等于t=t*k%mod;

=========================================================

更新中，笔记搬运未完全。。。大概率不会更新太久（懒），权当复习