头像

Sniper02


访客:2864

离线:6天前



Sniper02
4个月前

一开始写的代码只过了小部分样例, 如果数很大的话就WA了。
下面是一开始的代码:

C++ 代码

#include<iostream>
#include<vector>

using namespace std;

vector<int> a;

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

    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }

    int maxSum = -1e9, sum, ansDep = 1;
    for(int i = 0, j = 1, dep = 1; i < a.size(); i++, dep++){
        sum = 0;
        for(int k = i, m = 0; k < a.size() && m < j; m++,k++) sum += a[k];
        if(maxSum < sum){
            maxSum = sum;
            ansDep =  dep;
        }
        j *= 2;
        i = j - 2;
    }

    cout << ansDep << endl;

    return 0;
}

下面是改后的代码将maxSumsum 都定义为long long类型的了。

C++ 代码

#include<iostream>
#include<vector>

using namespace std;

vector<int> a;

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

    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }

    long long maxSum = a[0], sum;
    int ansDep = 1;
    for(int i = 0, j = 1, dep = 1; i < a.size(); dep++){
        sum = 0;
        for(int k = i, m = 0; k < a.size() && m < j; m++,k++) sum += a[k];
        if(maxSum < sum){
            maxSum = sum;
            ansDep =  dep;
        }

        j *= 2;
        i = j - 1;
    }

    cout << ansDep << endl;

    return 0;
}




Sniper02
4个月前

算差的最大公约数。然后求出数列元素的个数

一开始写的时候最后输出是这样的:

    cout << max((a[n - 1] - a[0])/t + 1 , n)<< endl;

有个样例是

3
1 1 1

这样的话,就输出1了,但应该输出3
所以当输出小于n,的时候,一定是等差数列,要输出n
所以最后改成了这样

    cout << max((a[n - 1] - a[0])/t + 1 , n)<< endl;

C++ 代码

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

using namespace std;

const int N = 1e5 + 10;

//a存样例并排序。
//b存a中相邻的元素值的差,并去重排序
vector<int> a, b;
int n;

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b, a%b);
}


int main(){
    int x;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }

    sort(a.begin(), a.end());

    //处理差
    for(int i = 1; i < a.size(); i++){
        b.push_back(a[i] - a[i - 1]);
    }

    sort(b.begin(), b.end());

    b.erase(unique(b.begin(), b.end()), b.end());

    //求多个数的最大公因数
    int t = 1;
    for(int i = 1; i < b.size(); i++){
        t = gcd(b[i], b[i - 1]);
        b[i] = t;
    }

    cout << max((a[n - 1] - a[0])/t + 1 , n)<< endl;
    return 0;
}

后面可以这么写

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

using namespace std;

const int N = 1e5 + 10;

//a存样例并排序。
//b存a中相邻的元素值的差,并去重排序
vector<int> a, b;
int n;

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b, a%b);
}


int main(){
    int x;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }

    sort(a.begin(), a.end());

    //处理差
    for(int i = 1; i < a.size(); i++){
        b.push_back(a[i] - a[i - 1]);
    }

    sort(b.begin(), b.end());

    b.erase(unique(b.begin(), b.end()), b.end());

    if(b[0] == 0){
        cout << n << endl;
        return 0;
    }

    //求多个数的最大公因数
    int t = 1;
    for(int i = 1; i < b.size(); i++){
        t = gcd(b[i], b[i - 1]);
        b[i] = t;
    }

    cout << (a[n - 1] - a[0])/t + 1 << endl;
    return 0;
}





Sniper02
4个月前

算法

区间合并

Image.png
如果st == -2e9 的话, 相当于传入的segs是个空的,就什么也不放进去,这样segs.size() == 0 相当于没有区间。
这里的 if(st != -2e9) 说明传入了至少有一个区间。

遍历segs时遇到一个新而且在外面的区间,要先push进去上一个维持的区间res.push_back({st, ed});
(如果没有上一个区间,即st == -2e9,就不放了,直接维持遇到的这个空间),
然后更新遇到的这个新的区间为当前维持的区间。
最后遍历完了,退出时最后正在维持的区间也要push进去。所以遍历完还有一句
if(lt != -2e9) res.push_back({lt, ed});

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs){
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int lt = -2e9, ed = -2e9;
    for(auto seg : segs){
        if(seg.first > ed){
            if(lt != -2e9) res.push_back({lt, ed});
            lt = seg.first;
            ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }

    if(lt != -2e9) res.push_back({lt, ed});

    segs = res;
}

int main(){
    vector<PII> segs;
    int n;
    cin >> n;

    while(n--){
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

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

    return 0;
}

陈哥说这个是个贪心的题目,下面是另一个思路也一样的code
对左端点排序以后, 能合并的就合并,不能合并的就新开一个区间。
陈哥的题解




Sniper02
4个月前

算法

离散化
vector<int> alls; //存储所有待离散化的值
sort(alls.begin(), alls.end());//将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());//去掉重复元素
  1. 有n个数, m个查询, 所以有 n + 2m 个坐标
    这里n 和 m 的范围都是1e5内, 所以 数组a 和 前缀和s数组都定义为 3e5 + 10。
  2. a中可能有重复的元素。unique 返回去重后的下标。最后 erase 掉多余的
  3. 用二分求出x离散化后的值

*: 注意的是处理前缀和的时候, s数组从1开始存储, 但是总坐标的个数还是alls.size()不变, 所以是i <= alls.size() ‘=’ 号不能少。

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

C++ 代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10;
int a[N], s[N];
int n, m;

vector<int> alls;
vector<PII> query, add;

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 r + 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());

    //处理add
    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);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}




Sniper02
4个月前

位运算

x & -x = x & (~x + 1)
       x = 101...100...0
      ~x = 010...01....1
    ~x+1 = 010...10....0
x&(~x+1) = 0....010....0

C++ 代码

#include<iostream>

using namespace std;

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

    int res;
    while(n--){
        res = 0;
        scanf("%d", &x);
        for(int i = x; i; i -= i & -i) res++;
        cout << res << ' ';
    }

    return 0;
}



Sniper02
4个月前

算法1

(暴力枚举) $O(n*m)$

暴力会超时

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x;

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

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i] + b[j] == x){
                cout << i << ' ' << j << endl;
                return 0;
            }
        }
    }

    return 0;
}

算法2

i从左往右找, j 从往左找

时间复杂度

O(n)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x;

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

    for(int i = 0, j = m - 1; i < n; i++){
        while(j >= 0 && b[j] + a[i] > x) j--;
        if(a[i] + b[j] == x){
            cout << i << ' ' << j << endl;
            return 0;
        }
    }

    return 0;
}



Sniper02
4个月前

算法

双指针算法

板子

for(int i = 0, j = 0; i < n; i++){
    while(j <= i && check(i, j) j++;

    //后面+每道题的逻辑
}

a数组存输入的样例, s数组当前维持的区间内下标的数字出现的个数。
这道题中, check(i, j) 是 s[a[i]] > 1 。s[a[i]]表示当前维持的这个区间里面, a[i] 这个数字出现的次数。
如果当前维持的这个区间里面, a[i] 这个数字出现的次数大于1, j(左边的指针)就要向右挪一个单位,挪动的时候,先让s数组里s[a[j]]--, 再挪动j, 这两步可以写成s[a[j++]]--
j 永远不会超过i, 当j == i 的时候,代表维持的那个区间就一个数, 所以check(i, j)是false, while就会结束。
所以这里while里只需要写check(i, j) 就可以了。

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];
int n;

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

    int res = 0;
    for(int i = 0, j = 0; i < n; i++){
        s[a[i]]++;
        while(s[a[i]] > 1) s[a[j++]]--;
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}



Sniper02
4个月前

题目描述

输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上c。

请你将进行完所有操作后的矩阵输出。

输入格式
第一行包含整数n,m,q。

接下来n行,每行包含m个整数,表示整数矩阵。

接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。

输出格式
共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000

输入样例

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例

2 3 4 1
4 3 4 1
2 2 2 2

算法

二维差分应用——差分矩阵
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;

将样例存储在s数组中, 可以将s数组理解为二维前缀和数组,
然后构造b数组, 可以将b数组理解为二维差分数组,
然后根据题目要求修改二维b数组,
最后再求一下修改后的二维b数组的二维前缀和数组并输出就好了。

C++ 代码

#include<iostream>

using namespace std;

const int N = 1010;
int b[N][N], s[N][N];
int n, m, q, x1, y1, x2, y2, c;

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(){
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i, j, i, j, s[i][j]);

    while(q--){
        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]; 
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}



Sniper02
4个月前

题目描述

输入一个长度为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

输入样例

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例

3 4 5 3 4 2

算法

差分

bl + c 会使 s1 + c , s2 + c, s3 + c …
br+1 - c 会使 sr+1 - c , sr+2 -c…
bl + c 和 br - c 结合 就可以指定s数组[l,r]中的元素都+c了

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int n, m, l, r, c;
int b[N], s[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", &s[i]);

    for(int i = 1; i <= n; i++) insert(i, i, s[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;
}



Sniper02
4个月前

题目描述

输入一个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

算法

子矩阵的和

构造前缀和矩阵:s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

计算子矩阵的和s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

C++ 代码

#include<iostream>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];
int n, m, q, x1, y1, x2, y2;

int main(){
    cin >> 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--){
        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]);
    }

    return 0;
}