精华内容
下载资源
问答
  • 众数中位数在分组区间计算方法

    千次阅读 2020-03-13 09:40:09
  • 对于区间计数问题,一般都是令F {i}(n)为[0,n]...0-3999,最高只出现过0,1,2,3, 对应的它出现的次数为1000(x***),其他上每种数字出现的次数相同,都是(1000*3)/10 前导0不算,为了计算方便,先算进去,

    对于区间计数问题,一般都是令F {i}(n)为[0,n]之间i出现的次数,再去区间相减就可以了

    第一种方法:

    例如 4321,分别求0-3999,4000-4299,4300-4319,4320+4321

    0-3999中,最高位只出现过0,1,2,3, 对应的它出现的次数为1000(x***),其他位上每种数字出现的次数相同,都是(1000*3)/10

    前导0不算,为了计算方便,先算进去,再减,不算的情况只出现在了第一次计算0-3999的时候,有多少个呢? 

    1000+100+10

    所以我们按位从高位开始枚举,来统计各个数字出现的次数

    注意 在计算10^n的时候不能用pow转换成整形来计算,会出现精度丢失的情况吗,所以自己生成一个就行了。

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <set>
    #include <queue>
    using namespace std;
    
    const int INF=1e9+1000;
    const double EPS = 1e-10;  
    typedef long long ll;
    int a[15],b[15];
    int pova[17];
    int mpow10[10];
    void cal(int n,int *d){
        int tmp=n;
        int pos=0;
        int c[15];
        do{
            c[pos++]=tmp%10;
            tmp/=10;
          }while(tmp);
    
        pos--;
        char s[15];
        sprintf(s,"%d",n);
        for(int i=0;i<=pos;i++){
            sscanf(s+pos-i,"%d",&pova[i]);
        }
        int k=mpow10[pos];
        for(int i=pos;i>0;i--){
    
            for(int j=0;j<c[i];j++){
                d[j]+=k;
                for(int z=0;z<=9;z++){
                    d[z]+=k*i/10;
                }
            }
            d[c[i]]+=pova[i-1]+1;
            d[0]-=k;
            k/=10;
            
        }
        
        for(int i=0;i<=c[0];i++)
            d[i]++;
    }
    int main(){
        //freopen("out.txt","w",stdout);
        //ios_base::sync_with_stdio(false);
        int l,r;
        mpow10[0]=1;
        for(int i=1;i<=8;i++)
            mpow10[i]=mpow10[i-1]*10;
        while(scanf("%d %d",&l,&r)&&l+r){
            if(l>r) swap(l,r);
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            cal(l-1,a);
            cal(r,b);
            for(int i=0;i<=9;i++)
                printf("%d%c",b[i]-a[i],i==9?'\n':' ');
        }
        return 0;
    }


    第二种方法,数位dp,就是记忆化搜索,对于重复计算的状态,存在数组中就可以直接返回了。

    其中  cnt的设置很是精妙,避免了一大堆的判定,lead用来判断枚举到该位的时候是否有前导0,。

    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <set>
    #include <queue>
    using namespace std;
    
    const int INF=1e9+1000;
    const double EPS = 1e-10;  
    typedef long long ll;
    int a[15],b[15];
    int digit[15];
    int d[15][2][15][15];
    
    int dfs(int pos,int lead,int val,int limit,int cnt){
    	if(pos==-1){
    		if(lead)
    			return 1;
    		else
    			return cnt;
    	}
    	if(!limit&&d[pos][lead][val][cnt]!=-1) return d[pos][lead][val][cnt];
    	int up=limit?digit[pos]:9;
    	int ans=0;
    	for(int i=0;i<=up;i++){
    		if(!lead){
    			ans+=dfs(pos-1,0,val,limit&&i==up,cnt+(i==val));
    		}else{
    			if(i==0){
    				ans+=dfs(pos-1,1,val,limit&&i==up,cnt);
    			}
    			else{
    				ans+=dfs(pos-1,0,val,limit&&i==up,cnt+(i==val));
    			}
    		}
    	}
    	if(!limit) d[pos][lead][val][cnt]=ans;
    	return ans;
    }
    
    void cal(int n,int *f){
    	int pos=0;
    	do{
    		digit[pos++]=n%10;
    		n/=10;
    	}while(n);
    	for(int i=0;i<=9;i++){
    		f[i]=dfs(pos-1,1,i,1,0);
    	}
    }
    int main(){
    	//freopen("out.txt","w",stdout);
    	//ios_base::sync_with_stdio(false);
    	int l,r;
    	memset(d,-1,sizeof(d));
    	while(scanf("%d %d",&l,&r)&&l+r){
    		if(l>r) swap(l,r);
    		memset(a,0,sizeof(a));
    		memset(b,0,sizeof(b));
    		cal(l-1,a);
    		cal(r,b);
    		for(int i=0;i<=9;i++)
    			printf("%d%c",b[i]-a[i],i==9?'\n':' ');
    	}
    	return 0;
    }




    展开全文
  • 给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个。 (注意,计算置位代表二进制表示1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有,1 不是质数。) 示例 1: 输入: L...
  • 这是这次百度之星初赛2B的第六题。之前白山云做过类似的题,省赛完回来,我看了一下大概就有这样的思路:首先枚举每一个数k,计算以这个数为中位数的...于是区间中位数大于k的区间和就大于0,小于k的小于0,等于k的...

    http://acm.hdu.edu.cn/showproblem.php?pid=5701

    这是这次百度之星初赛2B的第六题。之前白山云做过类似的题,省赛完回来,我看了一下大概就有这样的思路:首先枚举每一个数k,计算以这个数为中位数的区间个数。关键是计算中位数的处理方法,将所有大于k的数置为1,小于k的数置为-1,等于k的数置为0。于是区间中位数大于k的区间和就大于0,小于k的小于0,等于k的等于0。而且每个数都不等,所以区间和为0的个数就是中位数为k的个数。

    关于计算区间和为0的个数。如果维护前缀和sum的个数。那么维护到i的时候,以i为右区间值的区间必然是sum(i)-sum(j),那么区间和为0就是前面有多少个前缀和为sum(i)。然后区间必须是奇数长度,所以需要对奇偶区间维护前缀和,此外,还需要对sum==0的情况特判。

     

    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <queue>
    #include <vector>
    #include <string>
    #define LL long long
    
    using namespace std;
    
    const int maxN = 8005;
    int n, a[maxN], b[maxN];
    int cnt[2][maxN<<1];
    
    int cal(int k)
    {
        for (int i = 0; i < n; ++i)
        {
            if (a[i] > k) b[i] = 1;
            else if (a[i] < k) b[i] = -1;
            else b[i] = 0;
        }
        int ans = 0, sum = 0;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; ++i)
        {
            sum += b[i];
            ans += cnt[!(i&1)][sum+maxN];
            if (sum == 0 && i%2 == 0) ans++;
            cnt[i&1][sum+maxN]++;
        }
        return ans;
    }
    
    void work()
    {
        for (int i = 0; i < n; ++i)
        {
            if (i) printf(" ");
            printf("%d", cal(a[i]));
        }
        printf("\n");
    }
    
    int main()
    {
        //freopen("test.in", "r", stdin);
        //freopen("test.out", "w", stdout);
        while (scanf("%d", &n) != EOF)
        {
            for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
            work();
        }
        return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/andyqsmart/p/5523489.html

    展开全文
  • 对于未分组数据,可使用Excel的MEDIAN函数求解中位数。 对于分组数据,分为: 1. 组离散数据的中位数: 首先要构造累积频率分布表,然后通过累积频率分布表确定数据的中...看似非常简单的中位数计算,在使用了实际数

    对于未分组数据,可使用Excel的MEDIAN函数求解中位数。
    对于分组数据,分为:
    1. 组离散数据的中位数:
    首先要构造累积频率分布表,然后通过累积频率分布表确定数据的中位数对应的观测值的位置,然后根据观测值的位置按照插值法估算数据的中位数。
    2. 组连续数据的中位数

    在假设数据在每个等级区间内均匀分布下,采用以下公式来估计组数据的中位数。

    看似非常简单的中位数计算,在使用了实际数据进行计算时,并不简单,耗时约1小时。

    结论:分组时分的越细致,计算出的分组数据的中位数越接近未分组中位数。

    其中,观测值数目通过Frequency数组函数计算得到。


    备注:上次没搞清楚组离散数据和组连续数据的区别,这次加以修正。(访问量是离散数据,而不是连续数据)。

    对于组连续数据的中位数求解,留待日后单独说明。

    展开全文
  • 内存足够:将所有整数加载进内存,类似于快速排序的思路,选取某个整数,将整个数组分为两部分,即此数左边全部小于这个,右边全部大于此数,计算左右两边的数的个数后,重新选择区间然后重复递归,直到找到中位数。...
  • 数位 DP

    2020-11-05 10:17:53
    解题思路:用 DP 对“数位”进行操作,记录已经算过的区间的状态,用后续计算中,快速进行大范围的筛选 问题 给定 m 和 n,0<m<=n<10^6,统计 [m, n] 范围内不含 ‘4’ 的的个数(hdu20.
  • 数位DP

    2020-08-18 01:12:51
      这个专题学习的时间跨度有些大,因为被中间的训练给隔开了,然后我发现我好像突然对树形DP有些陌生了,我是废物 ,改天再加深...解题的思路是用DP对“数位”进行操作,记录算过的区间的状态,然后再后续计算中,快
  • 对于书说的不考虑时间效率的解法很好理解,可以直接完成,但是对于书介绍的另一种方法,没有理解,于是按照自己的思路进行了分析。1位数,1-9,1一共出现了1次;2位数,10-99,10-19的十上...
  • 在信息安全风险评估的过程需要收集多专家的评估意见作为基础数据,为了更准确地提取专家意见包含的信息,对基于区间数模糊综合评判的风险评估模型提出了一种改进方案。该方案建立了一种新的评判矩阵形式,为...
  • 数位dp 模板加例题

    2020-07-29 10:20:17
    概念:所谓数位”dp“,是指对数字的”“进行的与计数有关...解题的思路是用DP对”数位“进行操作,记录已经算过的区间状态,用在后续计算中,快速进行大范围的筛选。 实现方法:1.递推实现 2.用记忆法搜索实现。 ...
  • 数位dp入门

    2018-07-31 16:29:05
    所谓数位dp统计每一数字的情况,统计的过程一定会遇到各种重复,那么我们利用记忆化的方法来避免这些重复计算就是我们今天要学的数位dp。 话不多说,我们先从一个小例子来说, 这个题意很简单就是不要49。让你...
  • 计算机组成原理 第二章 —— 运算...注意:从1010到1111这6个无效码,运算结果若在这个区间需要加6并向高位进位。 答案:C ASCII码需要记忆的码值: 0:48(30H) A:65(41H) a:97(61H) 答案:B 解析:A
  • 给出一个范围 \((l,r)\) , 要求计算该范围 满足 其中连续两不为62, 并且不包含4 的符合条件个。 思路: 在用数位dp写之前发现自己以前用暴力的方法过去了....(就直接枚举然后除余 4 和 64)所以明明做过一道...
  • 给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个。 (注意,计算置位代表二进制表示1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有,1 不是质数。) 示例 1: 输入:...
  • HDU 4352 XHXJ's LIS 数位dp

    千次阅读 2015-04-01 21:05:20
    题意: 一个自身的最长子序列=每一都是一个数字然后求的LIS ...dp[i][j] 表示长度为i的数字,最长子序列出现的数字状态j的方法数。由于询问=K,也存下来避免重复计算。 #includ
  • DG计算机视觉公司机试题

    千次阅读 2017-03-17 15:58:40
    给定区间1~n,判断小B取值在中位数的哪侧,也就是说,如果小B取值在中位数右侧,那小A只要取值为小B取值数-1,反之,如果小B取值在中位数左侧,那小A只要取值为小B取值数+1。更具体地说: 情况一:如果小B取值在...
  • 题意: 一个自身的最长子序列=每一都是一个数字然后求的LIS ...dp[i][j] 表示长度为i的数字,最长子序列出现的数字状态j的方法数。由于询问=K,也存下来避免重复计算。 #include #include #include
  • 思路:可以用类似求lis的方法来做,因为k最大只有10,而且lis的g数组是递增的,g的值只有可能取0到9,所以我们可以用状态压缩表示当前g数组0到9是否出现,然后在数位dp的时候计算状态即可。#include #include #...
  • 一个“合法”的输入是 [−1000,1000] 区间内的实数,并且最多精确到小数点后 2 。当你计算平均值的时候,不能把那些非法的数据算在内。 输入格式: 输入第一行给出正整数 N(≤100)。随后一行给出 N 个实数,数字...
  • 问题是这样的,给出一个n,让你求出1~n之间的所有整数的...最直观的方法:依次判断每一个区间内的每一个整数,对一个逐渐除10判断其每一。这个方法的时间复杂度为O(n*lgn)。 介绍一个优化的方法(注意其中分治和
  • 排列问题

    2012-11-12 22:42:08
    之后,抛掉万位数字,对于4567,再使用上面的方法计算,一直计算到个即可。 import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; public class Arirgmetic { public ...
  • 2000ms 内存限制: 128000KB64整型: Java 类名:题目描述南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌最高的人与杀敌最低的人进行比较,计算出两个人的杀敌差值,用这种方法一...
  • 【精品】40篇文章带你系统学习统计基础但是,在使用这些方法之前,我们需要先对总体分布进行假定,而且它们并不能有效估计中位数、四分位数和标准差等分布参数。20世纪80年代以来,计算机技术快速发展,使统计学家能...
  • 前面转载了一篇博文,这里...是指基于指定的箱子的个数自定向下的分裂计数,通过使用等宽或等频分箱,然后用箱子中的均值或者中位数来代表每个箱子,实现离散化 2.通过聚类离散化 通过将属性A的值划分为簇或组,产...
  • 求出1 ~ 13的整数1出现的次数,并算出100 ~ 1300的整数1出现的次数?为此他特别了一下1~13包含1的数字有1、10、11、12、13...某位中 1 出现次数的计算方法: 根据当前 cur 值的不同,分为以下三种情况: 当 c

空空如也

空空如也

1 2 3 4 5 6
收藏数 117
精华内容 46
关键字:

区间中位数计算方法