825. Friends Of Appropriate Ages

Binary search, pay attention to determine whether the search interval contains a solution

835. Image Overlap

The puzzle is the same, and it is suggested to search the solution

870. Advantage Shuffle

Rearrange array A to maximize the number of A[I] > B[I]

For each B[I], try to use the smallest A[I]

873. Length of Longest Fibonacci Subsequence

Given a list of numbers, find the longest Fibonacci sequence

The Fibonacci numbers are not very many if they are less than 10^9

891. Sum of Subsequence Widths

Given a list of numbers, for each subsequence, set width = the maximum value in the sequence – the minimum value in the sequence, and find the sum of the width of all the subsequences in the column

Answer key: First, the result obviously has nothing to do with the order of the column number, so the column number is sorted first, then the width of each subsequence is the “last number – first number” of the subsequence, so as long as the enumeration of the head (I) and tail (j) of the subsequence, the middle number of j-i-1 has 2^(J-I-1). The width of the 2^(j-i-1) subsequence is equal to A[j] -a [I]

The answer can be written as:

∑ ∑ (I = 0, n – 2) (j = I + 1, n – 1) (A) [j] – [I] A) * 2 ^ (j – I – 1)

= (I =0, n-2) 2^-(I +1)∑(j= I +1, n-1)A[j]*2^j –

∑ (I = 0, n – (2) A [I] * ^ 2 – (I + 1) ∑ (j = I + 1, n – 1) ^ 2 j

Can use two arrays were scored p [I] = ∑ (j = I, n – 1) and A [j] * 2 ^ j p2 [I] = ∑ (j = I, n – 1) ^ 2 j

So I can solve it in order N

Code:

class Solution {
public:
    int modn = 1e9 + 7;
    int quickpower(long long b, int x)
    {
        long long s = 1;
        while(x)
        {
            if(x & 1)
                s = s * b % modn;
            b = b * b % modn;
            x >>= 1;
        }
        return s;
    }
    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        int n = A.size();
        vector<int> p(n + 5);
        vector<int> p2(n + 5);
        for(int i = n - 1; i >= 0; i--)
        {
            int t = 1ll * A[i] * quickpower(2, i) % modn;
            p[i] = (t + p[i + 1]) % modn;
            int tt = 1ll * quickpower(2, i) % modn;
            p2[i] = (tt + p2[i + 1]) % modn;
        }
        int s1 = 0, s2 = 0;
        for(int i = 0; i < n - 1; i++)
        {
            int t = 1ll * quickpower(quickpower(2, i + 1), modn - 2) * p[i + 1] % modn;
            s1 = (s1 + t) % modn;
            int tt = 1ll * A[i] * quickpower(quickpower(2, i + 1), modn - 2) % modn * p2[i + 1] % modn;
            s2 = (s2 + tt) % modn;
        } cout<<s1<<' '<<s2<<endl;
        return((s1 - s2) % modn + modn) % modn; }};Copy the code

900. RLE Iterator

Half naked