精华内容
下载资源
问答
  • 湖南师范大学 11460 区间求最值

    千次阅读 2014-06-09 14:58:13
    区间求最值   Problem description  给定一个长度为N 的数组,有q个询问,每个询问是求在数组的一段区间内那个元素的因子的个数最大,比如24的因子的个数就是8。  Input  首先是一个...

    区间求最值
     
    Problem description
      给定一个长度为N 的数组,有q个询问,每个询问是求在数组的一段区间内那个元素的因子的个数最大,比如24的因子的个数就是8。 
    Input
      首先是一个整数t,表示有t组测试数据,每组测试数据的第一行是一个整数N(1<=N<=10^6),第二行有N个整数ai(1<=ai<=10^6,i=1,2,.....N)表示数组的元素。第三行有一个整数q(1<=q<=10^5),代表有q个询问,接下来每一行有两个整数,li,ri(li<=ri,li>=1,ri<=N).代表数组的一段区间,并且li+1>=li,ri+1>=ri
    Output
      对于每组数据的每个询问都输出一个整数表示在这段区间里面元素因子个数的最大值。
    Sample Input
    1
    10
    2 3 5 6 9 11 12 36 39 44
    3
    2 6
    3 8
    3 9
    Sample Output
    4
    9
    9
    Problem Source

    代码:

    #include <cstdio>
    #include <cstring>
    #define maxn 1000005
    int find[maxn];
    int num[maxn];
    int main()
    {
    	memset(find, 0, sizeof(find));
    	for (int i = 1; i < maxn; i++){
    		for (int j = i; j < maxn; j += i)
    			find[j]++;
    	}
    	int t;
    	scanf("%d", &t);
    	while (t--)
    	{
    		int n, q;
    		scanf("%d", &n);
    		for (int i = 1; i <= n; i++)
    			scanf("%d", &num[i]);
    		scanf("%d", &q);
    		int a, b, ans = -1;
    		int aa, bb, sign;
    		scanf("%d%d", &a, &b);
    		aa = a, bb = b;
    		for (int i = a; i <= b; i++)
    			if (ans < find[num[i]]){
    				ans = find[num[i]];
    				sign = i;
    			}
    
    		printf("%d\n", ans);
    		--q;
    		while (q--)
    		{
    			scanf("%d%d", &a, &b);
    			if (sign >= aa&&sign <= a){
    				ans = -1;
    				for (int i = a; i <= b; i++)
    				if (ans < find[num[i]]){
    					ans = find[num[i]];
    					sign = i;
    				}
    			}
    			else
    			{
    				for (int i = bb; i <= b; i++)
    				if (ans < find[num[i]]){
    					ans = find[num[i]];
    					sign = i;
    				}
    			}
    			aa = a, bb = b;
    			printf("%d\n", ans);
    		}
    	}
    	return 0;
    }
    展开全文
  • N个区间求交集

    千次阅读 2018-07-30 11:14:53
    博主遇​​到一个问题,要对文章根据用户阅读记录进行... 最终博主想到了一个优化策略,在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重,这时就涉及到对用...

          博主遇​​到一个问题,要对文章根据用户阅读记录进行去重,但用户阅读记录的文章ID最长可以达到300条,然后在数据库中使用NOT  IN语句在查询时对文章进行去重,但是这样操作在记录比较长时,语句执行效率极其低下,

           最终博主想到了一个优化策略,在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重,这时就涉及到对用户的阅读文章ID区间进行求交集的操作,具体求交集思路见代码:

    import java.util.*;
    
    
    public class Main {
    
        public static boolean union(Set<String> set) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    
        public static void main(String[] args) {
          /*测试运行效率*/
            Random random = new Random();
            Set<String> set = new HashSet<String>();
            for (int i = 0; i < 100000; i++) {
                String insStr = "";
                int num = random.nextInt(10000000);
                insStr = random.nextInt(num) + "," + num;
                set.add(insStr);
            }
            /*测试准确性*/
            set.add("0,15");
            set.add("8,15");
            set.add("6,7");
            set.add("100,150");
            set.add("12,85");
            set.add("4,10");
            set.add("5,16");
    
            System.out.println("0.0 " + new Date().getTime());
            while (union(set)) {
            }
            System.out.println("-.- " + new Date().getTime());
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
    }

    优化代码:后期博主需要获取最大值 并对过小的值进行合并整合  故而优化方法如下(该优化弃用) ;

    /**
         * 合并所有集合 并返回最大值
         * @param set
         * @param max
         * @return
         */
        public static Long union(Set<String> set ,Long max) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                if (Long.parseLong(arr[1]) > max) {
                    max = Long.parseLong(arr[1]);
                }
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
                            max = union(set , max);
                            return max;
                        }
                    }
                }
            }
            return max;
        }
    

    博主对上面的代码进行大数据(10W+区间)测试后,发现会出现堆栈错误,递归调用太多,线程池满了;

    重新优化代码后 耦合度增加  但减少运算次数

    import java.util.*;
    
    
    public class Main {
    
        /**
         * 合并所有集合 并返回最大值
         *
         * @param set
         * @param max
         * @return
         */
        public static Long union(Set<String> set, Long max) {
            /*求并集  每次将两个可并集的区间合并*/
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                String old = it.next();
                String[] arr = old.split(",");
                Iterator<String> it2 = set.iterator();
                if (Long.parseLong(arr[1]) > max) {
                    max = Long.parseLong(arr[1]);
                }
                while (it2.hasNext()) {
                    String newstr = it2.next();
                    String[] arr2 = newstr.split(",");
                    if (!(arr[0].equals(arr2[0]) && arr[1].equals(arr2[1]))) {
                        //标记是否被合并
                        boolean isRemove = false;
                        //是否两个区间有交集 思路:如果没交集 区间二一定在区间一两边
                        if ((Long.parseLong(arr2[1]) - Long.parseLong(arr[0])) > -1 && (Long.parseLong(arr2[0]) - Long.parseLong(arr[1])) < 1) {
                            //如果区间一的终点小于区间二的终点 将区间二的终点代替区间一的终点
                            if (Long.parseLong(arr[1]) < Long.parseLong(arr2[1])) {
                                arr[1] = arr2[1];
                                isRemove = true;
                            }
                            //如果区间一的起点大于区间二的起点 将区间二的起点代替区间一的起点
                            if (Long.parseLong(arr[0]) > Long.parseLong(arr2[0])) {
                                arr[0] = arr2[0];
                                isRemove = true;
                            }
                            set.remove(newstr);
                            if (isRemove) {
                                //如果区间一的值被改变 修改区间一
                                set.remove(old);
                                set.add(arr[0] + "," + arr[1]);
                            }
    //                        max = union(set , max);
                            return max;
                        }
                    }
                }
            }
            return -1L;
        }
    
        public static void removeSmall(Set<String> set) {
            Iterator<String> it = set.iterator();
            Long min = 0L;
            Long max = 0L;
            while (it.hasNext()) {
    
            }
        }
    
        public static void main(String[] args) {
            /*测试运行效率*/
            Random random = new Random();
            Set<String> set = new HashSet<String>();
            for (int i = 0; i < 100000; i++) {
                String insStr = "";
                int num = random.nextInt(10000000);
                insStr = random.nextInt(num) + "," + num;
                set.add(insStr);
            }
            /*测试准确性*/
            set.add("0,15");
            set.add("8,15");
            set.add("6,7");
            set.add("100,200");
            set.add("12,85");
            set.add("4,10");
            set.add("5,16");
    
            System.out.println("0.0 " + new Date().getTime());
            Long max = 0L;
            for(Long tempMax=max; (tempMax = union(set, max)) >= 0 ; )
            {
                max = tempMax;
            }
            System.out.println("MAX = " + max);
            System.out.println("-.- " + new Date().getTime());
            Iterator<String> it = set.iterator();
            while (it.hasNext()) {
                System.out.println(it.next().toString());
            }
        }
    }

     

    展开全文
  • 算法 数学区间求并集

    千次阅读 2017-08-13 02:20:00
    例如:有区间[3,7],[11,12],[14,16],[17,19],[21,24],[1,2],[4,8],[5,6],[9,10],[13,15],[18,22],[20,23] 将区间放入List list中: list.add(3); list.add(7); list.add(11); ...... list中数据格式如下3,7,11,...
    例如:有区间[3,7],[11,12],[14,16],[17,19],[21,24],[1,2],[4,8],[5,6],[9,10],[13,15],[18,22],[20,23]
    将区间放入List<Long> list中:
    list.add(3);
    list.add(7);
    list.add(11);
    ......
    list中数据格式如下3,7,11,12,14,16,17,19,21,24,1,2,4,8,5,6,9,10,13,15,18,22,20,23
    然后直接调用函数
    GetCombinedSets(list,0);

    list即为输出。


    public void GetCombinedSets(List<Long> list,int index){		
    		
    		int i=index;
    		boolean isbreak=false;
    		for(;i<list.size()-2;i+=2){
    			if(isbreak){i-=2;break;}
    			Long   start  =list.get(i);    Long   end  =list.get(i+1);
    			for(int j=i+2;j<list.size();j+=2){
    				
    				Long nextstart=list.get(j);  Long nextend=list.get(j+1);
    				if(start>nextend || end<nextstart){continue;}
    				//          |dstart_____|    or   |dstart_____|  
    				//      |cstart_____|       or |cstart_________|
    				if(start>nextstart){
    					//          |_____|    
    					//      |_____|       
    					if(end>=nextend){
    						list.set(i,nextstart);
    						list.remove(j); list.remove(j);
    						isbreak=true;
    						break;
    					}else{
    						//          |_____|    
    						//      |_____________|  
    						list.set(i,nextstart);  list.set(i+1,nextend);
    						list.remove(j); list.remove(j);
    						isbreak=true;
    						break;
    					}
    				}else{
    					//      |_____________|    
    					//        |_____|
    					if(end>=nextend){					
    						list.remove(j); list.remove(j);
    						isbreak=true;
    						break;
    					}else{
    						//      |________|    
    						//        |_________| 
    						list.set(i+1,nextend);
    						list.remove(j); list.remove(j);
    						isbreak=true;
    						break;
    					}
    				}
    			}
    			
    			
    		
    		}
    		if(i==list.size()-2){return;}		
    		GetCombinedSets(list,i);
    	}
    
    


    展开全文
  • 有序区间求交集算法

    千次阅读 2018-08-29 18:13:24
    题目描述:有两个有序的集合,集合的每个元素都是一段范围,其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。 我们知道,两个集合的交集必定是去满足范围小的那个集合,因此此题的解法就是每次...

    题目描述:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。

    我们知道,两个集合的交集必定是去满足范围小的那个集合,因此此题的解法就是每次寻找一个小的范围。那么,关键之处就在于如何寻找这个范围。

    如下图所示,两个集合{[2,8],[9,14]}和{[1,10],[12,15]}:

    集合示例
    集合示例

    集合从左到右进行扫描,每次选取边界的时候都是去选取值小的边界,假设两个数组的索引分别为i和j并指向起始位置。

    • 1<2,选1,索引j向后移动,此时i指向2,j指向10;
    • 2<10,选2,索引i向后移动,此时i指向8,j指向10;
    • 8<10,选8,找到一个右边界,[2,8]为其中一个结果,索引i向后移动,此时i指向9,j指向10;

    以此类推……

    那么,什么时候确定为一个结果子集呢?

    由于扫描为从左到右扫描,开始扫描的时左边界,每次总是取边界中值较小的边界,我们要去寻找一个右边界,因此达到一左一右的状态时,即为一个结果子集。但是,这里有一个重要的地方就是判断结果是否正确。比如上面的例子中,选择1之后的索引达到了一左一右的状态,但是[2,10]并不是我们想要的。在我们选2之后,选8之前,i和j分别指向8和10,即在确定右边界之前,必定要达到两个集合的索引同时达到右边界,然后对两个右边界加以判断。因此需要加一个标志,去判断确定右边界之前是否同时达到右边界。

    public class SetIntersection {
    
    	private void intersection(int[] a, int[] b) {
    		int len1 = a.length, len2 = b.length;
    		int flag = 0, i = 0, j = 0;
    		int pre1 = 0, pre2 = 0;
    		while (i < len1 && j < len2) {
    			pre2 = pre1;
    			if (i % 2 == 1 && j % 2 == 1) {
    				flag = 1;
    			} else {
    				flag = 0;
    			}
    			if (a[i] < b[j]) {
    				pre1 = a[i++];
    			} else {
    				pre1 = b[j++];
    			}
    			if (flag == 1 && ((i % 2 == 0 && j % 2 == 1) || (i % 2 == 1 && j % 2 == 0))) {
    				System.out.println(pre2 + " " + pre1);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		int a[] = { 2, 8, 9, 14, 15, 20, 22, 25 };
    		int b[] = { 1, 10, 12, 16, 19, 25, 30, 40 };
    		new SetIntersection().intersection(a, b);
    	}
    }

    这里我们将两个集合的边界有序地放到了数组里面,下面是程序的输出结果。

    有兴趣的朋友可以自己试着改进一下我的算法。

     

     

     

     

    展开全文
  • 自己的错误做法 #include<stdio.h> main() { int c,d,i,k,m; printf("please input c,d(c>2):\n"); scanf("%ld,%ld",&c,&d); for(m = c; m <= d; m++) { for(i = 2; i ...
  • 区间求并集c++实现

    千次阅读 2013-08-21 22:02:03
    #include #define NULL 0 using namespace std; struct section//每个小区间 { double start; double end; bool isuse;...struct whole_section//区间并集 { section* sec; int length; int size;
  • 区间求mex的几种方法

    2017-01-09 09:11:00
    无修改,求区间 \(mex\) 做法1 莫队+二分+树状数组 树状数组维护维护桶,每次扫完二分答案,用树状数组判断 \(O(n\sqrt n \log n)\) 做法2 莫队+分块 分块维护桶,若块内满,则答案不在这一块,否则进去找 \(O(n\...
  • 问题描述:给定整数M到N区间内素数的个数并对他们求和。 输入格式 输入在一行中给出正整数M和N(1<=M<=N<=500) 输出格式 在一行中顺序输出给定区间内素数的个数以及他们之和。 输入案例 1 10...
  • 树状数组之区间求最值

    千次阅读 2014-10-28 17:17:32
     经过近几天的学习,发现树状数组不仅可以解决区间求和问题,还能很好的解决区间求最值的问题!(是的,不会线段树也没关系!光有树状数组包就您满意!)好了开始具体介绍这个方法~  用树状数组求区间和就是...
  • (一)单个正态总体N(μ,σ2)N(\mu...设X1,...,XnX_1,...,X_nX1​,...,Xn​是取自N(μ,σ2)N(\mu,\sigma^2)N(μ,σ2)的样本,σ2\sigma^2σ2已知,参数μ\muμ的置信度为1−α1-\alpha1−α的置信区间。 (明确问题...
  • 在20-100之间能同时能被3和7整除的数 for i in range(20,101): if i%3==0 and i%7==0: print(i)
  • /*区间筛素数 简述:有的时候,我们需要知道某个特定区间的素数(区间大小较小,但数可能很大)。 那么数组就开不下,这时候我们仍然可以使用筛法,只是所有的下标都进行了偏移。 大家理解下面这段代码可以先用普通...
  • 插值查询:如果有这样一张表,有一列叫水位,有一列叫库容,比如下面的图...算法要点:如果这个输入的值是位于数据库值的某一个区间内的话,那么取最小的区间,然后这个区间内单位数量的值。 大家听得可能有点不太明
  • (题目为Codeforce 527D Clique Problem题解,戳此:点击打开链接)
  •  最大最小值 时间限制:1000 ms | 内存限制:65535 KB 难度:2 描述 给出N个整数,执行M次询问。 对于每次询问,首先输入三个整数C、L、R:  如果C等于1,输出第L个数到第R个数之间的...(包括
  • 这种情况代表输入的值都在一个区间里面,所以max1和max2也都不存在,只需要直接e-s+1就可以出答案 在一般情况下,寻找b数组中的区间最大值,可以用很多方法解决 我用的是线段树,但是...
  • 线段树求区间最大值+区间更新+区间求和+lazy标记
  • 求区间并集

    千次阅读 2018-09-29 09:15:51
    ///代表是区间左端点 sid[top].num = r; sid[top++].pos = 1; ///代表是区间右端点 } int cover = 0; int sum = 0; sort(sid, sid + top, cmp); for(int i = 0; i ; ++ i) { if(sid[i].pos == 0) cover +...
  • 最近工作中用到了区间估计,将自己程序中用到的方法整理如下,仅供参考~interval_estimated &lt;- function(x, sigma=-1, side=0, alpha=0.05){ n &lt;- length(x); xb &lt;- mean(x) if (sigma &...
  • 置信区间

    千次阅读 2012-02-20 11:17:52
    英文为:binomial proportion confidence interval 一.正态近似——最常见和常用... ...它的英文名:normal approximation interval.... 这个区间应完全在(0,1)区间之内。 对公式的更多了解: http://en.wikip
  • 区间第k大(4种法)

    千次阅读 2017-09-25 16:50:14
    线性区间求第k大是一个老生常谈的问题,我们来总结下4种求解方法(当然远不止这4种,老话说思想有多远就能走多远)。 这里我们对每种方法的各种属性进行一个简单评级(1-5,没有任何倍数关系) 1:主席树 (实现难度...
  • for(ll i = 2;i*i ;i++) is_prime_small[i] = true; for(ll i = 0;i ;i++) is_prime[i] = true; for(ll i = 2;i*i ;i++) { if(is_prime_small[i]) { for(ll j = 2*i;j*j ;j += i) is_prime_small[j] = ... }
  • 求区间内的素数

    2017-01-23 12:07:43
    实现从键盘输入两个数字,区间内的素数。没能实现其素数个数。 代码如下#include #include main() { int i,n,j,n1,n2; int max,min; printf("请输入需要查找素数的区间范围:"); scanf("%d%d",&n1,&n2); ...
  • 【算法】求区间并集的长度

    千次阅读 2017-05-28 18:47:35
    给定数轴上的一些区间求区间并集的长度。 只需要用一个cover来记录当前区间覆盖的层数。从左到右遇到一个点就判断:每作过一次区间左端点,cover就加1,每作过一次区间右端点,cover就减1,。显然cover只有正...
  • 小白都能看懂的95%置信区间

    万次阅读 多人点赞 2018-09-14 22:56:35
    1.点估计与区间估计 首先我们看看点估计的含义: 是用样本统计量来估计总体参数,因为样本统计量为数轴上某一点值,估计的结果也以一个点的数值表示,所以称为点估计。点估计虽然给出了未知参数的估计值,但是未给...
  • 给定一个数组序列,使得区间经过如下计算的值是所有区间中最大的:区间中的最小数*区间所有数的和如[6,2,1],则区间为[6] 输入: 3 6 2 1输出: 36大体思路: 给定一个数组序列, 使得区间经过如下计算的值...
  • R语言——自定义函数置信区间

    万次阅读 2017-12-10 18:51:01
    自定义函数单正态样本均值、方差置信区间,两个正态样本均值差、方差比的置信区间
  • 数组的区间

    2015-09-19 09:42:47
    问题描述 就是输入n 然后输入n个数 下标为1~n 然后查询 查询次数...//这事朴素的数组区间和的问题 import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner input=new
  • 闲来无事,补一下小知识。给定整数a和b,请问区间[a,b)内有多少个素数? a#include #include #include #include #include #include #include #include using namespace std; #define
  • 用树状数组求区间最值

    千次阅读 2014-08-08 23:52:31
    注意bit数组存放的是一个区间的最值。更新最值的时候要传递更新。查找的时候也要注意。如果已经不是在一个区间段上了,应该和num[]比。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 198,983
精华内容 79,593
关键字:

区间怎么求