2024-02-21 23:09 山东大学 C++ 发布于山东

关注

个人题解 | 转载

mutsumi的质数合数

https://ac.nowcoder.com/acm/contest/67745/A

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

2024牛客寒假算法基础集训营5-个人题解

（开幕雷击，wcgo）

A：mutsumi的质数合数

签到题，只需要注意1既不是质数也不是合数即可。

#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的字符串迷茫值

做法其实相当的简单粗暴，赛时没想出来，忏悔...

既然不能删除连续的字符，那么就只有"mygo"，"m_ygo"，"my_go"，"myg_o"，"m_y_go"，"m_yg_o"，"my_g_o"，"m_y_g_o"这8种子串能够通过删除得到"mygo"；

那么我们就只需要寻找这八种子串的数量。对于匹配的子串，子串内的删除方式是唯一确定的，因此现在需要考虑子串外删除的方式有多少种：只需要分别求左边删的方式数和右边删的方式数，再相乘即可得。

至于怎么求删除方式的种数，我们考虑对于任意一个长度为n字符串，由于不能连续删除，我们这里使用dp，简单思考易知转移方程为dp[i]=dp[i-1]+dp[i-2]，其中dp[i]表示长度为i的字符串有多少种删除方式（发现这就是个斐波那契数列）

那么愉快解决问题：

#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的私货

比较典的贪心题，思路是：在两个数字之间插入x个0，可以等效为这两个数字同时减去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的数组操作（easy）

显然n%2==0时，若干次操作总能使得原数组变为非降序；

那么我们其实只需要探讨n%2==1的情况：

由于k是偶数，此时我们最多只能操控到倒数第二个数。

通过最后一个数与倒数第二个数的差值，我们可以知道倒数第二个数最多能被操作多少次，如此操作；然后，倒数第四个数最多能被操作多少次也可以算出来...依次类推，这样，我们可以知道所有偶数位上的数字最多能被操作多少次。

所有操作完成后，判断数组是否有序即可。

#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的数组操作（hard）

与上题唯一的不同是偶数的计算，这里使用二分强行糊过去的（数据似乎不是很强...）

#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的排列构造（easy）

构造题，经典数字找规律。

一开始没思路，搓了两个样例之后豁然开朗了。

比如：1 2 3 4 5 6

我们发现，如果将其倒序，即6 5 4 3 2 1，此时 $p_i i$ 均为7，都是质数，符合题意；

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

我们发现，大于7的最小质数是11，这意味着我们需要往11上凑，但显然不是所有的数都能凑出11。

这时候，我们发现只需用1 2 3这前三个凑不出11的数字垫一下，后面接上的7 6 5 4就都能凑出11。

那么前三个怎么凑呢？事实上样例中就有：1 3 2即可。

那么1 3 2 7 6 5 4就是该样例的一个解。

那么此时我们基本也明白这个题的做法了：

首先用埃氏筛求出1~2n的所有质数；

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

然后在1~n中遍历i，当n+i为质数时停止遍历，这样是为了找到大于n的最小质数；

那么此时我们就可以找到一个“断点”了： $[i,n]$ 范围内数字需要全部倒序输出；

然后我们继续dfs(i-1)，直到1~n的所有数字都被输出。

在1e3范围内是一定有解的，所以不需要输出-1（开始的时候写一半忘了加-1的输出条件发现还过了.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的排列构造（hard）

与上题的唯一区别是数组大小和-1的输出。

（赛时忘改数组大小就交了，喜提一发罚时）

#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的数组陡峭值

很妙的贪心：遍历，当发现相邻区间有交集时，将其合并，此时合并的区间变成原来两个区间的交集，就这样将所有能合并的都合并起来，再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的排列连通

贪心+讨论。

一个很重要的思路：当可以通过删除操作得到两个以上连通块时，最多只需要两次删除操作；

比如：

a：1 2 3 4 5 6

b：4 5 6 1 3 2

随意找两个处于相同位置的数字，比如数组a中，3在第三列，数组b中，6也在第三列，那么只需要删去3和6就能得到两个以上连通块；

另外，若使用a[x]表示数字x在数组a上的位置，用b[x]表示数字x在数组b上的位置，那么我们知道：当 $abs(a[x]-b[x])\le 1$ 时，似乎只需要一次操作就能将原来的排列分成两个连通块；

但是需要注意一点：当 $abs(a[x]-b[x])== 0$ 时，可能会是这种情况：

1 2 3 4

1 3 2 4

故此时需要进行特判（判断 $abs(a[x]-b[x])==0$ 是否在头部或者尾部）；

至于什么情况下输出-1，简单思考后，我们可以知道只有两种情况：

（1） $n==1$ 时

（2） $n==2$ 且数组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;
}