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。表示到第个为止，已经选了奇数个数的最大价值，表示到第个为止，已经选了偶数个数的最大价值。

状态转移方程：

#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 结束这一段是等差数列。因此这一段对答案的贡献是。最后注意长度为 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