21天好习惯第一期－3

牛客算法周周练1 【题解】
牛客算法周周练1 【题解】
小结：
这个比赛最有意思了，对小白来说很友好，都是一些基础的算法，第一题就是我在学习前缀和的时候写过的，当时非常高兴直接秒提交了，E题打表简直不要太爽，就是题目长了点，还是不够冷静读题。

题解部分
A、Maximize The Beautiful Value
题意：
输入t组数据，每组数据给定n个递增的数，选择任意一个数(必须在第k个数后面)向前移动k步，美丽值f就是每个数与下标之积的和，求最大的美丽值f是多少

难度：
前缀和的基础题。
题目类型：前缀和

思路：
解法是前缀和。
对比移动前和移动后美丽值f的表达式：
5 3
1 1 3 4 5
f=a1 * 1 + a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5,f '=a1 * 1 + a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5 - a4 * 3 + (a1+a2+a3)
我们可以先得到最初的美丽值f，然后前k个数相加得到最初的前缀和h，那么f=f-k*a(k+1)+h,从k+1接着往后遍历，同时维护前缀和h=h-a[i-1]+a[i+k-1]，然后再记录下最大的美丽值就是答案了

复杂度：
O(n)

#include <stdio.h> #include <string.h> long long z, ans, a[], sum, m, h; int n, k, num, t,i; long long max(long long a,long long b){ 
    return a>b?a:b; } int main(){ 
    scanf("%d",&t); while(t--){ 
    ans=sum=h=0; scanf("%d%d",&n,&k); for(i=1;i<=n;i++){ 
    scanf("%lld",&a[i]); sum+=a[i]*i; } for(i=1;i<=k;i++) h+=a[i]; num=n-k; for(i=1;i<=num;i++){ 
    m=sum-a[i+k]*k; if(i>=2) h=h-a[i-1]+a[i+k-1]; m=m+h; ans=max(ans,m); } printf("%lld\n",ans); } } 

B、身体训练
题目大意：
n个人排成一队以相同的速度跑步，最后一个人相对第一个人而言向前跑nu米到排头后，此时的最后一名也这样做，但是第i个人是第j个排尾时跑到排头的速度会减少(j-1)d[i],而且每个人都可能是排头，求每个人都跑到过排头的期望

难度：
模拟就可以了
题目类型：模拟，暴力枚举

思路：
枚举每一个人的花的时间，因为每个人的位置都是随机的，所以对第i个人他可能是第j\in∈ (1,n)个跑的，每个人的时间就是：\sum_{j=1}^{n}∑
j=1
n
​
(n * u/(c[i]-(j-1)*d[i]-v))/n =(n∗u/(c[i]−(j−1)∗d[i]−v))/n= \sum_{j=1}^{n}∑
j=1
n
​
u/(c[i]-(j-1)*d[i]-v)u/(c[i]−(j−1)∗d[i]−v)
最后加上每一个人的时间就是答案了

复杂度：
O(n^2)

#include<bits/stdc++.h> #define ll long long  #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int n; double v,u,d,sum=0; double c[1001]; int main() { 
    js; cin>>n>>v>>u; for(int i=1;i<=n;++i) cin>>c[i]; for(int i=1;i<=n;++i) { 
    cin>>d; for(int j=1;j<=n;++j) { 
    sum+=u/(c[i]-(j-1)*d-v); } } cout<<fixed<<setprecision(3)<<sum<<endl; } 

C、Borrow Classroom
题目大意：
全部的点在一颗根为1的树上，同学从B到C然后再到1，老师要从A出发在同学从B走到C时拦截他或者在在他从C出发到1之前拦截他，如果能成功拦截输出Yes，反之No。

前导知识：
LCA最近公共祖先，因为每个结点的距离都是1，所以不需要dis[]–距离数组,dp[i][j]表示节点i的2^j2
j
级祖先，只需要dep[]—深度数组。这里用的是倍增+dfs在线算法实现的，Tarjan ，离线算法目前还不会
别的大佬的博客：

难度：
LCA的简单应用

思路：
每个位置到根结点1的距离就是它的深度，老师到教务处的距离ans1=dep[A],
同学到C再到教务处的距离ans2=dep[B]+2*dep[C]-2 * dep[LCA(B,C)]。
如果ans1<an2,一定能拦截成功；
如果ans1==ans2,表示老师和同学能同时到教务处，如果老师和同学在还没到教务处就相遇了LCA(A,C)!=1那么拦截成功，否则失败；
如果ans1>ans2一定失败。

先看key 1，这里的代码是尝试将a与b调制统一高度，而这里出现的位运算有些巧妙,其实就是利用二进制的特性实现逐渐加上一个二进制数。比如5=101_{2}5=101
2
​
,那么只要加2^{0}、222
0
、2
2
就可以了。

再来看key 2，因为这两个节点到LCA的深度差可以被分解成多个2的幂之和，因此我们有办法逐步将它们上移至LCA的位置。但是为了方便判断是否跳的太远，我们不让它们最后跳到LCA的位置，而是跳到LCA的儿子节点处。

复杂度：
预处理复杂度 \thetaθ (VlogV)，每次查询 \thetaθ(logV)

#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int t,n,m,a,b,c; vector<int> e[];//保存边信息  int dep[];//存该点在新建的树中的深度，也就是第几层  //遍历图， 求出各节点到根节点的路径长度和各节点的深度，并将每个点的父节点保存下来  int dp[][20]; void dfs(int root,int pre) { 
    dp[root][0]=pre; dep[root]=dep[pre]+1; for(int i=1;i<20;++i) if(dp[root][i-1]!=-1) dp[root][i]=dp[dp[root][i-1]][i-1]; for(int i=0;i<e[root].size();++i) { 
    int v=e[root][i]; if(v==pre)//避免回到父节点上 continue; dfs(v,root); } } //查询函数 int LCA(int a,int b) { 
    if(dep[a]<dep[b]) swap(a,b);//始终保持a所处的深度较深 int dist = dep[a] - dep[b];//将a上调dist个距离，使得a、b深度相同 for(int i=19;i>=0;i--) { 
    if((1<<i)&dist)//key 1 a=dp[a][i]; } if(a==b) return a; //将a、b同时上调 for(int i=19;i>=0;i--) { 
    if(dp[a][i]!=dp[b][i]) { 
    a=dp[a][i]; b=dp[b][i]; }//key 2 } //最后a、b会变成lca的子节点 return dp[a][0]; } int ans1,ans2; int main() { 
    js; cin>>t; while(t--) { 
    cin>>n>>m; for(int i=1;i<=n;i++) e[i].clear(); for(int i=1;i<n;i++) { 
    cin>>a>>b; e[a].push_back(b); e[b].push_back(a); } dep[0]=-1; dfs(1,0); while(m--) { 
    cin>>a>>b>>c; ans1=dep[a]; ans2=dep[b]+(dep[c]<<1)-(dep[LCA(b,c)]<<1); if(ans1<ans2||ans1==ans2&&LCA(a,c)!=1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; } 

D、景区路线规划
题意：
游客只能游玩k分钟，游览每个景点要花对应的时间同时会得到一定的满意度–男女获得的满足度不同，从一个景点到另一个景点也要花时间，游览路线是一个无向有权图，一男一女随机选择一个景点开始游览同时随机走向另一个景点(可能是已经看过的)，问男士和女士在游玩结束后满意度的期望。

难度：
看题解的话还是很好懂的，就是不好想到。
题目类型：记忆化搜索，概率

思路：
用dfs先求出游览最后一个景点的期望，在求出游览上一个景点的期望。
枚举现在景点能到的所有景点作为游客下一步可能参观的地方，同时统计有几种可能的方案，算出不同方案的总满足度ans后ans/cnt求得这个从最后一个景点游览到现在游客满意度的期望。因为男女不同，所以要dfs两次。因为起点随机同时参观过的还可以再参观，会有不少已经处理过的状态，所以要记忆化搜索。

复杂度：
目测\thetaθ (n^2)

#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; struct node{ 
    int h1,h2,c; }a[105]; int n,m,k,e[105][105]; double f1[105][500],f2[150][500]; double dfs1(int u,int t) { 
    if(f1[u][t]) return f1[u][t]; int cnt=0; double ans=0.0; for(int i=1;i<=n;++i) if(e[u][i]&&t>=e[u][i]+a[i].c) { 
    ++cnt; ans+=dfs1(i,t-e[u][i]-a[i].c); } if(cnt) ans/=cnt; ans+=a[u].h1; f1[u][t]=ans; return ans; } double dfs2(int u,int t) { 
    if(f2[u][t]) return f2[u][t]; int cnt=0; double ans=0.0; for(int i=1;i<=n;++i) if(e[u][i]&&t>=e[u][i]+a[i].c) { 
    ++cnt; ans+=dfs2(i,t-e[u][i]-a[i].c); } if(cnt) ans/=cnt; ans+=a[u].h2; f2[u][t]=ans; return ans; } int u,v,w; double ans1=0,ans2=0; int main() { 
    js; cin>>n>>m>>k; for(int i=1;i<=n;++i) cin>>a[i].c>>a[i].h1>>a[i].h2; for(int i=1;i<=m;++i) { 
    cin>>u>>v>>w; e[u][v]=e[v][u]=w; } for(int i=1;i<=n;++i) if(k>=a[i].c) { 
    ans1+=dfs1(i,k-a[i].c); ans2+=dfs2(i,k-a[i].c); } ans1/=n; ans2/=n; cout<<fixed<<setprecision(5)<<ans1<<" "<<ans2<<endl; return 0; } 

E、幸运数字Ⅱ
题目大意：
只有4，7的数字叫幸运数字，对于区间[L,r]的每一个数找出第一个大于它的幸运数字，对这些幸运数字求和

难度：
本场比赛的签到题。
题目类型：暴力枚举，贪心

思路：
打表出所有的幸运数字,然后找到第一个不小于L的幸运数字。
打表代码如下，记得要手动加上，打表要用ll，不然会死循环：

#include<bits/stdc++.h> #define ll long long #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll a[]; void dfs(int x) { 
    if((a[x]<<3)+(a[x]<<1)+4>) return; a[x<<1]=(a[x]<<3)+(a[x]<<1)+4; a[x<<1|1]=a[x<<1]+3; dfs(x<<1); dfs(x<<1|1); } int main() { 
    a[1]=0; dfs(1); for(int i=2;i<=1023;++i) printf("%lld,",a[i]); } 

#include<bits/stdc++.h> #define ll long long  #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll dp[1023]={ 
   4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774, 4777,7444,7447,7474,7477,7744,7747,7774,7777,44444,44447,44474,44477,44744,44747,44774,44777,47444, 47447,47474,47477,47744,47747,47774,47777,74444,74447,74474,74477,74744,74747,74774,74777,77444,77447, 77474,77477,77744,77747,77774,77777,,,,,,,,,, ,,,,,,,,,,,,,, ,,,,,,,,,,,,,, ,,,,,,,,,,,,,, ,,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,}; int main() { 
    js; ll ans=0; int l,r,mid,a,b; cin>>l>>r; a=lower_bound(dp,dp+1023,l)-dp; for(int i=l;i<=r;++i) { 
    if(dp[a]<i) ++a; ans+=dp[a]; } printf("%lld\n",ans); }