Game 4 S2 (Bronze and Silver Group)
Welcome to follow my public account ACJavaBear, learn Java together
1. Niu Niu flips a coin
Topic describes
Niuniu likes to toss coins recently. Because he is very bored today, he has tossed coins for n times at home. Niuniu will be happy if the coins are all up or all down. (The probability of coming up on each flip is the same as the probability of coming down)
Sample 1
The input
1
Copy the code
return
"1.00"
Copy the code
instructions
With a probability of 1, the string rounded to two decimal places is "1.00"Copy the code
The sample 2
The input
5
Copy the code
return
"0.06"
Copy the code
instructions
The probability is 0.0625, with the string "0.06" rounded to two decimal places.Copy the code
note
For 50% data: 1≤ N ≤10011≤ N ≤10011≤ N ≤1001
For 100% data: 1≤ N ≤ 1E91 ≤ N ≤ 1E91 ≤ N ≤1e9
For each n, return a string that is strictly rounded to two decimal places.
For example, if the probability is 0.372, return the string “0.37”.
Returns the string “0.96” with probability of 0.957.
(Note that the string returned is not quoted)
Answer key
Let’s calculate 0.5n−10.5^{n-1}0.5n−1 and round it to two decimal places. I chose to call the function directly
public class Solution {
public String Probability (int n) {
return String.format("%.2f",Math.pow(0.5,n-1)); }}Copy the code
Niuniu puts dolls
Topic describes
Niuniu has n(2≤n≤105)n(2≤n≤10^5) N (2≤n≤105) dolls. Niuniu intends to put the n dolls on the table. The table is long in shape, which can be regarded as a one-dimensional number line. The table has M disjoint intervals (1≤M≤105) (1≤M≤10 ^5) (1≤M≤105) on which dolls can be placed. Only one doll can be placed in one position, and the larger the distance between the dolls, the more beautiful it is. Niuniu wants to maximize the value of D, where D is the distance between the nearest two dolls. Please help Niuniu find the maximum possible value of D.
Sample 1
The input
[[0, 3, 5, 2], [4, 7], [9, 9]]Copy the code
return
2
Copy the code
note
Range length ≤231−1\leq 2^{31} -1≤231−1
Answer key
Personally, I think this question is more difficult for those who have less brushes (including me). And what they’re saying is let’s find the largest of all the smallest D’s.
So if you want to do this kind of problem and you want to maximize the smallest of XX or you want to minimize the largest of XX, you can think about this dichotomy. And if you want to use binary, you have to sort first, so the first step is to sort the interval.
Step two, how to place the dolls? An interval an interval pendulum, and greedy consideration, as far as possible according to a certain spacing D, placed on the left. So the first doll we definitely put at the beginning of the first interval. See the code for specific ideas.
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) {
// the interval is sorted by the left endpoint
Arrays.sort(intervals,(a,b) -> a.start - b.start);
// Find spacing in the entire interval
long l = 0, r = (1l << 31) - 1;
while(l < r){
long mid = l + (r - l) / 2 + 1;
if(check(intervals,mid,n)){
// The mid pendulum can swing more than n dolls, indicating that the spacing is too small, so the latter half of the search
l = mid;
}else r = mid - 1; // The space is too wide, search in the first half
}
return (int) l;
}
public boolean check(Interval[] intv,long mid,int n){
int num = 1; //num is the number of dolls placed, with the first doll in the starting position
long now = intv[0].start + mid;// Now judge whether the position mid from the starting point can be placed dolls
for(int i = 0; i < intv.length; i++){// iterate over the interval
// If the current position is already outside the interval, it indicates that the interval can not swing, and determine the next interval
if(now > intv[i].end) continue;
// It is possible that the current position falls between the two intervals, so to prevent this situation, set a maximum value between now and the start of the interval
now = Math.max(now,(long) intv[i].start);
// Calculate the number of dolls that can be placed in the interval between mid
long nums = (intv[i].end - now) / mid + 1;
// Count the number of dolls
num += nums;
// Update the current location
now = now + mid * nums;
}
//true indicates that n dolls can be enlarged by mid spacing
/ / false otherwise
returnnum >= n; }}Copy the code
3. The cross
Topic describes
Niuniu, who is in the second grade of primary school, has mastered integer addition and multiplication. Now you’re going to test him. You start with an array of integers a1, A2… ,ana_1,a_2,… ,a_na1,a2,… , an, then every time you will give a pair of integers l and r (r) or less l l, r (r) or less l l, r, l, r) or less, niuniu need to calculate the ∑ ∑ ri = l j = I + 1 rai ∗ aj ∑ ^} {I = l _r ∑ ^ r_ + 1} {j = I a_i ∗ a_j ∑ ∑ ri = l j = I + 1 rai ∗ aj’s value. But after niuniu finished, you couldn’t help but be sure that he was right. To test his answer, YOU decided to do it yourself.
To not print too large an answer, suppose the answer is ANS, print ANS % 1,000,000,007.
Hint: /2 is equivalent to *500,000,004 in the sense of %1,000,000,007
Sample 1
The input
,2,5,3,4 [1], [1,4,2,5,2,2]Copy the code
return
[41,71,0]
Copy the code
instructions
First query, l=1,r=4, ans=1*2+1*5+1*3+2*5+2*3+5*3=41; Second query, l=2,r=5, ans=2*5+2*3+2*4+5*3+5*4+3*4=71; Third query, l=2,r=2, ans=0.Copy the code
note
30% data satisfy 1<=n, Q <=10001<=n, Q <=10001<=n,q<=1000
100% data meet 1 < = n, q < = 100000, 1 < < = 100000, 1 < = = ai li < = ri < = n1 < < = 100000, 1 < = n, q = a_i < = 100000, 1 < = l_i < = r_i < = n1 < = n, q < = 100000, 1 < < = 100000, 1 < = = ai li < = ri < = n
Answer key
Main idea: multiplication table + prefix sum
We can observe, for example, l=1,r= 4L =1,r= 4L =1,r=4
And let’s look at the multiplication table
12 * 12 2 ∗ ∗ 1, 2 * 22 ∗ ∗ 22 2
∗13*13∗1, 3∗23*23∗2, 3∗33*33∗3
∗1, 4∗24*24∗2, 4∗34*34∗3, 4∗44*44∗4
Notice that the subscripts of ansansans correspond to the subscripts of the multiplication table, that is, ansansans is the sum of all the elements below the diagonal of the multiplication table
We can choose to use a two-dimensional prefix sum, but we can also change to a one-dimensional prefix sum.
If we complete the multiplication table
∗11*11∗1, 1∗21*21∗2, 1∗31*31∗3, 1∗41*41∗4
∗12*12∗1, 2∗22 *22∗2, 2∗32*32∗3, 2*42∗4
∗13*13∗1, 3∗23*23∗2, 3∗33*33∗3, 3∗43*43∗4
∗1, 4∗24*24∗2, 4∗34*34∗3, 4∗44*44∗4
Have amazed to find this matrix elements and is (1 + 2 + 3 + 4) ∗ (1 + 2 + 3 + 4) (1 + 2 + 3 + 4) * (1 + 2 + 3 + 4) (1 + 2 + 3 + 4) ∗ (1 + 2 + 3 + 4), and the elements in the matrix of inclined diagonal symmetry
So what is ansansans equal to? It’s pretty clear, actually, ((1 + 2 + 3 + 4) ∗ (1 + 2 + 3 + 4) 1 2 ∗ ∗ 1-2-3-4 ∗ ∗ 3-4) / 2 ((1 + 2 + 3 + 4) * (1 + 2 + 3 + 4) – 1 * 1 or 2 * 2-3 * 3-4 * 4) / 2 ((1 + 2 + 3 + 4) ∗ (1 + 2 + 3 + 4) 1 2 ∗ ∗ 1-2-3-4 ∗ ∗ 3-4) / 2 .
So we can deal with two prefixes and arrays, one is the prefix sum of elements, and one is the prefix sum of elements squared.
The general term formula is going to be something that you can derive for yourself. Let’s look at the code.
public class Solution {
public int[] getSum (int[] a, int[] query) {
int mod = 1000000007;
int n = a.length;
// Store element prefixes and
long[] sum = new long[n+1];
// Store the prefix sum of the squares of the elements
long[] powSum = new long[n+1];
// Initialize the annotation and array, be careful not to overstep the bounds
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;
}
// Store the answer
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];
// add mod to prevent negative subtraction
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;
// As prompted, divide by 2 as follows
t *= 500000004;
t %= mod;
res[i/2] = (int) t;
}
returnres; }}Copy the code