syh_9

阅读量

+关注发消息

离线：2小时前

最近来访(0)

新鲜事原文

AcWing《考研算法辅导课》拼团优惠！https://www.acwing.com/activity/content/introduction/48/group_buy/149918/

活动打卡代码 AcWing 798. 差分矩阵

syh_9
4天前

                #include<iostream>

using namespace std;

const int N = 1010;

int n,m,q;

int a[N][N],b[N][N];


void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

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 ++)
            insert(i,j,i,j,a[i][j]);

    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1,y1,x2,y2,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 ++)
        printf("%d ",b[i][j]);
        puts(" ");
    }
}

            

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

syh_9
8天前

                确定分界点
递归排序 left right
归并合二为一 数组合并

#include<iostream>

using namespace std;

const int N = 100010;

int n,m;

int q[N],tmp[N];

void merge_sort(int l,int r,int q[])
{
    if(l >= r) return ;

    int mid = (l + r) / 2;

    merge_sort(l,mid,q),merge_sort(mid + 1,r,q);

    int i = l,j = mid + 1,k = 0;
    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; j ++, i ++) q[i] = tmp[j];

}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n ; i ++) scanf("%d",&q[i]);

    merge_sort(0,n - 1, q);

    for(int i = 0; i < n ; i ++) printf("%d ",q[i]);
}

            

活动打卡代码 AcWing 785. 快速排序

syh_9
8天前

                确定分界点 q[l] q[(l + r) / 2] q[r] 随机
调整区间
递归处理左右两段

#include<iostream>

using namespace std;

const int N = 100010;

int n,m;

int q[N];




void quick_sort(int l, int r,int q[])
{
    if(l >= r) return;

    int x = q[(l + r) / 2],i = l - 1,j = r + 1;
    while(i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x); //注意这是j--
        if(i < j) swap(q[i],q[j]);
    }
    quick_sort(l,j,q);
    quick_sort(j + 1,r,q);
}


int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++) scanf("%d",&q[i]);

    quick_sort(0,n - 1,q);

    for(int i = 0; i < n; i ++) printf("%d ",q[i]);
}

            

活动打卡代码 AcWing 797. 差分

syh_9
8天前

                #include<iostream>

using namespace std;

const int N = 100010;

int n,m;

int a[N],b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}


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 ++) insert(i,i,a[i]);

    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);

        insert(l,r,c);
    }

    for(int i = 1; i <= n ; i ++) b[i] += b[i - 1];
    for(int i = 1; i <= n ; i ++) printf("%d ",b[i]);

}

            

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

syh_9
9天前

两个公式:
s[i][j] = s[i - 1][j] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j]

s[x2][y2] = s[x1 - 1][y2] + s[x2][y1 - 1] - s[x1 - 1][y1 - 1]

#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]);
    }
}

活动打卡代码 AcWing 795. 前缀和

syh_9
10天前

                前缀和:
思路:
a[n] 从 1 开始赋值
s[0] = 0
定义两个数组 a[n] s[n]  s[i] = s[i - 1]  + a[i]
公式:[l,r] -----> s[r] - s[l - 1]


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

            

活动打卡代码 AcWing 794. 高精度除法

syh_9
11天前

include[HTML_REMOVED]

using namespace std;

vector[HTML_REMOVED] div(vector[HTML_REMOVED] &A,int &b,int &r)
{
vector[HTML_REMOVED] 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;
int r;
cin >> a >> b;
vector [HTML_REMOVED] 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 --) printf("%d",C[i]);
cout << endl;
printf("%d",r);

}

活动打卡代码 AcWing 793. 高精度乘法

syh_9
11天前

include[HTML_REMOVED]

using namespace std;

vector[HTML_REMOVED] mul(vector[HTML_REMOVED] A,int b)
{
vector[HTML_REMOVED] C;
int t = 0;
if(b==0)
{
C.push_back(0);
return C;
}
for(int i = 0; i < A.size() || t; i ++)
{
if(i < A.size())t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}

return C;

}

int main()

{
string a;
int b;
cin >> a >> b;
vector [HTML_REMOVED] 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]);

}

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

syh_9
12天前

include[HTML_REMOVED]

using namespace std;

bool cmp(vector[HTML_REMOVED] &A,vector[HTML_REMOVED] &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[HTML_REMOVED] sub(vector[HTML_REMOVED] &A,vector[HTML_REMOVED] &B)
{
vector[HTML_REMOVED] 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);
    if(t < 0) t = 1;
    else t = 0;
}

while(C.size() > 1 && C.back() == 0) C.pop_back();

return C;

}

int main()
{
vector[HTML_REMOVED] A,B;
string 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]);
}

}