牛客小白月赛22补题

发表于 更新于 分类于 阅读次数：

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

A.Maximize The Beautiful Value

题意

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

思路

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

代码

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
#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;
}

B.身体训练

题意

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

思路

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

代码

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
#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;
}

C. Borrow Classroom

题意

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

  • 同学行走的路径为$b\Rightarrow c\Rightarrow1$，保证$c\neq 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)$

代码

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
#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;
}

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 log_{10}^{r-l})$？

代码

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
#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;
}