NO.1 基础算法
包括,排序,二分,高精度,前缀和与差分,双指针,位运算,离散化,区间合并
#include<iostream>
using namespace std;
const int N =1e5+9;
int arr[N];
void quick_sort(int arr[],int l,int r){
if(l>=r)return ;
int i=l-1,j=r+1,x=arr[l+r>>1];
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
if(i<j) swap(arr[i],arr[j]);
}
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++)printf("%d ",arr[i]);
return 0;
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int arr[N],tmp[N];
void merge_sort(int arr[],int l,int r){
if(l>=r)return ;
int mid=l+r >>1;
merge_sort(arr,l,mid);
merge_sort(arr,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
if(arr[i]<=arr[j])tmp[k++]=arr[i++];
else tmp[k++]=arr[j++];
}
while(i<=mid)tmp[k++]=arr[i++];
while(j<=r)tmp[k++]=arr[j++];
for(int i=0;i<k;i++)arr[l+i]=tmp[i];
}
int main(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
merge_sort(arr,0,n-1);
for(int i=0;i<n;i++)printf("%d ",arr[i]);
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int arr[N];
int main(){
int n,q;scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
int l,r,x;
while(q--){
scanf("%d",&x);
l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(arr[mid]>=x)r=mid;
else l=mid+1;
}
if(arr[l]!=x)cout<<"-1 -1\n";
else {
cout<<l<<' ';
l=0,r=n-1;
while(l<r){
int mid= l+r+1 >>1;
if(arr[mid]<=x)l=mid;
else r=mid-1;
}
cout<<l<<'\n';
}
}
}
#include<iostream>
using namespace std;
int main(){
double n,ans;
scanf("%lf",&n);
double l=-1e4,r=1e4;
while(r-l >= 1e-8){
double mid= (l+r) /2;
if(mid*mid*mid <n)l=mid;
else r=mid;
}
printf("%.6lf",l);
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int> a,b;
string A,B;
vector<int> high_plus(vector<int> &a,vector<int> &b){
if(a.size()<b.size())return high_plus(b,a);
vector<int>c;
int res=0;
for(int i=0;i<a.size();i++){
res+=a[i];
if(i<b.size())res+=b[i];
c.push_back(res%10);
if(res>=10)res=1;
else res=0;
}
if(res)c.push_back(res);
return c;
}
int main(){
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=high_plus(a,b);
for(int i=c.size()-1;i>=0;i--)cout<<c[i];
}
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
vector<int> a,b;
string A,B;
bool cmp(vector<int> &a,vector<int> &b){
if(a.size()!=b.size())return a.size()>b.size();
for(int i=a.size()-1;i>=0;i--)if(a[i]!=b[i])return a[i]>b[i];
return 1;
}
vector<int> high_minus(vector<int>&a,vector<int>&b){
if(!cmp(a,b)){cout<<'-';return high_minus(b,a);}
vector<int>c;
int res=0;
for(int i=0;i<a.size();i++){
res+=a[i];
if(i<b.size())res-=b[i];
c.push_back((res+10)%10);
if(res<0)res=-1;
else res=0;
}
while(c.back()==0 && c.size()>1)c.pop_back();
return c;
}
int main(){
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=high_minus(a,b);
for(int i=c.size()-1;i>=0;i--)cout<<c[i];
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
string A;
int b;
vector<int>a;
vector<int> high_multiply(vector<int> &a,int b){
vector<int>c;
int res=0;
for(int i=0;i<a.size()||res;i++){
if(i<a.size())res=a[i]*b+res;
c.push_back(res%10);
res/=10;
}
while(c.size()>1 && c.back()==0)c.pop_back();
return c;
}
int main(){
cin>>A>>b;
for(int i=A.size()-1;i>=0;i--)a.push_back(A[i]-'0');
auto c=high_multiply(a,b);
for(int i=c.size()-1;i>=0;i--)cout<<c[i];
}
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<int> high_divive(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;
}
int main(){
vector<int>a;
string A;
int b,r=0;
cin>>A>>b;
for(int i=A.size()-1;i>=0;i--)a.push_back(A[i]-'0');
auto c=high_divive(a,b,r);
for(int i=c.size()-1;i>=0;i--)cout<<c[i];
cout<<"\n"<<r;
}
#include<iostream>
using namespace std;
const int N=1e3+9;
int arr[N][N],Sum[N][N];
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&arr[i][j]);
Sum[1][1]=arr[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
Sum[i][j]=Sum[i-1][j]+Sum[i][j-1]+arr[i][j]-Sum[i-1][j-1];
int x1,y1,x2,y2;
while(q--){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",Sum[x2][y2]-Sum[x2][y1-1]-Sum[x1-1][y2]+Sum[x1-1][y1-1]);
}
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int arr[N],d[N];
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
for(int i=1;i<=n;i++) d[i]=arr[i]-arr[i-1];
int l,r,q;
while(m--){
scanf("%d%d%d",&l,&r,&q);
d[l]+=q;d[r+1]-=q;
}
for(int i=1;i<=n;i++){
arr[i]=d[i]+arr[i-1];
cout<<arr[i]<<' ';
}
}
#include<iostream>
using namespace std;
const int N=1e3+9;
int arr[N][N],d[N][N];
void in(int x1,int y1,int x2,int y2,int q){
d[x1][y1]+=q;
d[x1][y2+1]-=q;
d[x2+1][y1]-=q;
d[x2+1][y2+1]+=q;
}
int main(){
int n,m,q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&arr[i][j]);
in(i,j,i,j,arr[i][j]);
}
int x1,x2,y1,y2,x;
while(q--)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&x);
in(x1,y1,x2,y2,x);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[i][j]=d[i][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
cout<<d[i][j]<<' ';
}
cout<<"\n";
}
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int arr[N],s[N];
int main(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
int ans=0;
for(int i=0,j=0;i<n;i++){
s[arr[i]]++;
while(s[arr[i]]>1){
s[arr[j++]]--;
}
ans=max(i-j+1,ans);
}
cout<<ans;
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int a[N],s[N], n,m;
int main(){
int x;scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)scanf("%d",&s[i]);
for(int i=0,j=m-1;i<n;i++){
while(a[i]+s[j]>x && j>=0)j--;
if(a[i] +s[j] ==x && j>=0){
cout<<i<<' '<<j ;
break;
}
}
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int a[N],s[N];
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)scanf("%d",&s[i]);
int i=0;
for(int j=0;j<m;j++){
if(a[i]==s[j] && i<n)i++;
}
if(i==n)cout<<"Yes";
else cout<<"No";
}
#include<iostream>
using namespace std;
int lowerbit(int x){
return x &-x;
}
int main(void ){
int n;scanf("%d",&n);
int x,res=0;
while(n--){
scanf("%d",&x);
while(x>0){
x-=lowerbit(x);
res++;
}
cout<<res<<' ';
res=0;
}
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+9;
int a[N],s[N];
vector<int> alls;
vector<pair<int ,int>> add,query;
int find(int x){
int l=0,r=alls.size()-1;
while(l<r){
int mid = l+r>>1;
if(x<=alls[mid])r=mid;
else l=mid+1;
}
return l+1;
}
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
int x,l;scanf("%d%d",&x,&l);
alls.push_back(x);
add.push_back({x,l});
}
for(int i=0;i<m;i++){
int l,r;scanf("%d%d",&l,&r);
alls.push_back(l);
alls.push_back(r);
query.push_back({l,r});
}
//去重
sort(alls.begin(),alls.end());
alls.erase( unique(alls.begin(),alls.end()),alls.end());
for(auto item:add){
int x=find(item.first);
a[x]+=item.second;
}
for(int i=1;i<=alls.size();i++){
s[i]=a[i]+s[i-1];
}
for(auto item: query ){
int l=find(item.first),r=find(item.second);
cout<<s[r]-s[l-1]<<'\n';
}
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void merge(vector<pair<int,int>> &a){
sort(a.begin(),a.end());
int st=-2e9,ed=-2e9;
vector<pair<int,int>>res;
for(auto i:a){
if(ed<i.first){
if(st !=-2e9)res.push_back({st,ed});
st=i.first,ed=i.second;
}
else ed=max(i.second,ed);
}
if(st !=-2e9)res.push_back({st,ed});
a=res;
}
int main(){
vector<pair<int,int>> segs;
int n,l,r;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&l,&r);
segs.push_back({l,r});
}
merge(segs);
cout<<segs.size();
}