头像

飞龙在天_1




离线:2小时前


最近来访(3)
用户头像
隹隹隹隹隹
用户头像
YHL29

活动打卡代码 AcWing 788. 逆序对的数量

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
using namespace std;//假定我们使用的归并排序的功能是既把数组排好序的同时,又同时把逆序对给找出来
const int N = 100010;
int n;
int q[N],tmp[N];  

long long  mergesort (int q[],int l ,int r){
    if(l >= r) return 0;
    int mid = (l+r) / 2;
    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])
            tmp[k++ ] = q[i++];
            else { 
                res +=mid-i+1;
                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];
    return res;
}
int main(){
    cin >> n;
    for(int i =0 ;i < n;i ++)
    cin>> q[i];
    cout << mergesort(q, 0,n -1);
    return 0;

}



题目描述

为什么要用归并排序呢?(学哥给予的解释)

因为数据范围是10的5次方,这就限制了时间复杂度要控制到O(nlogn)O(nlogn)以内,而朴实方法求逆序对的时间复杂度是O(n2)O(n2),这个可以参考冒泡排序,冒泡排序的本质就是消除所有逆序对的过程,冒泡排序就是O(n2)O(n2)的,而归并排序的时间复杂度是O(nlogn)O(nlogn),是满足题目要求的,这就是采取归并排序的原因

样例

#include<iostream>
#include<cstdio>
using namespace std;//假定我们使用的归并排序的功能是既把数组排好序的同时,又同时把逆序对给找出来
const int N = 100010;
int n;
int q[N],tmp[N];  

long long  mergesort (int q[],int l ,int r){
    if(l >= r) return 0;
    int mid = (l+r) / 2;
    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])
            tmp[k++ ] = q[i++];
            else { 
                res +=mid-i+1;
                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];
    return res;
}
int main(){
    cin >> n;
    for(int i =0 ;i < n;i ++)
    cin>> q[i];
    cout << mergesort(q, 0,n -1);
    return 0;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 796. 子矩阵的和

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
using namespace std;
const int N =1010;
int m,n,q;
int 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",&s[i][j]);
    for(int  i = 0;i <= n;i ++)
        for(int j =0 ;j <= m; j ++)
           s[i][j]=s[i- 1][j]+ s[i][j-1]- s[i -1][j -1]+ s[i][j]; 
    while(q--){
        int x1,x2,y1,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;

}


活动打卡代码 AcWing 792. 高精度减法

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B){//首先cmp最初的初始条件是认为A.size()是大于B.size()的,这样对下面else的描述比较会更好理解
    if(A.size() != B.size()) return A.size() > B.size();
    else {//如果A的size不等于B的size,则要从最高位开始比较
        for(int i = A.size() -1; i >= 0; i--)//理解第一条注释的含义,为什么这里是从A的元素开始,而不是B的
        if(A[i] != B[i])  return A[i]  > B[i];
    }
    return true;//AB 中的元素全部完全相等
}

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说明A[i]在借位的影响下(也有可能没有借位的影响只是简单的A中的这一位上的元素小于B中的这一位上的元素)
        else t = 0;
    }//注意减法与乘法的不同是减法的借位最大就是1,乘法可以大
      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)){
            vector<int> c = sub(A,B);
            for(int i = c.size()- 1;i>=0;i--)
            cout << c[i];
    }
    else{
        vector<int> c= sub(B,A);
        cout <<"-";
        for(int i =c.size() -1;i >=0;i --)
        cout << c[i];
    }

    return 0 ;

}



题目描述

详解

样例

#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B){//首先cmp最初的初始条件是认为A.size()是大于B.size()的,这样对下面else的描述比较会更好理解
    if(A.size() != B.size()) return A.size() > B.size();
    else {//如果A的size不等于B的size,则要从最高位开始比较
        for(int i = A.size() -1; i >= 0; i--)//理解第一条注释的含义,为什么这里是从A的元素开始,而不是B的
        if(A[i] != B[i])  return A[i]  > B[i];
    }
    return true;//AB 中的元素全部完全相等
}

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说明A[i]在借位的影响下(也有可能没有借位的影响只是简单的A中的这一位上的元素小于B中的这一位上的元素)
        else t = 0;
    }//注意减法与乘法的不同是减法的借位最大就是1,乘法可以大
      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)){
            vector<int> c = sub(A,B);
            for(int i = c.size()- 1;i>=0;i--)
            cout << c[i];
    }
    else{
        vector<int> c= sub(B,A);
        cout <<"-";
        for(int i =c.size() -1;i >=0;i --)
        cout << c[i];
    }

    return 0 ;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


题目讨论 AcWing 788. 求讲解

为什么要用归并排序呢这个题
我们只要找前面的数比后面的数小的不就行了,为什么还要用tmp数组去存排好序的数组呢
这有点迷糊




题目描述

详细解释

样例

#include<iostream>
#include<vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B){//首先cmp最初的初始条件是认为A.size()是大于B.size()的,这样对下面else的描述比较会更好理解
    if(A.size() != B.size()) return A.size() > B.size();
    else {//如果A的size不等于B的size,则要从最高位开始比较
        for(int i = A.size() -1; i >= 0; i--)//理解第一条注释的含义,为什么这里是从A的元素开始,而不是B的
        if(A[i] != B[i])  return A[i]  > B[i];
    }
    return true;//AB 中的元素全部完全相等
}

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说明A[i]在借位的影响下(也有可能没有借位的影响只是简单的A中的这一位上的元素小于B中的这一位上的元素)
        else t = 0;
    }//注意减法与乘法的不同是减法的借位最大就是1,乘法可以大
      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)){
            vector<int> c = sub(A,B);
            for(int i = c.size()- 1;i>=0;i--)
            cout << c[i];
    }
    else{
        vector<int> c= sub(B,A);
        cout <<"-";
        for(int i =c.size() -1;i >=0;i --)
        cout << c[i];
    }

    return 0 ;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



题目描述

子矩阵的和
1.显示S.[i][j]的意义变为从[i][j]这个点向左上全部元素的和
2.再由这个前提求出局部的矩阵和

样例

#include<iostream>
#include<cstdio>
using namespace std;
const int N =1010;
int m,n,q;
int 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",&s[i][j]);
    //1.显示S.[i][j]的意义变为从[i][j]这个点向左上全部元素的和       
    for(int  i = 0;i <= n;i ++)
        for(int j =0 ;j <= m; j ++)
           s[i][j]=s[i- 1][j]+ s[i][j-1]- s[i -1][j -1]+ s[i][j]; 
    //2.再由这个前提求出局部的矩阵和       
    while(q--){
        int x1,x2,y1,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;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



题目描述

样例

#include<iostream>
#include<cstdio>
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;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 787. 归并排序

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
using  namespace std;
const int N = 1e6+10;
int n;
int q[N],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);
    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这个条件
    while(j <= r)    tmp[k++] =q[j++];//说明符合的是i< mid这个条件
    //上面两步说明左右数列其中一个遍历完了之后,把剩下那个没遍历完的剩下的部分直接补到tmp数组里
    for(int i = l,j =0;i <= r; i++,j++)
    q[i] =tmp[j];

}
int main(){
    scanf("%d",&n);
    for(int i = 0;i< n;i ++)    scanf("%d",&q[i]);
    merge_sort(q,0,n - 1);
    for(int i = 0; i < n;i ++)   printf("%d",q[i]);
    return 0;


}