精华内容
下载资源
问答
  • 取数游戏2

    2021-02-28 18:02:57
    给定两个长度为n的整数列A和B,每次你可以从A数列的左端或右端走一个。假设第i次走的为ax,则第i次走的的价值vi=bi⋅ax,现在希望你求出∑vi的最大值...对于第二个样例, 第一次从左边取走a1,v1=a1⋅b1=1

    给定两个长度为n的整数列A和B,每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax,则第i次取走的数的价值vi=bi⋅ax,现在希望你求出∑vi的最大值。

    输入描述:
    第一行一个数T,表示有T组数据。
    对于每组数据,第一行一个整数n,
    接下来两行分别给出A数列与B数列。

    输出描述:
    每一组数据输出一行,最大的∑vi。
    示例1
    输入
    2
    2
    1 1000
    2 1
    5
    1 3 5 2 4
    1 2 3 4 5
    输出
    2001
    52
    说明
    对于第二个样例,
    第一次从左边取走a1,v1=a1⋅b1=1,
    第二次从左边取走a2,v2=a2⋅b2=6,
    第三次从右边取走a5,v3=a5⋅b3=12,
    第四次从右边取走a4,v4=a4⋅b4=8,
    第五次取走剩下的a3,v5=a3⋅b5=25。
    总价值∑vi=1+6+12+8+25=52

    备注:
    T≤10
    1≤n≤103
    1≤ai,bi≤103

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=1010;
    int Case,n,a[N],f[N];
    int main()
    {
    	scanf("%d",&Case);
    	while (Case--)
    	{
    		scanf("%d",&n);
    		for (int i=1;i<=n;++i)
    			scanf("%d",a+i);
    		f[0]=0;
    		for (int x,i=1;i<=n;++i)
    		{
    			scanf("%d",&x);
    			f[i]=f[i-1]+a[i]*x;
    			for(int j=i-1;j;--j)
    				f[j]=max(f[j-1]+a[j]*x, f[j]+a[n-i+j+1]*x);
    			f[0]+=a[n-i+1]*x;
    		}
    		int ans=0;
    		for (int i=0;i<=n;++i)
    			ans=max(ans,f[i]);
    		printf("%d\n",ans);
    	}
    	return 0;
    }
    
    展开全文
  • ,就是像尺子一样,在一段区域内,选取区间端点,通过控制下标的方法,一段一段的截取。...我们可以先用sum存当前子序列的和,从左边第个数来存,知道这子序列的和大于等于m为止,再记录下...

    尺取

    尺取,就是像尺子一样,在一段区域内,选取区间端点,通过控制下标的方法,一段一段的截取。
    举个栗子。。。(大佬们都举的
    Poj3061
    给长度为n的数组和一个整数m,求总和不小于m的连续子集序列的最小长度。
    输入
    n = 10, m = 15.
    5 1 3 5 10 7 4 9 2 8
    输出
    2
    我们可以先用sum存当前子序列的和,从左边第一个数来存,知道这个子序列的和大于等于m为止,再记录下这个长度。
    如下
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    5 1 3 5 10 7 4 9 2 8
    菜鸟理论,dalao看看就好。

    展开全文
  • 所以不能先向前再向下然后向左到达),然后可以推第二列,发现有从上往下走和从下往上走,从上往下走的话,发现第一行是只有左边能走过来的,于是接下来的每行都是上一行到达的最大值和从左边过来的,当然从下往上走...

    洛谷 P7074 [CSP-J2020] 方格取数

    思路:第一列是肯定可以推出的,而且是唯一的(因为不能往左走,所以不能先向前再向下然后向左到达),然后可以推第二列,发现有从上往下走和从下往上走,从上往下走的话,发现第一行是只有左边能走过来的,于是接下来的每行都是上一行到达的最大值和从左边过来的,当然从下往上走和刚才的很类似,先推最后一行,这里就不作太详细的分析了,然后推完了,把两种情况中较大的一个放到数组里,接着一直推,推出最后一行。
    注意点

    我们这里是一列列推的,所以循环外层是代表列,内层是行,不要在计算时把两者搞反了,如下,三个max那里j代表的是行,i代表的是列。

    代码

    #include<bits/stdc++.h>
    using namespace std;
    long long n,m,x[1001][1001],a[1001],b[1001],i,j;
    int main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n>>m;
    	for(i=1;i<=n;i++)
    		for(j=1;j<=m;j++)
    			cin>>x[i][j];	
    	for(i=2;i<=n;i++)
    		x[i][1]+=x[i-1][1];
    	for(i=2;i<=m;i++){
    		a[n]=x[n][i-1]+x[n][i];
    		for(j=n-1;j>=1;j--)
    			a[j]=max(x[j][i-1],a[j+1])+x[j][i];
    		b[1]=x[1][i-1]+x[1][i];
    		for(j=2;j<=n;j++)
    			b[j]=max(x[j][i-1],b[j-1])+x[j][i];
    		for(j=1;j<=n;j++)
    			x[j][i]=max(a[j],b[j]);
    	}
    	cout<<x[n][m];
    	return 0;
    }
    
    展开全文
  • 给定两正整数a,b,分别定义两集合L和R, 集合L:即把1~a,1~b中...现L中任整数作为A,R中任整数作为B,如果必要在B的左边补0,使得B达到:“b的位数+1”位(十进制),然后把B接到A的右边,形成

    给定两个正整数a,b,分别定义两个集合L和R,

    集合L:即把1~a,1~b中整数乘积的集合定义为L = {x * y | x,y是整数且1 <= x <=a , 1 <= y <= b};

    集合R:1~a,1~b中整数异或的集合定义为集合R = {x ^ y | x,y是整数且1 <= x <=a , 1 <= y <= b},其中^表示异或运算。

    现从L中任取一个整数作为A,从R中任取一个整数作为B,如果必要在B的左边补0,使得B达到:“b的位数+1”位(十进制),然后把B接到A的右边,形成的一个十进制数AB。求所有这样形成数的和。


    输入a,b  1<=a<=30, 1<=b<=10000000。

    输出所有产生的AB数的和,由于结果比较大,输出对1000000007取余数的结果。


    例如:a = 2, b = 4,

    则L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} =  {1, 2, 3, 4, 6, 8}

      R =  {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} =  {0, 1, 2, 3, 5, 6}

    相接的时候保证R中的数至少有两位,所以相接后所有的AB数的集合是

    {

    100, 101, 102, 103, 105, 106,

    200, 201, 202, 203, 205, 206,

    300, 301, 302, 303, 305, 306,

    400, 401, 402, 403, 405, 406,

    600, 601, 602, 603, 605, 606,

    800, 801, 802, 803, 805, 806

    }

    输出它们的和:14502。


    题目分析:

    这其实算两个题,这么整齐的矩阵实际上主要就是Sum(L)和Sum(R).

    求这两个部分都是独立的。所以拆成2个题也没什么问题。

    最后的结果result=Sum(L)*Count(R)*Len(p)+Sum(R)*Count(L);

    Len(p)简单就是个Pow(10,"b的位数+1")

    public static int Len(int b)
     {
                int len = 100;
                while (b/10 > 0)
                {
                    len = len*10;
                    b = b/10;
                }
                return len;
    }

    • 这题一眼看上去,暴力肯定是可以实现的。
    var aa = new bool[a*b+1];
                var bb = new bool[a + b + 1];
                Int64 len = Len(b);
                Int64 result1 = 0;
                Int64 result2 = 0;
                int size1 = 0;
                int size2 = 0;
    
    
                for (int i = 1; i <= a; i++)
                {
                    for (int j = 1; j <= b; j++)
                    {
                        if (!aa[i*j])
                        {
                            result1 += ((i*j))%MOD;
                            size1++;
                            aa[i*j] = true;
                        }
                        if (!bb[i ^ j])
                        {
                            result2 += (i ^ j)%MOD;
                            size2++;
                            bb[i ^ j] = true;
                        }
                    }
                }
                result1 = (result1%MOD)*(len%MOD);
                result1 = (result1%MOD)*(size2%MOD);
                result2 = (result2%MOD)*(size1%MOD);
                return (int) ((result1 + result2)%MOD);

    • 优化
    但是暴力,算一个run(30,10000000)就会超过3秒了
    1.先优化 XOR 吧
    这个还算比较简单
    因为a<=30。把b分为很多段。
    00001-11111 

    1 00000
    1 11111
    。。
    X..X 00000
    X..X 11111

    Y..Y 00000
    b
    显然,对于b<=31的部分,直接暴力算效率也没问题。而对于 
    X..X 00000
    X..X 11111
    这种,直接算X..X乘以a与00000-11111 XOR的结果就行了。
    最后多出来的一段
    Y..Y 00000
    b
    数据量不会超过31,暴力吧。
    如果a更小的话,可以按000-111之类做更细的分解。但是基本按11111分解的效率就足够了。这个代码写得有点啰嗦,基本原理应该是对的。
    private static void DoXor(int a, int b)
            {
                var bb = new bool[a + b + 1];
                if (b <= 31)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        for (int j = 1; j <= b; j++)
                        {
                            if (!bb[i ^ j])
                            {
                                sum2 += (i ^ j)%MOD;
                                count2++;
                                bb[i ^ j] = true;
                            }
                        }
                    }
                    return;
                }
    
                int k = b/32 - 1;
                int m = (k + 1)*32;
                if ((b & 31) == 31)
                {
                    k = k + 1;
                    m = b + 1;
                }
                Int64 sum2kk = 0;
                Int64 count2kk = 0;
                for (int i = 1; i <= a; i++)
                {
                    for (int j = 0; j <= 31; j++)
                    {
                        if (!bb[i ^ j])
                        {
                            sum2kk += (i ^ j)%MOD;
                            count2kk++;
                            bb[i ^ j] = true;
                        }
                    }
                }
                count2 += (count2kk*k);
                sum2 += (sum2kk*k)%MOD;
                sum2 += count2kk*(k + 1)*k*(32/2)%MOD;
                for (int j = m; j <= b; j++)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        if (!bb[i ^ j])
                        {
                            sum2 += (i ^ j)%MOD;
                            count2++;
                            bb[i ^ j] = true;
                        }
                    }
                }
                var kk = new bool[32 + a + 1];
                for (int j = 1; j <= 31; j++)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        if (!kk[i ^ j])
                        {
                            sum2 += (i ^ j)%MOD;
                            count2++;
                            kk[i ^ j] = true;
                        }
                    }
                }
            }
    2.Sum(L)的优化

    把a*b的结果也分为a段
    1->b
    b+1->2b
    ...
    kb+1->(k+1)b
    ...
    (a-1)b+1->ab

    显然对于(k-1)b+1->kb这个区间
    只有(k->a)*b才会出现。
    所以(k-1)b+1->kb区间内,所以能被(k->a)整除的都在集合L里。
    对于(k-1)b+1->kb区间内,能被m整除的数的Count和Sum是很容易求的。
    很简单的思路就是计算Count(k),Count(k+1)..Count(a)
    但是这里有个重复的问题。比如k->a为3->8
    能被6整除的肯定能被3整除,所以算了Count(3)就不用算Count(6)
    于是开始求从k->a不包含倍数关系的集合
    3->8
    为3,4,5,7
    算完Count(3)+Count(4)+Count(5)+Count(7)。
    但是12在Count(3)的时候算了,在Count(4)的时候也算了。
    于是Count(3)+Count(4)+Count(5)+Count(7)-Count(3*4)-Count(3*5)-Count(3*7)....+Count(3*4*5).....-Count(3*4*5*7)
    实际计算的时候其实Count里面还要算gcd
    做完提交后才有人在群里面说这个是容斥原理

    	private const int MOD = 1000000007;
            private static Int64 count1 = 0;
            private static Int64 count2 = 0;
            private static Int64 sum1 = 0;
            private static Int64 sum2 = 0;
            public static int Len(int b)
            {
                int len = 100;
                while(b/10>0)
                {
                    len = len*10;
                    b = b / 10;
                }
                return len;
            }
    
            private static Int64 gcd2(Int64 a, Int64 b)
            {
                if (b == 0) return a; 
                return gcd2(b, a % b); 
            }
    
    
            private static List<int> ValidNum(int a, int k)
            {
                List<int> result = new List<int>();
                result.Add(k);
                bool bFlag = true;
                for (int i = k+1; i <= a; i++ )
                {
                    bFlag = true;
                    foreach (int kk in result)
                    {
                        if (i % kk == 0)
                        {
                            bFlag = false;
                            break;
                        }
                    }
                    if (bFlag)
                    {
                        result.Add(i);
                    }
                }
                return result;
            }
    
            private static void CalcSeg(Int64 k, Int64 b, Int64 m, bool add)
            {
                if (m < k ||m > k*b) return;
                Int64 start = ((k - 1) * b + 1) / m + 1;
                if (((k-1)*b+1)%m==0)
                    start = ((k - 1) * b + 1) / m;
                Int64 end = k * b / m;
                if (add)
                {
                    sum1 += ((start + end) * (end - start + 1) * m / 2) % MOD;
                    count1 += end - start + 1; 
                }
                else
                {
                    sum1 -= ((start + end) * (end - start + 1) * m / 2) % MOD;
                    if (sum1 < 0)
                    	sum1 += MOD;
                    count1 -= end - start + 1;
                }
            }
            public static int run(int a, int b)
            {
                count1 = count2 = sum1 = sum2 = 0;
                bool[] bb = new bool[a + b + 1];
                Int64 len = Len(b);
                for (int i = 1; i <= a; i++ )
                {
                    List<int> nums = ValidNum(a,i);
                    int nn = nums.Count;
                    int[] digit = new int[nn];
                    int ii,jj;
                    while (true)//这其实是一个求1-n的全部非空集合的一个模板
                    {
                        for (ii = 0; ii < nn && digit[ii] == 1; digit[ii] = 0, ii++) ;
                        if (ii == nn) 
                            break;
                        else         
                            digit[ii] = 1;
                        for (ii = 0; ii < nn && digit[ii] == 0; ii++) ; 
                        int c = 1;
                        Int64 mul = nums[ii];
                        for (jj = ii + 1; jj < nn; jj++)
                        {
                            if (digit[jj] == 1)
                            {
                                mul = (nums[jj] * mul) / gcd2(nums[jj], mul);//太耗时
                                c++;
                            }
                        }
                        CalcSeg(i, b, mul, c % 2 == 1);
                    }
                }
                DoXor(a,b);
                sum1 = (sum1 % MOD) * (len % MOD);
                sum1 = (sum1 % MOD) * (count2 % MOD);
                sum2 = (sum2 % MOD) * (count1 % MOD);
                return (int)((sum1 + sum2) % MOD);
            }

    运行了一下,总算在1秒以下了。但是还是慢,用工具分析了一下,发现计算gcd花费的时间太多了。
    又费了不少脑细胞,用递归把每个区间内的gcd重复计算的情况减少了很多。
    最后看着代码接近200行。。。应该有更简单的方法吧。。
    	private const int MOD = 1000000007;
            private static Int64 count1;
            private static Int64 count2;
            private static Int64 sum1;
            private static Int64 sum2;
    
            public static int Len(int b)
            {
                int len = 100;
                while (b/10 > 0)
                {
                    len = len*10;
                    b = b/10;
                }
                return len;
            }
    
            private static Int64 gcd2(Int64 a, Int64 b)
            {
                if (b == 0) return a;
                return gcd2(b, a%b);
            }
    
    
            private static List<int> ValidNum(int a, int k)
            {
                var result = new List<int>();
                result.Add(k);
                bool bFlag = true;
                for (int i = k + 1; i <= a; i++)
                {
                    bFlag = true;
                    foreach (int kk in result)
                    {
                        if (i%kk == 0)
                        {
                            bFlag = false;
                            break;
                        }
                    }
                    if (bFlag)
                    {
                        result.Add(i);
                    }
                }
                return result;
            }
    
            private static void CalcSeg(Int64 k, Int64 b, Int64 m, bool add)
            {
                if (m < k || m > k*b)
                {
                    return;
                }
                Int64 start = ((k - 1)*b + 1)/m + 1;
                if (((k - 1)*b + 1)%m == 0)
                    start = ((k - 1)*b + 1)/m;
                Int64 end = k*b/m;
                if (add)
                {
                    sum1 += ((start + end)*(end - start + 1)*m/2)%MOD;
                    count1 += end - start + 1;
                }
                else
                {
                    sum1 -= ((start + end)*(end - start + 1)*m/2)%MOD;
                    if (sum1 < 0)
                        sum1 += MOD;
                    count1 -= end - start + 1;
                }
            }
    
    
            private static void DoAdd(List<int> nums, int lastkk, Int64 pregcd, int lastn, int n, int i, int b)
            {
                if (lastn == n)
                {
                    return;
                }
    
                for (int m = lastkk + 1; m <= n; m++)
                {
                    Int64 newPregcd = pregcd*nums[m - 1]/gcd2(pregcd, nums[m - 1]);//gcd(a,b,c,d),gcd(a,b,c,e)的时候,pregcd就是gcd(a,b,c),这相当于一个缓存
                    CalcSeg(i, b, newPregcd, lastn%2 == 0);
                    DoAdd(nums, m, newPregcd, lastn + 1, n, i, b);//递归
                }
            }
    
    
            private static void DoXor(int a, int b)//啰嗦,可以简化一些代码的
            {
                var bb = new bool[a + b + 1];
                if (b <= 31)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        for (int j = 1; j <= b; j++)
                        {
                            if (!bb[i ^ j])
                            {
                                sum2 += (i ^ j)%MOD;
                                count2++;
                                bb[i ^ j] = true;
                            }
                        }
                    }
                    return;
                }
    
                int k = b/32 - 1;
                int m = (k + 1)*32;
                if ((b & 31) == 31)
                {
                    k = k + 1;
                    m = b + 1;
                }
                Int64 sum2kk = 0;
                Int64 count2kk = 0;
                for (int i = 1; i <= a; i++)
                {
                    for (int j = 0; j <= 31; j++)
                    {
                        if (!bb[i ^ j])
                        {
                            sum2kk += (i ^ j)%MOD;
                            count2kk++;
                            bb[i ^ j] = true;
                        }
                    }
                }
                count2 += (count2kk*k);
                sum2 += (sum2kk*k)%MOD;
                sum2 += count2kk*(k + 1)*k*(32/2)%MOD;
                for (int j = m; j <= b; j++)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        if (!bb[i ^ j])
                        {
                            sum2 += (i ^ j)%MOD;
                            count2++;
                            bb[i ^ j] = true;
                        }
                    }
                }
                var kk = new bool[32 + a + 1];
                for (int j = 1; j <= 31; j++)
                {
                    for (int i = 1; i <= a; i++)
                    {
                        if (!kk[i ^ j])
                        {
                            sum2 += (i ^ j)%MOD;
                            count2++;
                            kk[i ^ j] = true;
                        }
                    }
                }
            }
    
            public static int run(int a, int b)
            {
                count1 = count2 = sum1 = sum2 = 0;
                var bb = new bool[a + b + 1];
                Int64 len = Len(b);
                for (int i = 1; i <= a; i++)
                {
                    List<int> nums = ValidNum(a, i);
                    DoAdd(nums, 0, 1, 0, nums.Count, i, b);
                }
                DoXor(a, b);
                sum1 = (sum1%MOD)*(len%MOD);
                Console.WriteLine(sum1 + " " + count1 + " " + sum2 + " " + count2);
                sum1 = (sum1%MOD)*(count2%MOD);
                sum2 = (sum2%MOD)*(count1%MOD);
                return (int) ((sum1 + sum2)%MOD);
            }




    展开全文
  • 意思是3左边的3)中选出3(右边的3)。每数字分别有1、2、3,求出,并输出模10000的余数 样例输出 6 算法 典型的动态规划。 dp[i][j]dp[i][j]dp[i][j]为从前i个数(0~i−1号0~i-1号0~...
  • 如果这里用维数组记住每一空隙的位置,一是没有必要,是记录了还要大量的处理才能得到答案。反正我是没想过要怎么处理。 可以发现,要得到本题的答案,只要找到空隙最多的哪个位置,我们取左边参考点,每一行...
  • 所以把他还原成十进制的方法就是把这串二进制数从右往左边数位数,第一位是2的0次方第二位是2的1次方,依次类推。将位数上是1的所以次方加起来 就可以了。 转载于:https://www.cnblogs.com/my-youth/p/6416790.ht...
  • 我们来分析一下,对于倒数第二层开始的每一个数,与其对应的下一个数无非在其左边或右边,只有这两种可能。因此,可以把这两个数区分出左和右,进而,可以用标志量来标识我们左还是右。同样,我们再开辟一与...
  •  1221是一非常特殊的,它从左边读和从右边读是一样的,编程求所有这样的四位十进制。 输出格式  按从小到大的顺序输出满足条件的四位十进制。 方法1 思路:既然是回文,那么它的一位和最后一位肯定...
  • 问题1:N个人排成一排,从第一个人开始依次报到K的人则退出,接下来的人继续1开始数数,最右边的人数完数后最左边的人作为后继接着,形成一逻辑的环,如此反复直至最后一人,求最后一人的位置索引 ...
  • 维平面上有n块跷跷板,每块跷跷板都有三值:纵坐标,横坐标左右端点,,牛牛可以一块跷跷板走到另一块跷跷板当且仅当两块跷跷板有公共边(也就是公共点不算),然后牛牛想从第1块跷跷板走到n块跷跷板,问走的...
  • 常用排序算法()

    2019-04-03 17:55:00
    本篇主要介绍排序算法中的快速排序 堆排序和归并排序 一 快速排序 1 快排思路: 元素p(元素),是元素p归位(去它该去的地方) ...先把5出来,这时候就会有一空位,右边找比5小的填充过来...
  • (1)基准的方式有几种 一种是数组中的第一个数第二种是数组中的最后的一个数 ,第三种是第一和最后一以及数组中间三个数的中间 在分区过程,将这个数大的全部放到它的右边,小于这个数放到...
  • 第一遍遍历结束后,从第二个数开始,第二个数又是一个临时,以此类推。这样最左边就是已经排好的有序的了。 代码思路: 外层循环用out,数组开头开始向高位增长,内层循环用in,这些都是作为下标的。内层...
  • 算法--快速排序

    2014-02-17 17:42:38
    看别人视频自己总结的步骤,仅供自己娱乐玩耍  大概思路:  ...3.数组左边第二个数开始找比支点小的,数组右边倒数第三个开始找比支点大的,如果找到了,并且左边的角标比右边的角标小就将这
  • 单调栈

    2021-01-23 15:10:21
    给定一长度为N的整数数列,输出每个数左边第比它小的,如果不存在则输出-1。 输入格式 第一行包含整数N,表示数列长度。 第二行包含N整数,表示整数数列。 输出格式 共一行,包含N整数,其中第i个数表示...
  • 插入排序 从左至右两两对比,右边的比左边...再取第二个数变为A,做同样的步骤 冒泡排序 同样是经过两两对比,比如下图,从左边开始,第1,2位数对比,大的右移,第2,3位数对比,大的右移,以此类推,知道遍历...
  • 答案显然,最少链数取决于叶子结点个数,即叶子节点两两连接,(num+1)/2。 没想到如何连接,其实只要先求一遍dfs序,根据该顺序,对于叶子结点i,将其与i+num/2相连,我的理解就是这样的连接一定是过某个树根的,...
  • 选择排序

    2015-08-09 14:59:04
    剩余的中,当前排好的+1,最小的防盗左边第二个坑里,固定 循环。。。 最后当放完倒数第二个坑时,排序完成 void sort_select(int *array, int len) {  int i, j, tmp;  //固定到倒数...
  • uva 10891

    2017-10-24 10:51:21
    这一题,我们考虑从左边取还是从右边多少个数。可以枚举每状态。 dp[l[[r],表示从l到r,最大可以得到的。它可以由dp[k][r], dp[l][m]得来,k = l + 1---> r m = l ---- >r - 1。k和m相当于枚举 n - 1
  • 快速排序

    2018-07-19 15:07:11
    3、再对左右区间重复第二步,直到各区间只有一个数 快速排序图解 下面以数列{14,15,30,28,5,10}为例,演示它的快速排序过程(如下图) 分析第一趟排序: 首先选第一个数作为基准,i = 0, j =...
  • 排序 快排是不稳定的,归并是稳定的 ...​ 第二个区间里的都 大于等于 x (右半边 递归处理左右两端 ​ 左边排好序,右边排好序 第二步中两个小方法 方法一: 设两个数组 a[ ] b[ ] 检查
  • 思想:第一次:数组的最左边开始,第一个元素与第二个元素比较,小的往前边放,大的往后边放;然后第二个元素与第三个元素比较, 大的往第三的位置放,小的放在第二位置,,然后第三元素与第四元素比较,...
  • 手撕Java快排

    2021-01-25 23:45:26
    乱序的数字中找一中位(便于理解,就最后一个数),设想两游标,左游标指向第0个数,右游标指向最后一个数 第一步:左游标右移,直到找到一个数比中位大的停止 第二步:右游标左移,直到找到一个数比...
  • 快速排序的实现原理

    2017-09-18 15:38:18
    快速排序的实现原理: 拿第一个数为基准、后往前比较、比它小的就放在前面。然后从前往后比较,比它大的放在后面。一直找到中间的位置,就把基准放在中间的位置。...再前往后开始,比它大的放在第二
  • JAVA快速排序

    2020-04-01 21:20:30
    快速排序 主要思想:冒泡+分治+递归 ...再对左右区间重复第一步、第二步,直到各个区间只有一个数(递归) 代码如下: import java.util.Arrays; public class TestQuickSort { public static void...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 156
精华内容 62
关键字:

从左边第二个取数