牛客算法周周练1补题_算法补题

阿楚姐骗我们这场只有div2A~C难度
比赛传送门
题解传送门，目前似乎没有官方题解

A.Maximize The Beautiful Value

题意

给你长度为$n$的数组$a_1\dots a_n$，和一个整数$k$，你必须从数组中选一个数，并将它向前移动$k$位，使得$F(n)={\sum }_{i=1}^{n}i\times a_i$的值最大。

思路

前缀和+枚举。
先在读入时预处理出前缀和，计算出原本的$a$数组对应的$F(n)$，记为$M$。
当枚举到第$i$位时，因为第$i$位的移动使得前面的$k$位向后移一位，而自身又向前移动了$k$位，相对于$M$产生的变化即为$-a_i\ast k+{\sum }_{j=i-k}^{i-1}{a}_j$，记录其中的最大值即为答案
时间复杂度$O(n)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
ll a[maxn],sum[maxn];
signed main()
{
	int t,n,k;
	scanf("%d",&t);
	while(t--)
	{
		ll ans=0,ma=0;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			sum[i]=sum[i-1]+a[i];
			ma+=i*a[i];
		}
		for(int i=k+1;i<=n;i++)
			ans=max(ans,ma-a[i]*k+sum[i-1]-sum[i-k-1]);
		printf("%lld\n",ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

B.身体训练

题意

这道题原题题面很坑……建议不看自己猜题意
$n$个人排成一竖排以速度$v$跑步，正常队形中每两个人间隔为$u$，每个人有超车速度$c$和衰减速度$d$，当一个人在队伍末尾时，此人开始以速度$c-(j-1)\times d$进行超车，这里的$j$表示此人是第$j$个开始超车的。
现在$n$个人初始位置随机，求每个人都进行一次超车所用的时间期望。
坑点：当上一个人还在超车过程中，当前队伍末尾的人是不开始超车的；而当上一个人到达了新的排头，末尾的人立即开始进行超车。

思路

计算出每个人以每种可能的出发次序达到队首的所用时间并求和，最后除以$n$，即为答案。
时间复杂度$O(n^2)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int maxn=1010,inf=0x3f3f3f3f,mod=1000000007;
double c[maxn],d[maxn];//初始速度,每轮衰减量
signed main()
{
	int n;
	double v,u,ans=0;
	cin>>n>>v>>u;//n个人,间隔u米,每个人速度均为v
	for(int i=1;i<=n;i++)
		cin>>c[i];
	for(int i=1;i<=n;i++)
		cin>>d[i];
	for(int i=1;i<=n;i++)
	{//第i个人以第j位出发所用时间
		for(int j=1;j<=n;j++)
		{//此人相对于队伍的速度
			ans+=n*u/(c[i]-(j-1)*d[i]-v);
		}
	}
	cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans/n<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

C. Borrow Classroom

题意

一棵$n$个节点的树，$1$为树的根节点，$q$个询问，每个询问三个数字$a,b,c$，表示

• 同学行走的路径为$b\Rightarrow c\Rightarrow 1$，保证$c\ne 1$
• 老师初始位置为$a$
  询问老师是否能在同学到达$1$节点前追上同学

思路

很明显这是个LCA的题，符合题意的情况有两种
记$d1$为老师到$1$节点的路程，$d2$为同学先到$c$再到$1$行走的路程。

• 如果$d1<d2$，则说明老师可以先到$1$节点，从而截住同学
• 如果$d1=d2$，如果老师和节点$c$在关于$1$的同一棵子树上，则说明老师和同学会在到达$1$节点之前，即$lca(a,c)$相遇，否则无法在同学到达$1$之前截住

注意：多组输入，不用$memset$见祖宗
单组时间复杂度$O(n+qlogn)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
	x=0; int ch=getchar(),f=0;
	while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	if(f)x=-x;
	read(oth...);
}
const int maxl=30;
vector<int> G[maxn];//无权边,也可以选择链式前向星存图
int gene[maxn][maxl],depth[maxn],lg[maxn];
//int nodes[maxn];//子树结点的数量
void dfs(int x,int fa)
{
	depth[x]=depth[fa]+1;
	gene[x][0]=fa;
//	nodes[x]=1;
	for(int i=1;(1<<i)<=depth[x];i++)//倍增
		gene[x][i]=gene[gene[x][i-1]][i-1];
	for(int i=0;i<G[x].size();i++)
		if(G[x][i]!=fa)
		{
			dfs(G[x][i],x);//在dfs前后加语句可以求出许多有趣的东西
//			nodes[x]+=nodes[G[x][i]];
		}
}
int lca(int x,int y)
{
	if(depth[x]<depth[y])//保证x深度≥y
		swap(x,y);
	while(depth[x]>depth[y])//将x提到同一高度
		x=gene[x][lg[depth[x]-depth[y]-1]];
	if(x==y)//是同一个节点
		return x;
	for(int i=lg[depth[x]];i>=0;i--)
		if(gene[x][i]!=gene[y][i])
		{//二分思想,直到跳到LCA的下面一层
			x=gene[x][i];
			y=gene[y][i];
		}
	return gene[x][0];
}
int dist(int x,int y)//x节点到y结点的距离
{
	int tem=lca(x,y);
	return (int)(abs(depth[x]-depth[tem])+abs(depth[y]-depth[tem]));
}
void init(int s,int n)
{
	memset(gene,0,sizeof(gene));
	depth[s]=0;
	for(int i=1;i<=n;i++)//预处理出log2(i)+1的值
		lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);//不要写错
	dfs(s,0);
}
signed main()
{
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	#ifdef DEBUG
		freopen("input.in", "r", stdin);
	//	freopen("output.out", "w", stdout);
	#endif
	int t,n,u,v,q;
	read(t);
	while(t--)
	{
		read(n,q);
		for(int i=1;i<=n;i++)
			G[i].clear();
		for(int i=1;i<n;i++)
		{
			read(u,v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		init(1,n);
		int a,b,c;
		while(q--)
		{
			read(a,b,c);
			bool ok=0;
			int t=dist(a,1),sk=dist(b,c)+dist(c,1);
			if(t<sk||(t==sk&&lca(c,a)!=1))
				ok=1;
			printf("%s\n",(ok?"YES":"NO"));
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

E.幸运数字Ⅱ

题意

定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。
比如47、744、4都是幸运数字而5、17、467都不是。
定义$next(x)$为大于等于$x$的第一个幸运数字。
给定$l，r$，求出$next(l)+next(l+1)+...+next(r-1)+next(r)$。

思路

使用dfs枚举构造出所有幸运数字，排序后在数组中二分查找当前数字的幸运数字
时间复杂度估计为$O(2^{10}+10\times 2^{10}+10\times lo{g}_{10}^{r-l})$？

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
vector<ll>luck;
void dfs(ll x)
{
	if(x>5e9)
		return;
	luck.push_back(x);
	dfs(x*10+4);
	dfs(x*10+7);
}
signed main()
{
	dfs(0);
	sort(luck.begin(),luck.end());
	ll l,r,ans=0;
	cin>>l>>r;
	while(l<=r)
	{
		ll nex=*lower_bound(luck.begin(),luck.end(),l);
		if(nex>=r)
		{
			ans+=(r-l+1)*nex;
			break;
		}
		ans+=(nex-l+1)*nex;
		l=nex+1;
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34