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