AcWing

1、快排排序#include<iostream>using namespace std;const int N = 1e6 + 10;int n;int q[N];void quick_sort(int q[], int l, int r){if (l >= r) return;int x = q[(l + r) / 2],i = l - 1,j = r + 1;while(i

Driven_Pluto

115人浏览 · 2022-05-26 23:46:14

Driven_Pluto · 2022-05-26 23:46:14 发布

1、快排排序

#include<iostream>
using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int x = q[(l + r) / 2],i = l - 1,j = r + 1;
    while(i < j){
        while(q[++i] < x);
        while(q[--j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j + 1, r);
}
int main(){
    
    scanf("%d",&n);
    for(int i = 0;i < n;i++)scanf("%d",&q[i]);
    
    quick_sort(q, 0 , n-1);
    for(int i = 0 ;i < n ; i++) printf("%d ",q[i]);
    return 0;
}

2、归并排序

const int N = 1000010;
int tmp[N];
void merge_sort(int q[],int l,int r){
  if(l >= r) return;
  //中间数
  int mid = l + r >> 1;
  //分治
  merge_sort(q,l,mid),merge_sort(q,mid + 1,r);
  //k是数组中的个数，i是左端起点，j是右段起点
  int k = 0,i = l, j = mid + 1;
  while(i <= mid && j <= r){
    //如果左边值小与右边，将值赋给数组
    if(q[i] < q[j]){
      tmp[k++] = q[i++];
    }else{
      tmp[k++] = q[j++];
    }
  }
  while(i <= mid) tmp[k++] = q[i++];
  while(j <= r) tmp[k++] = q[j++];
  //最后将新数组值赋给以前数组
  for(int i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
}

3、二分查找

给定一个按照升序排列的长度为 n 的整数数组，以及 q个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数。

#include<iostream>
using namespace std;
const int N = 1000010;
int n,m;
int q[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++)scanf("%d",&q[i]);
    while(m--){
       int x;
       scanf("%d",&x);
       int l = 0,r = n -1;
       while(l < r){
           int mid = (l + r) >> 1;
           if (q[mid] >= x) r = mid;
           else l = mid + 1;
       }
       if (q[l] != x) cout << "-1 -1" << endl;
       else{
           cout << l << ' ';
           int l = 0,r = n - 1;
           while(l < r){
               int mid = (l + r + 1) >> 1;
               if (q[mid] <= x) l = mid;
               else r = mid - 1;
           }
           cout << l <<endl;
       }
    }
    
    return 0;
}

4、浮点数求平方根

#include <iostream>
using namespace std;
int main(){
  double x;
  cin >> x;
  double l = 0, r = x;
  while(r - l >= 1e-8){
    double mid = (l + r) / 2;
    if (mid * mid >= x) r = mid;
    else l = mid;
  }
  printf("%lf",l);
  return 0;
}

5、第K个数

int quicke_sort(int l,int r,int k){
  if(l == r) return q[l];
  int x = q[l],i = l - 1, j = r + 1;
  while(i < j){
    while(q[++i] < x);
    while(q[--j] > x);
    if(i < j) swap(q[i],q[j]);
  }
  int s1 = j - l + 1;
  if(k <= s1) return quick_sort(l,j,k);
  else return quick_sort(j + 1,r,k - s1);
}
int main(){
  cin >> n >> k;
  for(int i = 0;i < n;i++)cin >> q[i];
  cout << quick_sort(0,n - 1,k) << endl;
  return 0;
}

6、逆序对的数量

给定一个长度为 nn 的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 ii 个和第 jj 个元素，如果满足 i<ji<j 且 a[i]>a[j]a[i]>a[j]，则其为一个逆序对；否则不是。

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int q[N],tmp[N];
LL merge_sort(int l,int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int res = merge_sort(l,mid) + merge_sort(mid + 1,r);
    
    int k = 0,i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k ++] = q[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for(int i = l, j = 0;i <= r;i++,j++) q[i] = tmp[j];
    return res;
}
int main(){
    cin >> n;
    for(int i = 0;i < n;i++)cin >> q[i];
    cout << merge_sort(0,n - 1) << endl;
    return 0 ;
}

7、数的三次方

#include <iostream>
using namespace std;
int main (){
    double x;
    cin >> x;
    
    double l = -10000,r = 10000;
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf ",l);
    
    return 0;
}

8、高进位加法

#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 /= 10;
    }
    if(t) C.push_back(1); //最高位有没有进位
    return C;
}
int main (){
    string a, b;
    vector<int> A,B;
    cin >> a >> b; //a= "123456"
    for(int i = a.size() - 1;i >= 0;i--)A.push_back(a[i] - '0'); //"654321"
    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--)printf("%d",C[i]);
    return 0;
}

9、高进位减法

#include<iostream>
#include<vector>
using namespace std;

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

vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int>C;
    for(int i = 0,t = 0;i < A.size();i++){
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1; //如果进位小于0，借一位
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0)C.pop_back(); //高位0去掉
    
    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)){
        auto C = sub(A,B);
        for(int i = C.size() - 1;i >= 0;i--)printf("%d",C[i]);
    }else{
        auto C = sub(B,A);
        printf("-");
        for(int i = C.size() - 1;i >= 0;i--)printf("%d",C[i]);
    }
    
    return 0;
}

10、高进位乘法

#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;
        C.push_back((t % 10));
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0)C.pop_back();
    return C;
}
int main(){
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    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--)printf("%d",C[i]);
    return 0;
}

11、高位除法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//r是余数
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];
        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(){
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = a.size() - 1;i >= 0;i--) A.push_back(a[i] - '0');
    int r;
    auto C = div (A,b,r);
    for(int i = C.size() - 1;i >= 0;i--)printf("%d",C[i]);
    cout << endl << r << endl;
    return 0;
}

12、前缀和

#include<iostream>
using namespace std;
const int N = 100010;

int n,m;
int a[N],s[N];
int main(){
    scanf("%d%d",&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;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

13、数组前缀和

输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个询问，每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

#include<iostream>
using namespace std;

const int N = 1010;
int n,m,q;
int a[N][N],s[N][N];
int main(){
    scanf("%d%d%d",&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;
       scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
       printf("%d\n",s[x2][y2] - s[x1 - 1][y2] - s[x2][y1-1] + s[x1- 1][y1 - 1]);
    }
    return 0;
}

14、输入一个长度为 n 的整数序列。

接下来输入 mm 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 c。

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],s[N];

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++)cin >> a[i];
    for(int i = 1;i <= n;i++)s[i] = s[i - 1] + a[i];
    
    while(m--){
        int l,r;
        cin >> l >> r;
        printf("%d\n",s[r] - s[l - 1]);
    }
    return 0;
}

15、798差分矩阵_HomeWork

#include <iostream>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],s[N][N];

int main(){
    scanf("%d%d%d",&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][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2] - s[x2][y1 - 1] -s[x1 - 1][y2] + s[x1 - 1][y1 - 1] );
    }
    return 0;
}

16、797

输入一个长度为 nn 的整数序列。

接下来输入 mm 个操作，每个操作包含三个整数 l,r,cl,r,c，表示将序列中 [l,r][l,r] 之间的每个数加上 cc。

#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
        
    }
    int l,r,c;
    while(m--){
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c;
    }
    for(int i = 1;i <= n;i++)a[i] = b[i] + a[i - 1];
    for(int i = 1;i <= n;i++)printf("%d ",a[i]);
    return 0;
}

天启AI社区

GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。

更多推荐

对近期接触到的直播相关知识进行梳理

M3U8 文件是 HLS (HTTP Live Streaming) 协议的核心组件，它本质上是一个播放列表文件，包含媒体流的结构信息。直播与视频聊天的对比：我觉得直播是通过流媒体技术把现场的图像和声音采集后分发出去，供观众在线围观，可以认为是开放的，一般没有人数限制；而视频聊天是点对点的线上交流，是基于UDP/TCP的实时传输协议实现的。流媒体是通过互联网实时传输音视频内容的技术，用户无需等待完