牛客算法周周练1题解
牛客算法周周练1题解
A：要最大的美丽
#include using namespace std;
typedef long long ll;
typedef pair pii;
const int N=1e5+10;
const int M=2e5+10;
ll a[N],pre[N];
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;
i<=n;
i++)scanf("%lld",&a[i]);
ll ans=0;
ll sum=0;
for(int i=1;
i<=n;
i++)sum+=i*a[i],pre[i]=pre[i-1]+a[i];
for(int i=k+1;
i<=n;
i++){
ll sum1=sum-a[i]*i+a[i]*(i-k)+pre[i-1]-pre[i-k-1];
ans=max(ans,sum1);
}
printf("%lld\n",ans);
}
return 0;
} B：首先要锻炼
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int N=1e3+10;
const int M=2e5+10;
double c[N],d[N];
int main()
{
int n;
scanf("%d",&n);
double v,u;
scanf("%lf %lf",&v,&u);
for(int i=1;
i<=n;
i++)scanf("%lf",&c[i]);
for(int i=1;
i<=n;
i++)scanf("%lf",&d[i]);
double ans=0;
for(int i=0;
i C:其次要拦截成功
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int N=1e5+10;
int head[N],cnt,n,q,dep[N],fa[N][17];
struct edge{
int next,to;
}e[N<<1];
void add(int u,int v){
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int f){
fa[u][0]=f;
dep[u]=dep[f]+1;
for(int i=head[u];
i;
i=e[i].next){
int v=e[i].to;
if(v==f)continue;
dfs(v,u);
}
}
void init(){
dfs(1,0);
for(int j=0;
(1<<(j+1))dep[v])swap(v,u);
int temp=dep[v]-dep[u];
for(int i=0;
(1<=0;
i--)
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
return fa[u][0];
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
cnt=0;
scanf("%d %d",&n,&q);
for(int i=0;
i<=n;
i++)head[i]=0;
for(int i=1;
i D：然后要和妹子去旅游
#include using namespace std;
typedef long long ll;
typedef pair pii;
const int N=110;
const int M=1e4+10;
int head[N],cnt,n,m,k,c[N],h1[N],h2[N];
double dp[N][500];
bool vis[N][500];
struct edge{
int next,to,w;
}e[M<<1];
void add(int u,int v,int w){
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
double dfs(int u,int t){
if(vis[u][t])return dp[u][t];
double ans=0;
int num=0;
for(int i=head[u];
i;
i=e[i].next){
int v=e[i].to,w=e[i].w;
if(c[v]+w<=t){
num++;
ans+=dfs(v,t-w-c[v])+h1[v];
}
}
vis[u][t]=1;
if(num)dp[u][t]=ans/num;
else dp[u][t]=0;
return dp[u][t];
}
double dfs1(int u,int t){
if(vis[u][t])return dp[u][t];
double ans=0;
int num=0;
for(int i=head[u];
i;
i=e[i].next){
int v=e[i].to,w=e[i].w;
if(c[v]+w<=t){
num++;
ans+=dfs1(v,t-w-c[v])+h2[v];
}
}
vis[u][t]=1;
if(num)dp[u][t]=ans/num;
else dp[u][t]=0;
return dp[u][t];
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i=1;
i<=n;
i++)scanf("%d %d %d",&c[i],&h1[i],&h2[i]);
for(int i=1;
i<=m;
i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
double ans1=0,ans2=0;
for(int i=1;
i<=n;
i++)ans1+=dfs(i,k-c[i])+h1[i];
memset(vis,false,sizeof vis);
for(int i=1;
i<=n;
i++)ans2+=dfs1(i,k-c[i])+h2[i];
printf("%.5f %.5f\n",ans1/n,ans2/n);
return 0;
} 【牛客算法周周练1题解】E:最后拿到一个幸运数字
#include using namespace std;
typedef long long ll;
typedef pair pii;
const int N=1e5+10;
const int M=2e5+10;
vectorvt;
void dfs(int pos,ll val){
if(pos==0){
vt.push_back(val);
return ;
}
dfs(pos-1,val*10+4);
dfs(pos-1,val*10+7);
}
int main()
{
for(int i=1;
i<=10;
i++)dfs(i,0);
sort(vt.begin(),vt.end());
ll ans=0;
int a,b;
scanf("%d %d",&a,&b);
int x=lower_bound(vt.begin(),vt.end(),a)-vt.begin();
int y=lower_bound(vt.begin(),vt.end(),b)-vt.begin();
y--;
if(y 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法