封面原图 画师かにょこ
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");elseprintf("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;
}
E - Sightseeing Tour
题意
N个点，M条边，每次询问只用其中给定的K条带权边，走过所有给定边从1到N的最小长度
思路
K最大只有5，所以每个里面遍历所有情况，然后套班子求最短路就行
代码
#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=200010;
int n,m,q,u[N],v[N],a[10],ss;
bool vis[10];
long long t[N],f[410][410],inf=1e18,b[10][3],ans;
void dfs(int now)
{if(now==ss+1){ll sum=f[1][b[1][0]];for(int i=1;i<ss;i++)sum+=b[i][2]+f[b[i][1]][b[i+1][0]];sum+=b[ss][2]+f[b[ss][1]][n];ans=min(ans,sum);return;}for(int j=1;j<=ss;j++)if(!vis[j]){int i=a[j];vis[j]=1,b[now][0]=u[i],b[now][1]=v[i],b[now][2]=t[i],dfs(now+1),vis[j]=0;vis[j]=1,b[now][0]=v[i],b[now][1]=u[i],b[now][2]=t[i],dfs(now+1),vis[j]=0;}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=inf;for(int i=1;i<=n;i++) f[i][i]=0;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>t[i];f[u[i]][v[i]]=f[v[i]][u[i]]=min(f[u[i]][v[i]],t[i]);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=f[j][i]=min(f[i][j],f[i][k]+f[k][j]);cin>>q;while(q--){cin>>ss;for(int i=1;i<=ss;i++) cin>>a[i];ans=inf;dfs(1);cout<<ans<<'\n';}return 0;
}
