首页 > 编程语言 >c++常用模板（持续更新中）

c++常用模板（持续更新中）

时间：2024-08-14 17:24:04浏览次数：16  
标签：return string int str1 更新 c++ str 模板 dis

二分手写

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[N];
bool f=0;
int FIND(int x)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(x==a[mid])return mid;
		if(x < a[mid])r=mid-1;
		if(x > a[mid])l=mid+1;
	}
	return -1;
	
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i)
	{
		int q;
		cin >> q;
		cout << FIND(q) << " ";
	}
	return 0;
}

二分STL

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[1000005];

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i)
	{
		int q;
		cin >> q;
		if(a[lower_bound(a+1,a+n+1,q)-a]==q)cout << lower_bound(a+1,a+n+1,q)-a << " ";
		else cout << -1 << " ";
	}
	return 0;
}

Kruskal最小生成树

#include<bits/stdc++.h>

using namespace std;

struct node{
	int to,w,u;
}edge[20005];
bool cmp(node a,node b)
{
	return a.w<b.w; 
}
int n,m;
int u;
int f[20005];
int find(int x)
{
	if(x == f[x])return x;
	f[x]=find(f[x]);
	return f[x];
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<=m;++i)cin >> edge[i].u >> edge[i].to >> edge[i].w;
	sort(edge+1,edge+m+1,cmp);
	int cnt=0,ans=0;
	for(int i=1;i<=m;++i)
	{
		if(cnt == n-1)break;
		if(find(edge[i].to)!=find(edge[i].u))
		{
			f[find(edge[i].u)]=find(edge[i].to);
			cnt++;
			ans+=edge[i].w;
		}
	} 
	cout << ans;
	return 0;
	
}

并查集

#include<bits/stdc++.h>

using namespace std;

int n,m;
int z,x,y;
int f[20005];
int find(int x)
{
	if(x == f[x])return x;
	f[x]=find(f[x]);
	return f[x];
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;++i)
	{
		cin >> z >> x >> y;
		if(z==1)
		f[find(x)]=find(y);
		else
			if(find(x)==find(y))printf("Y\n");
			else printf("N\n");
	}
	return 0;
}

dijkstra堆优化pair版

#include<bits/stdc++.h>
using namespace std;
int n, m, s;//s为出发点
int  vis[100005], dis[100005], u;//flag表示这个点是否被访问过,d表示从起点到下标的最优解u表示当前点
struct node {
	int x, w;//x为编号，w为权值
};
vector<node> G[100005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;//定义了从小到大的pair型优先队列
const int inf = 0x3f3f3f;
int main() {
//	freopen("dijkstra.in","r",stdin);
//	freopen("dijkstra.out","w",stdout);
	cin >> n >> m >> s;

	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back(node{v, w});
	}
//	u = s;//把起点标记为第一个u  
    q.push(make_pair(0,s));//将起点压入q
	dis[s] = 0;
	while (!q.empty()) {//只要还有点没被访问算法就不会结束
	    u=q.top().second;//取队首编号
		vis[u] = 1;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].x;//v为编号
			int w = G[u][i].w;//w为权值
			if (!vis[v]&&dis[v]>dis[u]+w) {//如果新的解比原来的解大并且这个点没有被访问就进行松弛操作
				//进行松弛操作,更新最优解
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
q.pop();
	}
	for (int i = 1; i <= n; i++) {
		if (dis[i] == inf) {
			printf("2147483647 ");
		} else {
			cout << dis[i] << " ";
		}
	}
	return 0;
}

dijkstra未优化版

#include<bits/stdc++.h>
using namespace std;
int n, m, s;//s为出发点
int  flag[10005], d[10005], u;//flag表示这个点是否被访问过,d表示从起点到下标的最优解u表示当前点
struct node {
	int x, w;//x为编号，w为权值
};
vector<node> G[10005];
const int inf = 0x3f3f3f;
int main() {
	cin >> n >> m >> s;

	for (int i = 1; i <= n; i++) {
		d[i] = inf;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back(node{v, w});
	}
	u = s;//把起点标记为第一个u
	d[s] = 0;
	while (!flag[u]) {//只要还有点没被访问算法就不会结束
		flag[u] = 1;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].x;//v为编号
			int w = G[u][i].w;//w为权值
			if (flag[v] == 0) {//如果新的解比原来的解大并且这个点没有被访问就进行松弛操作
				//进行松弛操作,更新最优解
				d[v] = min(d[v], d[u] + w);
			}
		}
		int tmp = 0x3f3f3f3f;
		for (int i = 1; i <= n; i++) {//找最小值
			if (tmp > d[i] && flag[i] == 0) {
				tmp = d[i];
				u = i;//将最小的值作为新的u
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == 4144959) {
			printf("2147483647 ");
		} else {
			cout << d[i] << " ";
		}
	}
	return 0;

dijkstra堆优化优先队列版

#include<bits/stdc++.h>
using namespace std;
int n, m, s;//s为出发点
int  vis[200005], dis[200005], u;//flag表示这个点是否被访问过,d表示从起点到下标的最优解u表示当前点
struct node {
	int w, x;//x为编号，w为权值
};
vector<node> G[200005];
priority_queue<pair<int, int> > q; //定义了从小到大的pair型优先队列
const int inf = 0x3f3f3f3f;
void dj() {
	dis[s] = 0;
	q.push(make_pair(0, s)); //将起点压入q
	while (!q.empty()) {//只要还有点没被访问算法就不会结束
		u = q.top().second;//取队首编号
		q.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].x;//v为编号
			int w = G[u][i].w;//w为权值
			if (dis[v] > dis[u] + w) { //如果新的解比原来的解大并且这个点没有被访问就进行松弛操作
				//进行松弛操作,更新最优解
				dis[v] = dis[u] + w;
				q.push(make_pair(-dis[v], v));

			}
		}

	}
}
int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++) {
		dis[i] = inf;
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(node{w, v});
	}
	dj();
	for (int i = 1; i <= n; i++) {
//		if (dis[i] == inf) {
//			printf("2147483647 ");
//		} else {
			cout << dis[i] << " ";
//		}
	}
	return 0;
}

Floyd

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

using namespace std;

int g[1005][1005],a,b,c,n,m,k;

int main()
{
    //freopen("floyd.in","r",stdin);
    //freopen("floyd.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)g[i][j]=inf;
    for(int i=1;i<=m;i++)
	{
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=c;
    }
    for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)	
			for(int j=1;j<=n;j++)								
					g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
    for(int i=1;i<=n;i++)
	{
        for(int j=1;j<=n;j++)
        {
        	if(g[i][j]==inf)
			{
        		printf("inf ");
			} 
			else /*if(j!=i)*/printf("%d ",g[i][j]);
		}
        printf("\n");
    }
    return 0;
}

树的深度

#include<bits/stdc++.h>

using namespace std;

vector<int>tree[500005];
int deep[500005];
void dfs(int u,int fa)
{
	for(int i=0;i<tree[u].size();++i)
	{
		int v=tree[u][i];
		if(v == fa)continue;
		deep[v]=deep[u]+1;
		dfs(v,u);
	}
}

int main()
{
	int n;
	cin >> n;
	for(int i=1;i<n;++i)
	{
		int u,v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);	
	}	
	dfs(1,0);
	for(int i=1;i<=n;++i)
	{
		cout << deep[i] << "\n";
	}
	return 0;
}

高精度

#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
//compare比较函数：相等返回0，大于返回1，小于返回-1
int compare(string str1,string str2)
{
    if(str1.length()>str2.length()) return 1;
    else if(str1.length()<str2.length())  return -1;
    else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
string add(string str1,string str2)//高精度加法
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    //前面补0，弄成长度相同
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
           str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
           str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;
}
//高精度减法
//只能是两个正数相减，而且要大减小
/*string sub(string str1,string str2)//高精度减法
{
    string str;
    int tmp=str1.length()-str2.length();
    int cf=0;
    for(int i=str2.length()-1;i>=0;i--)
    {
        if(str1[tmp+i]<str2[i]+cf)
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
            cf=1;
        }
        else
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
            cf=0;
        }
    }
    for(int i=tmp-1;i>=0;i--)
    {
        if(str1[i]-cf>='0')
        {
            str=char(str1[i]-cf)+str;
            cf=0;
        }
        else
        {
            str=char(str1[i]-cf+10)+str;
            cf=1;
        }
    }
    str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
    return str;
}
//高精度乘法
//只能是两个正数相乘
string mul(string str1,string str2)
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    string tempstr;
    for(int i=len2-1;i>=0;i--)
    {
        tempstr="";
        int temp=str2[i]-'0';
        int t=0;
        int cf=0;
        if(temp!=0)
        {
            for(int j=1;j<=len2-1-i;j++)
              tempstr+="0";
            for(int j=len1-1;j>=0;j--)
            {
                t=(temp*(str1[j]-'0')+cf)%10;
                cf=(temp*(str1[j]-'0')+cf)/10;
                tempstr=char(t+'0')+tempstr;
            }
            if(cf!=0) tempstr=char(cf+'0')+tempstr;
        }
        str=add(str,tempstr);
    }
    str.erase(0,str.find_first_not_of('0'));
    return str;
}
//高精度除法
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
void div(string str1,string str2,string &quotient,string &residue)
{
    quotient=residue="";//清空
    if(str2=="0")//判断除数是否为0
    {
        quotient=residue="ERROR";
        return;
    }
    if(str1=="0")//判断被除数是否为0
    {
        quotient=residue="0";
        return;
    }
    int res=compare(str1,str2);
    if(res<0)
    {
        quotient="0";
        residue=str1;
        return;
    }
    else if(res==0)
    {
        quotient="1";
        residue="0";
        return;
    }
    else
    {
        int len1=str1.length();
        int len2=str2.length();
        string tempstr;
        tempstr.append(str1,0,len2-1);
        for(int i=len2-1;i<len1;i++)
        {
            tempstr=tempstr+str1[i];
            tempstr.erase(0,tempstr.find_first_not_of('0'));
            if(tempstr.empty())
              tempstr="0";
            for(char ch='9';ch>='0';ch--)//试商
            {
                string str,tmp;
                str=str+ch;
                tmp=mul(str2,str);
                if(compare(tmp,tempstr)<=0)//试商成功
                {
                    quotient=quotient+ch;
                    tempstr=sub(tempstr,tmp);
                    break;
                }
            }
        }
        residue=tempstr;
    }
    quotient.erase(0,quotient.find_first_not_of('0'));
    if(quotient.empty()) quotient="0";
}
*/

int main()
{
     string str1,str2;
     //string str3,str4;
     cin>>str1>>str2;
     //while()
     //{
         cout<<add(str1,str2)<<endl;
         //cout<<sub(str1,str2)<<endl;
         //cout<<mul(str1,str2)<<endl;
         //div(str1,str2,str3,str4);
         //cout<<str3<<"  "<<str4<<endl;
     //}
     return 0;
}

__int128

快读：
void read(__int128 &n) {
    __int128 x = 0; bool f = false;
    char ch = cin.get();
    while(!isdigit(ch)) {
        if(ch == '-') f = true;
        cin.get(ch);
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        cin.get(ch);
    }
    n = f ? -x : x;
}
快写：
void print(__int128 n) {
    if(n < 0) {
        cout.put('-');
        n *= -1;
    }
    if(n > 9) {
        print(n / 10);
    }
    cout.put(n % 10 + '0');
}
主函数
int main()
{
    __int128 a=read(),b=read();
    print(a+b);
    return 0;
}

标签：return,string,int,str1,更新,c++,str,模板,dis
From： https://blog.csdn.net/2301_82112620/article/details/141193429

相关文章

  • C++中STL用法汇总
    1什么是STL？ STL（StandardTemplateLibrary），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++StandardLibrary）中，是ANSI/ISOC++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++......
  • 关于c++ 匿名函数的 记录
    后续补充与测试在C++中，匿名函数（lambda表达式）要使用同作用域下的一个临时变量，可以通过捕获列表和参数列表的不同组合来实现。以下是几种常见的组合：1.按值捕获（[=]）：inttemp=10;autolambda=[=](){returntemp;};1.按引用捕获（[&]）：inttemp=10;autolambda=[&](){r......
  • C++单例模式
    当我们学习类的时候，有private、public、构造函数和析构函数等等，帮助我们应对不同的需求，以此来应对不同的设计问题。那么会存在以下一种情况，我们模拟一个国家政体，一个国家只能有一个总统。我们目前能创建多个对象的方法有，1.通过复制对象，2.实例化时创建多个对象，对于第一种我们可以......
  • 3163：【例27.3】 第几项（C、C++、python）
    3163：【例27.3】第几项信息学奥赛一本通-编程启蒙（C++版）在线评测系统[例27.3]第几项2020：【例4.5】第几项信息学奥赛一本通（C++版）在线评测系统27.3_哔哩哔哩_bilibiliC语言代码：#include<stdio.h>#include<stdlib.h>intmain(){intm,s=0,n=0;s......
  • 【C++ Allocator】 详解C++的空间配置器和vector的底层实现以及push_back()和empalce_
    空间配置器用于管理动态内存分配和释放，STL容器类（如std::vector,std::list,std::map等）都使用配置器来管理内存。它有非常重要的特点：将容器的内存开辟和对象构造分离开将容器的对象析构和内存释放分离开这样能够高效的插入元素以及删除元素vectorSTL中典型的容器vec......
  • C++赋值运算符
    赋值运算符 = 用于将一个值赋给一个变量。对于自定义类型，如类和结构体，你可以重载赋值运算符以定义如何将一个对象的值赋给另一个对象。默认赋值运算符对于类类型，默认的赋值运算符会执行成员逐一赋值（member-wisecopy）。这意味着对于两个对象a和b，表达式a=b;将每个成员从b复制......
  • C++关键字static
    1.静态成员变量：当static关键字用于类的成员变量时，意味着这个变量是类的所有实例共享的。无论类实例有多少个，静态成员变量只有一个副本。静态成员变量经常用于存储类的公共数据，如配置选项或计数器。classMyClass{public:staticintcount;//静态成员变量};intMyCl......
  • 回溯算法介绍以及模板
    回溯算法的理解：回溯算法可以理解为一颗树形结构，即一颗n叉树，当遍历到叶子节点的时候，我们就到达了递归的终点，此时我们应该往上走。回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就......
  • 彼岸花开C++，类和对象（下）
    目录对类和对象的深层理解（1）再谈构造函数（2）Static成员（3）友元（4）内部类（5）匿名对象（6）再次理解类和对象对类和对象的深层理解（1）再谈构造函数1.构造函数体赋值在创建对象时，编译器通过调用构造函数，给对象中各个成员变量一个合适的初始值。classDate{public:Date(int......
  • C++-练习-16
    题目：编写一个程序，它要求用户输入其名，然后输入其姓。然后程序使用一个逗号和空格将姓和名组合起来，并存储和显示结果。请使用char数组和头文件cstring(string.h)中的函数。源代码：#define_CRT_SECURE_NO_WARNINGS //vs版本不加这个无法使用strcat等函数#include<iostream>#......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99