头像

二月




离线:2020-05-19 09:18


最近来访(16)
用户头像
889
用户头像
_Airヾ梦及丨
用户头像
狗头人挖土豆
用户头像
TonyStank
用户头像
tideline
用户头像
puyagang
用户头像
._723
用户头像
bluehat
用户头像
归期
用户头像
257973846
用户头像
LC.
用户头像
Teardrop
用户头像
IceCola丶
用户头像
糖豆
用户头像
无聊滑稽
用户头像
是雪菜啊


二月
2019-11-01 07:24

程序说明

alls 用于储存增加和查询的所有数轴上的点, sum 用于保存前缀和结果,
add 保存需要添加的操作,包括数轴位置和值,query 保存询问的左右边界

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int find (const vector<int>& alls, const int& x)
{
    int l = 0, r = alls.size()-1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

int main ()
{
    // 读入n和m
    int n, m;
    scanf ("%d%d", &n, &m);

    vector<int> sum(n + 2 * m + 1, 0), alls;
    vector<PII> add, query;

    // 读入数据
    for (int i = 0; i < n; i++)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }

    //排序并去重
    sort (alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 预处理,将alls的数据映射到1 — n + 2*m
    for (int i = 0; i < add.size(); i++)
    {
        int idx = find(alls, add[i].first);
        sum[idx] += add[i].second;
    }

    // 求前缀和
    for (int i = 1; i < sum.size(); i++)
        sum[i] += sum[i-1];

    // 查询
    for (int i = 0; i < query.size(); i++)
    {
        int l = find(alls, query[i].first);
        int r = find(alls, query[i].second);
        printf ("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;

}



二月
2019-10-31 02:29

时间复杂度o(n)

c++代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// res = A / b, r = A % b;
string div(const string& A, const int& b, int& r)
{
    string res;

    for (int i = 0; i < A.size(); i++)
    {
        r = r * 10 + (A[i] - '0');
        res += (r / b) + '0';
        r %= b;
    }

    while (res.size() > 1 && res.front() == '0') res = res.substr(1);

    return res;
}

int main ()
{
    ios::sync_with_stdio(false);
    string A;
    int b;

    cin >> A >> b;

    int r = 0;

    cout << div(A, b, r) << endl;
    cout << r << endl;
    return 0;
}



二月
2019-10-31 02:12

使用string存储大数与结果,并进行处理

时间复杂度o(n)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// res = A * B
string mul(const string& A, const int b)
{
    string res;

    for (int i = A.size() - 1, t = 0; i >= 0 || t > 0; i--)
    {
        if (i >= 0) t += (A[i] - '0') * b;
        res += (t % 10) + '0';
        t /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main ()
{
    ios::sync_with_stdio(false);
    string A;
    int b;
    cin >> A >> b;
    cout << mul(A, b) << endl;
    return 0;
}



二月
2019-10-30 09:50

C++11 代码

使用string处理大数的减法

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string sub(const string& A, const string& B)
{
    string C;
    int t = 0;

    for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
    {
        if (i >= 0) t = (A[i] - '0') - t;
        if (j >= 0) t -= (B[j] - '0');
        C += ((t + 10) % 10 + '0');
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == '0') C.pop_back(); 
    reverse(C.begin(), C.end());
    return C;
}

bool cmp(const string& A, const 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;
}

int main ()
{
    ios::sync_with_stdio(false);

    string A, B;
    cin >> A >> B;

    if (cmp(A, B)) cout << sub(A, B) << endl;
    else cout << "-" << sub(B, A) << endl;

    return 0;
}



二月
2019-10-30 09:21

算法分析

使用string完成大数存储和加法操作。

时间复杂度 o(n)

c++代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// C = A + B;  
string add(const string& A, const string& B)
{
    string C;
    int t = 0;
    for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
    {
        if (i >= 0) t += (A[i] - '0');
        if (j >= 0) t += (B[j] - '0');
        C += ((t % 10) + '0');
        t /= 10;
    }

    reverse(C.begin(), C.end());
    return C;
}

int main()
{
    ios::sync_with_stdio(false);
    string A, B;
    cin >> A >> B;
    cout << add(A, B) << endl;
    return 0;
}




二月
2019-10-29 09:11

题目描述

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

接下来再输入m个询问,每个询问输入一对l, r。

对于每个询问,输出原序列中从第l个数到第r个数的和。

输入格式
第一行包含两个整数n和m。

第二行包含n个整数,表示整数数列。

接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。

输出格式
共m行,每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

样例

5 3
2 1 3 6 4
1 2
1 3
2 4
答案:
3
6
10

算法1

目前能想到的最省空间和时间的做法
#include <iostream>
#include <vector>

using namespace std;

int main ()
{
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> sum(n+1, 0);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &sum[i]);
        sum[i] += sum[i - 1];
    }
    while (q--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r] - sum[l-1]);
    }
    return 0;
}

时间复杂度 o(n)