头像

CHarming_lyyqqq


访客:821

离线:1天前


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N = 1010;
int main()
{
    int arr[N][N], n, m, q, pre[N][N];
    cin >> n >> m >> q;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)      cin >> arr[i][j];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)     pre[i][j] = arr[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
    }
    while(q--)
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1]);
    }
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int>& A, int b, int& r)
{
    int t = 0;
    vector<int> res;
    for(int i = 0; i < A.size(); i++)
    {
        r = r * 10 + A[i];
        res.push_back(r / b);
        r %= b;
    }
    reverse(res.begin(), res.end());
    while(res.size() > 1 && res.back() == 0)    res.pop_back();
    return res;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = 0; i < a.size(); i++)  A.push_back(a[i] - '0');
    int r = 0;
    auto res = div(A, b, r);
    for(int i = res.size() - 1; i >= 0; i--)     cout << res[i];
    cout << endl << r;
    return 0;
}


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

#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool cmp(string& a, string& b)
{
    if(a.size() != b.size())    return a.size() > b.size();
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] != b[i])     return a[i] > b[i];
    }
    return true;
}
vector<int> sub(vector<int>& a, vector<int>& b)
{
    int n = a.size();
    vector<int> res;
    for(int i = 0, t = 0; i < n; i++)
    {
        t = a[i] - t;
        if(i < b.size())    t -= b[i];
        res.push_back((t + 10) % 10);
        if(t < 0)   t = 1;
        else    t = 0;
    }
    while(res.size() > 1 && res.back() == 0)      res.pop_back();
    return res;
}
int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> 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');
    vector<int> res;
    if(cmp(a, b))   res = sub(A, B);
    else
    {
        cout << "-";
        res = sub(B, A);
    }
    for(int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    return 0;
}


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

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

vector<int> mult(vector<int>& a, int b)
{
    int n = a.size(), t = 0;
    vector<int> res;
    for(int i = 0; i < n; i++)
    {
        t += (a[i] * b);
        res.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        res.push_back(t % 10);
        t /= 10;
    }
    while(res.size() > 1 && res.back() == 0)    res.pop_back(); 
    return res;
}
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 res = mult(A, b);
    for(int i = res.size() - 1; i >= 0; i--)     cout << res[i];
    return 0;
}



题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(压位) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int base = 1e9;
vector<int> Add(vector<int>& A, vector<int>& B)
{
    if(A.size() < B.size())     return Add(B, A);
    int m = A.size(), n = B.size(), t = 0;
    vector<int> res;
    for(int i = 0; i < m; i++)
    {
        t += A[i];
        if(i < n)   t += B[i];
        res.push_back(t % base);
        t /= base;
    }
    if(t)   res.push_back(t);
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1, j = 0, s = 0, t = 1; i >= 0; i--)
    {
        s += (a[i] - '0') * t;
        t *= 10, j++;
        if(i == 0 || j == 9)
        {
            A.push_back(s);
            j = s = 0;
            t = 1;
        }
    }
    for(int i = b.size() - 1, j = 0, s = 0, t = 1; i >= 0; i--)
    {
        s += (b[i] - '0') * t;
        t *= 10, j++;
        if(i == 0 || j == 9)
        {
            B.push_back(s);
            j = s = 0;
            t = 1;
        }
    }
    auto res = Add(A, B);
    cout << res.back();      //输出第一个存的数,有可能不足9位,所以先输出
    for(int i = res.size() - 2; i >= 0; i--)
    {
        printf("%09d", res[i]);  //必须按9位不足补0格式输出, 有的数字实际达不到9位,但是对应于结果里相当于在前面加0
    }
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include<iostream>
using namespace std;
const double eps = 1e-8;
int main()
{
    double n;
    cin >> n;
    bool flag = true;
    if(n < 0) 
    {
        n *= -1.0;
        flag = false;
    }
    if(n <= 1.0)
    {
        double l = 0.0, r = 1.0;
        while(r - l >= eps)
        {
            double mid = (l + r) / 2.0;
            if(mid * mid * mid <= n)    l = mid;
            else    r = mid;
        }
        if(flag)    printf("%lf", l);
        else    printf("-%lf", l);
    }
    else
    {
        double l = 1.0, r = n;
        while(r - l >= eps)
        {
            double mid = (l + r) / 2.0;
            if(mid * mid * mid <= n)    l = mid;
            else    r = mid;
        }
        if(flag)    printf("%lf", l);
        else    printf("-%lf", l);
    }
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include<iostream>
using namespace std;
const int N = 1e5+10;
int main()
{
    int n, m, q[N];
    cin >> n >> m;
    for(int i = 0; i < n; i++)  cin >> q[i];
    for(int i = 1; i <= m; i++)
    {
        int target;
        cin >> target;
        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(q[mid] >= target)    r = mid;
            else    l = mid + 1;
        }
        if(q[l] != target)
        {
            cout << -1 << " " << -1 << endl;
            continue;
        }
        cout << l << " ";
        l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] <= target)     l = mid;
            else    r = mid - 1;
        }
        cout << l << endl;
    }
    return 0;
}






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

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


活动打卡代码 AcWing 786. 第k个数

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int q[N];
int check(int l, int r, int k)
{
    if(l == r)  return q[l];
    int i = l - 1, j = r + 1, x = q[(l+r)/2];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j)   swap(q[i], q[j]);
    }
    int cnt = j - l + 1;
    if(k <= cnt)    return check(l, j, k);
    else    return check(j + 1, r, k - cnt);
}
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)  cin >> q[i];
    int ans = check(0, n - 1, k);
    cout << ans;
    return 0;
}


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

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int q[N], pre[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
    {
        cin >> q[i];
        pre[i] = pre[i-1] + q[i];
    }
    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l-1] << endl;
    }
    return 0;
}