A - 369
样例已经包括了所有的情况(真良心)。
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;int main()
{int a,b; scanf("%d%d",&a,&b);int ans=0;if(a>b) swap(a,b);if(a==b) ans=1;else if((b-a)&1) ans=2;else ans=3;printf("%d\n",ans);return 0;
}
B - Piano 3
最开始左右手分别放在最初需要用左右手的键上,然后模拟即可。
点击查看代码
#include<cstdio>
#include<cmath>
using namespace std;int main()
{int n; scanf("%d",&n);int l=0,r=0,ans=0;for(int i=1;i<=n;i++){int x; char s[5];scanf("%d%s",&x,s);if(s[0]=='L'){if(!l) l=x;ans+=abs(l-x);l=x;}if(s[0]=='R'){if(!r) r=x;ans+=abs(r-x);r=x;}}printf("%d\n",ans);return 0;
}
C - Count Arithmetic Subarrays
简单题。
有一个性质(我没有证明,但看上去就是对的):等差数列的子串一定是等差数列。
所以双指针找出原数列的所有的极大等差数列子串(即这个等差数列不是任何更大等差数列的真子串),然后这个等差数列的内每一个区间都是等差数列,公式求数量即可。
还要注意两个相邻的等差数列在边界上会公用一个元素,这个元素所构成的单元素等差数列不能重复计算,要减一。但是最后答案要加一个来补齐数列的两端。
#include<cstdio>
using namespace std;const int N=2e5+5;
int n,a[N];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int l=0,r=0;long long ans=0;for(l=1;l<n;l=r){for(r=l+1;r<=n;r++)if(a[r+1]-a[r]!=a[r]-a[r-1]) break;int len=r-l+1;ans+=1ll*(1+len)*len/2-1;}printf("%lld\n",ans+1);return 0;
}
D - Bonus EXP
一眼 DP。
设 \(f_{0,i}\) 表示