AcWing基础算法课Level-2 第一讲 基础算法
快速排序
AcWing 785. 快速排序5475人打卡
AcWing 786. 第k个数4874人打卡
归并排序
AcWing 787. 归并排序4776人打卡
AcWing 788. 逆序对的数量4107人打卡
二分
AcWing 789. 数的范围4414人打卡
AcWing 790. 数的三次方根4110人打卡
高精度
AcWing 791. 高精度加法3796人打卡
AcWing 792. 高精度减法3410人打卡
AcWing 793. 高精度乘法3258人打卡
AcWing 794. 高精度除法3081人打卡
前缀和与差分
AcWing 795. 前缀和4087人打卡
AcWing 796. 子矩阵的和3806人打卡
AcWing 797. 差分3742人打卡
AcWing 798. 差分矩阵3349人打卡
双指针算法
AcWing 799. 最长连续不重复子序列3687人打卡
AcWing 800. 数组元素的目标和3402人打卡
AcWing 2816. 判断子序列1977人打卡
位运算
AcWing 801. 二进制中1的个数3669人打卡
离散化
AcWing 802. 区间和2833人打卡
区间合并
AcWing 803. 区间合并
代码
AcWing 785. 快速排序
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
void QuickSort(int a[], int n, int l, int r){
if(l > r)return ; //递归出口,越界返回
int k = a[l];//k就是基准数(k的选取与内循环的找数顺序有关)
int i = l, j = r;//区间
while(i < j){ //i==j时,两数相遇,
//顺序有影响,先从右往左找,找到第一个比基准数小的位置
while(i<j && a[j]>=k)j--;//切记‘>=’(可以忽略掉与k相等的值,不然i永远不会大于j,则死循环)
//然后从左往右找到第一个比基准数大的位置
while(i<j && a[i]<=k)i++;
//如果他们没有相遇,就交换这两个数的位置,并继续寻找
if(i < j)swap(a[i],a[j]);
}
//将基准数归位
a[l] = a[i]; //相遇的位置
a[i] = k; //
QuickSort(a,n,l,i-1);//递归后不用考虑基准数
QuickSort(a,n,i+1,r);
}
int n, a[maxn];
int main(){
int n; scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
//QuickSort(a,n,1,n);
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++)
printf("%d ",a[i]);
return 0;
}
AcWing 786. 第k个数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
int n, a[maxn];
int main(){
int n,k; scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
//QuickSort(a,n,1,n);
sort(a+1,a+n+1);
cout<<a[k];
return 0;
}
AcWing 787. 归并排序
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
void MergeSort(int a[], int n, int l, int r){
if(l == r)return ;
int mid = l+r>>1;
MergeSort(a,n,1,mid);
MergeSort(a,n,mid+1,r);
int i = 1, j = mid+1;
int c[r-l+1], k = 1;
while(i <= mid && j <= r){
if(a[i]<a[j])c[k++] = a[i++];
else c[k++] = a[j++];
}
while(i <= mid)c[k++] = a[i++];
while(j <= r)c[k++] = a[j++];
for(int i = l; i <= r; i++)
a[i] = c[i];
}
int n, a[maxn];
int main(){
int n; scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
//MergeSort(a,n,1,n);
sort(a+1,a+n+1);
for(int i = 1; i <= n; i++)
printf("%d ",a[i]);
return 0;
}
AcWing 788. 逆序对的数量
#include<iostream>
using namespace std;
const int maxn = 500010;
int a[maxn]; long long ans = 0;
void MergeSort(int l, int r){
if(l >= r)return ;
int m = l+r>>1;
MergeSort(l,m);
MergeSort(m+1,r);
int i = l, j = m+1;
int t[r-l+1], k = 0;
while(i<=m && j<=r){
if(a[i]<=a[j])t[k++]=a[i++];
else{
t[k++] = a[j++];
ans += m-i+1;//加上剩余元素个数
}
}
while(i<=m)t[k++]=a[i++];
while(j<=r)t[k++]=a[j++];
for(i=l, k=0; i <= r; i++,k++)a[i]=t[k];
}
int main(){
int n; cin>>n;
ans = 0;
for(int i = 1; i <= n; i++)cin>>a[i];
MergeSort(1,n);
cout<<ans<<"\n";
return 0;
}
AcWing 789. 数的范围
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int a[maxn];
int main(){
int n, q; cin>>n>>q;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= q; i++){
int x; cin>>x;
int l = lower_bound(a+1,a+n+1,x)-a;
int r = upper_bound(a+1,a+n+1,x)-a;
if(l==n+1||a[l]!=x)cout<<"-1 -1\n";
else{
cout<<l-1<<" "<<r-2<<"\n";
}
}
return 0;
}
AcWing 790. 数的三次方根
#include<bits/stdc++.h>
using namespace std;
int main(){
double a;
scanf("%lf",&a);
printf("%.6lf",cbrt(a));
return 0;
}
AcWing 791. 高精度加法
//Add Template
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 100010;
int a[maxn], b[maxn], c[maxn];
int main(){
string s1, s2; cin>>s1>>s2;
a[0] = s1.size(); b[0] = s2.size();
for(int i = 1; i <= a[0]; i++)a[i]=s1[a[0]-i]-'0';
for(int i = 1; i <= b[0]; i++)b[i]=s2[b[0]-i]-'0';
c[0] = max(a[0],b[0])+1;
for(int i = 1; i <= c[0]; i++){
c[i] += a[i]+b[i];
if(c[i] >= 10){
c[i] %= 10;
c[i+1]++;
}
}
while(c[0]>1 && c[c[0]]==0)c[0]--;
for(int i = c[0]; i >= 1; i--)cout<<c[i];
return 0;
}
AcWing 792. 高精度减法
//Sub Template
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn], c[maxn];
int main(){
string s1, s2; cin>>s1>>s2;
if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2)){
cout<<"-"; swap(s1,s2);
}
a[0] = s1.size(); b[0] = s2.size();
for(int i = 1; i <= a[0]; i++)a[i]=s1[a[0]-i]-'0';
for(int i = 1; i <= b[0]; i++)b[i]=s2[b[0]-i]-'0';
c[0] = max(a[0],b[0])+1;
for(int i = 1; i <= c[0]; i++){
if(a[i]<b[i]){ a[i+1]--; a[i]+=10; }
c[i] = a[i]-b[i];
}
while(c[0]>1 && c[c[0]]==0)c[0]--;
for(int i = c[0]; i >= 1; i--)cout<<c[i];
return 0;
}
AcWing 793. 高精度乘法
#include <algorithm> // max
#include <cassert> // assert
#include <cstdio> // printf,sprintf
#include <cstring> // strlen
#include <iostream> // cin,cout
#include <string> // string类
#include <vector> // vector类
using namespace std;
struct BigInteger {
typedef unsigned long long LL;
static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;
BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
BigInteger(LL num = 0) {*this = num;}
BigInteger(string s) {*this = s;}
BigInteger& operator = (long long num) {
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while (num > 0);
return *this;
}
BigInteger& operator = (const string& str) {
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for (int i = 0; i < len; i++) {
int end = str.length() - i*WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start,end-start).c_str(), "%d", &x);
s.push_back(x);
}
return (*this).clean();
}
BigInteger operator + (const BigInteger& b) const {
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
BigInteger operator - (const BigInteger& b) const {
assert(b <= *this); // 减数不能大于被减数
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = s[i] + g;
if (i < b.s.size()) x -= b.s[i];
if (x < 0) {g = -1; x += BASE;} else g = 0;
c.s.push_back(x);
}
return c.clean();
}
BigInteger operator * (const BigInteger& b) const {
int i, j; LL g;
vector<LL> v(s.size()+b.s.size(), 0);
BigInteger c; c.s.clear();
for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
for (i = 0, g = 0; ; i++) {
if (g ==0 && i >= v.size()) break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
BigInteger operator / (const BigInteger& b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
BigInteger m; // 余数:初始化为0
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return c.clean();
}
BigInteger operator % (const BigInteger& b) const { //方法与除法相同
BigInteger c = *this;
BigInteger m;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return m;
}
// 二分法找出满足bx<=m的最大的x
int bsearch(const BigInteger& b, const BigInteger& m) const{
int L = 0, R = BASE-1, x;
while (1) {
x = (L+R)>>1;
if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
else R = x;
}
}
BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}
bool operator < (const BigInteger& b) const {
if (s.size() != b.s.size()) return s.size() < b.s.size();
for (int i = s.size()-1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator >(const BigInteger& b) const{return b < *this;}
bool operator<=(const BigInteger& b) const{return !(b < *this);}
bool operator>=(const BigInteger& b) const{return !(*this < b);}
bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};
ostream& operator << (ostream& out, const BigInteger& x) {
out << x.s.back();
for (int i = x.s.size()-2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
istream& operator >> (istream& in, BigInteger& x) {
string s;
if (!(in >> s)) return in;
x = s;
return in;
}
int main(){
BigInteger a, b;
cin>>a>>b;
cout<<a*b<<"\n";
return 0;
}
AcWing 794. 高精度除法
//高精除低精
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int a[maxn], b, c[maxn], r;
int main(){
string s; cin>>s>>b;
string ss = to_string(b);
if(s.size()<ss.size() ||ss.size()==s.size()&&s<ss){
cout<<"0\n"<<s; return 0;
}
int n = s.size();
for(int i = 0; i < n; i++)a[i]=s[i]-'0';
for(int i = 0; i < n; i++){
r = r*10+a[i];
c[i] = (r/b);
r = r%b;
}
//while(!c[n] && n>1)n--;
int d = 0; while(!c[d] && d<=n-1)d++;
for(int i = d; i <= n-1; i++)cout<<c[i];
cout<<"\n"<<r<<"\n";
return 0;
}
AcWing 795. 前缀和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
typedef long long LL;
LL a[maxn], f[maxn], sum, ans;
int main(){
ios::sync_with_stdio(false);
int n, q; cin>>n>>q;
for(int i = 1; i <= n; i++){
cin>>a[i]; f[i] = f[i-1]+a[i];
}
for(int i = 1; i <= q; i++){
int l, r; cin>>l>>r;
cout<<f[r]-f[l-1]<<"\n";
}
return 0;
}
AcWing 796. 子矩阵的和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn][maxn], s[maxn][maxn];
int main(){
int n, m, q;
cin>>n>>m>>q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
for(int i = 1; i <= q; i++){
int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<"\n";
}
return 0;
}
AcWing 797. 差分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], s[maxn];
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= n; i++){
cin>>a[i]; s[i]=a[i]-a[i-1];
}
for(int i = 1; i <= m; i++){
int l, r, c; cin>>l>>r>>c;
s[l]+=c; s[r+1]-=c;
}
for(int i = 1; i <= n; i++){
s[i] = s[i-1]+s[i];
cout<<s[i]<<" ";
}
return 0;
}
AcWing 798. 差分矩阵
/*差分矩阵：
+ b[i][j]+=x表示从(i,j)到(n,m)之后每个数前缀和后都会加上x。
+ 前缀和则是(1,1)到(i,j)求和，是差分的逆运算。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010, inf=1e9+10;
int a[maxn][maxn], b[maxn][maxn];
int main(){
int n, m, q; cin>>n>>m>>q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
b[i][j] += a[i][j];
b[i+1][j] -= a[i][j];
b[i][j+1] -= a[i][j];
b[i+1][j+1] += a[i][j];
}
}
for(int i = 1; i <= q; i++){
int x1, y1, x2, y2, c;
cin>>x1>>y1>>x2>>y2>>c;
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<b[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
AcWing 799. 最长连续不重复子序列
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], s[maxn];
int main(){
int n; cin>>n;
int d = 0, ans = -1;
for(int i = 1; i <= n; i++){
cin>>a[i]; s[a[i]]++;
while(s[a[i]]>1){ s[a[d]]--; d++;}
ans = max(ans, i-d+1);
}
cout<<ans<<"\n";
return 0;
}
AcWing 800. 数组元素的目标和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
int main(){
int n, m, x;
cin>>n>>m>>x;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= m; i++)cin>>b[i];
int l = 1, r = m;
while(l <= n){
//cout<<l<<" "<<r<<"\n";
while(r>=1 && a[l]+b[r]>x)r--;
if(r>=1 && a[l]+b[r]==x)cout<<l-1<<" "<<r-1<<"\n";
l++;
}
return 0;
}
AcWing 2816. 判断子序列
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
int main(){
int n, m, x;
cin>>n>>m;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= m; i++)cin>>b[i];
int d = 1;
for(int i = 1; i <= m; i++)
if(b[i]==a[d])d++;
if(d==n+1)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
AcWing 801. 二进制中1的个数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn], b[maxn];
int main(){
int n; cin>>n;
for(int i = 1; i <= n; i++){
int x; cin>>x;
int cnt = 0;
while(x){
if(x&1==1)cnt++;
x >>= 1;
}
cout<<cnt<<" ";
}
return 0;
}
AcWing 802. 区间和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10, inf=1e9+10;
map<int,int>ma;
vector<pair<int,int>>vc;
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= n; i++){
int x, c; cin>>x>>c;
if(!ma.count(x))ma[x] = c;
else ma[x] += c;
}
int sum = 0;
for(pair<int,int> x : ma){
vc.push_back(make_pair(x.first,sum));
sum += x.second;
}
vc.push_back(make_pair(inf,sum));
for(int i = 1; i <= m; i++){
int l, r; cin>>l>>r;
auto p1 = upper_bound(vc.begin(),vc.end(),make_pair(l,-inf));
auto p2 = upper_bound(vc.begin(),vc.end(),make_pair(r,inf));
cout<<p2->second-p1->second<<"\n";
}
return 0;
}
AcWing 803. 区间合并
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10, inf=1e9+10;
vector<pair<int,int>>vc;
int main(){
int n; cin>>n;
for(int i = 0; i < n; i++){
int l, r; cin>>l>>r;
vc.push_back(make_pair(l,r));
}
sort(vc.begin(),vc.end());
int cnt = 1, t = vc[0].second;
for(int i = 1; i < n; i++){
if(vc[i].first>t){
cnt++;
t = vc[i].second;
}else t = max(t,vc[i].second);
}
cout<<cnt<<"\n";
return 0;
}