[dynamic planning hundred questions strengthening plan] 11~20 (continuously updating)

Strengthen in summer DP A plan for learning , Brush some every day cf, Every day, it surpasses the living gods （bushi）

The questions are cf The inside has dp Labeled , There are also some simple problems such as greed

11.CF_1677A（1600）

Click here directly
tag -> brute force , dp , math

label ： Violence optimization , Preprocessing , Prefixes and suffixes

The main idea of the topic ：

Now let's give you a length of n Permutation p, Respectively p1,p2,p3… also pi≠pj（i≠j） Ask how many combinations there can be [a,b,c,d] Satisfy （a<b<c<d） also （$p_a<p_c$ and $p_b>p_d$）

Ideas ：

Follow the usual line of thinking , The most violent solution is that the time complexity is O(n⁴) Enumeration , Now let's think about how to optimize .

You can handle prefixes and suffixes , Fix b and c, Then for each group （b,c） The answer is b Left side less than a[c] The number of and c The right side is smaller than a[b] The product of the number of

The preprocessing code is as follows ：

for(int i=1;i<=n;i++)
        v[i]=0;
    for(int i=1;i<=n;i++)
    {
    
        int s=0;
        for(int j=1;j<=n;j++)
        {
    
            f1[i][j]=s;
            s+=v[j];
        }
        v[a[i]]=1;
    }
    for(int i=1;i<=n;i++)
        v[i]=0;
    for(int i=n;i>=1;i--)
    {
    
        int s=0;
        for(int j=1;j<=n;j++)
        {
    
            f2[i][j]=s;
            s+=v[j];
        }
        v[a[i]]=1;
    }

Finally, accumulate the result , Pay attention long long

12.CF_1661B（1300）

Click here directly
tag -> mitmasks , brute force , dp , dfs and similar ,greedy

label ： greedy , An operation

The main idea of the topic ：

Now give me a number v, It can be executed in one operation ：

1. send $ v=(v+1) mod 32768$

2. send $v=(2\ast v)mod32768$

Now you have n A digital , Ask how many times you need to operate each number at least to make it become 0？

Ideas ：

32768, A very sensitive number ,32768 It happens to be 2^15, in other words , No matter what the numbers are , Can be in 15 operations 2 Then make it 0, Therefore, the minimum operand cannot be greater than 15.

Because of the operation 2 Every time I take 2, We can look at it from a binary point of view , multiply 2 Just add one at the back 0, and 2¹⁵ Namely 1000000000000000（15 individual 0）, Then for operation 1, You can only make the end of its binary number +1, But operation 1 For continuous 1 Come on , Contribution ratio operation 2 Big , such as 100111111 Want to be 128 Multiple , It only needs +1 become 1010000000, And if you use operations 2, You need to add 7 individual 0, Perform seven operations 2.

So our greedy strategy is obvious ： Enumerate the addition and multiplication operations respectively , Get the minimum value of the target result

Core code ：

int get_cal(int x)
{
    
    int pos=15;
    for(int i=0;i<=15;i++)
    {
    
        if(x&(1<<i))// Judge x After i Isn't it 1
        {
    
            pos=i;
            break;
        }
    }
    return 15-pos;
}
int solve(int n)
{
    
    int ans=1e7;
    for(int j=0;j<=15;j++)
    {
    
        ans=min(ans,j+get_cal((n+j)%MOD));
    }
    return ans;
}

With the 2 Multiple of , Keep a sensitive heart , Is to consider whether bit operation bitmasks Easier to solve