devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯算法总结2_csdn蓝桥杯

作者：繁依Fanyi0 | 2024-03-22 06:29:11

赞

踩

csdn蓝桥杯

蓝桥杯A/B C ++组算法辅导课

图片已经完整上传。
算法题特点：

①模型少（相对）

②思维量大

③编写实际代码（尽可能AC）

解题流程：

①根据题目描述抽象出模型（dfs，贪心，DP模型，图论，排序，贪心等）

②判断模型是否可用（时间复杂度总共10^8左右，极端值是否正确）

递归

时间复杂度的计算：

master公式，根据递推关系，如T(n) = aT(n/b) + O(n^d)，则时间复杂度为O( n m a x ( l o g b a , d ) n^{max(log_ba, d)} nmax(logb​a,d))。O(n^d)为执行子程序所需要的时间。

img

如从1~n中挑选任意多个数，可能的方案有多少。

T(i) = (n - i + 1)T(i - 1) + O(1)。因此时间复杂度为O(n!)根据

数学知识

可以打表找规律。

动态规划DP

状态表示很重要，不同的状态表示下有不同的做法，简单的状态表示会让算法简单很多。无论是数位DP还是其他的各种DP问题，和简单的DP相比较就是根据状态表示不同而难度有差别。比如波动数列中利用同余的性质进行状态表示，又或者是地宫取宝中的四维的状态表示。

通常做DP问题的时候可以先考虑用dfs算法怎么做，然后根据dfs算法的各个参数来设置DP数组的维数以及使用的方法。一般来说，限制的条件越多，DP的数组的维数就越大。因为要表示的信息量增加了。

线段树和树状数组

树状数组能解决的问题包含于线段树，但是树状数组的代码很短、效率高

树状数组：只能解决快速求动态前缀和O(logn)

①给某个位置上的数加上一个数（单点修改）

②求某一个前缀和（区间查询，属性是个数）

算法原理

image-20230221143311323

c [ x ] = ∑ c [ i ] , i = 离 x 距离最近、层数比 x 小且未重复层数的数 c[x] =\sum{c[i]},i=离x距离最近、层数比x小且未重复层数的数 c[x]=∑c[i],i=离x距离最近、层数比x小且未重复层数的数

层数如何确定：x的二进制表示最后有k个0，如8:1000所以是第3层，

从上图来看可以知道c[x] = a[x-2^k：x]的和。

lowbit(x) = x & -x，因为-x是x的补码，就是反码加1，全部转过来后再+1就是x的最后一位不为0的数的2^k - 1。如图image-20230221141948499

那么就知道如果要求[a,b]区间的和，就可以算[1,b]-[1,a]。

a[1,b] = c[b] + c[b - lowbit[x]] + c[b - lowbit[lowbit[x]]] + c[1]，这样子就可以求得某个区间的前缀和了。

如果是修改原数组a的某个点x的话实际上就是还要修改c数组中x后面靠近x的所有层数不重复的c数组中的数，就是c[x + lowbit[x]]直到最高层，如上lowbit(x)的原理容易知道每次i = x + lowbit(x)后就可以让i为x后面最考近x的层数的值，一共logn层，因此求某个区间的前缀和和加某个位置上的数都是logn的时间复杂度。

image-20230221211655637

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], c[N];

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

// void init(){
//     for(int i = 1; i <=n; i ++){
//         for(int j = i; j <= n; j += lowbit(j)){
//             c[j] += a[i];
//         }
//     }
// }

void add(int x, int v){
    for(int i = x; i <= n; i += lowbit(i)){
        c[i] += v;
    }
}

int sum(int l, int r){
    int res = 0;
    for(int i = r; i > 0; i -= lowbit(i)){
        res += c[i];
    }
    for(int i = l - 1; i > 0; i -= lowbit(i)){
        res -= c[i];
    }
    return res;    
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) add(i, a[i]);
    
    // init();
    
    while(m --){
        int op;
        cin >> op;
        int i, j;
        cin >> i >> j;
        if(op == 1){
            add(i, j);
        }
        else{
            cout << sum(i, j) << endl;
        }
    }
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
线段树（最大值，面积，长度等等都可以用）

①某个位置发生变化（单点修改）

②区间查询（这里的区间查询的东西是可以自己定义的，如最值，个数等），O(logn)但是常数要稍微大一些。

四个函数都是递归着调用的。

image-20230221215025220

例题同上

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int n, m, w[N];
struct Node{
    int l, r;
    int sum;
}tr[N * 4];

void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[(u << 1) | 1].sum;
}

void build(int u, int l, int r){//build构建线段树这棵树。就是从1到n往下递归设置左边界，右边界和属性，然后一层一层返回的时候更新上面的信息。
    if(l == r) tr[u] = {l, r, w[r]};
    else{
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l ,mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r){
    if(tr[u].l >= l && tr[u]. r <= r) return tr[u].sum;//需要搜索的区间已经大于现在结点的区间了，就把现在结点的区间信息返回。
    
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    //否则就将现在结点从中间劈开，看下劈开后的左儿子是否是完整包含的，右儿子是否是完整包含的。
    if(l <= mid) sum = query(u << 1, l, r);
    if(r >= mid + 1) sum += query(u << 1 | 1, l, r);
    return sum;
}

void modify(int u, int x, int v){
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x >= mid + 1) modify(u << 1 | 1, x, v);
        else modify(u << 1, x, v);
        pushup(u);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    build(1, 1, n);
    while(m --){
        int op;
        cin >> op;
        int a, b;
        cin >> a >> b;
        if(op == 1) modify(1, a, b);
        else cout << query(1, a, b) << endl;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

小朋友排队

归并算法

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
struct Child{
    int h, idx;
    long long move;//当前孩子的高度，当前孩子的位置，当前孩子移动的距离。
}temp[N], child[N];
int n;

void merge_sort(int l, int r){
    if(l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1;
    int k = 0;
    int m;
    while(i <= mid && j <= r){
        if(child[i].h <= child[j].h){
            temp[k ++] = child[i ++];
        }
        else{
            temp[k ++] = child[j ++];
        }
    }
    while(i <= mid) temp[k ++] = child[i ++];
    while(j <= r) temp[k ++] = child[j ++];
    
    for(int i = l, j = 0; i <= r; i ++, j ++){//更新每个孩子的信息。temp就是此次重新排列后孩子的位置顺序，i代表当前孩子的位置，child代表当前孩子移动的距离。当前位置孩子当前孩子移动的距离，是temp的id以前的移动距离加上现在位置-以前位置的距离。
        child[i] = {temp[j].h, i, temp[j].move + abs(temp[j].idx - i)};
    }
}



int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> child[i].h;
        child[i].idx = i;
    }
    
    merge_sort(0, n - 1);
    
    long long res = 0;
    
    for(int i = 0; i < n; i ++){
        res += (child[i].move + 1) * child[i].move / 2;
    }
    cout << res << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

树状数组

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], c[N], c1[N], c2[N];//c是树状数组，c1和c2分别是第i个前面有多少大于他的，i的后面有多少小于他的。
int lowbit(int x){
    return x & -x;
}

void add(int x, int v){
    for(int i = x; i <= N; i += lowbit(i)) c[i] += v;
}

int sum(int x){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) res += c[i];
    return res;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        a[i] ++;
        c1[i] = sum(N) - sum(a[i]);
        add(a[i], 1);
    }
    
    memset(c, 0 ,sizeof c);
    
    for(int i = n; i >= 1; i --){
        c2[i] = sum(a[i] - 1);
        add(a[i], 1);
    }
    long long res = 0;
    for(int i = 1; i <= n; i ++){
        res += (long long) (c1[i] + c2[i]) * (c1[i] + c2[i] + 1) / 2;
    }
    cout << res << endl;
    return 0;
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

油漆面积

核心思想：把原来的二维的坐标求面积换成了，根据x排序导入的y轴坐标，把x1,x2,y1,y2换成{x1,y1,y2,1},{x2,y1,y2,-1}。
每次用x[i] - x[i - 1]就是两个x中间的长度，然后通过线段树来计算从0到N上的面积，也就是根结点覆盖的面积，如果读入的是-1就代表之前还在的y的范围要被删除了。如果是1，就是现在读入的x和之前的x夹了新的y可以用来计算面积的。
而且cnt由于只有大于0和等于0的情况，如果等于零那么子结点长度就是0，反馈到父节点来说也是0。若果子节点不为0，那么覆盖的区域就是其本身的长度，反馈到父节点上，距离就是左儿子距离加右儿子距离。

image-20230222181639281

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;
int n;
struct Segment{
    int x, y1, y2;
    int k;
    bool operator <(Segment s){
        return x < s.x;
    }
}seg[N * 2];
struct Node{
    int l,r;//左右边界
    int cnt;//当前区间被覆盖的次数
    int len;//至少被覆盖1次的区间长度
}tr[N * 4];

void pushup(int u){
    if(tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
    else if(tr[u].l == tr[u].r) tr[u].len = 0;
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}


void build(int u, int l, int r){
    tr[u] = {l, r};
    if(l == r) return ;
    else{
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
    
}

void modify(int u, int l, int r, int k){
    if(tr[u].l >= l && tr[u].r <= r){
        tr[u].cnt += k;
        pushup(u);
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, k);
        if(r >= mid + 1) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main(){
    cin >> n;
    int m = 0;
    for(int i = 0; i < n; i ++){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        seg[m ++] = {x1, y1, y2, 1};
        seg[m ++] = {x2, y1, y2, -1};
    }
    sort(seg, seg + m);
    
    build(1, 0, 10000);
    
    int res = 0;
    
    for(int i = 0; i < m; i ++){
        if(i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
        modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);
    }
    cout << res << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

三维前缀和

仍然是容斥原理。

p(A∪B∪C) = p(A) + P(B) + P© - P(AB) - p(BC) -p(AC) + P(ABC)

因此就有三维前缀和为s[i , j , k] = s[i - 1, j , k] + s[i, j - 1, k] + s[i , j ,k - 1] - s[i - 1, j - 1, k] - s[i - 1, j , k - 1] - s[i, j - 1, k - 1] + s[i - 1, j - 1, k - 1] + d[i , j , k]。

那么三维差分序列就等于d[i , j , k] = s[i , j , k] - s[i - 1, j , k] - s[i, j - 1, k] - s[i, j, k - 1] + s[i -1, j - 1, k] + s[i - 1, j , k - 1] + s[i, j - 1, k - 1] - s[i - 1, j - 1, k - 1]。

三体攻击

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
LL s[N], b[N], bp[N];
int A, B, C, m;
int op[N][7];

int get(int x, int y, int z){
    return x * B * C + y * C + z;
}

void add(int x1, int y1, int z1, int x2, int y2, int z2, int v, LL q[]){
    q[get(x1, y1, z1)] += v;
    q[get(x2 + 1, y1, z1)] -= v;
    q[get(x1, y2 + 1, z1)] -= v;
    q[get(x1, y1, z2 + 1)] -= v;
    q[get(x2 + 1, y2 + 1, z1)] += v;
    q[get(x2 + 1, y1, z2 + 1)] += v;
    q[get(x1, y2 + 1, z2 + 1)] += v;
    q[get(x2 + 1, y2 + 1, z2 + 1)] -= v;
}

bool check(int x){
    memcpy(bp, b, sizeof b);
    for(int i = 1; i <= x; i ++){
        add(op[i][0], op[i][2], op[i][4], op[i][1], op[i][3], op[i][5], - op[i][6], bp);
    }
    memset(s, 0, sizeof s);
    for(int i = 1; i <= A; i ++){
        for(int j = 1;  j <= B; j ++){
            for(int k = 1; k <= C; k ++){
                s[get(i, j, k)] += bp[get(i, j, k)]  + s[get(i - 1, j, k)] + s[get(i, j - 1, k)] + s[get(i, j, k - 1)] - s[get(i - 1, j - 1, k)] - s[get(i - 1, j, k - 1)] - s[get(i, j - 1, k - 1)] + s[get(i - 1, j - 1, k - 1)];
                if(s[get(i, j, k)] < 0) return true;
            }
        }
    }
    return false;
}


int main(){
    cin >> A >> B >> C >> m;
    for(int i = 1; i <= A; i ++){
        for(int j = 1; j <= B; j ++){
            for(int k = 1; k <= C; k ++){
                cin >> s[get(i, j, k)];
                add(i, j, k, i, j, k, s[get(i, j, k)], b);
            }
        }
    }
    
    for(int i = 1; i <= m; i ++){
        for(int j = 0; j < 7; j ++){
            cin >> op[i][j];
        }
    }
    
    
    int l = 1, r = m;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    
    
    cout << l << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

裁剪序列

单调队列加动态规划。

image-20230223231336132

image-20230223231423370

#include<iostream>
#include<queue>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int a[N], n, q[N];
LL m;
LL dp[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] > m){
            cout << -1 << endl;
            return 0;
        }
    }
    
    int tt = -1, hh = 0;
    LL sum = 0;
    for(int i = 1, j = 0; i <= n; i ++){
        sum += a[i];
        while(sum > m) sum -= a[++ j];//通过双指针找到当前i对应的后面一块<sum的j的离i最远的区域
        while(hh <= tt && q[hh] < j) hh ++;//如果这块区域太小了，就把hh++，保证当前队列中的是这块区域中的单调队列。
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;//对于a[i]，寻找大于a[i]的最近一个的坐标。
        q[++ tt] = i;//然后把i放进去。
        dp[i] = dp[j] + a[q[hh]];//初始化dp[i]，让dp[i]为这块和<m的区域中的第一个数j＋后面的最大值a[q[hh]]。
        for(int k = hh; k <= tt; k ++) dp[i] = min(dp[i], dp[q[k]] + a[q[k + 1]]);//因为hh是一个单调队列，里面的每一个元素都是在j到i中的高点，而其他的点一定是会比这些点大的，因此找这些点中最小的就是总的最小的。
        //证明，如果不选择队列中的值的结果一定比选择队列中的值大，假设对于队列中某个值q[k1]，选择q[k1]+1,则f[i]=f[q[k1]+1] + a[q[k1+1]]，由于a[q[k1+1]]是一样的，都是k1后面的第一个数，但是f[q[k1]]≤f[q[k1 + 1]]，因此一定有在选择点后面，且未到达下一个选择点其他点≥队列中的点，对于队列中的某个值q[k1]，如果选择q[k1]-1，则有f[q[k1]-1]+a[q[k1]]因为a[q[k1]]＞a[q[k1+1]]，而前面的也是相等，因此选择队列外左边的点也比队列中的小。
    }
    cout << dp[n] << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

图论

交换瓶子

置换群

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;
int a[N], n;
bool v[N];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        if(!v[i]){
            for(int j = i; !v[j] ; j = a[j]){
                v[j] = true;
            }
            cnt ++;
        }
    }
    cout << n - cnt << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

KMP算法

字符串的最小循环节 = n - kmp[n]

证明如下

image-20230224185934876

奶牛矩阵

#include<iostream>
#include<cstring>
#include<string.h>
using namespace std;
const int N = 1e4 + 10;
int n, m;
char s[N][100];
int kmp[N];
bool v[N];
int main(){
    cin >> n >> m;
    
    memset(v, true, sizeof v);
    
    for(int i = 1; i <= n; i ++){//通过暴力去求每个列的最小循环节。由于此处是可以非完美循环的，因此只能通过暴力来求，只要任何一行对于这个长度的循环节不通过，则对于这个长度都不接受。
        cin >> s[i];
        for(int j = 1; j <= m; j ++){
            if(v[j]){
                for(int k = j; k < m; k += j){
                    for(int u = 0; u < j && k + u < m; u ++){
                        if(s[i][u] != s[i][k + u]){
                            v[j] = false;
                            break;
                        }
                    }
                    if(!v[j]) break;
                }
            }
        }
    }
    int width;
    for(int i = 1; i <= m; i ++){//找到大家都接受的最小的循环节长度。
        if(v[i]){
            width = i;
            break;
        }
    }
    
    for(int i = 1; i <= n; i ++) s[i][width] = 0;//设置每行字符串的长度为width，即在width这个位置设为0.
    
    for(int i = 2, j = 0; i <= n; i ++){//把每行的字符串看做是一个字符，然后用kmp算法求最小循环节，字符串比较用strcmp，相等为0，不相等为1或者-1
        while(j && strcmp(s[i],s[j + 1])) j = kmp[j];
        if(!strcmp(s[i], s[j + 1])) j ++;
        kmp[i] = j;
    }
    
    int hight = n - kmp[n];//最小宽度*最小循环节就是最小面积。为什么这里是宽度用暴力是因为宽只有75，而长太大了，而且宽可以不完美匹配长度需要完美匹配。
    
    cout << hight * width << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

贪心

糖果传递

image-20230225183904833

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N], c[N];
int main(){
    scanf("%d", &n);
    long long sum = 0;
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    int avg = sum / n;
    
    for(int i = 1; i < n; i ++){
        c[i] = a[i] + c[i - 1] - avg;
    }
    
    sort(c, c + n);
    
    int mid = c[(n - 1 >> 1)];
    
    long long res = 0;
    for(int i = 1; i <= n; i ++){
        res += abs(mid - c[i - 1]);
    }
    cout << res << endl;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

乘积最大

从小到大排序，每次成对的去选数。选择乘积最大的

image-20230226140108407

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 9;
int n, k;
int a[N];
int main(){
    cin >> n >> k;
    for(int i =0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    int res = 1;
    if(k == n){
        for(int i = 0; i < n; i ++) res *= a[i] % mod;
    }
    else{
        int l = 0, r = n  - 1;
        int sign = 1;
        if(k % 2){//如果是奇数，就看一下最后那个是正数还是负数，如果是负数就设置符号为-1，代表全部都是负数的情况，然后无论是正数还是负数都是偶数的情况了，就从两头向中间取值就行了
            res = a[r --];
            k --;
            if(res < 0) sign = - 1;
        }
        while(k){
            LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
            if(x * sign > y * sign){
                res = x % mod * res % mod;
                l += 2;
            }
            else{
                res = y % mod * res % mod;
                r -= 2;
            }
            k -= 2;
        }
    }
    cout << res << endl;
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

灵能传输

难点1：
首先得发现当某个发生变化的时候实际是交换该点和前一个点的前缀和。我一开始有感觉要用前缀和，但是我以为是从前缀和中找到组合最小的。

灵能传输.png

难点2：
发现s0和sn是不能移动的。√，想到了。但是实在样例错误的情况下想到的。。。

难点3：
发现难点2后要怎么排序。
从s0向向下跳点走，sn先想上跳点走。
然后从最下面向最上面一个个走就行了。
1123.png
因为已经把一部分从s0到min的点和sn到max的用了，剩下的都用在min到max上。

然后求a_i，找到最大的就行了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3e5 + 10;
typedef long long LL;
int n, t;
LL a[N], s[N];
bool v[N];
int main(){
    cin >> t;
    while(t --){
        cin >> n;
        memset(v, false, sizeof v);
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
            s[i] = s[i - 1] + a[i];
        }
        
        
        LL s0 = s[0], sn = s[n];
        if(s0 > sn) swap(s0, sn);
        
        sort(s, s + n + 1);
        for(int i = 0; i <= n; i ++){
            if(s[i] == s0){
                s0 = i;//记住s0是第几个点
                break;
            }
        }
        for(int i = n; i >= 0; i --){
            if(s[i] == sn){
                sn = i;//记住sn是第几个点。
                break;
            }
        }
        int l = 0, r = n;
        for(int i = s0; i >= 0; i -= 2){
            a[l ++] = s[i];//在s0之前的点进行一次隔着的跳，并在a数组中重新排序这个顺序。
            v[i] = true;
        }
        
        for(int i = sn; i <= n; i += 2){
            a[r --] = s[i];//对sn之后的点进行一次隔着的跳，并在a数组中从后开始重新排序这个顺序。
            v[i] = true;
        }
        
        for(int i = 0; i <= n; i ++){
            if(!v[i]){
                a[l ++] = s[i];//剩下的点按照顺序从小到大排序进a中就行。
            }
        }
        
        LL res = 0;
        for(int i = 1; i <= n; i ++){
            res = max(res, abs(a[i] - a[i - 1]));
        }
        cout << res << endl;
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

二分

最佳牛围栏（二分的是最大的平均数）

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
double a[N], s[N];
int n, k;

int check(double avg){
    for(int i = 1; i <= n; i ++){
        s[i] = s[i - 1] + (a[i] - avg);//计算当前avg时的前缀和。
    }
    
    double minv = 0;
    for(int i = 0, j = k; j <= n; j ++, i ++){
        minv = min(s[i], minv);
        if(s[j] - minv > 0){//如果在区间大于等于k的时候能够让这个区间里的数的和>0，则说明这个区间里的数累加的平均是大于平均数的。
            return true;//放回存在。
        }
    }
    return false;//如果一直找不到，就返回没有。
}

int main(){
    cin >> n >> k;
    double l = 0, r = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        r = max(r, a[i]);
    }
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;//如果有的话，则说明平均值可能的最大值还要更大一些，因此在右边寻找。这里是不是寻找的k区域，而是寻找的平均值的最大值。
        else r = mid;
    }
    
    cout << int(r * 1000) << endl;
    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/285906?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号