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}\) 表示前 \(i\) 个数中，已经选了偶数个小怪的最大经验值；\(f_{1,i}\) 则表示选了奇数个的。
那么当前的每只小怪就有选和不选两种选择。
如果不选，\(f_{k,i} = f_{k,i-1}\)，不变。
如果选了第 \(i\) 只小怪，那么小怪数量的奇偶性转换，
\[f_{k,i} = \left \{ \begin{aligned} &f_{1,i-1} + 2 a_i &, k=0 \\ &f_{0,i-1} + a_i &, k=1 \end{aligned}\right.\]最后答案即为 \(\max\{f_{0,n},f_{1,n}\}\)。
E - Sightseeing Tour
因为 \(n \le 400\)，所以 Floyd 跑出全源最短路。
因为 \(k \le 5\)，所以直接枚举所有可能的走法（五条边走的顺序和每条边进入的位置），然后依次用刚才求出的全源最短路累加求出按照这个走法从 \(1\) 走到 \(n\) 的最短路。
最后所有走法的最短路的最小值即为所求。
时间复杂度 \(O( n^3 + q \times k! \times 2^k )\)。
代码稍微有点难度，不过可以用 C++ 的一些函数减轻工作量。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=405,M=2e5+5,K=10;
int n,m,raw_g[N][N];
pair<pair<int,int>,int> raw_edge[M];
long long g[N][N];
int q,k,b[K],od[K<<1];
void Floyd()
{
for(int i=1;i<=n;i++)
g[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof(g));
for(int i=1;i<=m;i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
raw_edge[i]={{x,y},z};
raw_g[x][y]=g[x][y]=min(g[x][y],(long long)z);
raw_g[y][x]=g[y][x]=min(g[y][x],(long long)z);
}
Floyd();
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
scanf("%d",&b[j]);
sort(b+1,b+k+1);
long long ans=1e18;
do
{
for(int z=0;z<1<<k;z++)
{
long long len=0;
for(int j=1;j<=k;j++)
{
od[j*2-1]=raw_edge[b[j]].first.first;
od[j*2]=raw_edge[b[j]].first.second;
if((z>>j-1)&1) swap(od[j*2-1],od[j*2]); //reversed
} //od[1~2k]
len+=g[1][od[1]];
for(int j=1;j<=k*2;j+=2)
{
len+=raw_edge[b[j+1>>1]].second;
if(j+2<=k<<1) len+=g[od[j+1]][od[j+2]];
}
len+=g[od[k*2]][n];
ans=min(ans,len);
}
next_permutation(b+1,b+k+1);
}while(!is_sorted(b+1,b+k+1));
printf("%lld\n",ans);
}
return 0;
}
F - Gather Coins
还没做，等做了再补上。
标签：AtCoder,Beginner,Contest,int,od,ans,using,include,等差数列 From： https://www.cnblogs.com/jerrycyx/p/18490031