第四场周赛题解

时间学的已经够久了，很多人已经用上c++了，以后题解就用户c++来写，没学c++的尽快学一下，输入输出很简单，主要学c++的STL库的函数

A.小陆学长的123

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

int main() {
    string s;
    cin>>s;
    map<char,int>mp;//c++的map,非常好用，没学的去CSDN学一下
    for(int i=0;i<s.size();i++){
        mp[s[i]]++;
    }
    if(mp['1']==1&&mp['2']==2&&mp['3']==3)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

B.小陆学长的糖果

根据题意模拟即可，按照顺序如果相差大于定于c则计数+1

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

int main(){
    int n,c;
    cin>>n>>c;
    vector<int>a(n+1);
    int last=-1e9;//初始化
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]-last>=c)ans++,last=a[i];
    }
    cout<<ans<<endl;
}

C.签到题1！？

前缀和，前面已经考过2次了，不在解释了，记得开long long

#include<stdio.h>
typedef long long ll;

int a[100010];
ll pre[100010];

int main(){
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",pre[r]-pre[l-1]);
    }
    return 0;
}

D.小陆学长跳石头(eazy)

（简单版本，a数组的顺序是排好的）根据题意可知，找两数的最大差值

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n+2);
    a[n+1]=m;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n+1;i++){
        ans=max(ans,a[i]-a[i-1]);
    }
    cout<<ans<<endl;
}

E.小陆学长跳石头(mid)

（中等版本，a数组的顺序未排好）根据题意可知，排个序，然后找两数的最大差值

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n+2);
    a[n+1]=m;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin(),a.end());//c++自带的排序，非常好用
    for(int i=1;i<=n+1;i++){
        ans=max(ans,a[i]-a[i-1]);
    }
    cout<<ans<<endl;
}

F.进制转换

自己看代码吧

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

int main(){
    int n,m;
    string s;
    cin>>n>>s>>m;
    int num=0;
    for(int i=0;i<s.size();i++){
        if(s[i]>='A'&&s[i]<='F'){
            num=num*n+(s[i]-'A'+10);
        }
        else num=num*n+(s[i]-'0');
    }
    string ans;
    while(num){
        int now=num%m;
        num/=m;
        if(now>9)ans+=('A'+now-10);
        else ans+=('0'+now);
    }
    reverse(ans.begin(),ans.end());翻转函数
    cout<<ans<<endl;
}

G.离散化

用map离散化一下(用map存值,自动离散化）,然后区间合并即可

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

int main(){
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        mp[l]++;
        mp[r]--;
    }
    int now=0;
    int ans=0;
    int flag=0;
    int pre=0;
    for(auto [u,v]:mp){//u相当于数组的下标，v相当于下标为i的数组的值（去学一下map吧）
        now+=v;
        if(now>0&&flag==0)flag=1,pre=u;
        if(now<=0&&flag==1)flag=0,ans+=u-pre;
    }
    cout<<ans<<endl;
}

H.小陆学长跳石头(hard)

（困难版本，a数组的顺序未排好，且多了1次翻倍的机会）二分答案，用二分来枚举答案，check是用来检查这个now值是否符合条件(用now走完全程使用翻倍次数不超过1次)

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

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>a(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=0,a[n+1]=m;
    sort(a.begin(),a.end());
    int l=1,r=m;

    auto check=[&](int now){
        int sta=0;
        for(int i=1;i<=n+1;i++){
            int len=a[i]-a[i-1];
            if(len>now){
                if(len<=now*2)sta++;
                else return 0;
            }
        }
        if(sta<=1)return 1;
        else return 0;
    };

    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r=mid;//缩小l,r的范围
        else l=mid+1;
    }
    cout<<r<<endl;//取最小的符合条件的r值
}

I.小陆学长打怪兽

动态规划(dp),数据水了，这才是正解(对于目前的你们来说太难了，以后有实力了再回来写吧）

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    vector<vector<int>>dp(n+1,vector<int>(n+1,-1));
    dp[0][0]=m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j>=0;j--){
            if(j==0){
                dp[i][j]=dp[i-1][j];
                continue;
            }
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-a[i]);
        }
    }
    for(int j=n;j>=0;j--){
        if(dp[n][j]>=0){
            cout<<j<<endl;
            return 0;
        }
    }
}