AtCoder ABC369 A-D题解

比赛链接:ABC369

省流：A<B<D<C（题解是按照该顺序写的）

Problem A:

#include <bist/stdc++.h>
using namespace std;
int main(){int A,B;cin>>A>>B;if(A==B)cout<<1<<endl;else if(abs(A-B)%2==0)cout<<3<<endl;elsecout<<2<<endl;return 0;
}

Problem B:

暴力即可。

#include <bits/stdc++.h>
using namespace std;
int main(){int N;cin>>N;int l=0,r=0,ans=0;for(int i=1;i<=N;i++){int A;char S;cin>>A>>S;if(S=='L' && !l)l=A;if(S=='R' && !r)r=A;if(S=='L'){ans+=abs(A-l);l=A;}if(S=='R'){ans+=abs(A-r);r=A;}}cout<<ans<<endl;return 0;
}

Problem D:

非常简单的一道 dp。 $dp_{i,0}$ 表示到第 $i$ 个为止，已经选了奇数个数的最大价值， $dp_{i,1}$ 表示到第 $i$ 个为止，已经选了偶数个数的最大价值。

状态转移方程：

$dp_{i,0}=max(dp_{i-1,0},dp_{i-1,1}+2\cdot A_i)\: \: dp_{i,1}=max(dp_{i-1,1},dp_{i-1,0}+A_i)$

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
int A[maxn],dp[maxn][2];
int main(){int N;cin>>N;for(int i=1;i<=N;i++)cin>>A[i];memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;for(int i=1;i<=N;i++){dp[i][1]=max(dp[i-1][1],dp[i-1][0]+A[i]);dp[i][0]=max(dp[i-1][0],dp[i-1][1]+2*A[i]); }cout<<max(dp[N][0],dp[N][1])<<endl;return 0;
}

Problem C:

赛场上 WA 了 3 次才AC。

考虑尺取。首先 i 从 1 开始往后扫，用 j 表示从 i 开始到 j 结束这一段是等差数列。因此这一段对答案的贡献是 $\frac{(j-i+1)\times (j-i)}{2}$ 。最后注意长度为 1 的区间也算等差数列。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=200005;
int A[maxn];
signed main(){int N;cin>>N;for(int i=1;i<=N;i++)cin>>A[i];int ans=0;for(int i=1;i<N;){int j=i+1,d=A[j]-A[i];while(A[j+1]-A[j]==d && j<=N)j++;ans+=(j-i+1)*(j-i)/2;i=j;}cout<<ans<<endl;return 0;
}

友情提醒:不要Ctrl C+Ctrl V

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1535735.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！