7.13 learning records

Because I haven't trained for a long time , Brush for a week first CF Get familiar with the problem of thinking structure , Familiarize yourself with some algorithms and your own templates learned before .
C. Even Picture

The question ： Given value n, Ask you to construct a pattern , This pattern has n There are squares in four directions of each square , And all squares have even number of squares in four directions , And the squares in this pattern are required to be linked .

Ideas ： Let's try to draw a square first , It is found that there are two possibilities

Then let's continue to look at the situation of the two squares

When we found two squares , Only one case is legal

And so on , The legal one should be a banded checkered pattern .

This construction problem , We can try to push from small to large , Look at the legal plan , The bigger the situation is , The more regular and unique the correct construction method is .

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

int main()
{
    
    int n;
    cin>>n;
    cout<<7+(n-1)*3<<endl;
    for(int i=0;i<=n+1;i++)
    {
    
        cout<<i<<" "<<i<<endl;
    }
    for(int i=1;i<=n+1;i++)
    {
    
        cout<<i<<" "<<i-1<<endl;
    }
    for(int i=0;i<=n;i++)
    {
    
        cout<<i<<" "<<i+1<<endl;
    }
    return 0;
}

D2. Sage’s Birthday (hard version)

The question ： Given an array , It is required to construct the most troughs .

We consider it from the perspective of greed , The trough position of this problem obviously requires the smallest number in this array , Choose the largest number in the first place to act as , Then the other peak positions from the remaining number , It's OK to arrange from small to large .

#include <iostream>
#include <algorithm>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5+100;
int a[N];
int b[N];
signed main()
{
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int con=1;
    for(int i=2;i<=n;i+=2)
    {
    
        b[i]=a[con++];
    }
    for(int i=1;i<=n;i++)
    {
    
        if(b[i]==0)
        {
    
            b[i]=a[con++];
        }
    }
    int ans=0;
    for(int i=2;i<=n-1;i++)
    {
    
        if(b[i]<b[i-1]&&b[i]<b[i+1])
        {
    
            ans++;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    {
    
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}

D. Non-zero Segments
This question is interesting , I have done a very similar one before .

The key to this question is , How do we decide whether to insert a number to cut off his interval sum for “0” The range of .

Interval sum is 0, interesting , We should be able to think directly of using prefix and to optimize , Prefix sum can flexibly calculate the interval sum of any interval , But if you query all the intervals ,n² Complexity is obviously unacceptable , Then we will use the interval sum in the topic to 0 This feature of , If the interval of a section starts from l To r And for 0, So clearly , Include this section l-1 And excluded segment intervals r+1 The prefix and of position should be equal .

In this way, the problem is basically solved .
Another problem is .

In general , If prefix and sum[l]==sum[r] There must be a harmony 0 The range of , But if there is sum[x]=0, Then it's no better than waiting for other prefixes and being equal to them , He can add one to the operand himself .

#include <iostream>
#include <map>
#define int long long
#define endl '\n'
#define fi first
#define se second

using namespace std;

const int N = 2e5+100;

int a[N],sum,n,ans;
map<int,int> mp;
signed main()
{
    
    cin>>n;
    mp[0]=1;
    for(int i=1;i<=n;i++)
    {
    
        cin>>a[i];
        sum+=a[i];
        if(mp[sum])
        {
    
            ans++;
            sum=a[i];
            mp.clear();
            mp[0]=1;
        }
        mp[sum]=1;
    }
    cout<<ans<<endl;
    return 0;
}

C. Binary String Reconstruction
At a glance, there seems to be 2-sat label , It can scare me to death , Look again ,diff only 1500,2-sat Where's NIMA .
First, according to the more constrained 0 To construct the , It's legal to check again .

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int a[N];
int b[N];
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
            b[i]=a[i];
        }
        sort(a+1,a+n+1);
        bool falg1=0;
        bool falg2=0;
        int fi=1000000,se=-1;
        for(int i=1;i<=n;i++)
        {
    
            if(a[i]!=b[i])
            {
    
                falg2=1;
                fi=min(i,fi);
                se=max(se,i);
            }
        }
        for(int i=fi;i<=se;i++)
        {
    
            if(a[i]==b[i])
            {
    
                falg1=1;
            }
        }
        if(falg1&&falg2)
        {
    
            cout<<2<<endl;
        }
        else if(!falg2)
        {
    
            cout<<0<<endl;
        }
        else if(!falg1&&falg2)
        {
    
            cout<<1<<endl;
        }
    }
    return 0;
}

C. Omkar and Baseball
What's the structure of this problem? This is , Isn't this classified discussion .

The question : Give a length of n Permutation , And specify a special sort , namely ： Select a section , Let all the numbers in this range be out of the current position , Put it in other positions in this section . ask ： How many times can you get the ascending sequence after sorting
Ideas ： Sort twice at most , least 0 Time , The general situation is 1 Time

Be careful , We can only use the sorted array b And the original array a In contrast , We found that there was a[i]==B[i] also i There are both front and back of this position a[j]==b[j] When , That's what we need 2 Secondary ranking .

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int a[N];
int b[N];
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
            b[i]=a[i];
        }
        sort(a+1,a+n+1);
        bool falg1=0;
        bool falg2=0;
        int fi=1000000,se=-1;
        for(int i=1;i<=n;i++)
        {
    
            if(a[i]!=b[i])
            {
    
                falg2=1;
                fi=min(i,fi);
                se=max(se,i);
            }
        }
        for(int i=fi;i<=se;i++)
        {
    
            if(a[i]==b[i])
            {
    
                falg1=1;
            }
        }
        if(falg1&&falg2)
        {
    
            cout<<2<<endl;
        }
        else if(!falg2)
        {
    
            cout<<0<<endl;
        }
        else if(!falg1&&falg2)
        {
    
            cout<<1<<endl;
        }
    }
    return 0;
}