精华内容
下载资源
问答
  • 区间相乘
    2019-05-06 20:55:48

    Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

    Example 1:

    Input: [2,3,-2,4]
    Output: 6
    Explanation: [2,3] has the largest product 6.
    

    Example 2:

    Input: [-2,0,-1]
    Output: 0
    Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

    题目大意:

    给出一个数列,求解出区间的连乘的最大值。可以包括单个元素。

    解题思路:

    原始的思路是,可以记录下当前数值下的连乘所得到的正数和负数的值。这样我们可以消除此后还会出现负数的影响。但是这样我们会发现在符号变化时或者都是负数或者都是正数或者出现0时,判断量较大。

    所以我们可以记录当前位置与之前得到的最大与最小值,同时与本位置相乘并且与自身相比较得出当前的最大与最小值,这样的话我们可以看出,当符号发生变化:(最大值*当前值)会变成最小值,(最小值*当前值)会变成最大值。当遇到0时,计算会在之后重新开始。

    class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            int m_max(1), m_min(1), result(INT_MIN);
            for(int num:nums){
                int cor_min = std::min(num, std::min(m_min*num, m_max*num));
                int cor_max = std::max(num, std::max(m_min*num, m_max*num));
                result = std::max(result, cor_max);
                m_max = cor_max, m_min = cor_min;
            }
            return result;
        }
    };

     

    更多相关内容
  • 区间乘法&区间加法&区间修改

    千次阅读 2020-02-10 18:05:33
    将某区间每一个数乘上xx 将某区间每一个数加上xx 求出某区间每一个数的和 输入格式 第一行包含三个整数n,m,pn,m,p,分别表示该数列数字的个数、操作的总个数和模数。 第二行包含nn个用空格分隔的整数...

    题目描述

    如题,已知一个数列,你需要进行下面三种操作:

    • 将某区间每一个数乘上 xx

    • 将某区间每一个数加上 xx

    • 求出某区间每一个数的和

    输入格式

    第一行包含三个整数 n,m,pn,m,p,分别表示该数列数字的个数、操作的总个数和模数。

    第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。

    接下来 mm 行每行包含若干个整数,表示一个操作,具体如下:

    操作 11: 格式:1 x y k 含义:将区间 [x,y][x,y] 内每个数乘上 kk

    操作 22: 格式:2 x y k 含义:将区间 [x,y][x,y] 内每个数加上 kk

    操作 33: 格式:3 x y 含义:输出区间 [x,y][x,y] 内每个数的和对 pp 取模所得的结果

    输出格式

    输出包含若干行整数,即为所有操作 33 的结果。

    输入输出样例

    输入 #1

    5 5 38
    1 5 4 2 3
    2 1 4 1
    3 2 5
    1 2 4 2
    2 3 5 5
    3 1 4

    输出 #1复制

    17
    2

    说明/提示

    【数据范围】

    对于 30\%30% 的数据:n \le 8n≤8,m \le 10m≤10
    对于 70\%70% 的数据:n \le 10^3n≤103,m \le 10^4m≤104
    对于 100\%100% 的数据:n \le 10^5n≤105,m \le 10^5m≤105

    除样例外,p = 571373p=571373

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #pragma warning(disable:4996)
    struct Node
    {
    	ll l, r;
    	ll lazy = 0, sum = 0, mlz = 1;
    }tree[500005];
    ll input[500005];
    int n, m, p;
    void pushup(ll k)
    {
    	ll k1 = tree[k].mlz, k2 = tree[k].lazy;
    	tree[k << 1].sum = (tree[k << 1].sum*k1 + k2 * (tree[k << 1].r - tree[k << 1].l + 1)) % p;
    	tree[k << 1 | 1].sum = (tree[k << 1 | 1].sum*k1 + k2 * (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1)) % p;
    	tree[k << 1].mlz = (tree[k << 1].mlz*k1) % p;
    	tree[k << 1 | 1].mlz = (tree[k << 1 | 1].mlz*k1) % p;
    	tree[k << 1].lazy = (tree[k << 1].lazy*k1 + k2) % p;
    	tree[k << 1 | 1].lazy = (tree[k << 1 | 1].lazy*k1 + k2) % p;
    	tree[k].lazy = 0;
    	tree[k].mlz = 1;
    	return;
    }
    void build(int k, int l, int r)
    {
    	tree[k].l = l, tree[k].r = r;
    	if (l == r)
    	{
    		tree[k].sum = input[l]%p; return;
    	}
    	int mid = (l + r) >> 1;
    	build(2 * k, l, mid);
    	build(2 * k + 1, mid + 1, r);
    	tree[k].sum = (tree[2 * k].sum + tree[2 * k + 1].sum) % p;
    }
    void add1(int k, int dis, int x)//单点修改
    {
    	if (tree[k].l == tree[k].r)
    	{
    		//cout << "!!!!!   " << tree[k].l<<" "<< tree[k].sum<<"  << endl;
    		tree[k].sum += x;
    		return;
    	}
    	int mid = (tree[k].l + tree[k].r) >> 1;
    	if (mid >= dis)add1(2 * k, dis, x);
    	else add1(2 * k + 1, dis, x);
    	tree[k].sum = tree[2 * k].sum + tree[2 * k + 1].sum;
    }
    void add2(int k, ll l, ll r, ll x)
    {
    	if (tree[k].l == l && tree[k].r == r)
    	{
    		tree[k].sum += ((r - l + 1)*x) % p;
    		tree[k].lazy = (tree[k].lazy + x) % p;
    		return;
    	}
    	pushup(k);
    	int mid = (tree[k].l + tree[k].r) >> 1;
    	if (mid >= r)add2(2 * k, l, r, x);
    	else if (mid < l)add2(2 * k + 1, l, r, x);
    	else add2(2 * k, l, mid, x), add2(2 * k + 1, mid + 1, r, x);
    	tree[k].sum = (tree[2 * k].sum + tree[2 * k + 1].sum) % p;
    }
    void mul(int k, ll l, ll r, ll x)
    {
    	if (tree[k].l == l && tree[k].r == r)
    	{
    		tree[k].sum = (tree[k].sum*x) % p;
    		tree[k].mlz = (tree[k].mlz*x) % p;
    		tree[k].lazy = (tree[k].lazy*x) % p;
    		return;
    	}
    	pushup(k);
    	int mid = (tree[k].l + tree[k].r) >> 1;
    	if (mid >= r)mul(2 * k, l, r, x);
    	else if (mid < l)mul(2 * k + 1, l, r, x);
    	else mul(2 * k, l, mid, x), mul(2 * k + 1, mid + 1, r, x);
    	tree[k].sum = (tree[2 * k].sum + tree[2 * k + 1].sum) % p;
    }
    ll query(int k, ll l, ll r)
    {
    	if (tree[k].l == l && tree[k].r == r)
    	{
    		return tree[k].sum%p;
    	}
    	pushup(k);
    	int mid = (tree[k].l + tree[k].r) >> 1;
    	if (mid >= r)return query(2 * k, l, r) % p;
    	if (mid < l)return query(2 * k + 1, l, r) % p;
    	return (query(2 * k, l, mid) % p + query(2 * k + 1, mid + 1, r) % p) % p;
    }
    int main()
    {
    
    	cin >> n >> m >> p;
    	for (int i = 1; i <= n; i++)scanf("%d", &input[i]);
    	build(1, 1, n);
    	//for (int i = 1; i <= 7; i++)cout << tree[i].sum << " ";
    	while (m--)
    	{
    		int a;
    		scanf("%d", &a);
    		if (a == 1)
    		{
    			int x, y, k;
    			
    			scanf("%d%d%d", &x, &y, &k);k %= p;
    			mul(1, x, y, k);
    		}
    		else if (a == 2)
    		{
    			int x, y, k;
    			
    			scanf("%d%d%d", &x, &y, &k);k %= p;
    			add2(1, x, y, k);
    		}
    		else
    		{
    			int x, y;
    			scanf("%d%d", &x, &y);
    			cout << query(1, x, y)%p << endl;
    		}
    	}
    
    
    
    }

     

    展开全文
  • 对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n]。例如34*56,我们通常这么计算: 将3,4分别于6相乘,记录低位的进位,然后将3,4对5进行相同的操作,知道第二个乘数
  • public class Test { public int getMaxValue2(int[] y, int[] x) { // 动态转移方程 l和r代表当前构造方案的区间 // dp[l][r] = max( dp[l+1][r]+x[a]*y[l], dp[l][r-1]+x[a]*y[r]); a=l+n-r int[][] dp = new int...

    给定两个数组x,y,每次从数组x顺序取一个数a,从数组y的头或者尾巴取一个数b,求所有a*b的最大和。

    举例说明:

     x= {1,2,3},y={1,2,1};

    依次从x取出的数为 1 ,2,3。

    依次从y 取出的数为 1 ,1,2。

    输出结果为 1*1+2*1+3*2 = 9; 

    刚开始想到的就是暴力枚举所有情况,然后再剪枝,结果稳稳地超时了。

    代码如下

    package com.company.nothing;
    
    import java.util.*;
    
    public class Test {
       
    
        private int ans = 0;
        private Map<String, Integer> map;
        public int getMaxValue(int[] nums, int[] values) {
            // write code here
            map = new HashMap<>();
            find(0, nums, 0, nums.length - 1, values, 0);
            return ans;
        }
    
        private void find(int sum, int[] nums, int l, int r, int[] values, int x) {
            if (l > r) {
                ans = Math.max(ans, sum);
                return;
            }
            String key = l + "--" + r;
            Integer old = map.get(key);
            if (old != null && old.intValue() >= sum) {
                return;
            } else {
                map.put(key, sum);
            }
            find(sum + nums[l] * values[x], nums, l + 1, r, values, x + 1);
            find(sum + nums[r] * values[x], nums, l, r - 1, values, x + 1);
        }
    }
    

    后来经人指点采用区间dp。

    package com.company.nothing;
    
    import java.util.*;
    
    public class Test {
        
    
        public int getMaxValue2(int[] y, int[] x) {
            // 动态转移方程 l和r代表当前构造方案的区间    
            // dp[l][r] = max( dp[l+1][r]+x[a]*y[l],  dp[l][r-1]+x[a]*y[r]);  a=l+n-r
            int[][] dp = new int[x.length][x.length];
            for (int i = 0; i < x.length; i++) {
                for (int j = 0; j < dp[i].length; j++) {
                    dp[i][j] = 0;
                }
            }
            //每个数只剩一个时,x数组一定是取到最后一个了
            for (int i = 0; i < x.length; i++) {
                dp[i][i] = y[i] * x[x.length - 1];
            }
            // len从1开始向外拓展,一开始没想到这层,只用了两个循环,猝。
            // 向外扩展时需保证当前dp[l][r]已经是最优解,这样更新才有意义,所以要限制每次更新的长度。
            for (int len = 1; len <= x.length; len++) {
                for (int l = 0; l < x.length; l++) {
                    //这边可以优化成 r = l+len-1,因为重复计算了,这样时间优化为o(n*n)
                    for (int r = l; r-l+1 <= len && r < x.length; r++) {
                        if (l - 1 >= 0) {
                            dp[l - 1][r] = Math.max(dp[l - 1][r], 
                                        dp[l][r] + y[l - 1] * x[x.length - 1 - (r + 1 - l)]);
                        }
                        if (r + 1 < x.length) {
                            dp[l][r + 1] = Math.max(dp[l][r + 1], 
                                        dp[l][r] + y[r + 1] * x[x.length - 1 - (r + 1 - l)]);
                        }
                    }
                }
            }
            return dp[0][x.length - 1];
        }
    
       
    }
    

    本质上就是先算出区间长度为1的结果,之后合并成2,再合并成3,以此类推。
     

    展开全文
  • MMULT()函数是矩阵相乘函数,很多人运用得轻车熟路,但还有许多人想学,说实在的!照着套用人家设计好的MMULT公式倒也不错,但许多人根据就不知道这是怎样个原理!再说白的,许多人学习《线性代数》,其实是死记...
  • 1 划分为若干长度为len的区间 2 确定区间起点 i 与 终点 3 用中间变量 k 遍历整个区间, 计算该区间min 写法一:其中每个新区间的 dp[i][j] ( A(i) * A(i + 1) * A(i + 2) * ... * A(j) )需要先计算一次, 有个...

    1 划分为若干长度为len的区间

    2 确定区间起点 i 与 终点

    3 用中间变量 k 遍历整个区间, 计算该区间min

    写法一:其中每个新区间的 dp[i][j] ( A(i) * A(i + 1) * A(i + 2) * ... * A(j) )需要先计算一次, 有个初值再进行后续循环

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int dp[10005][10005];
    int n;
    int w[10005];
    
    int main()
    {
        cin >> n;   // 矩阵数量, n 个矩阵, n + 1个信息
        for(int i = 0; i <= n; ++i) cin >> w[i];     //下标 0 ~ n 有效
        
        for(int len = 2; len <= n ; ++len)   //枚举不同区间的长度
            for(int i = 1; i + len - 1 <= n; ++i)   //起点
            {
                int j = i + len - 1;    //终点
                dp[i][j] = dp[i + 1][j] + w[i - 1] * w[i] * w[j];    
    // 计算初值, 后面少遍历一次, 其实这个表达式就是把下面的一长串拿出来, 
    // i j k都是确定的,带进去化简得到
                for(int k = i + 1; k < j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i - 1] * w[k] * w[j]);
            }
        
        cout << dp[1][n];
        
        
        return 0;
    }
    
    //区间dp 先算小区间, 再算大区间
    // dp[i][j], 第i个 - 第j个矩阵范围内的矩阵连乘的最小计算次数    1 2 3 4 5 实际上算四个矩阵 2 3 4 5, 分别是他的第二个维度
    // dp[1][3] = A1 * A2 * A3
    // 矩阵连乘, 先相乘, 再将结果相加 = 总运算次数

    写法二: 直接给他初值0x3f3f3f3f, 从头开始计算

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int dp[10005][10005];
    int n;
    int w[10005];
    
    int main()
    {
        cin >> n;   // 矩阵数量, n 个矩阵, n + 1个信息
        for(int i = 0; i <= n; ++i) cin >> w[i];     //下标 0 ~ n 有效
        
        for(int len = 2; len <= n ; ++len)   //枚举不同区间的长度
            for(int i = 1; i + len - 1 <= n; ++i)   //起点
            {
                int j = i + len - 1;    //终点
                dp[i][j] = 0x3f3f3f3f;    //直接给初值 后面完全遍历
                for(int k = i; k < j; ++k)    //这里需要注意
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i - 1] * w[k] * w[j]);
            }
        
        cout << dp[1][n];
        
        
        return 0;
    }
    
    //区间dp 先算小区间, 再算大区间
    // dp[i][j], 第i个 - 第j个矩阵范围内的矩阵连乘的最小计算次数    1 2 3 4 5 实际上算四个矩阵 2 3 4 5, 分别是他的第二个维度
    // 矩阵连乘, 先相乘, 再将结果相加 = 总运算次数

    展开全文
  • 这题一看就是莫队吧 然后如何看区间里面是否有两个数相减 或相加 或相乘为k 先讲相乘 因为这个最简单 我们直接暴力遍历k的因子 如果 y和k/y 都在的话 那么就可以 反正是带根号的 和莫队的复杂度一样 没什么问题 ...
  • 区间相交问题

    千次阅读 2016-03-01 14:54:11
    给定x轴上n个闭区间,去掉尽可能少的闭区间,使剩下的闭区间都不相交。 注意:这里,若区间与另一区间之间仅有端点是相同的,不算做区间相交。 例如,[1,2]和[2,3]算是不相交区间。  输入格式 第一行一个正...
  • python对应位置相乘

    千次阅读 2019-05-28 13:32:14
    import time import numpy as np A = np.arange(1,1000001).reshape(500,1000,2) B = np.arange(0,1000000).reshape(500,1000,2) for i in range(10): start=time.time() np.multiply(A,B) ... p...
  • 该文首先分析了弹道中段进动锥体目标RCS...基于非参数统计理论,本文提出了一种变区间分组检验相乘积累的RCS序列进动周期估计方法,仿真结果表明,该方法不仅能够有效克服虚假周期影响,并能明显改善进动周期估计精度.
  • 算法基础 -- 区间合并

    2022-02-12 11:31:18
    区间合并 问题: 给定 n 个区间 [ l , r ],要求合并所有有交集的区间。(如果在端点处相交,也算有交集) 输出合并完成后的区间个数。 核心思想: 首先按每个区间的左端点进行排序,然后再依次处理剩下三种可能...
  • 题目大意 有n个矩阵相乘,保证可以相乘。...很明显,这是一道区间DP的题。定义为第个矩阵到第个矩阵连乘的最小复杂度。可以知道 其中,表示第i个矩阵的行数,表示第i个矩阵的列数。然后代码就很简单了。 ...
  • 区间DP 矩阵相乘复杂度计算

    千次阅读 2016-04-01 10:10:10
    一个 a*b的矩阵与一个b*c的矩阵相乘,复杂度是 a*b*c,会得到一个a*c的矩阵。但是!!!我出题目的时候懵逼了!!!!!,复杂度弄成a*b*b*c了,所以你们就按我的来。 现在有N个矩阵连乘,不同的计算顺序复杂度是不...
  • 总而言之,如果输入时2 3 5 10 2,就是23的矩阵和35的矩阵,,,到10*2的矩阵完成相乘。不同的相乘顺序会得到不同的计算次数。只不过这道题是一个环形的。断开的点不同,情况不同。 还是和环形石子合并一样的思路,...
  • 矩阵相乘最少计算次数问题

    千次阅读 2019-10-18 11:13:14
    矩阵相乘最少计算次数 题目描述 不同的计算顺序的乘法计算次数是不一样的,如 (AB)C(AB)C(AB)C 和 A(BC)A(BC)A(BC)的乘法计算次数分别为 p0p1p2+p0p2p3p_0p_1p _2 + p_0p_2p_3p0​p1​p2​+p0​p2​p3​ 和 p1p2p3+p...
  • 算法 | 大数相乘

    2021-07-18 16:01:13
    注意一点:一个n位数乘以一个m位的数,相乘最终的结果位数区间应该在:n到n+m之间。 代码体现: //大数相乘 public class Solution { public static void main(String[] args) { String a = "9674657999"; String...
  • matlab中两个函数相乘

    千次阅读 2021-04-27 09:06:23
    而 1 中变量相乘或除 时都以点乘和点除的形式写出来的 尝试用 fminbnd fminunc fminsearch 及遗传算法求解上述函数在区间[-1,2]中的最小值,看看 它们四个有...... 当一个指令或矩阵太长时,可用???续行 ? 冒号的作用...
  • 算法:C++实现大数相乘

    千次阅读 2017-08-02 08:53:32
    大数相乘,是指那些相乘结果或是乘数本身用long long类型都会溢出的数字,通常这些数字都通过string类型进行表示,借助于可动态调整大小的数据结构(vector,string,deque)模拟实现数字的乘法操作。
  • 大数相乘

    2019-09-18 18:01:50
    大数相乘,是指那些相乘结果或是乘数本身用...对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n]。例如34*56,我们通常这么计算:将3,4分别于6相乘,记录低位的进位,然后将3,4对5...
  • 把一个整数分解成几个质数相乘的形式 #include<stdio.h> int main(){ int n; scanf("%d",&n); printf("%d=",n); for(int i=2;i<n;i++){ if(n%i==0){ n/=i; printf("%d*",i); i--; }...
  • SIUS已知样本均值和样本方差做区间估计总体X~N(μ,σ2), 其中μ是总体均值,σ2是总体方差,σ是总体标准差,样本容量为n, 样本均值为x。在下面输入n,x和σ的值后,单击“开始计算”按钮进行计算:n=x=σ=总体X~N(μ...
  • 区间合并类动态规划也属于线性动规。它以区间的长度为阶段,使用区间的两个端点来描述这个状态(如 F[i][j]F[i][j]F[i][j])。在区间DP中,一个阶段通常由若干个比它更小且包含于它的区间所代表的的状态转移过来。 ...
  • 创建一个4行5列的标准正态分布随机数,并指定随机数种子为学号后两位,下图为产生的示例数据。 再创建一个4行5列的标准正态分布随机数,并指定随机数种子为学号后两位,将其与上图所示二维数组进行相乘
  • 正确解法: 所有的0都一定是2*5产生的,所以将每个数拆成一堆2乘上一堆5再乘上一个数,之后统计下有多少个2和多少个5取少的那个就是答案 例题: 如下的10行数据,每行有10个整数,请你求出它们的乘积的末尾有多少个...
  • 大家应该都知道一般我们在区间dp的更新中都需要三层循环来实现,第一层枚举区间长度,第二层枚举区间起始点,第三层就是枚举区间断点来寻求最优解,对于动态规划问题来说n^3的复杂度属实有点高,那我们能不能找到...
  • 而一个拆分后包含某一个素数的合数,一定可以通过这个素数和大于等于2的自然数相乘得到,同样这个素数和大于等于2的自然数相乘可以得到所有能够拆分得到这个素数的合数。证明也很简单,你只需要思考让合数除以这...
  • * 动态规划在矩阵链相乘的应用,目的求出最小的计算代价,即矩阵的计算顺序,用加小括号表示。 * 主要的计算思想是递归,而且是带备忘录的递归,辅助作用,存放计算结果。 问题描述:当计算一个矩阵链的时候,计算...
  • 分析:二分,两边夹,细节见代码。(复杂度为O(2nlog(maxa*maxb))) 代码一: #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;algorithm&gt;...cons...
  • 给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个: 区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列 [6 2 1]则...
  • 区间动态规划的含义与模板解释 区间DP,其实求的就是一个区间内的最优值. 一般这种题目,在设置状态的时候,都可以设f[i][j]为区间i-j的最优值 而f[i][j]的最优值,这有两个小区间合并而来的,为了划分这两个更小的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,329
精华内容 7,331
关键字:

区间相乘