首页 > 牛客巅峰赛S2第四场题解(青铜白银组)
头像
ACJavaBear
编辑于 2020-11-28 20:27
+ 关注

牛客巅峰赛S2第四场题解(青铜白银组)

牛客巅峰赛S2第四场题解(青铜白银组)

1.牛牛掷硬币

题目描述

牛牛最近很喜欢掷硬币,由于他今天很无聊,所以他在家掷了n次硬币,如果这n次硬币全部朝上或者全部朝下牛牛就很开心,请问牛牛开心的概率是多少。(每次掷硬币朝上的概率与朝下的概率相同)

样例1

输入

1

返回

"1.00"

说明

概率为1,四舍五入保留两位小数的字符串为"1.00"
样例2

输入

5

返回

"0.06"

说明

概率为0.0625,四舍五入保留两位小数的字符串为"0.06"
备注

对于50%的数据:

对于100%的数据:

对于每个n,返回一个严格四舍五入保留两位小数的字符串。

比如概率为0.372的话,返回字符串"0.37"。

概率为0.957的话,返回字符串"0.96"。

(注意,返回的字符串不带引号)

题解

题意就是让我们算 并四舍五入保留两位小数,可以选择循环累乘。我选择了直接调用函数

public class Solution {
    public String Probability (int n) {
        return String.format("%.2f",Math.pow(0.5,n-1));
    }
}

2.牛牛摆玩偶

题目描述

牛牛有个玩偶,牛牛打算把这n个玩偶摆在桌子上,桌子的形状的长条形的,可以看做一维数轴。 桌子上有 M 个互不相交的区间,这些区间上面可以放玩偶。一个位置只能放一个玩偶,玩偶之间的距离越大越美观,牛牛想最大化 D 的值,其中 D 为最近的两个玩偶之间的距离。请帮牛牛求出 D 的最大可能值。

样例1

输入

5,3,[[0,2],[4,7],[9,9]]

返回

2
备注

区间长度

题解

个人认为这道题对于刷题量少的人来说是比较难的(包括我)。题面意思就是让我们求所有最小的D中最大的一个。

对于这类问题求最小的XX中的最大值 或 求最大的XX中的最小值都可以往二分想想。而想要用二分就需要先排序,故第一步我们先给区间排序。

第二步,如何摆放玩偶?一个区间一个区间摆,并贪心考虑,尽量按照某个间距D,摆在左边。所以第一个玩偶我们肯定放在第一个区间的起始位置。具体思路见代码。

import java.util.*;
/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */
public class Solution {
    public int doll (int n, int m, Interval[] intervals) {
        //lambda表达式,按左端点给区间排序
        Arrays.sort(intervals,(a,b) -> a.start - b.start);
        //在整个区间里面找间距
        long l = 0, r = (1l << 31) - 1;
        while(l < r){
            long mid = l + (r - l) / 2 + 1;
            if(check(intervals,mid,n)){
                //按mid摆可以摆大于等于n个玩偶,说明间距小了,所以在后半部分搜索
                l = mid;
            }else r = mid - 1; //间距大了,在前半部分搜索
        }
        return (int) l;

    }

    public boolean check(Interval[] intv,long mid,int n){
        int num = 1; //num为摆放的玩偶数,第一个玩偶摆在起始位置
        long now = intv[0].start + mid;//现在判断离起点间距为mid的位置能不能摆放玩偶
        for(int i = 0; i < intv.length; i++){//遍历区间
            //如果当前位置已经在区间外了,说明这个区间摆不了,判断下一个区间
            if(now > intv[i].end) continue;  
            //有可能当前位置落在两区间的间隙里面,所以为防止这种情况,在now与区间起点取一个最大值
            now = Math.max(now,(long) intv[i].start);
            //计算这个区间,以mid为间隔摆放,一共可以摆放的玩偶数
            long nums = (intv[i].end - now) / mid + 1;
            //统计玩偶数
            num += nums;
            //更新当前位置
            now = now + mid * nums;
        }
        //true表示按mid间距摆放可以放大于等于n个玩偶
        //false反之
        return num >= n;
    }
}

3.交叉乘

题目描述

上小学二年级的牛牛已经精通整数的加法和乘法。现在你要考考他。你先给出一个整数数组,然后每次你会给一对整数,牛牛需要算出的值。
但是牛牛算完之后你不能不确定他算得对不对,为了验证他的答案,你决定自己算一遍。

为了不输出过大的答案,假设答案为ans,请输出ans % 1,000,000,007。

提示: 在%1,000,000,007的意义下/2相当于*500,000,004

样例1

输入

[1,2,5,3,4],[1,4,2,5,2,2]

返回

[41,71,0]

说明

第一个询问,l=1,r=4,ans=1*2+1*5+1*3+2*5+2*3+5*3=41;
第二个询问,l=2,r=5,ans=2*5+2*3+2*4+5*3+5*4+3*4=71;
第三个询问,l=2,r=2,ans=0。
备注

30%数据满足

100% 数据满足

题解

主要思路:九九乘法表+前缀和

我们可以来观察一下,以样例中 为例

而我们来看九九乘法表

注意观察,各项的下标是不是刚好对应着九九乘法表的下标,**也就是说其实就等于九九乘法表斜对角线下方的所有元素之和**

我们可以选择采用二维前缀和,但也可以化为一维前缀和。

我们如果补全九九乘法表的话

有没有惊奇的发现这个矩阵的元素和就是,且矩阵中的元素关于斜对角线对称

那么等于什么呢?其实已经很明白了,即

所以我们可以处理出两个前缀和数组,一个是元素的前缀和,一个是元素的平方的前缀和。

通项公式相必大家能自己推导了。我们看代码。

public class Solution {
    public int[] getSum (int[] a, int[] query) {
       int mod = 1000000007;
        int n = a.length;
        //存储元素前缀和
        long[] sum = new long[n+1];
        //存储元素的平方的前缀和
        long[] powSum = new long[n+1];
        //初始化签注和数组,一定要注意,不要越界
        for(int i = 0; i < n; i++){
            sum[i+1] = (sum[i] + a[i]) % mod;
            powSum[i+1] = powSum[i] + (long) a[i]* a[i]  % mod;
        }
        //存储答案
        int[] res = new int[query.length/2];
        for(int i = 0; i < query.length; i+=2){
            int l = query[i];
            int r = query[i+1];
            //通项公式,加mod防止相减出现负数
            long t = ((sum[r]  - sum[l-1] + mod) )*((sum[r]  - sum[l-1] + mod));
            t -= powSum[r] - powSum[l-1];
            t = (t % mod + mod) % mod;
            //根据提示,把除以2换成下面的方式
            t *= 500000004;
            t %= mod;
            res[i/2] = (int) t;
        }
        return res;
    }
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐