头像

恒心


访客:1925

离线:1天前



恒心
6个月前

题目

给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续区间,输出它的长度。

输入格式

第一行包含整数n。

第二行包含n个整数(均在0~100000范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。

数据范围

1≤n≤100000

输入样例:

5
1 2 2 3 5

输出样例:

3

分析

双指针算法:
其优化思路是:将一个朴素方法O(n^2)优化成一个O(n)的方法
关键是怎么找到其满足的性质
for i = 0 ,j = 0, i < n
while(j < i && check(i,j)) && 操作 j
更新相关参数

编码

#include <iostream>

using namespace std;

#define N 100010

int a[N], s[N]; //a存储数组,s存储每个数字出现的次数
int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    int res = 0;
    for(int i = 0, j = 0; i < n; ++i){
        s[a[i]]++;
        while(j < i && s[a[i]] > 1) s[a[j++]]--; //记住这步很重要
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}



恒心
6个月前

题目

输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。

输出格式

共一行,包含n个整数,表示最终序列。

数据范围

1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000

分析

1.对数组进行初始化操作: a[1] a[2] a[3] a[4] ...... a[n]
2.对数组进行差分结果是: a[1] a[2] -a[1] a[3] - a[2] a[4] - a[3] ...... a[n] - a[n - 1]
差分性质:
差分性质探索:
3.对数组中[l,r]区间每个数进行添加c: a[1] + c a[2] + c a[3] + c a[4] + c a[5] + c ...... a[n] + c
4.对进行差分操作: a[1] + c a[2] -a [1] ..... a[n] - a[n - 1] a[n + 1] - a[n] -c

Coding

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];
int l,r,c;

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--){
       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]);
    return 0;
}



恒心
6个月前

题目

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数n,m,q。
接下来n行,每行包含m个整数,表示整数矩阵。
接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。

输出格式

共q行,每行输出一个询问的结果。

数据范围

1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,

−1000≤矩阵内元素的值≤1000

输入样例:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例:

17
27
21

分析

假定:a[n][m]为矩阵, b[n][m]为矩阵的前缀和
1. 要知道矩阵中的每项的前缀和是怎么计算?

b[n][m] = b[n - 1][m] + b[n][m - 1] - a[n - 1][m -1];
  1. 要知道怎么计算任意两点之间的区域怎么计算?
x1, y1, x2, y2
S{[x1, y1],[x2, y2]} = b[x2][y2] + b[x1 - 1][y1 - 1] - b[x1 - 1][y2] - b[x2][y1 - 1];
记住:这里是包含b[x1][y1]这个点,所以减去的是b[x1 - 1][y1 - 1]的这块面积

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[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)
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];

    while(q--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        cout << b[x2][y2] + b[x1 - 1][y1 - 1] - b[x1 - 1][y2] - b[x2][y1 - 1] << endl;
    }
    return 0;
}

这份代码中,多开了一份前缀和空间,我们可以进行优化!

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int b[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",&b[i][j]);
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; 
        }

    while(q--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        cout << b[x2][y2] + b[x1 - 1][y1 - 1] - b[x1 - 1][y2] - b[x2][y1 - 1] << endl;
    }
    return 0;
}

优化思路:因为b[i][j]是横向进行计算的,所以每个B[i - 1][j], b[i][j - 1]是前缀和, b[i][j]是矩阵元素,所以
进行优化!妙!




恒心
7个月前

题目

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

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

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

输入格式

第一行包含两个整数n和m。

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

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

输出格式

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

数据范围

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

分析

  1. 采用空间换时间的思想
  2. 通过o(n)来存储前缀和
  3. 进行求解的时候,可以o(1)来快速求解任意连续段内的数值和

代码

#include <iostream>

using namespace std;

const int N = 100010;

int a[N], b[N];

int n, m;

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



恒心
7个月前

题目

给定两个正整数,计算它们的和。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的和。

数据范围

1≤整数长度≤100000 

输入样例:

12
23

输出样例:

35

分析

1.将string类型视为int型的大容器
2.将string转为vector[HTML_REMOVED]进行存储
3.两个数相加,迭代公式{
压栈数 = (数A的第i位 + 数B的第i位 + 进位) % 10;//余数
t = (数A的第i位 + 数B的第i位 + 进位) / 10;//商
}

Coding

#include <iostream>
#include <vector>

using namespace std;

vector<int> myadd(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;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0'); // 转为vetor<int>存储
    for(int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');
    auto C = myadd(A, B);
    for(int i = C.size() - 1; i >= 0; --i) cout << C[i];
    cout << endl;
    return 0;
}



恒心
7个月前

题目

给定一个浮点数n,求它的三次方根。

输入格式

共一行,包含一个浮点数n。

输出格式

共一行,包含一个浮点数,表示问题的解。

注意,结果保留6位小数。

数据范围

−10000≤n≤10000

输入样例:

1000.00

输出样例:

10.000000

分析

1.注意精度,一般是取所要求的精度的后面加两个0
2.mid * mid * mid 不能用 mid^3来表示
3.抽象理解:从边界空间的两侧向中间搜寻,寻找满足性质P的点

Coding

#include <iostream>

int main(){
    double x;
    scanf("%lf",&x); //double 就是%lf格式
    double L = -10000.00, R = 10000.00;
    double mid = (L + R) / 2;
    while(R - L > 1e-8){
        mid = (R + L) / 2;
        if(mid * mid *mid >= x) R = mid;
        else L = mid;
    }
    printf("%lf\n",mid); //%lf的精度是小数点后6位
    return 0;
}



恒心
7个月前

题目描述

给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。

输入格式

第一行包含整数n和q,表示数组长度和询问个数。
第二行包含n个整数(均在1~10000范围内),表示完整数组。
接下来q行,每行包含一个整数k,表示一个询问元素。

输出格式

共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回“-1 -1”。

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例:

6 3
1 2 2 3 3 4
3
4
5

输出样例:

3 4
5 5
-1 -1

解析

  1. 起初的想法就是一个一个左右进行寻找,找到所查询的值就停止,查不到就返回”-1 -1”
    代码如下:
#include <iostream>

using namespace std;

const int N = 100010;
int n, c;
int q[N];

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

    while(c--){
        int w;
        cin >> w;
        int i = 0, j = n - 1;
        while(i < n && q[i++] < w );
        while(j >= 0 && q[j--] > w);

        if(i < n && j >= 0 && q[i] == w && q[j] == w){
            cout << i - 1 << " " << j + 1<< endl;
        }else{
            cout << "-1 -1" << endl;
        }
    }
    return 0;
}

但是缺点是,耗时太严重了!
2.二分查找有一个作用,可以快速定位到左右两侧最外端的符合的数值

#include <iostream>

using namespace std;

const int N = 100010;

int n, c;
int q[N];

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

    while(c--){
        int w;
        cin >> w;
        int i = 0, j = n - 1;
        while(i < j){
            int mid = (i + j) >> 1;
            if(q[mid] >= w) j = mid;
            else i = mid + 1;
        }
        if(q[i] != w){
            cout << "-1 -1" << endl;
        }else{
            cout << i << " ";
            i = 0, j = n - 1;
            while(i < j){
                int mid = (i + j + 1) >> 1;
                if(q[mid] <= w) i = mid;
                else j = mid - 1;
            }
            cout << j << endl;
        }
    }

    return 0;
}



恒心
7个月前

题目描述

给定一个长度为n的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数n,表示数列的长度。

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

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1≤n≤100000

输入样例:

6
2 3 4 5 6 1

输出样例:

5

解析

1.理解逆序对的概念,即(i,j) => (i > j)
2.知道逆序对分布情况 (i,j)存在左侧,存在右侧,存在两侧
3.定义每个子函数的作用: 排序 + 统计逆序对数
4.实现归并两侧有序数组 + 统计逆序对数

实现

#include <iostream>

using namespace std;

const int N = 1e5;
int n;
int q[N], tmp[N];
typedef long long LL; //注意:在完全逆排序数组的情况下,返回值会过爆int最大值

LL merge_sort(int q[], int L, int R){
    LL res = 0;
    if(L >= R) return res;

    int mid = L + R >> 1;
    int k = 0, i = L, j = mid + 1;
    res = res + merge_sort(q, L, mid) + merge_sort(q, mid + 1, R);
    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(q, 0, n - 1);
    return 0;
}



恒心
7个月前

题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行,第一行包含整数 n。

第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。

输出格式
输出共一行,包含 n 个整数,表示排好序的数列。

数据范围
1≤n≤100000

输入样例

输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5

解析

归并思路:
1.选取中间数值
2.sort()中间数值的左右两端
3.借助一个temp变量,进行归并排序
3.将temp变量赋值给原始数组

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n;
int q[N], temp[N];

void merge_sort(int q[], int L, int R){
    if(L >= R) return; //边界判断

    int mid = (L + R) >> 1; // 选取中间值

    merge_sort(q, L, mid); //sort左侧数组
    merge_sort(q, mid + 1, R); //sort右侧数组

    int index1 = L, index2 = mid + 1, index3 = 0; //index1为左侧数组的游标,index2为右侧数组的游标,index3为temp数组的游标
    while(index1 <= mid && index2 <= R)
        if(q[index1] <= q[index2]) temp[index3++] = q[index1++];
        else temp[index3++] = q[index2++];

    //如果index2已经到达R的位置
    while(index1 <= mid) temp[index3++] = q[index1++];
    //如果index1已经到达mid的位置
    while(index2 <= R) temp[index3++] = q[index2++];

    //从temp数组中拷贝数据到q数组中
    for(int i = L, j = 0; i <= R; ++i, ++j) q[i] = temp[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;
}



恒心
7个月前

题目

给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。

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

第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。

输出格式
输出一个整数,表示数列的第k小数。

输入格式

数据范围

1≤n≤100000,
1≤k≤n 

输入样例:

5 3
2 4 1 5 3

输出样例:

3

解析

此题思路和快排类似
1.在数组中选取一个随机值(我们这里选取中间值)
2.将小于选取的值放在左边,将大于选取的值的放在右边
3.每次的迭代的时候,进行选择迭代。
if(k <= sl){
迭代左侧
}else{
迭代右侧
}

C++代码

#include <iostream>

using namespace std;

const int N = 1e5; //设置数组的大小

int n, k;
int q[N];

int quick_select(int q[], int L, int R, int k){
    if(L == R) return q[L];

    int x = q[(L + R) >> 1];
    int i = L - 1;
    int j = R + 1;
    while(i < j){
        while(q[++i] < x);
        while(q[--j] > x);
        if( i < j) swap(q[i], q[j]);
    }
    int sl = j - L + 1;
    if(sl >= k) return quick_select(q, L, j, k);   // 迭代左侧
    else return quick_select(q, j + 1, R, k - sl); // 迭代右侧
}

int main(){
    cin >> n >> k;

    for(int i = 0; i < n; ++i) cin >> q[i];

    cout << quick_select(q, 0, n - 1, k) << endl;

    return 0;
}