原文鏈接： https://zhuanlan.zhihu.com/p/683282513

2024?？秃偎惴ɑA(chǔ)集訓(xùn)營5-個人題解

（開幕雷擊，wcgo）

A：mutsumi的質(zhì)數(shù)合數(shù)

簽到題，只需要注意1既不是質(zhì)數(shù)也不是合數(shù)即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    int num=0,val;
    for(int i=1;i<=n;i++){
        cin>>val;
        if(val<2)num++;
    }
    cout<<n-num<<'\n';
    return 0;
}

B：tomorin的字符串迷茫值

做法其實相當(dāng)?shù)暮唵未直?，賽時沒想出來，懺悔...

既然不能刪除連續(xù)的字符，那么就只有"mygo"，"m_ygo"，"my_go"，"myg_o"，"m_y_go"，"m_yg_o"，"my_g_o"，"m_y_g_o"這8種子串能夠通過刪除得到"mygo"；

那么我們就只需要尋找這八種子串的數(shù)量。對于匹配的子串，子串內(nèi)的刪除方式是唯一確定的，因此現(xiàn)在需要考慮子串外刪除的方式有多少種：只需要分別求左邊刪的方式數(shù)和右邊刪的方式數(shù)，再相乘即可得。

至于怎么求刪除方式的種數(shù)，我們考慮對于任意一個長度為n字符串，由于不能連續(xù)刪除，我們這里使用dp，簡單思考易知轉(zhuǎn)移方程為dp[i]=dp[i-1]+dp[i-2]，其中dp[i]表示長度為i的字符串有多少種刪除方式（發(fā)現(xiàn)這就是個斐波那契數(shù)列）

那么愉快解決問題：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7;

ll f[200005];

bool check(string s1,string s2){
    for(int i=0;i<s1.size();i++){
        if(s1[i]=='x')continue;
        else{
            if(s1[i]!=s2[i]) return 0;
        }
    }
    return 1;
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    string s;
    cin>>s;
    int n=s.size();
    f[0]=1;f[1]=2;
    for(int i=2;i<=n;i++){
        f[i]=(f[i-1]+f[i-2])%M;//f[i]表示長度為i的字符串有多少刪除方式
    }
    s=" "+s+"誒...一輩子？（笑）";
    ll sum=0;
    vector<string>str={"mygo","mxygo","myxgo","mygxo","mxyxgo","myxgxo","mxygxo","mxyxgxo"};
    for(int i=0;i<n;i++){
        for(auto &j:str){
            auto x=s.substr(i,j.size());
            if(check(j,x)){
                //cout<<j<<" "<<x<<'\n';
                sum=(sum+f[i-1]*f[n-(i+j.size())+1])%M;
            }
        }
    }
    cout<<sum<<"\n";
    return 0;

}

C：anon的私貨

比較典的貪心題，思路是：在兩個數(shù)字之間插入x個0，可以等效為這兩個數(shù)字同時減去x；

了解思路之后代碼就很好寫了：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200010];

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    for(int i=2;i<=2*n;i+=2){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    a[0]=1e9;a[2*n+2]=1e9;
    ll num=0;
    for(int i=1;i<=2*n+1;i+=2){
        ll s=min(a[i+1]-1,a[i-1]-1);
        a[i+1]-=s;a[i-1]-=s;
        num+=s;
    }
    cout<<num<<"\n";
    return 0;
}

D：soyorin的樹上剪切

仍是賽時沒做出來（唉，剪切線）

//后補

E：soyorin的數(shù)組操作（easy）

顯然n%2==0時，若干次操作總能使得原數(shù)組變?yōu)榉墙敌颍?/p>

那么我們其實只需要探討n%2==1的情況：

由于k是偶數(shù)，此時我們最多只能操控到倒數(shù)第二個數(shù)。

通過最后一個數(shù)與倒數(shù)第二個數(shù)的差值，我們可以知道倒數(shù)第二個數(shù)最多能被操作多少次，如此操作；然后，倒數(shù)第四個數(shù)最多能被操作多少次也可以算出來...依次類推，這樣，我們可以知道所有偶數(shù)位上的數(shù)字最多能被操作多少次。

所有操作完成后，判斷數(shù)組是否有序即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
//ll prex[10010];
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        bool flg=0;
        int n;cin>>n;
        //ll maxn=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        if(n%2==0)flg=1;
        else{
            ll sum=0;
            for(int i=n-1;i>=2;i-=2){
                a[i]+=sum*i;
                a[i-1]+=sum*(i-1);
                if(a[i]>a[i+1]){
                    break;
                }
                ll t=(a[i+1]-a[i])/i;
                sum+=t;
                a[i]+=t*i;
                a[i-1]+=t*(i-1);
//                 if(a[i-1]>a[i]){
//                     break;
//                 }
            }
            if(is_sorted(a+1,a+1+n)){
                flg=1;
            }
        }
        if(flg)cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
    return 0;
}

F：soyorin的數(shù)組操作（hard）

與上題唯一的不同是偶數(shù)的計算，這里使用二分強行糊過去的（數(shù)據(jù)似乎不是很強...）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
int n;

bool check(ll x){
    ll b[100010]={};
    for(int i=1;i<=n;i++){
        b[i]=a[i];
    }
    for(int i=1;i<=n;i++){
        b[i]+=x*i;
    }
    if(is_sorted(b+1,b+1+n)){
        return 1;
    }
    else{
        return 0;
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        bool flg=0;
        cin>>n;
        //ll maxn=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        ll sum=0;
        if(n%2==0){
            flg=1;
            ll l=0,r=1e9,mid=0,ans=0;
            while(l<r){
                mid=l+(r-l)/2;
                if(!check(mid)){
                    l=mid+1;
                }
                else{
                    ans=mid;
                    r=mid;
                }
            }
            sum=ans;
        }
        else{
              for(int i=n-1;i>=2;i-=2){
                a[i]+=sum*i;
                a[i-1]+=sum*(i-1);
                if(a[i]>a[i+1]){
                    break;
                }
                ll t=(a[i+1]-a[i])/i;
                sum+=t;
                a[i]+=t*i;
                a[i-1]+=t*(i-1);
            }
            if(is_sorted(a+1,a+1+n)){
                flg=1;
            }
        }
        if(flg)cout<<sum<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}

G：sakiko的排列構(gòu)造（easy）

構(gòu)造題，經(jīng)典數(shù)字找規(guī)律。

一開始沒思路，搓了兩個樣例之后豁然開朗了。

比如：1 2 3 4 5 6

我們發(fā)現(xiàn)，如果將其倒序，即6 5 4 3 2 1，此時 均為7，都是質(zhì)數(shù)，符合題意；

那如果是：1 2 3 4 5 6 7 呢？

我們發(fā)現(xiàn)，大于7的最小質(zhì)數(shù)是11，這意味著我們需要往11上湊，但顯然不是所有的數(shù)都能湊出11。

這時候，我們發(fā)現(xiàn)只需用1 2 3這前三個湊不出11的數(shù)字墊一下，后面接上的7 6 5 4就都能湊出11。

那么前三個怎么湊呢？事實上樣例中就有：1 3 2即可。

那么1 3 2 7 6 5 4就是該樣例的一個解。

那么此時我們基本也明白這個題的做法了：

首先用埃氏篩求出1~2n的所有質(zhì)數(shù)；

接下來是dfs(n)的操作：

然后在1~n中遍歷i，當(dāng)n+i為質(zhì)數(shù)時停止遍歷，這樣是為了找到大于n的最小質(zhì)數(shù)；

那么此時我們就可以找到一個“斷點”了：范圍內(nèi)數(shù)字需要全部倒序輸出；

然后我們繼續(xù)dfs(i-1)，直到1~n的所有數(shù)字都被輸出。

在1e3范圍內(nèi)是一定有解的，所以不需要輸出-1（開始的時候?qū)懸话胪思?1的輸出條件發(fā)現(xiàn)還過了.jpg）

丑陋的dfs如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[2000];
int prime[2000];
void sieve(int n){//埃氏篩
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
            prime[k++]=i;
        for(j=i+i;j<=n;j+=i)
            vis[j]=1;
    }
}

void dfs(int n){
    if(n==0) return;
    else if(n==1){cout<<1<<" ";return;}
    else if(n==2){cout<<2<<" "<<1<<" ";return;}
    for(int i=1;i<=n;i++){
        if(!vis[n+i]){
            dfs(i-1);
            for(int j=n;j>=i;j--){
                cout<<j<<" ";
            }
            break;
        }
    }
   
}

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    sieve(2*n);
    //cout<<vis[n+1]<<'\n';
    dfs(n);
    //cout<<-1<<'\n';
    return 0;
}

H：sakiko的排列構(gòu)造（hard）

與上題的唯一區(qū)別是數(shù)組大小和-1的輸出。

（賽時忘改數(shù)組大小就交了，喜提一發(fā)罰時）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[1000006];
int prime[1000006];
void sieve(int n)
{
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0)
            prime[k++]=i;
        for(j=i+i;j<=n;j+=i)
            vis[j]=1;
    }
}
bool flg=0;
void dfs(int n){
    if(n==0) return;
    else if(n==1){cout<<1<<" ";return;}
    else if(n==2){cout<<2<<" "<<1<<" ";return;}
    for(int i=1;i<=n;i++){
        if(!vis[n+i]){
            flg=1;
            dfs(i-1);
            for(int j=n;j>=i;j--){
                cout<<j<<" ";
            }
            break;
        }
    }
   
}

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    sieve(2*n);
    //cout<<vis[n+1]<<'\n';
    dfs(n);
    //cout<<-1<<'\n';
    if(!flg)cout<<-1<<'\n';
    return 0;
}

I：rikki的最短路

簡單模擬，簽到題

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    ll t,a,k,sum=0;
    cin>>t>>a>>k;
    if(t>0){
        if(-k<=a&&a<=t+k){
            sum+=abs(a);
            sum+=abs(a-t);
        }
        else{
            sum+=abs(t);
            sum+=2*abs(t-a);
        }
    }
    else{
        if(-k+t<=a&&a<=k){
            sum+=abs(a);
            sum+=abs(a-t);
        }
        else{
             sum+=abs(t);
            sum+=2*abs(t-a);
        }
    }
    cout<<sum<<"\n";
    return 0;
}

J：rikki的數(shù)組陡峭值

很妙的貪心：遍歷，當(dāng)發(fā)現(xiàn)相鄰區(qū)間有交集時，將其合并，此時合并的區(qū)間變成原來兩個區(qū)間的交集，就這樣將所有能合并的都合并起來，再DP就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l[100005],r[100005];
ll dp[100005][2];
vector<pair<ll,ll>> vec;
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    ll L=l[1],R=r[1];
    for(int i=2;i<=n;i++){
        if(L<=r[i]&&R>=l[i]){
            L=max(L,l[i]);
            R=min(R,r[i]);
        }
        else{
            //cout<<"l r"<<L<<" "<<R<<'\n';
            vec.push_back({L,R});
            L=l[i];R=r[i];
        }
    }
    //cout<<"l r"<<L<<" "<<R<<'\n';
    vec.push_back({L,R});
    
    ll ans=0;
    for(int i = 1; i < vec.size(); i++){
        dp[i][0] = min(dp[i - 1][0] + abs(vec[i].first - vec[i - 1].first), dp[i - 1][1] + abs(vec[i].first - vec[i - 1].second));
        dp[i][1] = min(dp[i - 1][0] + abs(vec[i].second - vec[i - 1].first), dp[i - 1][1] + abs(vec[i].second - vec[i - 1].second));
    }
    cout << min(dp[vec.size()-1][0], dp[vec.size()-1][1]) << endl;
    return 0;
}

K：soyorin的通知

DP，其實是個完全背包，但賽時大腦短路沒看出來，令人感慨

//后補

L：anon的星星

暴力枚舉，簽到題

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n,x;
    cin>>n>>x;
    int a,b;
    bool flg=0;
    for(a=0;a<=n;a++){
        b=n-a;
        if(a-b==x){
            cout<<a<<" "<<b<<'\n';
            flg=1;
            break;
        }
    }
    if(!flg)cout<<-1<<'\n';
    return 0;
}

M：mutsumi的排列連通

貪心+討論。

一個很重要的思路：當(dāng)可以通過刪除操作得到兩個以上連通塊時，最多只需要兩次刪除操作；

比如：

a：1 2 3 4 5 6

b：4 5 6 1 3 2

隨意找兩個處于相同位置的數(shù)字，比如數(shù)組a中，3在第三列，數(shù)組b中，6也在第三列，那么只需要刪去3和6就能得到兩個以上連通塊；

另外，若使用a[x]表示數(shù)字x在數(shù)組a上的位置，用b[x]表示數(shù)字x在數(shù)組b上的位置，那么我們知道：當(dāng)時，似乎只需要一次操作就能將原來的排列分成兩個連通塊；

但是需要注意一點：當(dāng)時，可能會是這種情況：

1 2 3 4

1 3 2 4

故此時需要進行特判（判斷是否在頭部或者尾部）；

至于什么情況下輸出-1，簡單思考后，我們可以知道只有兩種情況：

（1）時

（2）且數(shù)組a和b相同時

愉快解決：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100010],b[100010],c[100010];

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int x;
        for(int i=1;i<=n;i++){
            cin>>x;
            a[x]=i;
        }
        for(int i=1;i<=n;i++){
            cin>>x;
            b[x]=i;
        }
        if(n<=1)cout<<-1<<'\n';
        else if(n==2){
            if(a[1]==b[1]&&a[2]==b[2]){
                cout<<-1<<'\n';
            }
            else{
                cout<<1<<'\n';
            }
        }
        else if(n>2){
            for(int i=1;i<=n;i++){
                c[i]=abs(a[i]-b[i]);
            }
            //sort(c+1,c+1+n);
            bool flg=0;
            for(int i=1;i<=n;i++){
                if(c[i]<=1){
                    if(c[i]==0&&(i==1||i==n)){
                        continue;
                    }
                    else{
                        cout<<1<<'\n';
                        flg=1;
                        break;
                    }
                }
            }
            if(!flg)cout<<2<<'\n';
            //if(c[1]<=1)cout<<1<<'\n';
            
        }
        for(int i=1;i<=n;i++){
            a[i]=0;b[i]=0;c[i]=0;
        }
    }

    return 0;
}