【题解】ABC175

A

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int maxn=0,sum=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='R')sum++,maxn=max(maxn,sum);
        else sum=0;
    }
    cout<<maxn;
    return 0;
} 

B

枚举

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(a[i]==a[j]||a[j]==a[k]||a[i]==a[k])continue;
                if(a[i]+a[j]>a[k])ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
} 

C

离0最近的只有两个点,先分类讨论能否到达那两个点中离当前点较远的点。
若不能就输出最远能到达的点。
否则根据k和x/d的奇偶性判断答案。

#include<bits/stdc++.h>
using namespace std;
long long x,k,d; 
int main(){
    cin>>x>>k>>d;
    long long t=x/d;
    x=abs(x);
    if(x/d>=k){
        cout<<abs(x-k*d);
        return 0;
    }else{
        if((k-x/d)%2==0){
            cout<<abs(x-(x/d)*d);
            return 0;
        }else{
            cout<<abs(x-(x/d+1)*d);
        }
    }
    return 0;
} 

D

对于每一个位置枚举,求环,并找到环上最大的答案即可。

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long p[10005],c[10005];
long long sum[10005];
const long long inf=1LL << 62LL ;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    long long maxnn=-inf;
    for(int i=1;i<=n;i++){
        cin>>c[i]; 
        maxnn=max(maxnn,c[i]);
    }
    long long now;
    long long msum=0;
    for(int i=1;i<=n;i++){
        long long sum=0;
        now=p[i];
        long long lp=1;
        long long start=i;
        for(int j=1;j<=n;j++){
            if(now==start)break;
            now=p[now];
            lp++;
        }
        now=i;
        long long summ=0;
        for(int j=1;j<=lp;j++){
            summ=summ+c[now];
            now=p[now];
        }
        now=i;
        for(int j=1;j<=min(k,lp);j++){//这里记得取min!!!
            sum+=c[now];
            msum=max(msum,max(sum,sum+(k-j)/lp*summ));
            now=p[now];
        }
    }
    if(maxnn<=0){
        cout<<maxnn;
        return 0;
    }
    cout<<msum;
    return 0;
} 

E

明显一道DP。
(i,j)只能从(i-1,j)或(i,j-1)移动过来,则在所有肯能状态中取最大值即可。
$dp[i][j][k]$ 代表在(i,j)位置一行中有k个的最大情况。

#include<bits/stdc++.h>
using namespace std;
int mp[3005][3005];
long long dp[3005][3005][4];
int main(){
    int R,C,K;
    cin>>R>>C>>K;
    int r,c,v;
    for(int i=1;i<=K;i++){
        cin>>r>>c>>v;
        mp[r][c]=v;
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            for(int k=0;k<=3;k++){//每一种情况
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k]);
                dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+mp[i][j]);
            }
                dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][1]);
                dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][0]+mp[i][j]);
                dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+mp[i][j]);
                dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+mp[i][j]);
        }
    }
    long long ans=0;
    for(int i=0;i<=3;i++){
            ans=max(ans,dp[R][C][i]);
    }
    cout<<ans<<endl;
    return 0;
}

F

不会

本文链接:http://kaispace.com.cn/index.php/archives/690/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者