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


parameter a for v e c t o r < i n t > , followed by a 1 . a 2 . . . . . a n ; Vector <int>, a_1,a_2… , a_n;


parameter q u e r y for v e c t o r < i n t > , followed by l 1 . r 1 . l 2 . r 2 . . . . . l q . r q ; The query argument is vector<int>, l_1,r_1,l_2,r_2… , l_q r_q;


n As an array a The length, q Is the number of inquiries. N is the length of array A and q is the number of queries.

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


a n s = a 1 ∗ a 2 + a 1 ∗ a 3 + a 1 ∗ a 4 + a 2 ∗ a 3 + a 2 ∗ a 4 + a 3 ∗ a 4 ans = a_1 * a_2 + a_1 * a_3 + a_1 * a_4 +a_2*a_3+a_2*a_4+a_3*a_4

And let’s look at the multiplication table


1 ∗ 1 1 * 1

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