<iframe allowfullscreen="true" data-mediaembed="bilibili" frameborder="0" id="TybVg4eq-1725111471844" src="https://player.bilibili.com/player.html?aid=113056860406906"></iframe>
AtCoder Beginner Contest 369
我愿称之为等差数列场
A - 369
题意
给两个数，问能和他们构成等差数列的数有多少个
代码
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main()
{
int x,y;
cin >> x >> y;
if(x==y) printf("1\n");
else if((x+y)%2==1) printf("2\n");
else printf("3\n");
return 0;
}
B - Piano 3
题意
钢琴有100个键，有的键要用左手按有的要用右手按，现在你要按顺序按一些键，最小化两只手移动的距离
思路
说是最小化，其实手只能放在第一个按的键的位置，答案是固定的，直接模拟即可
代码
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main()
{
int n;
scanf("%d",&n);
int L=-1,R=-1,ans=0;
while(n--)
{
int x;
char c;
scanf("%d %c",&x,&c);
if(c=='R')
{
if(R==-1) R=x;
else
{
ans+=abs(x-R);
R=x;
}
}
else
{
if(L==-1) L=x;
else
{
ans+=abs(x-L);
L=x;
}
}
}
printf("%d\n",ans);
return 0;
}
C - Count Arithmetic Subarrays
题意
给你一个数组，问多少个连续子数组是等差数列
思路
记录每两个数之间的差值，连续的相同差值看有多少个，那么答案就可以从1加到n，用求和公式即可
为什么是1加到n呢？假设我们现在有4个数，他们之间的差值都是3，那么在我们的差值数组里面就存了3个3，1个一次算有3个，2个一次算有2个，3个一次算有3个，更多的也是一样的，不难证明
记得开long long
代码
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main()
{
ll n;
scanf("%lld",&n);
vector<ll> a(n),del(n-1);
for (int i=0;i<n;++i)
{
scanf("%lld",&a[i]);
if (i>0)
del[i-1]=a[i]-a[i-1];
}
if(n==1)
{
printf("1\n");
return 0;
}
if(n==2)
{
printf("3\n");
return 0;
}
if(n==3)
{
if(a[1]-a[0]==a[2]-a[1])
printf("6\n");
else
printf("5\n");
return 0;
}
ll ans=n;
ll cnt=1;
for(int i=1;i<n-1;i++)
{
if(del[i]==del[i-1])
cnt++;
else
{
ans+=cnt*(cnt+1ll)/2ll;
cnt=1ll;
}
}
ans+=cnt*(cnt+1ll)/2ll;
printf("%lld\n",ans);
return 0;
}
D - Bonus EXP
题意
一共N个怪兽，每个都可以选择打或者不打，打的第偶数个怪兽给的经验翻倍，每个怪兽给的经验已知，最大化总经验值
思路
看题很明显是一个dp，每个数用0/1代表奇偶即可
代码
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=1000010;
ll a[N],dp[N][2];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
dp[0][0]=0,dp[0][1]=-1e18;
for(int i=1;i<=n;i++)
{
dp[i][0]=max(dp[i-1][1]+a[i]*2,dp[i-1][0]);
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
}
printf("%lld\n",max(dp[n][0],dp[n][1]));
return 0;
}