这是蒟蒻在摸鱼许久之后的题解(图论还是不会....
A
这是一个签到题 思考移动会带来哪些影响后有了以下思路
先求出未移动的美丽值和a[i]的前缀和
经思考证明（贪心思路） 把所有向前移动k步的值算出来 最大的即最大美丽值
算的过程依靠之前求的 当你移动时是相当于有一部分没动 有一部分增加了一倍 等等
建议不懂的手动推导下
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int const maxn=1e5+5;
ll n,k,a[maxn],t,cnt[maxn],ans,z;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&k);
z=0;
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
z+=a[i]*i;
cnt[i]=cnt[i-1]+a[i];
}
ans=0;
for(int i=k+1;i<=n;++i)
{
ll ins=z-i*a[i]+a[i]*(i-k)+cnt[i-1]-cnt[i-k-1];
ans=max(ans,ins);
}
printf("%lld\n",ans);
}
return 0;
}B
这是一个概率题 由题目知道每个人是等概率的
于是我们计算每个人从最后跑到最前的时间除以n就是期望了
路程nu 相对速度 c[i]-(j-1)d[i]-v 时间为路程除以速度
#include<bits/stdc++.h>
#define ll long long
ll const maxn=1000+5;
using namespace std;
ll n;
double u,v,ans,c[maxn],d[maxn];
int main()
{
scanf("%d%lf%lf",&n,&v,&u);
for(int i=1;i<=n;i++) scanf("%lf",&c[i]);
for(int i=1;i<=n;i++) scanf("%lf",&d[i]);
for(int i=1;i<=n;i++)///第几个人
{
for(int j=1;j<=n;j++)///从最后跑到最前
{
ans+=n*u/(c[i]-(j-1)*d[i]-v);
}
}
ans/=n;
printf("%.3lf\n",ans);
return 0;
}C
这题刚开始看的时候很难 似乎无从下手 于是我们从怎么才能成功拦截出发
我们首先要知道 (i,1)的距离与 (j,k)+(k,1)的距离的关系
计算距离的话，算出所有节点的深度值，然后有ans1=h[k]+h[k]+h[j]-2*h[LCA(j,k)],ans2=h[i]， 其中lca为最近公共祖先。
如果
若ans1<ans2，那么老师总能更快一步到1号节点，然后在小C到达1号节点的子节点时，下一秒在路上拦截他，输出YES。
若ans1>ans2，那么小C总能更快一步到达1号节点，老师拦截失败，输出NO。
若ans1==ans2，需要进一步判断i和k的最近公共祖先。若i和k的最近公共祖先不为1，那么老师和小C可以在非1号节点的某节点碰面从而拦截成功，输出YES。若i和k的最近公共祖先为1，那么老师和小C只能在1号节点碰面，根据题意这样算作拦截失败，输出NO。
仔细思考后 这其实算是一个套lca板子的板子题
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int head[N<<1],nex[N<<1],to[N<<1],tot;
int n,q,t,f[N][30],lg[N],h[N];
void add(int a,int b){
to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
h[x]=h[fa]+1; f[x][0]=fa;
for(int i=1;(1<<i)<=h[x];i++) f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=nex[i]){
if(to[i]!=fa) dfs(to[i],x);
}
}
int LCA(int x,int y){
if(h[x]<h[y]) swap(x,y);
while(h[x]>h[y]) x=f[x][lg[h[x]-h[y]]-1];
if(x==y) return x;
for(int i=lg[h[x]]-1;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
int main(){
scanf("%d",&t);
while(t--)
{
memset(head,-1,sizeof(head));
memset(f,0,sizeof(f));
memset(h,0,sizeof(h));
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);int ans1=0,ans2=0;
for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
while(q--)
{
int i,j,k;
scanf("%d%d%d",&i,&j,&k);
ans1=h[k]+h[k]+h[j]-2*h[LCA(j,k)],ans2=h[i];
if(ans1>ans2)printf("YES\n");
else if(ans1==ans2)
{
if(LCA(i,k)==1)printf("NO\n");
else printf("YES\n");
}
else printf("NO\n");
}
}
return 0;
}E
直接打表 方便快捷
在套用一点点数学知识 一个区间有很大一部分的值是相同的
于是就出来了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll const maxn=1e9;
ll a[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,444444,444447,444474,444477,444744,444747,444774,444777,
447444,447447,447474,447477,447744,447747,447774,447777,474444,474447,
474474,474477,474744,474747,474774,474777,477444,477447,477474,477477,
477744,477747,477774,477777,744444,744447,744474,744477,744744,744747,
744774,744777,747444,747447,747474,747477,747744,747747,747774,747777,
774444,774447,774474,774477,774744,774747,774774,774777,777444,777447,
777474,777477,777744,777747,777774,777777,4444444,4444447,4444474,4444477,
4444744,4444747,4444774,4444777,4447444,4447447,4447474,4447477,4447744,4447747,
4447774,4447777,4474444,4474447,4474474,4474477,4474744,4474747,4474774,4474777,
4477444,4477447,4477474,4477477,4477744,4477747,4477774,4477777,4744444,4744447,
4744474,4744477,4744744,4744747,4744774,4744777,4747444,4747447,4747474,4747477,
4747744,4747747,4747774,4747777,4774444,4774447,4774474,4774477,4774744,4774747,
4774774,4774777,4777444,4777447,4777474,4777477,4777744,4777747,4777774,4777777,
7444444,7444447,7444474,7444477,7444744,7444747,7444774,7444777,7447444,7447447,
7447474,7447477,7447744,7447747,7447774,7447777,7474444,7474447,7474474,7474477,
7474744,7474747,7474774,7474777,7477444,7477447,7477474,7477477,7477744,7477747,
7477774,7477777,7744444,7744447,7744474,7744477,7744744,7744747,7744774,7744777,
7747444,7747447,7747474,7747477,7747744,7747747,7747774,7747777,7774444,7774447,
7774474,7774477,7774744,7774747,7774774,7774777,7777444,7777447,7777474,7777477,
7777744,7777747,7777774,7777777,44444444,44444447,44444474,44444477,44444744,44444747,
44444774,44444777,44447444,44447447,44447474,44447477,44447744,44447747,44447774,44447777,
44474444,44474447,44474474,44474477,44474744,44474747,44474774,44474777,44477444,44477447,
44477474,44477477,44477744,44477747,44477774,44477777,44744444,44744447,44744474,44744477,
44744744,44744747,44744774,44744777,44747444,44747447,44747474,44747477,44747744,44747747,
44747774,44747777,44774444,44774447,44774474,44774477,44774744,44774747,44774774,44774777,
44777444,44777447,44777474,44777477,44777744,44777747,44777774,44777777,47444444,47444447,
47444474,47444477,47444744,47444747,47444774,47444777,47447444,47447447,47447474,47447477,
47447744,47447747,47447774,47447777,47474444,47474447,47474474,47474477,47474744,47474747,
47474774,47474777,47477444,47477447,47477474,47477477,47477744,47477747,47477774,47477777,
47744444,47744447,47744474,47744477,47744744,47744747,47744774,47744777,47747444,47747447,
47747474,47747477,47747744,47747747,47747774,47747777,47774444,47774447,47774474,47774477,
47774744,47774747,47774774,47774777,47777444,47777447,47777474,47777477,47777744,47777747,
47777774,47777777,74444444,74444447,74444474,74444477,74444744,74444747,74444774,74444777,
74447444,74447447,74447474,74447477,74447744,74447747,74447774,74447777,74474444,74474447,
74474474,74474477,74474744,74474747,74474774,74474777,74477444,74477447,74477474,74477477,
74477744,74477747,74477774,74477777,74744444,74744447,74744474,74744477,74744744,74744747,
74744774,74744777,74747444,74747447,74747474,74747477,74747744,74747747,74747774,74747777,
74774444,74774447,74774474,74774477,74774744,74774747,74774774,74774777,74777444,74777447,
74777474,74777477,74777744,74777747,74777774,74777777,77444444,77444447,77444474,77444477,
77444744,77444747,77444774,77444777,77447444,77447447,77447474,77447477,77447744,77447747,
77447774,77447777,77474444,77474447,77474474,77474477,77474744,77474747,77474774,77474777,
77477444,77477447,77477474,77477477,77477744,77477747,77477774,77477777,77744444,77744447,
77744474,77744477,77744744,77744747,77744774,77744777,77747444,77747447,77747474,77747477,
77747744,77747747,77747774,77747777,77774444,77774447,77774474,77774477,77774744,77774747,
77774774,77774777,77777444,77777447,77777474,77777477,77777744,77777747,77777774,77777777,
444444444,444444447,444444474,444444477,444444744,444444747,444444774,444444777,444447444,444447447,
444447474,444447477,444447744,444447747,444447774,444447777,444474444,444474447,444474474,444474477,
444474744,444474747,444474774,444474777,444477444,444477447,444477474,444477477,444477744,444477747,
444477774,444477777,444744444,444744447,444744474,444744477,444744744,444744747,444744774,444744777,
444747444,444747447,444747474,444747477,444747744,444747747,444747774,444747777,444774444,444774447,
444774474,444774477,444774744,444774747,444774774,444774777,444777444,444777447,444777474,444777477,
444777744,444777747,444777774,444777777,447444444,447444447,447444474,447444477,447444744,447444747,
447444774,447444777,447447444,447447447,447447474,447447477,447447744,447447747,447447774,447447777,
447474444,447474447,447474474,447474477,447474744,447474747,447474774,447474777,447477444,447477447,
447477474,447477477,447477744,447477747,447477774,447477777,447744444,447744447,447744474,447744477,
447744744,447744747,447744774,447744777,447747444,447747447,447747474,447747477,447747744,447747747,
447747774,447747777,447774444,447774447,447774474,447774477,447774744,447774747,447774774,447774777,
447777444,447777447,447777474,447777477,447777744,447777747,447777774,447777777,474444444,474444447,
474444474,474444477,474444744,474444747,474444774,474444777,474447444,474447447,474447474,474447477,
474447744,474447747,474447774,474447777,474474444,474474447,474474474,474474477,474474744,474474747,
474474774,474474777,474477444,474477447,474477474,474477477,474477744,474477747,474477774,474477777,
474744444,474744447,474744474,474744477,474744744,474744747,474744774,474744777,474747444,474747447,
474747474,474747477,474747744,474747747,474747774,474747777,474774444,474774447,474774474,474774477,
474774744,474774747,474774774,474774777,474777444,474777447,474777474,474777477,474777744,474777747,
474777774,474777777,477444444,477444447,477444474,477444477,477444744,477444747,477444774,477444777,
477447444,477447447,477447474,477447477,477447744,477447747,477447774,477447777,477474444,477474447,
477474474,477474477,477474744,477474747,477474774,477474777,477477444,477477447,477477474,477477477,
477477744,477477747,477477774,477477777,477744444,477744447,477744474,477744477,477744744,477744747,
477744774,477744777,477747444,477747447,477747474,477747477,477747744,477747747,477747774,477747777,
477774444,477774447,477774474,477774477,477774744,477774747,477774774,477774777,477777444,477777447,
477777474,477777477,477777744,477777747,477777774,477777777,744444444,744444447,744444474,744444477,
744444744,744444747,744444774,744444777,744447444,744447447,744447474,744447477,744447744,744447747,
744447774,744447777,744474444,744474447,744474474,744474477,744474744,744474747,744474774,744474777,
744477444,744477447,744477474,744477477,744477744,744477747,744477774,744477777,744744444,744744447,
744744474,744744477,744744744,744744747,744744774,744744777,744747444,744747447,744747474,744747477,
744747744,744747747,744747774,744747777,744774444,744774447,744774474,744774477,744774744,744774747,
744774774,744774777,744777444,744777447,744777474,744777477,744777744,744777747,744777774,744777777,
747444444,747444447,747444474,747444477,747444744,747444747,747444774,747444777,747447444,747447447,
747447474,747447477,747447744,747447747,747447774,747447777,747474444,747474447,747474474,747474477,
747474744,747474747,747474774,747474777,747477444,747477447,747477474,747477477,747477744,747477747,
747477774,747477777,747744444,747744447,747744474,747744477,747744744,747744747,747744774,747744777,
747747444,747747447,747747474,747747477,747747744,747747747,747747774,747747777,747774444,747774447,
747774474,747774477,747774744,747774747,747774774,747774777,747777444,747777447,747777474,747777477,
747777744,747777747,747777774,747777777,774444444,774444447,774444474,774444477,774444744,774444747,
774444774,774444777,774447444,774447447,774447474,774447477,774447744,774447747,774447774,774447777,
774474444,774474447,774474474,774474477,774474744,774474747,774474774,774474777,774477444,774477447,
774477474,774477477,774477744,774477747,774477774,774477777,774744444,774744447,774744474,774744477,
774744744,774744747,774744774,774744777,774747444,774747447,774747474,774747477,774747744,774747747,
774747774,774747777,774774444,774774447,774774474,774774477,774774744,774774747,774774774,774774777,
774777444,774777447,774777474,774777477,774777744,774777747,774777774,774777777,777444444,777444447,
777444474,777444477,777444744,777444747,777444774,777444777,777447444,777447447,777447474,777447477,
777447744,777447747,777447774,777447777,777474444,777474447,777474474,777474477,777474744,777474747,
777474774,777474777,777477444,777477447,777477474,777477477,777477744,777477747,777477774,777477777,
777744444,777744447,777744474,777744477,777744744,777744747,777744774,777744777,777747444,777747447,
777747474,777747477,777747744,777747747,777747774,777747777,777774444,777774447,777774474,777774477,
777774744,777774747,777774774,777774777,777777444,777777447,777777474,777777477,777777744,777777747,
777777774,777777777,4444444444};
ll l,r,ans,next,cnt;
int main()
{
cin>>l>>r;
for(ll i=l;i<=r;++i)
{
ll z=lower_bound(a,a+1023,i)-a;
ll next=a[z],cnt=min(r,next)-i+1;
ans+=next*cnt;
i=next;
}
printf("%lld",ans);
return 0;
}看到最后的彩蛋 推荐一首轻音乐：夏の喚く
^-^
京公网安备 11010502036488号