牛客算法周周练1
题目连接
A-Maximize The Beautiful Value题意：意思是给你一个非递减的初始数组，然后让你选择一个位置下标并把他移到某个位置去，占据位置后，其他位置会按顺序的往后移动 两个位置的距离要大于等于k。i-j>=k
比如 a[1] a[2] a[3] a[4] a[5] a[5]移到a[2]的位置去==> a[1] a[5] a[2] a[3] a[4]
定义一个数组的F(n)函数为：
题意可能有点难理解，其实仔细读下题就发现 很简单啦。
求时间，就用 距离/速度就好了 感觉没什么知识点 看代码吧
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef unsigned long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e4+10;
double c[N],d[N],u,v;
int n;
int main(){
cin>>n>>v>>u;
rep(i,1,n) scanf("%lf",&c[i]);
rep(i,1,n) scanf("%lf",&d[i]);
double ans=0;
for(int i=1;i<=n;++i){
for(int j=0;j<n;++j){
ans+=u/(c[i]-j*d[i]-v);
}
}
printf("%.3f\n",ans);
}
C-Borrow Classroom
这题算一下单子走的距离和老师走到教务处1节点 的距离比一下大小就可以了。
至于树上怎么快速的算距离，需要百度学习一下LCA这个算法。
优化一下 只需要走老师这个点和小Q这个点的最近公共祖先就可以了。如果公共祖先是1这点，老师的距离要加1
#include
using namespace std;
const int N=1e5+10;
vectorG[N];
int fa[N][23],dep[N],n,m;
void dfs(int u,int f,int d)
{
fa[u][0]=f;
dep[u]=d;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==f) continue;
dfs(v,u,d+1);
}
}
void init()
{
dfs(1,0,0);
for(int k=1;k<=20;k++)
for(int i=1;i<=n;i++)
fa[i][k]=fa[fa[i][k-1]][k-1];
}
int lca(int u,int v)
{
if(dep[v]=0;k--)
if(dep[fa[v][k]]>=dep[u]) v=fa[v][k];
if(u==v) return v;
for(int k=20;k>=0;k--)
if(fa[v][k]!=fa[u][k]) v=fa[v][k],u=fa[u][k];
return fa[v][0];
}
int main()
{
int _;cin>>_;while(_--)
{
int u,v;
cin>>n>>m;
memset(fa,0,sizeof(fa));
memset(dep,0,sizeof(dep));
for(int i=1;i<=n+1;++i) G[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
init();
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int f=lca(b,c);
int f1=lca(a,c);
int l1,l2;
if(f1==1){
l1=dep[b]+dep[c]-2*dep[f]+dep[c];
l2=dep[a];
if(l2<l1) puts("YES");
else puts("NO");
}
else{
l1=dep[b]+dep[c]-2*dep[f]+dep[c]-dep[f1];
l2=dep[a]-dep[f1];
if(l2<=l1) puts("YES");
else puts("NO");
}
//printf("l1:%d l2:%d\n",l1,l2);
}
}
}
D-景区路线规划
D题可能有点难度，涉及概率dp+记忆化搜索。
设dp[u][t]为u这个节点 当前时间为t时的期望时间。
然后根据题意dfs一下就可以了。
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pii pair
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=5e2+10;
vectorG[N];
int h[3][N],c[N],n,m,k;
double ans1,ans2;
double dp[3][N][N];
int vis[3][N][N];
double dfs(int u,int k,int ty)
{
if(vis[ty][u][k]) return dp[ty][u][k];
vis[ty][u][k]=1;
double &ans=dp[ty][u][k];
ans=h[ty][u];
int sz=0;
//for(auto now:G[u]) if(k>=now.second) sz++;
for(auto now:G[u]) if(k>=now.second+c[now.first]) sz++;
if(sz==0) return ans;
for(auto now:G[u])
{
int v=now.first;
int w=now.second;
if(k>=w+c[v]) ans+=dfs(v,k-w-c[v],ty)/sz;
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
rep(i,1,n) scanf("%d%d%d",&c[i],&h[1][i],&h[2][i]);
rep(i,1,m)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(mk(v,w));
G[v].push_back(mk(u,w));
}
rep(i,1,n) ans1+=dfs(i,k-c[i],1)*1.0/n;
rep(i,1,n) ans2+=dfs(i,k-c[i],2)*1.0/n;
printf("%.5f %.5f\n",ans1,ans2);
}
E-幸运数字Ⅱ
将题目所得幸运数字全部预处理出来，发现幸运数字特别得少，只有2000个左右。
什么？怎么预处理出来，我是用优先队列，也可以用dfs，具体看代码
那么我们就遍历幸运数字，同时更新l区间
X[i]是你枚举得幸运数字 ans 是你的答案变量
如果X[i]>=l ans+=(min(X[i],r)-l)*l 同时l=X[i]+1
判断一下 l 是否小于r就可以了。
#include
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair
#define mk make_pair
using namespace std;
typedef unsigned long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N=1e5+10;
const ll inf=1e10;
ll X[N],len;
void init()
{
priority_queue<ll,vector,greater >que;
que.push(4);
que.push(7);
while(que.size()){
ll now=que.top();que.pop();
X[++len]=now;
ll t=now*10+4;
if(t<inf) que.push(t);
t=now*10+7;
if(t>l>>r;
ll ans=0;
for(int i=1;i<=len&&l=l) {
ll t=min(X[i],r);
ans+=(t-l+1)*X[i],l=X[i]+1;
}
}
cout<<ans<<endl;
}
作者：ccsu_deer
