牛客巅峰赛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;
}
} #题解#
拼多多主管面4人在聊