头像

东方可爱




离线:9小时前


分享 欧拉函数

东方可爱
11小时前

欧拉函数:https://blog.csdn.net/liuzibujian/article/details/81086324


小于 $x$ 的整数中与 $x$ 互质的数的个数
例如: $φ(1)=1$
$φ(24)=8$,因为1, 5, 7, 11, 13, 17, 19, 23均和 24 互质

题目表述:
给定n个正整数ai,请你求出每个数的欧拉函数。

输入格式
第一行包含整数n。
接下来n行,每行包含一个正整数aiai。

输出格式
输出共n行,每行输出一个正整数aiai的欧拉函数。

数据范围
1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109

输入样例:

3
3
6
8

输出样例:

2 
2
4

模板参考:

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

以12为例。12的因子有1,2,3,4,6,12。把与这些数互质的数列出来:

1:1
2:1
3:1 2
4:1 3
6:1 5
12 1 5 7 11

不妨把这些数作为分母,把与这些数互质的数作为分子,写成分数形式:

1/1
1/2
1/3 2/3
1/4 3/4
1/6 5/6
1/12 5/12 7/12 11/12

显然,每一行的数的个数就是该行的分母的欧拉函数值。倘若把这些数都改成以12为分母的数:

12/12
6/12
4/12 8/12
3/12 9/12
2/12 10/12
1/12 5/12 7/12 11/12

可以发现,这些数是以12为分母,1~12为分子的所有数,所以个数为12个。所以与12互质的数的欧拉函数值之和就是12。这样,命题大概就被证明了吧。

题目表述:
给定一个正整数n,求1~n中每个数的欧拉函数之和。

输入格式
共一行,包含一个整数n。

输出格式
共一行,包含一个整数,表示1~n中每个数的欧拉函数之和。

数据范围
1≤n≤1061≤n≤106

输入样例:

6

输出样例:

12

模板参考:

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}




关于质数的几个算法


  • 试除法判定质数
  • 试除法分解质因数
  • 线性筛法求素数

试除法判定质数

给定$n$ 个正整数 $ai$,判定每个数是否是质数。

输入格式
第一行包含整数n。
接下来 $n$ 行,每行包含一个正整数 $ai$。

输出格式
共 $n$ 行,其中第 $i$ 行输出第 $i$个正整数ai是否为质数,是则输出“Yes”,否则输出“No”。

数据范围
1≤n≤1001≤n≤100,
1≤ai≤231−11≤ai≤231−1

输入样例:

2
2
6

输出样例:

Yes
No

模板参考:

bool is_prime(int x){
    if(x<2) return 0;
    for(int i=2;i<=x/i;i++)
        if(x%i==0) return false;
    return true;//在循环外面 
} 

试除法分解质因数

给定 $n$ 个正整数$ai$,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式
第一行包含整数$n$。
接下来$n$行,每行包含一个正整数$ai$。

输出格式
对于每个正整数$ai$,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。

数据范围
1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109

输入样例:

2
6
8

输出样例:

2 1
3 1

2 3

模板参考:

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

线性筛法求素数( 欧拉筛 )

给定一个正整数$n$,请你求出$1-n$中质数的个数。

输入格式
共一行,包含整数$n$。

输出格式
共一行,包含一个整数,表示$1-n$中质数的个数。

数据范围
1≤n≤1061≤n≤106

输入样例:

8

输出样例:

4

模板参考


int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

int 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;
        }
    }
    return cnt;//素数的个数 
}




最小生成树

树:无向图中不能形成环,且连接所有顶点($n$个顶点,$n-1$条边)
最小:权值和最小的树


视频动画展示:最小生成树

模板来源(y总): 最小生成树算法模板

$Kruskal$算法

核心:从小到大挑不多余的边。

步骤: 将所有的边取出 (按照边对应权值从小到大排序)
       判断是否存在环,没有就加入,有就跳过判断下一条边
       最后直到选择了 n-1 条边
struct Edge
{
    int a, b, v;
    bool operator< (const Edge &W) const
    {
        return v < W.v;
    }
};

// 并查集——寻找当前集合的代表元素
int find(int x)
{
    if (father[x] != x) father[x] = find(father[x]);
    return father[x];
}

// 所有边存储在 Edge edges[M]; 
// 函数返回最小生成树中所有边的总长度
int Kruskal()
{
    int res = 0;
    // 初始化并查集代表元素
    for (int i = 1; i <= n; i ++ ) father[i] = i;
    sort(edge, edge + m);
    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b;
        if (find(a) != find(b))//不能形成一个环就继续
        {
            res += edge[i].v;
            father[find(a)] = find(b);
        }
    }
    return res;
}

$Prim$算法:

核心思想:从顶点出发每次挑一条与当前集合相连的最短边

步骤: 从一个顶点出发,更新所有与该顶点相连的信息(三个数组)
       下一次的顶点为 dist 数组里权值最小开始
// st[i] 表示点i是否在当前生成树集合中(是否被选择开始全为false)
// dist[i] 表示点i到当前集合的最短边的长度 (设开始的两条边的权值为INF无穷大)
// g[i][j] 表示点i和点j之间边的长度  (两个点构成一条边)
// 返回值:最小生成树中所有边的总长度
int Prim()
{
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        dist[i] = INF;
        st[i] = false;
    }
    dist[1] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int id = -1, min_dist = INF;
        // 寻找最短边
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && dist[j] < min_dist)
            {
                id = j;
                min_dist = dist[j];
            }
        st[id] = true;
        res += dist[id];
        // 用新加入的点更新其余点到生成树的最短边
        for (int j = 1; j <= n; j ++ )
            if (!st[j])
                dist[j] = min(dist[j], g[id][j]);
    }
    return res;
}

天空之城

注意map映射的用法:把字符串映射为整型
难点:想着如何取标记字符串名字的地方
然后套用 $Kruskal$算法 模板

#include <bits/stdc++.h>
using namespace std;
const int N=2000010;
typedef long long ll;
int pre[N];

struct node{
    int a,b,c;
    bool operator< (const node & t) const{
        return c<t.c;
    }
}q[N];
map<string,int > mp;

int find(int x){
    if(x!=pre[x]) pre[x]=find(pre[x]);
    return pre[x];
}
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        int tot=0;
        for(int i=1;i<=n;i++) pre[i]=i;//!!
        mp.clear();//多组数据输入 记得清空map
        string s;cin>>s;
        for(int i=0;i<m;i++){   
        string a,b;
        int c;
        cin>>a>>b>>c;
        if(!mp.count(a)) mp[a]=++tot; 
        if(!mp.count(b)) mp[b]=++tot;
        q[i] = (node){mp[a],mp[b],c };
        }
        ll res=0;
        int cnt=0;
        sort(q,q+m);
        for(int i=0;i<m;i++){
            int t1=find(q[i].a);
            int t2=find(q[i].b);
            if(t1!= t2) {
                pre[t1]=t2;
                res+=q[i].c;
                cnt++;
            }
        }
        if(cnt != n-1) puts("No!");
        else  printf("%lld\n",res);
    } 
    return 0;
} 

Prim算法求最小生成树

题目表述:

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,
其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入输出格式:

输入格式
第一行包含两个整数n和m
接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。

输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

输入样例:

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例:

6

$Kruskal$算法:

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=510;
int pre[N];
struct node{
    int a,b,c;
    bool operator<(const node& t)const{
        return c<t.c;//要对权值排序用结构体重载 
    }
}s[N];

int find(int x){
    if(x!=pre[x]) pre[x]=find(pre[x]);
    return pre[x];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) pre[i]=i;
    for(int i=1;i<=m;i++) {
        cin>>s[i].a>>s[i].b>>s[i].c;
    }
    sort(s+1,s+1+m);
    int sum=0,cnt=0;
    for(int i=1;i<=m;i++){
        int t1 = find(s[i].a);
        int t2 = find(s[i].b);
        if(t1 != t2 ) {//不能形成环 
            pre[t1]=t2;
            sum+=s[i].c;
            cnt++;
        }
    }
    if(cnt==n-1 ) cout<<sum<<endl;//终止条件 
    else cout<<'impossible'<<endl; 


    return 0;
}

$Prim$算法:

#include <bits/stdc++.h>
using namespace std;
const int N=520;
const int INF=0x3f3f3f3f;

int pre[N];
int g[N][N];//邻接矩阵(记录边) 
int dis[N];//权值 
bool st[N];//该顶点是否已经加入最小生成树 
int res,n,m;
int prim()
{
  //若图不连通返回INF,否则返回res;
  memset(dis,INF,sizeof(dis));
  int res=0;

  for(int i=0;i<n;i++)//迭代n次(而Dijkstra算法中为:for(int i=1;i<=n-1;i++))
  {
    int t=-1;
    for(int j=1;j<=n;j++)
    {
      if(!st[j]&&(t==-1||dis[j]<dis[t]))
      {
        t=j;
      }
     }
      if(i&&dis[t]==INF) return INF;
      if(i) res+=dis[t];
      st[t]=true;
    for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]);
  }

 return res;
}


int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++) pre[i]=i;
    memset(g,INF,sizeof(g));
    for(int i=1;i<=m;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] =g[b][a] = min(g[a][b],c);  
    }
    int ans=prim();
    if(ans == INF) cout<<"impossible"<<endl;
    else cout<<ans<<endl; 

    return 0;
} 

(补充):

1138. 城市公交网建设问题

1140. 最短网络

(补充map映射):

C++ map用法总结(整理)



分享 离散化

离散化


所谓离散化,就是当我们只关心数据的大小关系时,用排名代替原数据进行处理的一种预处理方法
原数据很大或含有负数小数时,难以表示为数组下标,一些算法和数据结构(如BIT)无法运作,这时我们就可以考虑将其离散化。


步骤:

* 将所有需要离散化的数据放到一个容器中(以下使用vector);

* 排序,去重(可以手写,也可以用STL的algorithm库中的unique函数);

* 要查询原数据在容器中的位置只需在容器中二分查找第一个大于等于该数据的数的位置

  • 注意点:特别注意:由于使用到了前缀和,数组要下标从 1 开始计算,因此使用 STL 的 lower_bound() 查找二分查找左边界的时候,需要将返回值增加 1。

1111111111111.png

模板一:用$lower bound $ 实现

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
     int a=alls.size()-1;
     return  lower_bound(alls,alls + a,x)-alls;

}

模板二:二分法

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}



题目表述 区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
近下来,进行 m 次询问,每个询问包含两个整数 l 和 r ,你需要求出在区间 [l, r] 之间的所有数的和。

输入格式:
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式:
共m行,每行输出一个询问中所求的区间内数字和。
数据范围:
−10^9 ≤ x ≤ 10^9,
1 ≤ n, m ≤ 10^5,
−10^9 ≤ l ≤ r ≤ 10^9,
−10000 ≤ c ≤ 10000
样例输入:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
样例输出
8
0
5

分析

数据范围分析:

第一眼看到题目的时候,觉得题目好简单,就是一个标准的前缀和模板题。但是看到数据范围后,才发现好多坑。

1) 有一个无限长的数轴,数轴上每个坐标上的数都是 0。我们看到 x 的范围是 [−10^9, 10^9] ,也就是 2*10^9 大小,如果直接定义这么大的数组,估计要爆

2) 实际操作的数据是 n,n 的范围是 [1, 10^5],也就是进过了 n 次操作后,需要插入的数据包括 n 个坐标和 m 个 [l, r],因此最多有 3*10^5 个数据是非零的,其他数据都是 0。310^5 对比 210^9,我们可以发现,非常符合离散化的前提

3) 由于事前不知道 n 的大小,可以使用 C++ STL 中的 vector,而不是定义数组。


加入到 vector 后的数据如下,注意将所有的坐标加入到 vector 中

1 3 7 1 3 4 6 7 8

排序后的数据变为

1 1 3 3 4 6 7 7 8

去重后的数据变为

1 3 4 6 7 8

加法操作后,离散化后数据变为

0 2 6 0 0 5

离散化后前缀和为

0 2 8 8 8 13

完整代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5+4;
int lsh[MAXN];//离散化后的数据
int sum[MAXN];//前缀和

int main() {
    int n,m,i;
    cin >> n >> m;

    vector<int> nums;//所有需要离散化数据
    vector<pair<int, int> > add;//加法操作
    vector<pair<int, int> > query;//查询操作
    //读入所有加法操作
    for (i=0; i<n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        nums.push_back(x);//x需要离散化
    }
    //读入查询操作
    for (i=0; i<m; i++) {
        int l,r;
        cin >> l >> r;
        query.push_back({l, r});
        nums.push_back(l);
        nums.push_back(r);
    }

    //排序
    sort(nums.begin(), nums.end());
    //去重
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    //处理加法
    for (auto item:add) {
        int x = lower_bound(nums.begin(), nums.end(), item.first)-nums.begin()+1;
        lsh[x]+=item.second;
    }

    //求前缀和
    for (i=1; i<=nums.size(); i++) {
        sum[i]=sum[i-1]+lsh[i];
    }

    //查询前缀和
    for (auto item:query) {
        int l = lower_bound(nums.begin(), nums.end(), item.first)-nums.begin()+1;
        int r = lower_bound(nums.begin(), nums.end(), item.second)-nums.begin()+1;
        cout << sum[r]-sum[l-1] << endl;
    }

    return 0;
}


分享 位运算

二进制中 1 的个数


补充

一个数$&$ 1的结果就是取二进制的最末位,还可以判断奇偶 $x & 1==0 $为偶,$x & 1==1$为奇。
运算符 $>> $, 二进制去掉最后一位

步骤:

1) 先将二进制数向右移动 k位(此时 k位移动到了第一位), 操作: x >> k
2) 获取最后一位的值, 操作: 移动后的值 & 1 是否为 1

注意点: 强制转换成无符号操作(因为考虑到负数)
在C++中如果我们右移一个负整数,系统会自动在最高位补1,这样会导致 un 永远不为0,就死循环了。
解决办法: 把 un 强制转化成无符号整型,这样 n 的二进制表示不会发生改变,但在右移时系统会自动在最高位补0。

位运算


模板

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n; //要用无符号的
        while (un) res += un & 1, un >>= 1;
        return res;
    }
};


法二:(时间复杂度更低)
将n - 1后再和n相与,得到的值相当于将n从右边数的第一个1变成0
n的二进制表示中有多少个1,就能变多少次

public int NumberOf1(int n)
{
    int count = 0;
    while (n != 0)
    {
        count++;
        n = (n - 1) & n;
    }
    return count;
}

例题补充: 数列
注意:可以把 N 转化成 二进制,二进制对应是1 就加上相应幂次方

$ N=1 ----> 1 ----> 3(0)$
$ N=2 ----> 10 ----> 3(1)$
$N=3 ----> 11 ----> 3(0)+3(1)$
$ N=4 ----> 100 ----> 3(2)$
$N=5 ----> 101 ----> 3(0)+3(2)$

完整代码:

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

int k, N;

int main()
{
    cin >> k >> N;
    int res = 0, t = 1;
    while (N)
    {
        if (N & 1) res += t;
        t *= k;
        N >>= 1;
    }
    cout << res << endl;
    return 0;
}

返回x的最后一位1:lowbit(x) = x & -x= x & (∼x+1)

就是每一次把 x 的最后一位 1 减掉,即 x−lowbit(x),只需要算下减多少次,减多少次就有多少个 1


41956_38156e8c64-位运算_lowbit.png

$lowbit(x) 操作返回 x 的最后一位 1$
$x=1010,那么 lowbit(x) 返回 10,即 lowbit(x)=10$
$ x=101000,那么 lowbit(x)返回 1000,即 lowbit(x)=1000$

模板如下:


int lowbit(int x)
{
    return x&(-x);
}

参考资料




一维前缀和

题目表述:求在区间 [l,r] 内所有的数的总和

12.png

21.png

模板:

初始化: d[i] = a[1] + a[2] + ... a[i] = d[i-1]+a[i]
结论:   a[l] + ... + a[r] = d[r] - d[l - 1]


二维前缀和

初始化: s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];

S[i][j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
结论: S[x2][y2] - S[x1 - 1][ y2] - S[x2][y1 - 1] + S[x1 - 1][ y1 - 1]


一维差分

题目表述: 在区间[l,r] ,对它进行 m 次区间修改(在区间所有书加上 或 减去一个数) ,输出修改后的序列

3211.png

32111.png

模板

a[i]=d[1]+d[2]+...+d[i];

结论:在区间 [l,r] 加 k, d[l]+=k,d[r+1]-=k;
最终值表示: a[i]=a[i-1] + d[i]  推算出区间各个数值

模板题: 一维差分
运用了 前缀和 和 差分

#include<bits/stdc++.h>
using namespace std;
int a[110];
int d[110];
int main(){
    int n,m;
    cin>>n>>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(m--){
        int x,y,z;
        cin>>x>>y>>z;
        d[x]+=z;//结论 
        d[y+1]-=z;

    }
    for(int i=1;i<=n;i++) a[i]=a[i-1]+d[i];//计算原数组 = 差分数组的前缀和  
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";


    return 0;
}


二维差分

给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c




!学习一下高精度算法

高精度加法:

思路:

以字符串形式读入数字,并逐位转换成数字倒序存储;
进行高精度加法计算;
倒序输出。

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

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);//保证 A 为长度多的 

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ) 
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10); // t是否进位
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}
int main()
{
    // 使用字符串读入
    string a, b;
    vector<int> A, B;
    cin >> a >> b; 
    // 使用vector逆序读入
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    // 相当于vector<int>
    auto C = add(A, B);//调用函数 
    // 倒序输出
    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}


高精度减法:

基本和加法一模一样,只不过从进位变成退位

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘法:

将加法运算改为乘法运算即可

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}


。

高精度除法:

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

https://www.acwing.com/blog/content/5702/





图的概念:

入度: 进入该点的边数

1111.png

扑拓排序

应用:用来判断有向图中是否有环

22222.png

该右图中: 0 和 1的入度都为 0 <起始点>
先让 0,1 入队,其它 <2,4,5> 入度都减小 1
2 本来入度为 1,现在减到 0,故让 2 入度;

算法思路:

算法思路:
1)统计图中每个节点的入度 用in[i]数组
2)借助一个队列 queue,将所有入度为0的节点入队
3)当queue非空时,依次将队首节点出队,依次将队首节点的所有邻接节点 in[v] 的入度-1
//你删掉一个入度为0的点,那么和它相连的点入度也相应减少 1
4)是有向无环图,则所有节点一定都入队并出队过
用个cnt 计数器

模板题目:
拓扑排序·一 HihoCoder - 1174

#include <bits/stdc++.h>
using namespace std;
const int mod=142857;
const int N=1e5+10;
int n,m,cnt,x,in[N];
vector <int > E[N];
queue <int > q; 

void init(){
    for(int i=1;i<=n;i++)
        in[i] = 0,E[i].clear();
    cnt=0; 
} 

bool topsort(){
    for(int i=1;i<=n;i++)//这里是n 
        if(!in[i]) q.push(i);
    while(!q.empty()){
        int now=q.front();
        q.pop();cnt++;
        for(int i=0;i<E[now].size();i++){// 遍历由某点指向的所有点E[1][0]=4;E[1][1]=5;
            int v=E[now][i];
            if(--in[v]==0) q.push(v);
        }
    }//是否为有向无环图 入队次数是否等于顶点数 
    return cnt==n;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int x,y;
        cin>>n>>m;
        init();
        while(m--){
            scanf("%d %d",&x,&y);
            E[x].push_back(y);  //E[1]=2
            in[y]++;
        }
        if(topsort()) puts("Correct");
        else puts("Wrong");
    }


    return 0;
}

补充 队列queue相关知识:

front() 获取队首
back() 获取队尾
pop() 队首元素出队
empty():如果 queue 中没有元素的话,返回 true
注意:在使用pop()之前,一定要使用empty()判断是否为空

补充 vector容器相关知识:

C++ 中vector的使用方法
C++ 中vector的使用方法

push_back 在数组的最后添加一个数据
pop_back 去掉数组的最后一个数据
erase 删除指针指向的数据项
clear 清空当前的vector

(vector<int>test;//建立一个vector
test.push_back(1);
test.push_back(2);//把1和2压入vector,这样test[0]就是1,test[1]就是2 )

使用迭代器访问元素:

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
    cout<<*it<<endl;

想补充一下队列

小L的编辑器
输入样例:

abcde
LLRLR

输出样例:

cedba

完整代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;

int main(){
    ios::sync_with_stdio(0);
    string s,t;cin>>s>>t;
    deque<char> pre,suf;;
    for(int i=0;i<t.size();i++){
        if(t[i]=='L'){
            suf.push_front(s[i]);
        }
        else{
            pre.push_back(s[i]);


*   }
    }
    for(auto &x:pre) cout<<x;
    for(auto &x:suf) cout<<x;
    return 0;
}

deque队列 https://blog.csdn.net/u011630575/article/details/79923132

deque容器为一个给定类型的元素进行线性处理,像向量一样,它能够快速地随机访问任一个元素,并且能够高效地插入和删除容器的尾部元素。但它又与vector不同,deque支持高效插入和删除容器的头部元素,因此也叫做双端队列



活动打卡代码 AcWing 1353. 滑雪场设计

思路:
控制每一对的范围 [l,r] 0 < l < 83
在该范围内算出 给出数据满足的最小值
参照作者 (血小板自动机)

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

inline int mypow(int n) { return n * n; }

int arr[1005];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];

    int tot = 1 << 30;

    // 在1到100中,枚举每一对差值刚好为17的数(i, i + 17)  1 <= i <= 83
    for(int i = 1; i < 84; i++) {
        int tmp = 0, l = i, r = i + 17;
        for(int j = 0; j < n; j++) { // 枚举处理每座山峰的情况,让每座山峰都满足差值小于等于17的情况
            if(arr[j] < l) tmp += mypow(arr[j] - l);
            else if(arr[j] > r) tmp += mypow(arr[j] - r);
        }
        tot = min(tot, tmp); // 找差值最小的情况
    }
    cout << tot << endl;
    return 0;
}




活动打卡代码 AcWing 3227. 折点计数

类似零点存在定理

#include <iostream>
using namespace std;
const int N = 1010;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i) cin >> a[i];

    int cnt = 0;
    for(int i = 1; i + 1 < n; ++ i)
        if((a[i - 1] - a[i]) * (a[i + 1] - a[i]) > 0) cnt ++;

    cout << cnt << endl;

    return 0;
}

。

思路二:
判断是否为高峰或者是低谷

if(a[i]>a[i+1]&&a[i]>a[i-1] || a[i]<a[i-1]&&a[i]<a[i+1])