7.13学习记录

由于长时间没训练了，先刷一个周的CF来一遍熟悉思维构造题，一遍熟悉之前学过的一些算法和自己的模板。
C. Even Picture

题意：给定数值n，要求你构造一个图案，这个图案有n个方格的四个方向上都有方格，并且所有方格四个方向上都有偶数个方格，并且要求这个图案中的方格是相链接的。

思路：我们先试着去把一个方格的情况画出来，发现有这两种可能

那么我们再继续看两个方格的情况

我们发现两个方格的时候，只有一种情况合法了

以此类推，合法的应该是一个条带状的方格图案。

这个构造题呢，我们可以试着去从小到大推，看看合法的方案，越大的情况下， 正确的构造方法就越有规律性和独一性。

#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)

题意：给定一个数组，要求构造出最多的波谷。

我们从贪心的角度去考虑，这个题的波谷位置显然需要这个数组中最小的若干个数，首位选取最大的数去充当，然后其他波峰位置从剩下的数中，从小到大安排就可以了。

#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
这个题可有意思了，我之前做过一个很相似的。

这个题的关键在于，我们怎么确定要不要插入一个数来切断他的区间和为“0”的区间。

区间和为0，有意思，我们应该能直接想到用前缀和来优化，前缀和可以灵活的求出任意区间的区间和，但是如果查询所有区间，n²复杂度显然不能接受，那么我们就要利用题目中区间和为0的这个特性来切入，如果说一段区间的区间从l到r的和为0，那么显然，包含这段区间l-1和不包含的段区间r+1位置的前缀和应该相等。

如此一来这题基本就结了。
另外一个问题是。

普通情况下，如果前缀和sum[l]==sum[r]必然就有一个和为0的区间了，但是如果有sum[x]=0，那么不比等待其他前缀和与其相等，他自己就可以让操作数加一。

#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
一眼看上去竟然有2-sat标签，能给我吓死，再一看，diff才1500，2-sat尼玛呢。
先按照约束多的0来构造，再去检查时候合法即可。

#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
这题啥构造啊这是，这不分类讨论吗。

题意:给定一个长为n的排列，并且规定一种特殊的排序，即：选定一段区间，让这段区间的所有数脱离目前位置，放在此区间其他位置上。问：多少次排序后能够获得升序的序列
思路：最多两次排序，最少0次，一般情况为1次

注意，我们只有当排序后的数组b和原数组a对比时，我们发现有a[i]==B[i]并且i这个位置的前后都有a[j]==b[j]的时候，才需要2次排序。

#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;
}