ACwing算法基础入门代码合集

这篇具有很好参考价值的文章主要介绍了ACwing算法基础入门代码合集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

ACwing算法基础入门代码合集

快速排序

786.第k个数
//第k个数
//算法思想:基于快速排序(分治)
#include<iostream>
using namespace std;
#define N 100010
int Partition(int a[], int low, int high);
int quicksort(int a[], int low, int high,int k)
{
	if (low == high) return a[low];
	int pviotment = Partition(a,low,high);
	int s1 = pviotment - low + 1;
	if (k <= s1) return quicksort(a, low, pviotment, k);
	else return quicksort(a,pviotment+1,high,k-s1);
}

int Partition(int a[], int low, int high)
{
	int pviot = a[low];
	while (low<high)
	{
		while (low < high && a[high] >= pviot)
			--high;
		a[low] = a[high];
		while (low < high && a[low] <= pviot)
			++low;
		a[high] = a[low];
	}
	a[high] = pviot;
	return low;
}
int main()
{
	int a[N];
	int n, k;
	cin >> n >> k;
	for (int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int res=quicksort(a,0,n-1,k);
	cout <<res;
	return 0;
}

归并排序

787.归并排序
//归并排序
//算法思想:基于分治与双指针
#include<iostream>
using namespace std;
#define N 100000

int temp[N];
int merge_sort(int q[],int l, int r)//归并排序
{
	if (l >= r) return 0;
	int mid = l + r >> 1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int k = 0, i = l, j = mid + 1;
	while (i<=mid&&j<=r)
	{
		if (q[i] <= q[j])
			temp[k++] = q[i++];
		else
			temp[k++] = q[j++];
	}
    //扫尾,将剩余的元素归到一个数组中
	while (i <= mid)temp[k++] = q[i++];
	while (j <= r)temp[k++] = q[j++];
    //物归原主
	for (int i = l, k = 0; i <= r; i++, k++)
		q[i] = temp[k];
}
int main()
{
	int n,q[N];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> q[i];

	merge_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++)
		cout << q[i]<<" ";
	return 0;
}
788.逆序对的数量
//求逆序数对
//算法思想:基于归并排序,注意事项:返回结果大于int的最大存储值,故要用long long来存储
#include<iostream>
using namespace std;
#define N 100010
int temp[N];

long long  mergesort(int q[],int l,int r)
{
	if (l >= r) return 0;
	int mid = l + r >> 1;
	long long res = mergesort(q,l,mid) + mergesort(q,mid+1,r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j])temp[k++] = q[i++];
		else
		{
			temp[k++] = q[j++];
			res += mid - i + 1;
		}
	}
	while (i <= mid)temp[k++] = q[i++];
	while (j <= r)temp[k++] = q[j++];
	//物归原主
	for (int i = l, j = 0; i <= r; i++, j++)
		q[i] = temp[j];
	return res;
}

int main()
{
	int n,q[N];
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d",&q[i]);
	long long  res=mergesort(q,0,n-1);
	cout << res;
	return 0;
}

二分

789.数的范围
//数的范围
//算法思想:二分,基于分治
#include<iostream>
using namespace std;
#define N 100000

int	q[N];
int n, m;

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> q[i];
	}
	while (m--)
	{
		int x;
		cin >> x;
		int l = 0;
		int r = n - 1;
		while (l<r)
		{
			int mid = l + r >> 1;//相当于除以二
			if (q[mid] >= x)//先求左边界,条件是分界点右边的值都大于等于分界点的值		
				r = mid;//若mid符合条件,则直接边界值等于mid,否则将mid+1
			else l = mid + 1;
		}
		if (q[l] != x)
			cout << "-1 -1" << endl;//若未找到数则返回-1 -1;
		else
		{
			cout << l << " ";
			int l = 0;
			int r = n - 1;
			while (l < r)
			{
				int mid = l + r + 1 >> 1;
				if (q[mid] <= x)//再求右边界,条件是分界点左边的数都小于等于x的值
					l = mid;
				else
					r = mid - 1;
			}
			cout << r<< endl;
		}
	}
	return 0;
}


790.数的三次方根
//数的三次方根
//算法思想:基于二分
#include<iostream>
using namespace std;

int main()
{
	double x;
	cin >> x;
	double r = 100000;
	double l = -100000;
	while (r - l > 1e-10)
	{
		double mid = (r + l) / 2;
		if (mid * mid * mid >= x)
			r = mid;
		else
			l = mid;
	}
	printf("%lf",l);
	return 0;
}

高精度

791.高精度加法(山西大学2023机试第三题)
//高精度加法
//算法思想:注意进位变化
#include<iostream>
#include<vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size() || i < B.size(); i++)
	{
		if (i < A.size())t += A[i];
		if (i < B.size())t += B[i];
		C.push_back(t % 10);//将结果放入
		t = t / 10;//进位
	}

	if (t)C.push_back(1);
	return C;
}

int main()
{
	string a, b;
	vector<int> A,B;
	cin >> a >> b;
	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');
	auto C = add(A,B);
	for (int i = C.size() - 1; i >= 0; i--)
		cout << C[i];
	return 0;
}
792.高精度减法
//高精度运算
//高精度减法
#include<iostream>
#include<vector>
using namespace std;

bool cmp(vector<int> &A,vector<int> &B)//比较A与B的大小关系,判断A是否大于B
{
	if (A.size() != B.size())//先判断位数,位数大则大
		return A.size() > B.size();
	else//位数相同再逐位比较
	{
		for (int i = A.size() - 1; i >= 0; i--)
			if (A[i] != B[i])
				return A[i] > B[i];
	}
	return true;
}

vector<int> sub(vector<int> &A,vector<int> &B)//C=A-B
{
	vector<int> C;
	int t = 0;
	for (int i = 0; i < A.size(); i++)
	{
		t = A[i] - t;
		if (i < B.size())
			t -= B[i];
		C.push_back((t + 10) % 10);//t值为正则直接压入C中,t值为负则+10压入C中
		if (t < 0) t = 1;
		else t = 0;
	}
	while(C.size() > 1 && C.back() == 0)//去掉输出时的前导零
		C.pop_back();
	return C;
}

int main()
{
	string a, b;
	vector<int> A, B;
	cin >> a >> b;
	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');

	if (cmp(A, B))//若A大于B则直接A-B
	{
		auto C = sub(A,B);
		for (int i = C.size() - 1; i >= 0; i--)
			cout << C[i];
	}
	else//若A小于B则执行(B-A)后在前面输出一个负号
	{
		auto C = sub(B,A);
		cout << '-';
		for (int i = C.size() - 1; i >= 0; i--)
			cout << C[i];
	}
	return 0;
}

793.高精度乘法
//高精度运算
#include<iostream>
#include<vector>
using namespace std;
//高精度乘法
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 + t;//t等于当前值加进位
		C.push_back(t%10);//结果位
		t = t / 10;//进位
	}
	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	return C;
}

int main()
{
	string a;
	int b;
	vector<int> A;
	cin >> a >> b;
	for (int i = a.size() - 1; i >= 0; i--)
		A.push_back(a[i]-'0');
	auto C=mul(A,b);
	for (int i = C.size() - 1; i >= 0; i--)
		cout << C[i];
	return 0;
}
794.高精度除法
//高精度运算
//高精度除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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];//上一位的余数乘以10加当前位
		C.push_back(r/b);//求商
		r = r % b;//求余数
	}
	reverse(C.begin(),C.end());
	while (C.size() > 1 && C.back() == 0)//去掉前导零
		C.pop_back();
	return C;
}

int main()
{
	string a;
	int b,r;
	cin >> a >> b;
	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i--)
		A.push_back(a[i]-'0');
	auto C = div(A,b,r);
	for (int i = C.size() - 1; i >= 0; i--)
		cout << C[i];
	cout << endl << r << endl;
	return 0;
}

前缀和与差分

795.前缀和
//前缀和
#include<iostream>
using namespace std;
#define N 100010

int main()
{
	int n, m;
	int a[N],s[N];
	s[0] = 0;
	cin >> n >> m;
	for (int i = 1; i <=n; i++)
		scanf("%d",&a[i]);
	for (int i = 1; i <= n; i++)
		s[i] = s[i - 1] + a[i];//前缀和的初始化,前缀和的基本公式
	while (m--)
	{
		int l, r;
		cin >> l >> r;
		cout << s[r] - s[l - 1]<<endl;//注意是l-1
	}
	return 0;
}
796.子矩阵的和
//子矩阵的和
//算法思想:前缀和
#include<iostream>
using namespace std;
#define N 1010

int main()
{
	int a[N][N], s[N][N];
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d",&a[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];//基本公式,初始化矩阵前缀和
	while (q--)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout <<s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]<<endl;
	}
	return 0;
}
797.差分
//差分
//算法思想:差分,便于求在l到r之间加上c这样的操作
#include<iostream>
using namespace std;

#define N 100010
int a[N], b[N];

void insert(int l,int r,int c)
{
	b[l] += c;
	b[r + 1] -= c;
}
int main()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	for (int i = 1; i <= n; i++)
		insert(i, i, a[i]);//将b数组初始化为a数组的差分
	while (q--)
	{
		int l, r,c;
		cin >> l >> r>>c;
		insert(l,r,c);//实现在l到r之间加上c
	}
	for (int i = 1; i <= n; i++)
		b[i] += b[i - 1];//求出b的前缀和即为加上c后的a数组
	for (int i = 1; i <= n; i++)
		printf("%d ",b[i]);
	return 0;
}

双指针算法

799.最长连续不重复子序列
//最长连续不重复子序列
//算法思想:双指针,双指针算法可以先想出一个暴力的解法,类似于双重循环,后将一重循环改为while使其时间复杂度降低
//基本模版为
/*
for(int i=0;i<n;i++)
{
while(j<i&&check(i,j))
{
i++;
j++;
}
}
*/
#include<iostream>
using namespace std;
#define N 100010
int a[N], s[N];
int subsequence(int n)
{
	int j = 0;
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		s[a[i]]++;//s数组记录重复的次数
		while (s[a[i]]>1)//若大于1即为重复,则让j指针向右移动来消除重复
		{
			s[a[j]]--;
			j++;
		}
		res = max(res,i-j+1);//结果即为i与j之间的长度
	}
	return res;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	int res=subsequence(n);
	cout << res;
	return 0;
}
800.数组元素的和
//目标和
//算法思想:双指针
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
int main()
{
	int n, m,x;
	int a[N], b[N];
	cin >> n >> m>>x;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	int j = m-1;
	for (int i = 0; i < n; i++)//令a数组从左向右遍历
	{
		while (j >= 0 && a[i] + b[j] > x)j--;//令b数组从右向左遍历
		if (a[i]+b[j]==x)//由于是唯一解,故只要找出一组值即可跳出
		{
			cout << i <<" "<< j;
			break;
		}
	}
	return 0;
}
2816.判断子序列
//子序列
//算法思想:双指针
#include<iostream>
using namespace std;
#define N 100010
int main()
{
	int n, m;
	int a[N], b[N];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	int j = 0;
	for (int i = 0; i < m; i++)
	{
		while (j<n&&a[j]==b[i])//当判断二者相同时要同步进位,防止有重复数字出现的情况
		{
			i++;
			j++;
		}
	}
	if (j == n)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

位运算

801.二进制中1的个数
#include<iostream>
using namespace std;
#define N 100010
int main()
{
    int n,a[N];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    for(int i=0;i<n;i++)
    cout << __builtin_popcount(a[i]) << ' ';//OI可用
    return 0;
}

离散化

802.区间和
//区间和
//算法思想:离散化
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define N 300010
int a[N]={0}, s[N];
vector<int> relect;
vector<pair<int, int>> add, query;
int find(int x)
{
	int l = 0, r = relect.size() - 1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (relect[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return r + 1;
}
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i=0;i<n;i++)
	{
		int x, c;
		cin >> x >> c;
		add.push_back({x,c});
		relect.push_back(x);
	}
	for (int i=0;i<m;i++)
	{
		int l, r;
		cin >> l >> r;
		query.push_back({l,r});
		relect.push_back(l);
		relect.push_back(r);
	}
	sort(relect.begin(),relect.end());
	relect.erase(unique(relect.begin(),relect.end()),relect.end());

	for (auto item : add)
	{
		int x = find(item.first);
		a[x] += item.second;
	}
	for (int i = 1; i <= relect.size(); i++) s[i] = s[i - 1] + a[i];
	for (auto item : query)
	{
		int l = find(item.first);
		int r = find(item.second);
		cout << s[r] - s[l - 1] << endl;
	}
	return 0;
}

区间合并

803.区间合并
//区间合并
//算法思想:贪心
#include<iostream>
#include<vector>
#include<Algorithm>
using namespace std;

void merge(vector<pair<int,int>> &segs)
{
	vector<pair<int, int>> res;//存放返回的结果
	if (segs.size() > 0)//防止输入的值为空值
	{
		sort(segs.begin(),segs.end());//先按左端点进行排序,sort函数默认情况下按照pair的左端点进行排序
		int st = segs[0].first;//初始化当前比较区间为排好序的segs中的第一个区间值
		int ed = segs[0].second;
		for (auto seg:segs)
		{
			if (ed < seg.first)
			{
				res.push_back({st,ed});//若当前比较区间的左端点值小于下一个区间的右端点值则将st与ed放入res中
				st = seg.first;//更新当前比较区间的值
		     	ed = seg.second;
			}
			else
			{
				ed = max(ed,seg.second);//反之则将右端点值更新为当前的右端点值与下一个右端点中的最大值,就是区间合并的效果
			}
		}
		res.push_back({st,ed});	//将最后一个区间加入到res中
	}
	segs = res;
}
int main()
{
	int n;
	vector<pair<int, int>> segs;//使用pair进行区间的输入
	cin >> n;
	for (int i=0;i<n;i++)
	{
		int l, r;
		cin >> l >> r;
		segs.push_back({l,r});
	}
	merge(segs);
	cout << segs.size();//segs的长度即为合并后的区间数量
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-824947.html

到了这里,关于ACwing算法基础入门代码合集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 【第十五课】数据结构:堆(acwing-839模拟堆 / ph和hp数组的映射关系 /c++代码 )

    目录 注意点  代码如下  上篇已经详细解释过堆的内容,需要可以回顾一下。 【第十五课】数据结构:堆 这里关注这道题提出几个注意点。  这道题有几个需要注意的点: ①没有事先给出完整的数组,而是靠我们一次次操作进行插入。因此,要定义一个size变量记录插入数

    2024年01月25日
    浏览(38)
  • 西工大数据结构实验NOJ参考代码和分析合集

    实验1.1 合并有序数组

    2023年04月08日
    浏览(75)
  • 【NLP文本分类算法集锦】零基础入门经典文本分类项目实战(附代码+数据集)

    大家好,我是阿光。 本专栏整理了《NLP文本分类算法集锦》,内包含了各种常见的中英文文本分类算法,以及常见的NLP任务:情感分析、新闻分类以及谣言检测等。 文本分类是NLP的必备入门任务,在搜索、推荐、对话等场景中随处可见,并有情感分析、新闻分类、标签分类

    2023年04月20日
    浏览(46)
  • ACWing算法基础课

    y总说 java不能用Scanner读入,要用Buffer.read();快十倍二十倍; y总19年5月的视频,牛13! 包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。 一定要先移动end(就是把大数移到右边),后移动start; 否则 先找小数,会出现end start重合位置

    2024年02月13日
    浏览(43)
  • 第1章:算法基础【AcWing】

    阅读前导 * 表示算法的核心步骤。 关于阅读体验:本文只会在比较重要的地方才会使用语法高亮。 虽然 STL 中有相应算法,但本文只讨论原理本身。 [luogu]P1177 【模板】快速排序 利用快速排序算法将读入的 N N N 个数从小到大排序后输出。 输入格式 第 1 1 1 行为一个正整数

    2023年04月27日
    浏览(33)
  • 第二讲:数据结构 AcWing 826. 单链表

    笔试的题目大部分 大部分涉及到链表都是十万级别的 用数组的方式创建链表速度很快,不会超时,而如果用new 一个结构体的话 大部分就是比较慢的 所以不建议使用 数组模拟单链表 单链表在笔试题中用的最多是 领接表 领接表最多的应用是存储数和图 双链表 最多的应用就

    2024年02月19日
    浏览(38)
  • 搜索与图论(acwing算法基础)

    排列数字 n皇后 走迷宫 单链表 点击跳转至例题 idx存的是指针 树与图的深度优先搜索 树的重心 每个节点都是一个单链表 模拟队列 hh = 0 , tt = -1 有向图的拓扑序列 都是从前指向后,即有向无环图(不能有环) 所有入度为0的点,都能排在前面的位置 删掉t-j的边,仅仅是j的入度

    2024年02月08日
    浏览(44)
  • acwing算法基础之搜索与图论--kruskal算法

    kruskal算法的关键步骤为: 将所有边按照权重从小到大排序。 定义集合S,表示生成树。 枚举每条边(a,b,c),起点a,终点b,边长c。如果结点a和结点b不连通(用并查集来维护),则将这条边加入到集合S中。 kruskal算法的时间复杂度为O(mlogm),它用来解决稀疏图的最小生成树问题

    2024年02月05日
    浏览(43)
  • acwing算法基础之动态规划--背包问题

    (零) 背包问题描述:有 N N N 个物品,每个物品的体积是 v i v_i v i ​ ,价值是 w i w_i w i ​ ,现有容量是 V V V 的背包,求这个背包能装下的物品的最大价值。 01背包问题:每个物品只有1个。 完全背包问题:每个物品有无穷多个。 多重背包问题:第 i i i 个物品有 s i s_i s

    2024年02月05日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包