头像

两袖清风丶




离线:13小时前


最近来访(13)
用户头像
晕染的月亮
用户头像
AC摆渡人
用户头像
ABInitio
用户头像
挑战关注所有大佬
用户头像
ljhs
用户头像
李濛语
用户头像
伪科学12308
用户头像
不成大神不改名
用户头像
打蓝桥杯的通信人
用户头像
moran236
用户头像
火芋圆

活动打卡代码 AcWing 1058. 股票买卖 V

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5+10;
int w[N];
int f[N][3];
int n;
const int INF = 0x3f3f3f;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    f[0][0]=-INF;
    f[0][1]=-INF;
    f[0][2]=0;

    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][2]-w[i]);
        f[i][1]=max(f[i-1][1],f[i-1][0]+w[i]);
        f[i][2]=max(f[i - 1][2], f[i - 1][1]);

    }
    printf("%d\n", max(f[n][1], f[n][2]));
    return 0;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int f[N][M][2];

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

    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;

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

    int res = 0;
    for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}




(1)大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺,每家店中都有一些现金。

阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。

他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

输入格式
输入的第一行是一个整数 T,表示一共有 T 组数据。

接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。

第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。

每家店铺中的现金数量均不超过1000。

输出格式
对于每组数据,输出一行。

该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。

数据范围
1≤T≤50,
1≤N≤105
输入样例:
2
3
1 8 2
4
10 7 6 14
输出样例:
8
24
样例解释
对于第一组样例,阿福选择第2家店铺行窃,获得的现金数量为8。

对于第二组样例,阿福选择第1和4家店铺行窃,获得的现金数量为10+14=24。

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e5+10;

int f[N][2];    二维0代表不偷,1代表偷
int a[N];
int T;
int n;


int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        memset(f,sizeof(f),0);
        for(int i=1;i<=n;i++)
        {
            f[i][0]=max(f[i-1][1],f[i-1][0]);
            f[i][1]=f[i-1][0]+a[i];
        }
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    return 0;
}

(2)股票买卖(I)只可以买一次
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

输入格式
第一行包含整数 N,表示数组长度。

第二行包含 N 个不大于 109 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105,

输入样例1:
6
7 1 5 3 6 4
输出样例1:
5
输入样例2:
5
7 6 4 3 1
输出样例2:
0
样例解释
样例1:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为你不能在买入股票前卖出股票。

样例2:在这种情况下, 不进行任何交易, 所以最大利润为 0。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;


const int N = 1e5+10;
const int INF = 0x3f3f3f3f;
int w[N];
int f[N][2][2];   //0表示手中没货,1表示有货
int n,k;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    memset(f,-INF,sizeof(f));

    for(int i=0;i<=n;i++) f[i][0][0]=0; //i要从0开始,第1天没货可以从第0天转移过来

    for(int i=1;i<=n;i++)
    {

            f[i][1][0]=max(f[i-1][1][0],f[i-1][1][1]+w[i]);  //上一次没买,这一次也没买,所以是j,不是j-1所以是f[i-1][j][0]  
                                                             //而正在进行第j次交易卖出去,所示是f[i-1][j][1]+w[i]

            f[i][1][1]=max(f[i-1][1][1],f[i-1][0][0]-w[i]);//上一次没卖,这一次也没卖,所以是j,不是j-1所以是f[i-1][j][1]  
                                                            //正在进行第j次交易,在转移之前已经进行j-1次交易,所以是f[i-1][j-1][0]-w[i]

    }
    int res = 0;
    for (int i = 0; i <= 1; i ++ ) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}

(3)股票买票(II)尽可能买多次
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入格式
第一行包含整数 N,表示数组长度。

第二行包含 N 个不大于 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105
输入样例1:
6
7 1 5 3 6 4
输出样例1:
7
输入样例2:
5
1 2 3 4 5
输出样例2:
4
输入样例3:
5
7 6 4 3 1
输出样例3:
0
样例解释
样例1:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

样例3:在这种情况下, 不进行任何交易, 所以最大利润为 0。

代码:

#include <iostream>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][2];    //0表示手中没货,1表示有货

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

    f[0][1] = -INF;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + w[i]);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
    }
    printf("%d\n", f[n][0]);
    return 0;
}


(4)股票买票(III)最多可交易2次
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入格式
第一行包含整数 N,表示数组长度。

第二行包含 N 个不大于 109 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105
输入样例1:
8
3 3 5 0 0 3 1 4
输出样例1:
6
输入样例2:
5
1 2 3 4 5
输出样例2:
4
输入样例3:
5
7 6 4 3 1
输出样例3:
0
样例解释
样例1:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。共得利润 3+3 = 6。

样例2:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

样例3:在这种情况下, 不进行任何交易, 所以最大利润为 0。
代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;


const int N = 1e5+10;
const int INF = 0x3f3f3f3f;
int w[N];
int f[N][3][2];   //0表示手中没货,1表示有货
int n,k;

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

    memset(f,-INF,sizeof(f));

    for(int i=0;i<=n;i++) f[i][0][0]=0; //i要从0开始,第1天没货可以从第0天转移过来

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2;j++)
        {
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);  //上一次没买,这一次也没买,所以是j,不是j-1所以是f[i-1][j][0]  
                                                             //而正在进行第j次交易卖出去,所示是f[i-1][j][1]+w[i]

            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);//上一次没卖,这一次也没卖,所以是j,不是j-1所以是f[i-1][j][1]  
                                                            //正在进行第j次交易,在转移之前已经进行j-1次交易,所以是f[i-1][j-1][0]-w[i]
        }
    }
        int res = 0;
    for (int i = 0; i <= 2; i ++ ) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}

(5)股票买票(IV) 最多可交易k次

给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。

输入格式
第一行包含整数 N 和 k,表示数组的长度以及你可以完成的最大交易数量。

第二行包含 N 个不超过 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105,
1≤k≤100
输入样例1:
3 2
2 4 1
输出样例1:
2
输入样例2:
6 2
3 2 6 5 0 3
输出样例2:
7
样例解释
样例1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

样例2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

qq.png

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int K =105;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f;
int w[N];
int f[N][K][2];   //0表示手中没货,1表示有货
int n,k;

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>w[i];
    memset(f,-INF,sizeof(f));

    for(int i=0;i<=n;i++) f[i][0][0]=0; //i要从0开始,第1天没货可以从第0天转移过来

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);  //上一次没买,这一次也没买,所以是j,不是j-1所以是f[i-1][j][0]  
                                                             //而正在进行第j次交易卖出去,所示是f[i-1][j][1]+w[i]

            f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);//上一次没卖,这一次也没卖,所以是j,不是j-1所以是f[i-1][j][1]  
                                                            //正在进行第j次交易,在转移之前已经进行j-1次交易,所以是f[i-1][j-1][0]-w[i]
        }
    }
    int res = 0;
    for (int i = 0; i <= k; i ++ ) res = max(res, f[n][i][0]);

    printf("%d\n", res);

    return 0;
}

(6)股票买票(V) 有冷冻期
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
输入格式
第一行包含整数 N,表示数组长度。

第二行包含 N 个不超过 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105
输入样例:
5
1 2 3 0 2
输出样例:
3
样例解释
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。

QQ图片20220114174303.png

代码:

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5+10;
int w[N];
int f[N][3];
int n;
const int INF = 0x3f3f3f;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);

    f[0][0]=-INF;
    f[0][1]=-INF;
    f[0][2]=0;

    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][2]-w[i]);
        f[i][1]=max(f[i-1][1],f[i-1][0]+w[i]);
        f[i][2]=max(f[i - 1][2], f[i - 1][1]);

    }
    printf("%d\n", max(f[n][1], f[n][2]));
    return 0;
}

(7)股票买票(VI)
给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格,再给定一个非负整数 f,表示交易股票的手续费用。

设计一个算法来计算你所能获取的最大利润。

你可以无限次地完成交易,但是你每次交易都需要支付手续费。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入格式
第一行包含两个整数 N 和 f,分别表示数组的长度以及每笔交易的手续费用。

第二行包含 N 个不超过 10000 的正整数,表示完整的数组。

输出格式
输出一个整数,表示最大利润。

数据范围
1≤N≤105,
1≤f≤10000
输入样例:
6 2
1 3 2 8 4 9
输出样例:
8
样例解释
在第 1 天(股票价格 = 1)的时候买入,在第 4 天(股票价格 = 8)的时候卖出,这笔交易所能获得利润 = 8-1-2 = 5 。随后,在第 5 天(股票价格 = 4)的时候买入,在第 6 天 (股票价格 = 9)的时候卖出,这笔交易所能获得利润 = 9-4-2 = 3 。共得利润 5+3 = 8。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n;
int f1;
int w[N];
int f[N][2];    //0表示手中没货,1表示有货

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

    f[0][1] = -INF;
    for (int i = 1; i <= n; ++i) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + w[i]-f1);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
    }
    printf("%d\n", f[n][0]);
    return 0;
}

总结:与(II)同,减去手续费即可


活动打卡代码 AcWing 1049. 大盗阿福

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int w[N], f[N][2];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

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

        printf("%d\n", max(f[n][0], f[n][1]));
    }

    return 0;
}





(1)聪明的质检员
小 T 是一名质量监督员,最近负责检验一批矿产的质量。

这批矿产共有 n 个矿石,从 1 到 n 逐一编号,每个矿石都有自己的重量 wi 以及价值 vi。

检验矿产的流程是: 

1、给定 m 个区间 [Li,Ri]; 
2、选出一个参数 W; 
3、对于一个区间 [Li,Ri],计算矿石在这个区间上的检验值 Yi : 

QQ截图20190314005531.png

这批矿产的检验结果 Y 为各个区间的检验值之和。

即:Y = Y1+Y2+…+Ym

若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。

小 T 不想费时间去检验另一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近标准值 S,即使得 S−Y 的绝对值最小。

请你帮忙求出这个最小值。

输入格式
第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。 

接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。 

接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间 [Li, Ri] 的两个端点 Li 和 Ri。

注意:不同区间可能重合或相互重叠。

输出格式
输出一个整数,表示所求的最小值。

数据范围
1≤n,m≤200000,
0<wi,vi≤106,
0<S≤1012,
1≤Li≤Ri≤n
输入样例:
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
输出样例:
10

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, m;
LL S;
int w[N], v[N];
int l[N], r[N];
int cnt[N];
LL sum[N];

LL get(int W)
{
    for (int i = 1; i <= n; i ++ )
        if (w[i] >= W)
        {
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        }
        else
        {
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }

    LL res = 0;
    for (int i = 0; i < m; i ++ ) res += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
    return res;
}

int main()
{
    scanf("%d%d%lld", &n, &m, &S);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &w[i], &v[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &l[i], &r[i]);

    int l = 0, r = 1e6 + 1;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get(mid) >= S) l = mid;
        else r = mid - 1;
    }

    printf("%lld\n", min(abs(get(r) - S), abs(S - get(r + 1))));

    return 0;
}

总结: Y 随 W 单调递减。
因此我们可以二分出距离 S 最近的值。
时间复杂度分析
总共二分 O(logW) 次,每次预处理前缀和的计算量是 O(N),求 Y的计算量是 O(M)。因此总时间复杂度是 O(N+M)logW。




一维前缀和
S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

(1)离散化区间和

假定有一个无限长的数轴,数轴上每个坐标上的数都是 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
难度:简单
时/空限制:2s / 64MB
总通过数:27209
总尝试数:46898
来源:模板题
算法标签
代码:

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

using namespace std;

const int N = 300010;

int n, m;
int a[N], s[N];//a数组存数, s数组存前缀和

vector<int> alls; //存原来的坐标x 
vector< pair<int, int> > add, query; //两种操作 

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;
} 

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() );  //unique()返回去重后数组的最后一位下标,后面都是重复元素

    //处理插入离散化后的数组 
    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;
}

(2)、K倍区间
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗?

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数,代表 K 倍区间的数目。

数据范围
1≤N,K≤100000,
1≤Ai≤100000
输入样例:
5 2
1
2
3
4
5
输出样例:
6
难度:中等
时/空限制:1s / 64MB
总通过数:5612
总尝试数:14501
来源:第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组
算法标签

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL res=0;
    cnt[0]=1;   //s[0]也有,余数为0
    for(int i=1;i<=n;i++)
    {
        res+=cnt[s[i]%k];
        cnt[s[i]%k]++;
    }


    printf("%lld\n", res);

    return 0;
}

二维前缀和 —— 模板题 AcWing 796. 子矩阵的和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

(1)子矩阵的和
输入一个 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

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

const int N = 1010;
using namespace std;
int a[N][N];
int s[N][N];
int n,m,q;

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]+a[i][j]-s[i-1][j-1];
        }
    }

    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
    }
    return 0;
}

一维差分:给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c

(1)输入一个长度为 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
代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[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", &a[i]);

    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    while (m -- )
    {
        int l, r, c;
        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;
}

(2)、增减序列
给定一个长度为 n 的数列 a1,a2,…,an,每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式
第一行输入正整数 n。

接下来 n 行,每行输入一个整数,第 i+1 行的整数代表 ai。

输出格式
第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围
0<n≤105,
0≤ai<2147483648
输入样例:
4
1
1
2
2
输出样例:
1
2
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int a[N], b[N];

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

    LL p = 0, q = 0;
    for (int i = 2; i <= n; i ++ )
        else q -= b[i];

    cout << max(p, q) << endl;
    cout << abs(p - q) + 1 << endl;

    return 0;
}


二维差分
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

(1)差分矩阵
输入一个 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

代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

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()
{
    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 ++ )
            insert(i, j, i, j, a[i][j]);

    while (q -- )
    {
        int x1, y1, x2, y2, c;
        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];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}
https://www.acwing.com/solution/content/27325/

(2)激光炸弹
地图上有 N 个目标,用整数 Xi,Yi 表示目标在地图上的位置,每个目标都有一个价值 Wi。

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 x,y 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式
第一行输入正整数 N 和 R,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

接下来 N 行,每行输入一组数据,每组数据包括三个整数 Xi,Yi,Wi,分别代表目标的 x 坐标,y 坐标和价值,数据用空格隔开。

输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围
0≤R≤109
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

int s[N][N];

int main()
{
    int n, R;
    scanf("%d%d", &n, &R);
    R = min(R, 5001);

    for (int i = 0; i < n; i ++ )
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++ ;
        s[x][y] += w;
    }

    for (int i = 1; i <= 5001; i ++ )
        for (int j = 1; j <= 5001; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;
    for (int i = R; i <= 5001; i ++ )
        for (int j = R; j <= 5001; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    printf("%d\n", res);

    return 0;
}


(3)、赶牛入圈
农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的,而且至少要包含 C 单位的三叶草,来当做它们的下午茶。

畜栏的边缘必须与 X,Y 轴平行。

约翰的土地里一共包含 N 单位的三叶草,每单位三叶草位于一个 1×1 的土地区域内,区域位置由其左下角坐标表示,并且区域左下角的 X,Y 坐标都为整数,范围在 1 到 10000 以内。

多个单位的三叶草可能会位于同一个 1×1 的区域内,因为这个原因,在接下来的输入中,同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中,才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下,能包含至少 C 单位面积三叶草的情况下,畜栏的最小边长是多少。

输入格式
第一行输入两个整数 C 和 N。

接下来 N 行,每行输入两个整数 X 和 Y,代表三叶草所在的区域的 X,Y 坐标。

同一行数据用空格隔开。

输出格式
输出一个整数,代表畜栏的最小边长。

数据范围
1≤C≤500,
C≤N≤500
输入样例:
3 4
1 2
2 1
4 1
5 2
输出样例:
4
难度:中等
时/空限制:1s / 64MB
总通过数:1528
总尝试数:4315
来源:《算法竞赛进阶指南》
算法标签

代码:

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

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;

int n, m;
PII points[N];
int sum[N][N];
vector<int> numbers;

bool check(int len)
{
    for (int x1 = 1, x2 = 1; x2 < numbers.size(); x2 ++ )
    {
        while (numbers[x2] - numbers[x1 ] + 1 > len) x1 ++ ;
        for (int y1 =1, y2 = 1; y2 < numbers.size(); y2 ++ )
        {
            while (numbers[y2] - numbers[y1 ] + 1 > len) y1 ++ ;
            if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= m)
                return true;
        }
    }
    return false;
}

int get(int x)
{
    int l = 0, r = numbers.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (numbers[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

// int get_id(int n)
// {
//     return lower_bound(numbers.begin(), numbers.end(), n) - numbers.begin();
// }


int main()
{
    cin >> m >> n;
    numbers.push_back(0);
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        numbers.push_back(x);
        numbers.push_back(y);
        points[i] = {x, y};
    }
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());

    for (int i = 0; i < n; i ++ )
    {
        int x = get(points[i].first), y = get(points[i].second);
        sum[x][y] ++ ;
    }

    for (int i = 1; i < numbers.size(); i ++ )
        for (int j = 1; j < numbers.size(); j ++ )
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

    int l = 1, r = 10000;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;

    return 0;
}

总结:不同于之前的激光炸弹,激光炸弹因为不能算边界,所以不需要-1。



活动打卡代码 AcWing 100. 增减序列

代码:

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int a[N], b[N];

int main()
{
scanf(“%d”, &n);
for (int i = 1; i <= n; i ) scanf(“%d”, &a[i]);
for (int i = 1; i <= n; i
) b[i] = a[i] - a[i - 1];

LL p = 0, q = 0;
for (int i = 2; i <= n; i ++ )
    else q -= b[i];

cout << max(p, q) << endl;
cout << abs(p - q) + 1 << endl;

return 0;

}



活动打卡代码 AcWing 99. 激光炸弹

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

int s[N][N];

int main()
{
    int n, R;
    scanf("%d%d", &n, &R);
    R = min(R, 5001);

    for (int i = 0; i < n; i ++ )
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++ ;
        s[x][y] += w;
    }

    for (int i = 1; i <= 5001; i ++ )
        for (int j = 1; j <= 5001; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;
    for (int i = R; i <= 5001; i ++ )
        for (int j = R; j <= 5001; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);

    printf("%d\n", res);

    return 0;
}




活动打卡代码 AcWing 102. 最佳牛围栏

#include <cstdio>
#include <iostream>

const int N = 100005;
int cows[N]; double sum[N];

int n, m;

bool check(double avg) {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + cows[i] - avg;
    }

    double minv = 0;
    for (int i = 0, j = m; j <= n; j++, i++) {
        minv = std::min(minv, sum[i]);
        if(sum[j] - minv >= 0) return true;
    } return false;
}

int main() {
    scanf("%d %d", &n, &m);
    double l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cows[i]);
        r = std::max(r, (double)cows[i]);
    }

    while(r - l > 1e-5) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    } printf("%d\n", (int)(r * 1000));
    return 0; 
}





整数二分模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

(1)、数的范围
给定一个按照升序排列的长度为 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

代码:

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100005;
int n,t,x;
int q[N];


int main()
{
    scanf("%d%d",&n,&t);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    while(t--)
    {
         scanf("%d", &x);
        int l,r;
        l=0;r=n-1;
        int mid;
        while(l<r)
        {
            mid=l+r >>1;
            if(q[mid]>=x)
            {
                r=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        if(q[r]==x)
        {
            printf("%d ",r);
            r=n-1;
            while(l<r)
            {
                mid=(l+r+1) /2;
                if(q[mid]<=x)
                {
                    l=mid;
                }
                else
                {
                    r=mid-1;
                }
            }
            printf("%d \n",r);
        }
        else
        {
            printf("-1 -1\n");
        }
    }
    return 0;
}

(2)、机器人跳跃问题
机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0 到 N 编号,从左到右排列。

编号为 0 的建筑高度为 0 个单位,编号为 i 的建筑高度为 H(i) 个单位。

起初,机器人在编号为 0 的建筑处。

每一步,它跳到下一个(右边)建筑。

假设机器人在第 k 个建筑,且它现在的能量值是 E,下一步它将跳到第 k+1 个建筑。

如果 H(k+1)>E,那么机器人就失去 H(k+1)−E 的能量值,否则它将得到 E−H(k+1) 的能量值。

游戏目标是到达第 N 个建筑,在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式
第一行输入整数 N。

第二行是 N 个空格分隔的整数,H(1),H(2),…,H(N) 代表建筑物的高度。

输出格式
输出一个整数,表示所需的最少单位的初始能量值上取整后的结果。

数据范围
1≤N,H(i)≤105,

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

代码:

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;
int q[N];
int n;
bool check(int e)
{
    for (int i = 0; i <n; i ++ )
    {
        e = e * 2 - q[i];
        if (e >= 1e5) return true;
        if (e < 0) return false;
    }
    return true;
}


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

    int l = 0, r = 1e5;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}

总结:1.由题意知不管下一个建筑物的高度是否高于现有能量能量的变化总为2*e-H[i];
2.最优值问题,能量有明确的范围,故使用二分,将最优解问题转化为判断问题;
(3)分巧克力
儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足:

形状是正方形,边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?

输入格式
第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式
输出切出的正方形巧克力最大可能的边长。

数据范围
1≤N,K≤105,
1≤Hi,Wi≤105
输入样例:
2 10
6 5
5 6
输出样例:
2

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
int h[N], w[N];


bool check(int a)
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        res+=(h[i]/a)*(w[i]/a);
        if(res>=k)return true;
    }
    return false;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&h[i],&w[i]);
    }
    int l=1,r=1e5;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<l;
    return 0;
}

(4)四平方和
四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去,就正好可以表示为 4 个数的平方和。

比如:

5=02+02+12+22
7=12+12+12+22
对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4 个数排序:

0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。

输入格式
输入一个正整数 N。

输出格式
输出4个非负整数,按从小到大排序,中间用空格分开。

数据范围
0<N<5∗106
输入样例:
5
输出样例:
0 0 1 2

代码:

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

struct Sum
{
    int s, c, d;
    bool operator< (const Sum &t)const
    {
        if (s != t.s) return s < t.s;
        if (c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int n, m;

int main()
{
    cin >> n;

    for (int c = 0; c * c <= n; c ++ )
        for (int d = c; c * c + d * d <= n; d ++ )
            sum[m ++ ] = {c * c + d * d, c, d};

    sort(sum, sum + m);

    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            int t = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            if (sum[l].s == t)
            {
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}


总结:空间换时间,先枚举c,d存起来,最下面的后面循环a,b去找满足要求的n-aa-bb

(5)最佳牛围栏
农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于 1 头,也不会超过 2000 头。

约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。

在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式
第一行输入整数 N 和 F,数据间用空格隔开。

接下来 N 行,每行输入一个整数,第 i+1 行输入的整数代表第 i 片区域内包含的牛的数目。

输出格式
输出一个整数,表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。

数据范围
1≤N≤100000
1≤F≤N
输入样例:
10 6
6
4
2
10
3
8
5
9
4
1
输出样例:
6500
代码:

#include <cstdio>
#include <iostream>

const int N = 100005;
int cows[N]; double sum[N];

int n, m;

bool check(double avg) {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + cows[i] - avg;
    }

    double minv = 0;
    for (int i = 0, j = m; j <= n; j++, i++) {
        minv = std::min(minv, sum[i]);
        if(sum[j] - minv >= 0) return true;
    } return false;
}

int main() {
    scanf("%d %d", &n, &m);
    double l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cows[i]);
        r = std::max(r, (double)cows[i]);
    }

    while(r - l > 1e-5) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    } printf("%d\n", (int)(r * 1000));
    return 0; 
}

①:我们要找的是 有没有一段不小于F的区间,使这段区间的平均数尽可能的大,如果我们找到了一段连续的区间且区间长度不小于F且平均数大于我们二分的平均数 那么大于这个数且区间也满足的一定满足了 我们直接判断正确即可

②:因为我们要找一段区间的平均数,根据平均数的一个基本应用,显而易见,对于一段序列,每个数减去我们所算的平均数,如果大于0 那么他本身就大于平均数,如果小于0 那么它本身就小于平均数 此时我们就能算出哪些数大于0 哪些数小于0 ,之后我们再使用前缀和,就能判断一个区间内的平均值是否大于或小于我们二分的平均数了

③:据②我们还可以继续优化,因为我们不仅需要找F大小区间内,我们还要找>F大小区间内的,我们如果用二次for太费时间了,我们这里可以使用双指针的做法,我们设i=0,j=Fi=0,j=F 每次使两个数++ 因为i,ji,j始终满足相距FF的距离,所以我们用一个变量minvminv来存储ii所遍历到的最小值,这样我们比较的距离一定是≥F≥F的,并且如果我们用jj位的前缀和数减去minvminv的话,就能得到我们的最优解,如果这个最优解>= 0 那么就满足我们的指定条件(如果不懂这一步 请看②)。 到此,结束

我们便可以写出二分的checkcheck代码

bool check(double avg) {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (cows[i] - avg); //计算前缀和
    }

    double minv = 0; //设置最小值
    for (int i = 0, j = m; j <= n; j++, i++) {
        minv = std::min(minv, sum[i]); //找最优极小值
        if(sum[j] - minv >= 0) return true; //进行判断
    } return false; //如果所有的都不满足,那么这个平均数就一定不满足
}

作者:Nicoppa
链接:https://www.acwing.com/solution/content/1148/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

(1)剪绳子
有 N 根绳子,第 i 根绳子长度为 Li,现在需要 M 根等长的绳子,你可以对 N 根绳子进行任意裁剪(不能拼接),请你帮忙计算出这 M 根绳子最长的长度是多少。

输入格式
第一行包含 2 个正整数 N、M,表示原始绳子的数量和需求绳子的数量。

第二行包含 N 个整数,其中第 i 个整数 Li 表示第 i 根绳子的长度。

输出格式
输出一个数字,表示裁剪后最长的长度,保留两位小数。

数据范围
1≤N,M≤100000,
0<Li<109
输入样例:
3 4
3 5 4
输出样例:
2.50
样例解释
第一根和第三根分别裁剪出一根 2.50 长度的绳子,第二根剪成 2 根 2.50 长度的绳子,刚好 4 根。

代码:

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int w[N];

bool check(double mid)
{
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        cnt += w[i] / mid;
    return cnt >= m;
}

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

    double l = 0, r = 1e9;
    while (r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", r);
    return 0;
}



浮点数二分:

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

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

输入格式
共一行,包含一个浮点数 n。

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

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

数据范围
−10000≤n≤10000
输入样例:
1000.00
输出样例:
10.000000

代码:

#include <iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%.6lf\n", l);
    return 0;
}

1、0到n-1中缺失的数字
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 到 n−1 之内。

在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。

数据范围
1≤n≤1000
样例
输入:[0,1,2,4]

输出:3

代码:

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty()) return 0;

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == r) r ++ ;
        return r;
    }
};


2、 不修改数组找出重复的数字
给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。

请找出数组中任意一个重复的数,但不能修改输入的数组。

数据范围
1≤n≤1000
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。
思考题:如果只能使用 O(1) 的额外空间,该怎么做呢?

代码:

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l=1;
        int r=nums.size()-1;
        while(l<r)
        {
            int mid = l+r>>1;
            int s=0;
            for(auto x:nums)
            {
                if(x>=l&&x<=mid)
                {
                    s+=1;
                }

            }
            if(s>mid-l+1)
            {
                r=mid;
            }
            else l=mid+1;
        }
        return r;
    }
};


3、防线
达达学习数学竞赛的时候受尽了同仁们的鄙视,终于有一天......受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。

就如同中二漫画的情节一样,怪兽达达打算毁掉这个世界。

数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋,于是她集合了一支由数学竞赛选手组成的超级行动队。

由于队员们个个都智商超群,很快,行动队便来到了怪兽达达的黑暗城堡的下方。

但是,同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。

防线由很多防具组成,这些防具分成了 N 组。

我们可以认为防线是一维的,那么每一组防具都分布在防线的某一段上,并且同一组防具是等距离排列的。

也就是说,我们可以用三个整数 S, E 和 D 来描述一组防具,即这一组防具布置在防线的 S,S+D,S+2D,…,S+KD(K∈Z,S+KD≤E,S+(K+1)D>E)位置上。

黑化的怪兽达达设计的防线极其精良。

如果防线的某个位置有偶数个防具,那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况,因为 0 也是偶数)。

只有有奇数个防具的位置有破绽,但是整条防线上也最多只有一个位置有奇数个防具。

作为行动队的队长,lqr 要找到防线的破绽以策划下一步的行动。

但是,由于防具的数量太多,她实在是不能看出哪里有破绽。

作为 lqr 可以信任的学弟学妹们,你们要帮助她解决这个问题。

输入格式
输入文件的第一行是一个整数 T,表示有 T 组互相独立的测试数据。

每组数据的第一行是一个整数 N。

之后 N 行,每行三个整数 Si,Ei,Di,代表第 i 组防具的三个参数,数据用空格隔开。

输出格式
对于每组测试数据,如果防线没有破绽,即所有的位置都有偶数个防具,输出一行 “There’s no weakness.”(不包含引号) 。

否则在一行内输出两个空格分隔的整数 P 和 C,表示在位置 P 有 C 个防具。当然 C 应该是一个奇数。

数据范围
防具总数不多于108,

Si≤Ei,

1≤T≤5,

N≤200000,

0≤Si,Ei,Di≤231−1
输入样例:
3
2
1 10 1
2 10 1
2
1 10 1
1 10 1
4
1 10 1
4 4 1
1 5 1
6 10 1
输出样例:
1 1
There’s no weakness.
4 3

代码:

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 200010;
int n;
struct Seq
{
    int s, e, d;
}seqs[N];

LL get_sum(int mid)
{
    LL res=0;
    for(int i=0;i<n;i++)
    {
        if(seqs[i].s<=mid)
        {
            res += (min(seqs[i].e, mid) - seqs[i].s) / seqs[i].d + 1;
        }
    }
    return res;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int l=0,r;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int s, e, d;
            scanf("%d%d%d", &s, &e, &d);
            seqs[i] = {s, e, d};
            r = max(r, e);
        }
         while (l < r)
        {
            int mid = (LL)l + r >> 1;
            if (get_sum(mid) & 1) r = mid;
            else l = mid + 1;
        }


        auto sum = get_sum(r) - get_sum(r - 1);
        if (sum % 2) printf("%d %lld\n", r, sum);
        else puts("There's no weakness.");
    }

    return 0;
}

总结:
算法:前缀和 + 二分位置
1、奇数位存在性
整个序列中至多有一个位置的数字所占数量是奇数,所以如果存在奇数位,则整个数列的总和必然是奇数(奇数 + 偶数 = 奇数,偶数 + 偶数 = 偶数)。反之,若不存在奇数位,则一定是偶数。故只需判断数字数量的总和的奇偶性即可。

2、二分位置
若存在这个奇偶性,我们可以通过二分答案的位置来找到这个位置,然后判断区间[l,mid][l,mid]的总和的奇偶性。若为奇数,则奇数位存在于此区间。反之若为偶数,则一定存在于[mid+1,r][mid+1,r]区间。用这个方法逐步缩小范围即可。

关于查找[l,mid][l,mid]的总和,我们可以用前缀和的思路,用sum[mid]−sum[l−1]sum[mid]−sum[l−1]即可求出。(sum[i]sum[i]为求出ii位置之前所有位置的和)

3、O(n)O(n)时间求出区间sum[x]sum[x]的数字个数
设整个数列的最小位置为minnminn
这里,我们枚举每一个等差数列(它的起点为ss,终点为ee,差为dd)。若s<=xs<=x,则两区间存在交集。

则它与[minn,x][minn,x]的共同区间为[s,min(e,x)][s,min(e,x)]。那么此区间包含此数列的个数是⌊(min(e,x)−s)/d⌋+1⌊(min(e,x)−s)/d⌋+1。

正确性证明十分容易:
在此区间中存在一段区间,共⌊s,min(e,x)/d⌋∗d⌊s,min(e,x)/d⌋∗d个位置,头尾的位置上都有数字,差为dd,则数字的数量就是⌊(min(e,x)−s)/d⌋+1⌊(min(e,x)−s)/d⌋+1。

时间复杂度:O(nlogn)O(nlogn)
二分的时间为O(logn)O(logn),每次check()check()的时间为O(n)O(n),故总的时间复杂度为O(nlogn)O(nlogn)。

作者:墨染空
链接:https://www.acwing.com/solution/content/2545/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

4、赶牛入圈
农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的,而且至少要包含 C 单位的三叶草,来当做它们的下午茶。

畜栏的边缘必须与 X,Y 轴平行。

约翰的土地里一共包含 N 单位的三叶草,每单位三叶草位于一个 1×1 的土地区域内,区域位置由其左下角坐标表示,并且区域左下角的 X,Y 坐标都为整数,范围在 1 到 10000 以内。

多个单位的三叶草可能会位于同一个 1×1 的区域内,因为这个原因,在接下来的输入中,同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中,才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下,能包含至少 C 单位面积三叶草的情况下,畜栏的最小边长是多少。

输入格式
第一行输入两个整数 C 和 N。

接下来 N 行,每行输入两个整数 X 和 Y,代表三叶草所在的区域的 X,Y 坐标。

同一行数据用空格隔开。

输出格式
输出一个整数,代表畜栏的最小边长。

数据范围
1≤C≤500,
C≤N≤500
输入样例:
3 4
1 2
2 1
4 1
5 2
输出样例:
4
代码: