A
注意题上说了，ai序列是不降序列，那么对于Σai * i来说，大的数自然是在后面更好啦。所以说至少移动k个位置，那么我们就只让他动k个位置，这样保证减少的数尽可能小，保证结果尽可能大。
那么我们首先求出最开始的ans=Σai * i 然后对k+1后的枚举
一个数字往前移动k位，对结果的影响就是：i-1-k到i-1这一段的数字统一向右移动了一位，增加的价值就是这一段的和，考虑前缀和维护即可，那么a[i]从当前位置去到了i-k，那么就应该减去a[i] * k 在加上a[i] * (i-k)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
ll ans=0;
vector<ll> a(n+1);
vector<ll> sum(n+1);
for(int i=1;i<=n;i++) cin>>a[i],ans+=a[i]*i,sum[i]=sum[i-1]+a[i];
// cout<<ans<<endl;
ll q=-1e18;
for(int i=k+1;i<=n;i++){
ll e=ans-a[i]*i+(sum[i-1]-sum[i-1-k])+a[i]*(i-k);
q=max(q,e);
}
cout<<q<<endl;
}
return 0;
}
B
因为概率是完全相等的，那么我们就枚举每个人是第i个出发，计算出来的总和除以n即可
总路程是n * u 因为最后要除以n 所以过程量直接消掉了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
//ios::sync_with_stdio(0);
int n;double v,u;
cin>>n>>v>>u;
double ans=0;
vector<double> a,b;
a.resize(n+1),b.resize(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ans+=1.0*u/(a[i]-v-(j-1)*b[i]);
}
}
printf("%.3f",ans);
return 0;
}
C
这题其实就是求lca(最近公共祖先)
计算出A->1的距离dist1
计算出B->C->1的距离dist2
如果dist1<dist2 也就是A先到根节点就是YES
如果dist1==dist2 我们这里要看一下lca(a,c)是不是1 如果是的话 说明他们是从根节点的两个子树过去的，在达到根节点之前不会碰到，就输出NO，如果lca!=1,因为距离还一样，他们一定会在lca(a,c)碰面 就输出YES
如果dist1>dist2 就输出NO
这题让我发现我的tarjan求lca的板子是错的。。
板子过于丑陋，仅供参考
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define fi first
#define se second
const int maxn=200005;
vector<paii> e[maxn];
vector<paii> query[maxn];
bool vis[maxn];
int f[maxn],d[maxn];
int lcaa[maxn];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
paii ans[maxn];
int q[maxn];
void lca(int root)
{
//cout<<root<<":";
vis[root]=1;
f[root]=root;
for(int i=0; i<e[root].size(); i++){
int next=e[root][i].fi;
if(!vis[next]){
d[next]=d[root]+e[root][i].se;
lca(next);
f[next]=root;
}
}
for(int i=0; i<query[root].size(); i++){
int v=query[root][i].fi;
// if(root==6) cout<<v<<" "<<vis[v]<<endl;
if(vis[v]){
int id=query[root][i].se;
lcaa[id]=find(v);
}
}
}
int main()
{
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) e[i].clear();
for(int i=1;i<=m;i++) query[i].clear();
me(d,0);me(vis,0);me(q,0);
for(int i=0; i<n-1; i++){
int x,y,d;cin>>x>>y;
d=1;
e[x].push_back({y,d});
e[y].push_back({x,d});
}
for(int i=1; i<=m; i++){
int x,y,d;cin>>d>>x>>y;
query[x].push_back({y,i});
query[y].push_back({x,i});
query[d].push_back({y,i+m});
query[y].push_back({d,i+m});
ans[i].fi=x,ans[i].se=y;
q[i]=d;
}
//d[1]=1;
lca(1);
for(int i=1; i<=m; i++){
int l=d[ans[i].fi]+d[ans[i].se]-2*d[lcaa[i]];
// cout<<lcaa[i]<<endl;
if(d[q[i]]<l+d[ans[i].se]) cout<<"YES"<<endl;
else if(d[q[i]]==l+d[ans[i].se]){
if(lcaa[i+m]==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
}
return 0;
}
D不会待补
E
就是问区间l到r的数的next[i]和，next[i]指的是大于等于i的第一个由4或者7组成的数字
发现l和r只有1e9，那么1到1e9之间由4或7组成的数字的个数其实很少
比如长度为1 由2^1个，因为要么是4要么7
那么其实长度到9也就是2^1+2^2+.....+2^9个
但注意一点，极限数据r是1e9 大于等于1e9的第一个是444 444 4444 所以枚举的时候枚举多一点，反正也就1000多个
然后接下来就是求和了
求和的话我是直接在这1000多个满足的数去遍历，
如果num[i]<=r 那么求和就是ans += (num[i]-l+1) * num[i] 然后更新l=num[i]+1否则就是ans +=(r-l+1) * num[i] 其实也就是一块一块的计算而已
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num[2005],cnt;
ll maxn=5e9;
int main()
{
queue<ll> q;
q.push(4),q.push(7);
while(!q.empty())
{
ll now=q.front();
num[++cnt]=now;
q.pop();
if(now*10+4<=maxn&&!mp[now*10+4])
q.push(now*10+4);
if(now*10+7<=maxn&&!mp[now*10+7])
q.push(now*10+7);
}
// cout<<cnt<<endl;
ll l,r;
cin>>l>>r;
ll ans=0;
for(int i=1; i<=cnt; i++)
{
if(num[i]>=l)
{
if(num[i]<=r)
{
ans+=(num[i]-l+1)*num[i];
l=num[i]+1;
}
else
{
ans+=(r-l+1)*num[i];
break;
}
}
}
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号