前面的碎碎念：
报名前看到比赛难度宣称DIV2 A-C，总担心出题人会不会虚晃一枪，把菜逼的我锤懵了。做完后感觉难度确实算是牛客比赛里偏简单的，挺适合我这种新手练习。
题解部分：
A-Maximize The Beautiful Value
首先我们算出原序列的F(n)值，然后题目要求我们把序列中某个元素前移k格，假设这个元素移动前的位置为i，那么移动后这个元素的位置就变成了i-k，很显然这个值前移导致原序列的F(n)值减少了kai。除此之外，原序列i-k到i-1位置的元素全部后移一格，那么这些元素后移导致原序列的F(n)值增加了a[i-k]+a[i-k+1]+...+a[i-1]，这个和可以利用前缀和预处理快速求解。因此，设原序列F(n)的值为s，设S数组为前缀和数组，那么将i位置元素前移k格之后的F[n]值即为：s-a[i]
k+S[i-1]-S[i-k-1]。
我们从k+1处往后扫描整个数组，计算每个元素前移k格后的F[n]值，令ans保存前移后最大的F[n]值即可。
时间复杂度：O(Tn)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long a[100005],S[100005]={0},s,ans;
int main()
{
int i,n,k,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k),ans=s=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s+=i*a[i],S[i]=S[i-1]+a[i];
}
for(i=k+1;i<=n;i++)ans=max(ans,s-a[i]*k+S[i-1]-S[i-k-1]);
printf("%lld\n",ans);
}
return 0;
}B-身体训练
因为题目说了每种顺序都是等概率的，那么某个人从最后面跑到最前面，他是第一个跑/第二个跑/.../第n个跑也都是等概率的。那么我们可以算出每个人从最后面跑到最前面，是第一个跑/第二个跑/.../第n个跑所消耗的时间。我们把这些时间全部求和，最后除以n即是答案。
至于计算时间，路程为nu，相对速度为c[i]-(j-1)
d[i]-v。用路程除以速度即可得到时间。
时间复杂度：O(n^2)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n;
double ans=0,v,u,c[1005],d[1005];
scanf("%d%lf%lf",&n,&v,&u);
for(i=1;i<=n;i++)scanf("%lf",&c[i]);
for(i=1;i<=n;i++)scanf("%lf",&d[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)ans+=n*u/(c[i]-(j-1)*d[i]-v);
printf("%.3lf\n",ans/n);
return 0;
}C-Borrow Classroom
判断dis(A,1)与dis(B,C)+dis(C,1)的大小：
若dis(A,1)<dis(B,C)+dis(C,1)，那么老师总能更快一步到1号节点，然后在小C到达1号节点的子节点时，下一秒在路上拦截他，输出YES。
若dis(A,1)>dis(B,C)+dis(C,1)，那么小C总能更快一步到达1号节点，老师拦截失败，输出NO。
若dis(A,1)=dis(B,C)+dis(C,1)，需要进一步判断A和C的最近公共祖先。若A和C的最近公共祖先不为1，那么老师和小C可以在非1号节点的某节点碰面从而拦截成功，输出YES。若A和C的最近公共祖先为1，那么老师和小C只能在1号节点碰面，根据题意这样算作拦截失败，输出NO。
计算dis的话，算出所有节点的深度值，然后对于任意两个节点i和j，有dis(i,j)=dep[i]+dep[j]-2dep[lca(i,j)]，其中lca为最近公共祖先。
时间复杂度：O(nlog(n)+q
log(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
vector<int>R[100005];
int Dep[100005],F[100005][20],t;
void DFS(int x,int fa)
{
int i,j,k;
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j==fa)continue;
Dep[j]=Dep[x]+1,F[j][0]=x;
for(k=1;k<=t;k++)F[j][k]=F[F[j][k-1]][k-1];
DFS(j,x);
}
}
int lca(int x,int y)
{
int i;
if(Dep[x]>Dep[y])swap(x,y);
for(i=t;i>=0;i--)if(Dep[F[y][i]]>=Dep[x])y=F[y][i];
if(y==x)return x;
for(i=t;i>=0;i--)if(F[y][i]!=F[x][i])y=F[y][i],x=F[x][i];
return F[x][0];
}
int main()
{
int i,j,k,n,q,T,ans1,ans2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q),t=(int)(log(n)/log(2))+1;
for(i=1;i<=n;i++)R[i].clear();
for(i=0;i<n-1;i++)
{
scanf("%d%d",&j,&k);
R[j].push_back(k),R[k].push_back(j);
}
Dep[1]=0,DFS(1,0);
while(q--)
{
scanf("%d%d%d",&i,&j,&k);
ans1=Dep[k]+Dep[k]+Dep[j]-2*Dep[lca(j,k)],ans2=Dep[i];
if(ans1>ans2)printf("YES\n");
else if(ans1==ans2)
{
if(lca(i,k)==1)printf("NO\n");
else printf("YES\n");
}
else printf("NO\n");
}
}
return 0;
}D-景区路线规划
待补...
E-幸运数字Ⅱ
首先利用DFS构造长度为1到9的幸运数字，那么就有2+2^2+2^3+..+2^9=1022个幸运数字，再加上一个长度为10的4444444444，总共也就1023个幸运数字。我们对这些数字排个序，每个幸运数字之间就形成了一个块，我们还可以将其再简单的分为三部分，前端：l到大于等于l的第一个幸运数字，中间部分，尾部：小于r且离r最近的幸运数字到r。我们对这三个部分进行求和即可，注意l和r同属于一个块内的情况。
时间复杂度：O(1023log(1023))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
long long n=0,lucky[2005];
void DFS(int L,int s)
{
if(L==10)return;
if(s)lucky[n++]=s;
DFS(L+1,s*10+4);
DFS(L+1,s*10+7);
}
int main()
{
long long i,a,b,l,r,ans=0;
DFS(0,0),lucky[n++]=4444444444,sort(lucky,lucky+n);
scanf("%lld%lld",&l,&r);
a=lower_bound(lucky,lucky+n,l)-lucky;
b=lower_bound(lucky,lucky+n,r)-lucky;
if(a==b)ans=(r-l+1)*lucky[a];
else
{
ans=(lucky[a]-l+1)*lucky[a]+(r-lucky[b-1])*lucky[b];
for(i=a+1;i<b;i++)ans+=(lucky[i]-lucky[i-1])*lucky[i];
}
printf("%lld\n",ans);
return 0;
}若有疏漏之处，还望大佬轻喷。
京公网安备 11010502036488号