头像

以梦为马


访客:10895

离线:30分钟前


活动打卡代码 AcWing 2. 01背包问题

以梦为马
7小时前
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N];

int main(){
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n;i ++) cin >> v[i] >>w[i];

    for(int i = 1; i <= n; i ++)
         for(int j = m; j >= v[i]; j --){
             f[j] = max( f[j], f[j - v[i]] + w[i]);
         }

    cout << f[m] << endl;

    return 0;
}




以梦为马
7小时前

区间合并

给定 n 个区间 [li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式

第一行包含整数n。

接下来n行,每行包含两个整数 l 和 r。

输出格式

共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围

1≤n≤100000,
−109≤li≤ri≤109

输入样例:

5
1 2
2 4
5 6
7 8
7 9

输出样例:

3

主要考点

区间合并

C ++代码

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

using namespace std;
typedef pair<int, int> PII;

vector<PII> segs;
int n;

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());

    int l = -2e9, r = -2e9;//动态维护的区间
    for(auto seg : segs){
        if(r < seg.first){
            if(l != -2e9) res.push_back({l, r});
            l = seg.first, r = seg.second;
        }else{
            r = max(r, seg.second);
        }
    }
    if(l != -2e9) res.push_back({l, r});//将最后一个区间加入到答案中
    segs = res;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}


分享 离散化

以梦为马
8小时前

离散化用途

数组范围很大,但是数组中用到的数却不是很多的情况

离散化步骤

1. 排序 ---- 便于处理
2. 去重 ---- 可能有重复元素
3. 二分 ---- 查找离散化后在新数组中的下标

离散化模板

vector<int> alls; // 存储离散化后的值
sort(alls.begin(),alls.end()); //排序
//unique () return An iterator to the element that follows the last element not removed.
alls.erase(unique(alls.begin(), alls.end()), alls,end()); //去重

//二分求出x对应的离散化的值
int find(int x) //找到第一个大于等于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 r+1; //映射到1,2,...,n
}

unique()函数可以自己实现:

vector<int>::iterator unique(vector<int> &a)
{
    int j=0;
    for(int i=0;i<a.size();i++)
        if(!i || a[i] != a[i-1])
            a[j++] = a[i];
    //a[0]~a[j-1]所有a中不重复的数
    return a.begin()+j;
}

经典案例

区间和

refenrence




以梦为马
8小时前

题目描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。

现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。

接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。

输入格式

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

接下来 n 行,每行包含两个整数x和c。

再接下里 m 行,每行包含两个整数l和r。

输出格式

共m行,每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000

输入样例:

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

输出样例:

8
0
5

主要考点

离散化前缀和

C ++ 代码

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

using namespace std;
const int N = 300010;

typedef pair<int, int> PII;

vector<PII> add, query;//分别为添加和询问操作
vector<int> alls;//离散化后的数组
int a[N], s[N];//s[]为前缀和数组,a[]为某个元素的值
int n, m;

//二分查找指定元素的下标
int find(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;//映射的下标从1开始,便于前缀和的处理
}

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

    for(int i = 0; i < n; i ++){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < m; i ++){
        int l, r;
        cin >> 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());
    //return An iterator to the element that follows the last element not removed.

    for(auto item : add){//在指定位置插入指定值
        int x = find(item.first);
        a[x] += item.second;
    }

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

    for(auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}



以梦为马
11小时前

题目描述

给定一个长度为n的数列,请你求出数列中每个数的二进制表示中1的个数。

输入格式

第一行包含整数n。

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

输出格式

共一行,包含n个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围

1≤n≤100000,
0≤数列中元素的值≤109

输入样例:

5
1 2 3 4 5

输出样例:

1 1 2 1 2

C ++代码

#include <iostream>
#include <algorithm>

using namespace std;

int lowbit(int x){
    return x & -x;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        int x;
        cin >> x;
        int res = 0;
        while(x){
            x -= lowbit(x);
            res ++;
        }
        cout << res << ' ';
    }

    return 0;
}



以梦为马
12小时前

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例:

5
3 1 2 4 5

输出样例:

1 2 3 4 5

C ++ 代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1e6 + 10;

int q[N];
int n;

void quick_sort(int *q, int l, int r)
{
    if(l >= r)   return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j)   swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);

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

    quick_sort(q, 0, n-1);

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

    return 0;
}



以梦为马
12小时前

双指针算法

实用i,j两个变量,不会退的扫描一个数组

朴素做法 — $O(n)$

for(int i = 0; i < n; i ++){
    for(int j = 0; j < n; j ++)
}

双指针算法

for(int i=0,j=0;i<n;i++)
{
    while(j<i && check(i,j)) j++;
    //每道题目的具体逻辑
}

核心思想

将朴素做法$O(n^2)$优化为$O(n^2)$

常用类型

类型1: 同时指向两个序列, 例如归并排序的归并过程
类型2: 同时指向一个序列, 例如快排

经典案例

最长连续不重复子序列
归并排序
快速排序

reference




以梦为马
12小时前

题目描述

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

输入格式

第一行包含整数n。

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

输出格式

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

数据范围

1≤n≤100000

输入样例:

5
1 2 2 3 5

输出样例:

3

主要考点

双指针算法

双指针算法思路

  1. 先写出朴素算法$O(n^2)$
  2. 找到某种单调性,优化为$O(n^2)$

C ++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int a[N];
int s[N];//动态维护l ~ r中每个元素出现的次数
int n;

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

    int res = 0;
    for(int r = 0, l = 0; r < n; r ++){
        s[a[r]] ++;//l是距离r最左端点的位置
        while(s[a[r]] > 1){//l <= r恒成立,条件可省略
            s[a[l]] --;
            l ++;
        }
        res = max(res, r - l + 1);
    }

    cout << res << endl;

    return 0;
}



以梦为马
13小时前

题目描述

给定两个非负整数A,B,请你计算 A / B的商和余数。

输入格式

共两行,第一行包含整数A,第二行包含整数B。

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

1≤A的长度≤100000,
1≤B≤10000
B 一定不为0

输入样例:

7
2

输出样例:

3
1

C ++ 代码

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

using namespace std;

//计算A / b, 商是C,余数是r
vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    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();//去前导0

    return C;
}

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');

    int r = 0;
    vector<int> C = div(A, b, r);
    for(int i = C.size() - 1; i >= 0; i --) cout << C[i];
    cout << endl << r << endl;

    return 0;
}



以梦为马
13小时前

题目描述

给定两个正整数A和B,请你计算A * B的值。

输入格式

共两行,第一行包含整数A,第二行包含整数B。

输出格式

共一行,包含A * B的值。

数据范围

1≤A的长度≤100000,
0≤B≤10000

输入样例:

2
3

输出样例:

6

C ++ 代码

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b){
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() || t; i ++){
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();//去掉前导 0
    return C;
}

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');

    vector<int> C = mul(A, b);

    for(int i = C.size() - 1; i >= 0;  i --) cout << C[i];


    return 0;
}