# 牛客编程巅峰赛青铜白银黄金组第4场

## A题：

### 练习快速幂

```public class Solution {
/**
* 返回一个严格四舍五入保留两位小数的字符串
* @param n int整型 n
* @return string字符串
*/
public String Probability (int n) {
// write code here
double A = 0.5;
double B = 2;
while(n > 0){
if((n & 1) == 1){
B *= A;
}
A *= A;
n >>= 1;
}
return String.format("%.2f", B);
}
}```

## B题

### 二分法，一定注意变量溢出的问题

```public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 玩偶数
* @param m int整型 区间数
* @param intervals Interval类一维数组 表示区间
* @return int整型
*/
public int doll (int n, int m, Interval[] intervals) {
// write code here
Arrays.sort(intervals, (a, b) -> a.start - b.start);
long l = 1;
long r = Long.MAX_VALUE;
while(l < r){
long mid = l + ((r - l + 1) >> 1);
if(!check(n, m, intervals, mid)){
r = mid - 1;
}else{
l = mid;
}
}
return check(n, m, intervals, l) ? (int)l : 0;
}
private boolean check(long n, long m, Interval[] intervals, long mid){
long curr = 0;    // 必须为long类型，不然计算过程溢出，只能通过90%用例。
long count = 0;
for(int i = 0; i < m; ++i){
if(curr > intervals[i].end){continue;}
curr = Math.max(intervals[i].start, curr);
long localCount = (intervals[i].end - curr) / mid + 1;
count += localCount;
curr += localCount * mid;
if(count >= n){return true;}
}
return false;
}
}```

## 第三题

### 动态规划

```public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 多次求交叉乘
* @param a int整型一维数组 a1,a2,...,an
* @param query int整型一维数组 l1,r1,l2,r2,...,lq,rq
* @return int整型一维数组
*/
public int[] getSum (int[] a, int[] query) {
// write code here
long MOD = 1000000007;
int len = a.length;
long[] dpSum = new long[len + 1];
long[] dpSumSquare = new long[len + 1];
int[] res = new int[query.length / 2];
for(int i = 0; i < len; ++i){
dpSum[i + 1] = (dpSum[i] + a[i]) % MOD;
dpSumSquare[i + 1] = (dpSumSquare[i] + (long)a[i] * (long)a[i]) % MOD;
}
for(int i = 0; i < query.length / 2; ++i){
int l = query[i * 2];
int r = query[i * 2 + 1];
long deltaSum = (dpSum[r] - dpSum[l - 1]) % MOD;
deltaSum = deltaSum * deltaSum % MOD;
long deltaSumSquare = (dpSumSquare[r] - dpSumSquare[l - 1]) % MOD;
long resI = ((deltaSum - deltaSumSquare) % MOD  + MOD) % MOD;    // 保证resI为正数。
resI = resI * 500000004 % MOD;
res[i] = (int)resI;
}
return res;
}
}```