精华内容
下载资源
问答
  • =F的平均值最大的连续子区间的平均值 #include<bits.stdc++.h> using namespace std; const int N = 100010; int n, F; double a[N], s[N]; bool check(double avg){ for (int i = 1; i <= n; i ++ ) s[i]...

    二分答案+前缀和+维护区间长度

    题目要求:求区间长度>=F的平均值最大的连续子区间的平均值

    #include<bits.stdc++.h>
    using namespace std;
    const int N = 100010;
    int n, F;
    double a[N], s[N];
    bool check(double avg){
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;
        double mins = 0;
        for (int k = F; k <= n; k ++ ){
            mins = min(mins, s[k - F]);
            if (s[k] >= mins) return true;
        }
        return false;
    }
    int main()
    {
        scanf("%d%d", &n, &F);
        double l = 0, r = 0;
        for (int i = 1; i <= n; i ++ ){
            scanf("%lf", &a[i]);
            r = max(r, a[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;
    }
    
    
    展开全文
  • 游戏一共有m轮,Alice手里有一个长度为n的序列a_i 和常数K,每轮取出一个连续区间 [L_i,R_i],问这个区间中存在多少个连续子区间满足区间中不同的数的个数不小于K。 1≤n,m,K≤10 ^5。 分析: f[i]表示i作为左端点时...

    原题链接
    游戏一共有m轮,Alice手里有一个长度为n的序列a_i 和常数K,每轮取出一个连续区间 [L_i,R_i],问这个区间中存在多少个连续子区间满足区间中不同的数的个数不小于K。
    1≤n,m,K≤10 ^5。
    分析:
    f[i]表示i作为左端点时向右扩展到f[i],此时这个区间刚好有k个不同的数字。
    对于一个区间L,R,可以求出pos,使f[pos-1]小于等于R,且f[pos]大于R。
    则答案就是
    在这里插入图片描述
    f数组可以用双指针法(尺取法)O(n)求得。
    pos可以用二分法求得。
    答案可以用前缀和求得。
    对于比较难的题目,我们可以先用暴力的思想,推出答案公式和思路,然后再将思路优化,将公式化简。
    代码如下:

    
    int a[maxv],f[maxv];
    LL sumF[maxv],ans=0;
    map<int,int> vis;
    int main(){
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int l=0,r=1,sum=0,l1,r1;
        while(l<=n){
            if(sum<k&&r<=n){
                if(!vis[a[r]]) sum++;
                vis[a[r]]++,r++;
            }else{
                if(sum==k) f[l]=r-1;
                else f[l]=n+1;
                vis[a[l]]--;
                if(!vis[a[l]]) sum--;
                l++;
            }
        }
        for(int i=1;i<=n;i++) sumF[i]=sumF[i-1]+f[i];
        for(int i=1;i<=m;i++){
            scanf("%d %d",&l1,&r1);
            l=min(l1^ans,r1^ans)+1,r=max(l1^ans,r1^ans)+1;
            int up=upper_bound(f+1,f+n+1,r)-f-1;
            //printf("%d %d ",l,r);
            if(up<l) ans=0;
            else ans=(LL)(r+1)*(up-l+1)-(sumF[up]-sumF[l-1]);
            printf("%lld\n",ans);
        }
        return 0;
    }
    
    展开全文
  • 他可以进行一次操作:选择一个区间L,R将其反转。 例如,对于序列A=(1,0,0,1,1),当L=2,R=4时,原序列将变为(1,1,0,0,1)。 小Z希望:通过这一次反转操作,使得这个序列的最长不下降序列的长度尽可能的大,并想让你...

    题目描述

    小Z有一个01序列A=(A1,A2,A3,…,An)。他可以进行一次操作:选择一个区间L,R将其反转。
    例如,对于序列A=(1,0,0,1,1),当L=2,R=4时,原序列将变为(1,1,0,0,1)。
    小Z希望:通过这一次反转操作,使得这个序列的最长不下降子序列的长度尽可能的大,并想让你输出这个最大值。
    一个序列的不下降子序列定义为:对于一个序列(p1,p2,…,pk)满足1≤p1<p2<…<pk≤n(n≤819200)且Ap1≤Ap2≤…≤Apk。则序列(Ap1,Ap2,…,Apk)为不下降子序列,其中k为这个不下降子序列的长度。

    输入

    一行一个01字符串,表示序列A

    输出

    一行一个正整数,表示最长不下降子序列长度的最大值。

    样例输入

    00111001101
    

    样例输出

    10
    提示
    一种最优策略为:反转区间[3,7],数列将变为(0,0,0,0,1,1,1,1,1,0,1) ,其最长不下降子序列的长度为10。

    在一开始的时候以为反转某一段区间之后,只会影响反转的这一块中0或1的数量与前一段或后一段的0或1的数量
    然后统计出来0或1的块的大小,只反转1…10…0这样的区间,其实是错的
    答案会影响四段
    wrong_code:
    记录反转了这一块后前面0的个数与后面1的数量思路其实是错的

    int n,k;
    int a[maxn];
    struct node{
        int id;
        int ct;
    }b[maxn];
    int main()
    {
        string s;
        cin >> s;
        n = s.size();
        s = "#" + s;
        int cnt = 0;
        int t = 0;
        int bak1 = 0;
        for(int i=1;i<=n;i++){
            ++ t;
            if(i == n || s[i] != s[i+1]){
                b[++cnt].id = s[i] - '0';
                b[cnt].ct = t;
                t = 0;
                if(s[i] == '1') bak1 += b[cnt].ct;
            }
        }
        /*for(int i=1;i<=cnt;i++){
            cout << b[i].id<<' '<<b[i].ct<<endl;
        }*/
        /// debug(bak1);
        if(cnt == 1 || cnt == 2){
            cout << n <<endl;
            return 0;
        }
         
        int pre0 = 0;
        int ans = 0;
        b[0].id = 0,b[0].ct=0;
        for(int i=1;i<cnt;i++){
            if(b[i-1].id == 0) pre0 += b[i-1].ct;
            else bak1 -= b[i-1].ct;
            ans = max(ans,bak1 + pre0);
            if(b[i].id == 1 && b[i+1].id == 0){
                ans = max(ans,pre0 + b[i+1].ct + bak1);
                /*debug(pre0);
                debug(b[i+1].ct);
                debug(bak1);*/
                // cout << pre0 + b[i+1].ct + bak1 <<endl;
            }
        }
        cout << ans <<endl;
        return 0;
    }
     
    /**************************************************************
        Problem: 13769
        Language: C++
        Result: 答案错误
    ****************************************************************/
    

    ac_code:

    int main()
    {
        string s;
        cin >> s;
        n = s.size();
        s = "#" + s;
        int t1,t2,t3,res;
        t1 = t2 = t3 = res = 0;
        for(int i=1;i<=n;i++){
            if(s[i] == '0'){
                ++ t1;
                t2 = max(t1,t2);
                t3 = max(t2,t3 + 1);
                res = max(res,t3);
            }else{
                t2 = max(t1,t2 + 1);
                t3 = max(t2,t3);
                res = max(t3,res + 1);
            }
        }
        cout << res <<endl;
        return 0;
    }
     
    /**************************************************************
        Problem: 13769
        Language: C++
        Result: 正确
        Time:40 ms
        Memory:15588 kb
    ****************************************************************/
    

    追更:
    其实这道题和acwing上面,这道题是一样的
    在这里插入图片描述
    应该考虑答案影响的四段

    最优质一定是在00000111110000011111
    这种情况下的
    我们用s1记录00000的最长长度
    用s2 记录0000011111的最长长度
    用s3 记录000001111100000的最长长度
    用s4 记录00000111110000011111的最长长度
    最终答案就是s3,s4中最大值
    O(n)
    该题code:

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        int n; cin >> n;
        int s1 = 0,s2 = 0,s3 = 0,s4 = 0;
        for(int i=1;i<=n;i++){
            int x;scanf("%d",&x);
            if(x == 1){
                ++ s1;
                s3 = max(s2 + 1,s3 + 1);
            }else{
                s2 = max(s1 + 1,s2 + 1);
                s4 = max(s3 + 1,s4 + 1);
            }
        }
        cout << max(s3,s4) <<endl;
        return 0;
    }
    
    展开全文
  • 编程函数保证接收的一定是一个介于min和max之间([min, max]区间内)的一个整数并最后返回该整数。它负责接收用户的输入,进行验证,如果用户输入的数不在min和max之间,则会提示继续输入,直到输入合法时为止。 其...

    编程函数保证接收的一定是一个介于min和max之间([min, max]区间内)的一个整数并最后返回该整数。它负责接收用户的输入,进行验证,如果用户输入的数不在min和max之间,则会提示继续输入,直到输入合法时为止。
    其完整的函数原型为:int getint(int min, int max);

    在主函数中输入min, max,然后调用上述函数。

    程序的运行结果示例:
    3,100↙
    Please enter an integer [3…100]:
    -1↙
    Please enter an integer [3…100]:
    103↙
    Please enter an integer [3…100]:
    45↙
    The integer you have entered is:45

    首先输入区间,输入格式: “%d,%d”
    输入整数提示信息:“Please enter an integer [%d…%d]:\n”
    输入整数格式: “%d”
    输出格式:“The integer you have entered is:%d\n”

    #include<stdio.h>
    int getint(int min, int max);
    int main()
    {
        int max,min,n;
        scanf("%d,%d",&min,&max);   //[3,100],min,max  
        n=getint(min,max);
        printf("The integer you have entered is:%d\n",n);
    }
    int getint(int min, int max)
    {
        int x;
        do{
            printf("Please enter an integer [%d..%d]:\n",min,max);
            scanf("%d",&x);
        }while(x<min||x>max);     //当不满足条件时一直循环提示用户输入信息,此处do—while语句最合适
        return x;
    }
    
    展开全文
  • 对于一个正整数n,给定序列a1~an,求出序列al,al+1…ar,使得Σai(l<=i<=r)最大 已知|ai|<...枚举右端点r,枚举过程中求出最大的sum[r]-sum[l-1],然后跟答案取max 难度升级:我们求出的
  • 给定一个序列求其长度大于f的子区间的平均值的最大值 思路 求平均值可以用二分法来找平均值,先假设一个平均值,让原序列a减去假设平均值生成一个新序列b,b序列中有正有负,将b序列的前缀和存在sum数组中,区间[i,j...
  • 题目描述给定一个数组序列,需要求选出一个区间,使得该区间是所有区间中经过如下计算的值最大的一个:区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列[6 2 ...
  • 795 区间子数组个数

    2021-02-13 13:05:25
    题目描述: 给定一个元素都是正整数的数组A ,正整数 L 以及 R (L <= R)。 求连续、非空且其中最大元素满足大于等于L 小于等于R的数组个数。 例如 : ...(1)分别找出最大数是R和L-1的区间子数组
  • 给定一个序列a[1],a[2],a[3]…a[n],你的工作是计算序列的最大和。例如,给定(6,-1,5,4,-7),这个序列中的最大和是6 +(-1)+ 5 + 4 = 14。 输入 输入的第一行包含一个整数T(1<=T<=20),这意味着测试用例...
  • 是否可以做到:nmlog(m) 、、、 j=1列:线段树最初存储p1, p2-1, p3-2, p4-3, p5-4,取max,dp1 = a1 + 线段树.max 、、、 j=2列:区间修改[p1] -= 1 [p2-1, p3-2, ..] += 1,dp2 = a2 + 线段树.max 、、、、、、...
  • 记录一下字母最晚出现的位置,不断更新当前枚举区间的右端点,记录一下字母最晚出现的位置,不断更新当前枚举区间的右端点,记录一下字母最晚出现的位置,不断更新当前枚举区间的右端点, 记录一下字母最晚出现的...
  • 区间调度问题详解

    2021-03-03 10:58:45
    今天给大家介绍一下区间调度问题。区间调度是一类难度比较大,但同时应用比较广的问题,经常会在面试中以各种形式出现。本文将会介绍区间调度的各种变形,希望能使大家在面临区间调度问题时得心应手,并可以在实际...
  • 题目一描述: 给定一个整数数组 nums ,找到一个具有最大和的连续数组(...动态规划: dp[i]=Math.max(dp[i-1]+nums[i],nums[i]) 贪心法: 分治法: 最优解:动态规划 代码: /** * @param {number[]} nums * @re
  • 无重叠区间 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1...
  • 转自http://blog.csdn.net/acmer_ak/article/details/52002537#include #include #include #include #include #define MAXN 100010#define inf 0x3f3f3f3fusing namespace std;...//区间[l,r]int add;/...
  • 假设长度为 ppp 的后缀,原本的 max⁡endpos\max endposmaxendpos 为 xxx ,那么区间加 [x−p+2,n−p+1][x-p+2,n-p+1][x−p+2,n−p+1] 即可,因为左端点属于这个区间内的时候,原来的那个没有被包含,而这个新的被...
  • 题意:\(n\times n\) 的棋盘上有 \(n\) 颗棋子,每行每列都有且仅有一颗棋子,求出有多少个 \(k\times k\) 的棋盘也满足每行每列只有一颗棋子。 将棋盘的 \(x\) 轴看作上一题中每个点的下标,\(y\) 轴看作这个点的...
  • nums 中,数组的范围是数组中最大元素和最小元素的差值。返回 nums 中所有数组范围的和 。数组是数组中一个连续非空的元素序列。 示例 1: 输入:nums = [1,2,3] 输出:4 解释:nums 的 6 个子数组如下所...
  • 工作时有些系统不支持 in、exists 等查询,不支持笛卡尔积,这时用窗口函数会比较容易解决。 主要用到的窗口函数:sum() over( order by …);lag() over( order by …) let’s do it 案例:有一组数据,第一列是...
  • 题目清单3.1 LeetCode 5459(基础形式)题目大意题目思路3.2 2021牛客寒假算法基础集训营5 石子游戏题目大意题目思路3.3 牛客OI周赛15-普及组 - C - 区间加题目大意题目思路O(n2)O(n^2)O(n2)解法O(n)O(n)O(n)解法3.4...
  • 说明:输入的数组为{1,-2,3,10,—4,7,2,一5},和最大的数组为{3,10,一4,7,2},因此输出为该数组的和 18。 思路 直接用简化动态规划,使用一个变量sum来表示当前连续的数组和,以及一个变量res来表示中间出现...
  • 给定一个整数数组 nums ,找到一个具有最大和的连续数组(数组最少包含一个元素),返回其最大和。 示例 1: 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续数组 [4,-1,2,1] 的和最大,为 6 。 ...
  • 如果边界两个字符是相等的,那么直接当前区间的最长回文串子序列+2, 如果是不相等的情况下,就要判断是包含左端点不包含右端点的长度长,还是包含右端点不包含左端点的长度长, 这一点的思路是和最长公共序列的思路是...
  • 对于任意序列可以计算一个X值,X=sum(subArray) * min(subArray) 求最大X X = (6+4+5) * 4 = 60 function fn(arr){ let max = 0 let result = [] while(arr.length){ let num = Math.max(...arr) ...
  • Input 3 4 1 2 3 4 3 7 4 -1 3 5 -5 5 Output YES ...思路:从第一个元素开始累加,用一个临时变量记录累加...(注意子区间不能同时取左右两端点,分两种情况讨论即可) #include <bits/stdc++.h> using namespa..
  • 输入一串数字,给你M个询问,每次询问就给你两个数字X,Y,要求你说出X到Y这段区间内的最大数。 输入描述: 第一行两个整数N,M表示数字的个数和要询问的次数; 接下来一行为N个数; 接下来M行,每行都有两个整数X,Y。 ...
  • 例如:-2 5 3 -6 4 -8 6 maxsum=8无论是高中学习c语言还是现在的Java,首先想法是就是找出所有的数组,重复计算,然后求其和,取最大。int Maxsum1(int *array,int n){int max=-INF;int sum;int i,j;for(i=0;imax)...
  • 区间DP详解

    2021-08-11 11:07:33
    1、acwing 282 石子合并 区间dp基础题 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时...
  • 区间筛板题目。 AC代码 #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define int long long #define endl "\n" const int max_n = 1e6 + 100; bool used[max_n], u[max_n]; ...
  • 区间DP练习

    2021-07-12 16:33:44
    dp[i][j]dp[i][j]dp[i][j]表示以i为开头,长度为j的区间内的最长合法序列 dp[i][j]dp[i][j]dp[i][j]能由2种方式转移过来 1)如果s[i]==s[i+j−1]s[i]==s[i+j-1]s[i]==s[i+j−1] dp[i][j]=max(dp[i][j],dp[i+1][j−...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,165
精华内容 28,066
关键字:

max子区间