牛客算法周周练1

A题题解：
假定原先序列为 $a_1,a_2,a_3,\cdots,a_n$
则不改变序列的话，值为 $sum=\sum\limits_{i=1}^{n}i*a[i]$
现在我们将 $a_i$ 移动到 $j$ 位置，会生什么呢，没受影响的有 $a_1,a_2\cdots,a_{j-1}$ 和 $a_{i+1},a_{i+2},\cdots,a_{n}$ ,而 $a_j,\cdots,a_{i-1}$ 都后移一位，即此时 $ans=sum+\sum\limits_{k=j}^{i-1}{a[k]}$ ,而 $a_i$ 产生的贡献减少了 $a_i*(i-j)$
即整体答案会变成 $ans=sum+\sum\limits_{k=j}^{i-1}{a[k]}-a_i*(i-j)=sum-\sum\limits_{k=j}^{i-1}{(a_i-a_k)}$ ,由于原序列非递减，所以有 $a_i-a_k>=0$ ，即 $j$ 越大，答案越大，所以暴力一下每个数往前k个然后计算取最大即可。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=5e5+7;
const int mod=1e9+7;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
ll a[MX],pre[MX];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
      int n,k;
      cin>>n>>k;
      pre[0]=0;
      ll sum=0;
      rep(i,1,n)
      {
          cin>>a[i];
          sum=sum+i*a[i];
          pre[i]=pre[i-1]+a[i];
      }
      ll ans=0;
      rep(i,k+1,n)
      {
          ans=max(ans,sum-k*a[i]+pre[i-1]-pre[i-k-1]);
      }
      cout<<ans<<endl;
  }
}

B题题解：
初始大家都是相隔 $u$ 米，速度为 $v米/s$ ，如果排在末尾的最高速度为 $w$ ，则其要跑到排头并且要甩掉第二名 $u$ 米所要花费时间就为 $t=n*u/(w-v)$ 。
那么对于特定顺序，设人 $i$ 为第 $b[i]$ 个跑的话，则花费时间为 $T=\sum\limits_{i=1}^{n}n*u/(c[i]-(b[i]-1)*d[i]-v);$
因为每个人位于第几轮是等概率的，所以 $ans=\sum\limits_{i=1}^{n}\frac{\sum\limits_{j=1}^{n}n*u/(c[i]-(j-1)*d[i]-v)}{n}$
代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=5e5+7;
const int mod=1e9+7;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
double c[MX],d[MX];
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  int n;
  cin>>n;
  double v,u;
  cin>>v>>u;
  rep(i,1,n)cin>>c[i];
  rep(i,1,n)cin>>d[i];
  double ans=0;
  rep(i,1,n)
  {
      rep(j,1,n)
      {
          ans+=(n*u)/(c[i]-(j-1)*d[i]-v);
      }
  }
  cout<<fixed<<setprecision(3)<<ans/n<<endl;


}

C题题解：
老师能追上小Q有两种情况。
(1)是老师和小Q去教务处的路径有相同的节点（除了根节点1），则有何老师如果到教务处的时间小于等于小Q到的时间就肯定可以。
(2)是老师与小Q的公共祖先只有根节点，则何老师到达根节点后要多走一步才能到达小Q的路径上，所以此时有何老师如果到教务处的时间小于小Q到的时间就肯定可以
要计算到根节点需要多上时间只需要记录一下各个节点的深度即可。
但还有SK到小Q也要花时间
这时候我们可以用lca求得他们的最近公共祖先，设 $dep[i]$ 为节点 $i$ 的深度，则显然，若其公共祖先为他们两个其一，则花费的时间有 $|dep[B]-dep[C]|$ ,否则有 $dep[B]+dep[C]-2*dep[f]$ ,f为BC的最近公共祖先jied画个图就很清晰的了。
BC最近公共祖先为他们两者其一
BC公共祖先为另一节点f
lca求的复杂度是 $O(logn)$ ，所以整题复杂度为 $O(T*q*logn)$
代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=1e5+7;
const int mod=1e9+7;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
vector<int>G[N];
int siz[N], son[N], dep[N], top[N], fa[N];
namespace LCA {
  void dfs1(int u, int f) {
    siz[u] = 1, son[u] = -1, fa[u] = f;
    for (int v : G[u]) if (v != f) {
      dep[v] = dep[u] + 1;
      dfs1(v, u);
      siz[u] += siz[v];
      if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
    }
  }
  void dfs2(int u, int t) {
    top[u] = t;
    if (son[u] != -1) dfs2(son[u], t);
    for (int v : G[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
  }
  int lca(int u, int v) {
    while (1) {
      if (top[u] == top[v]) return dep[u] > dep[v] ? v : u;
      if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
      else v = fa[top[v]];
    }
  }
  int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
}
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  int T;
  cin>>T;
  while(T--)
  {
      memset(siz,0,sizeof siz);
      memset(son,0,sizeof son);
      memset(dep,0,sizeof dep);
      memset(top,0,sizeof top);
      memset(fa,0,sizeof fa);
      int n,q;
      cin>>n>>q;
      rep(i,1,n)G[i].clear();
      rep(i,1,n-1)
      {
          int x,y;
          cin>>x>>y;
          G[x].push_back(y);
          G[y].push_back(x);
      }
      LCA::dfs1(1,0);
      LCA::dfs2(1,1);
      while(q--)
      {
          int A,B,C;
          cin>>A>>B>>C;
          int t1,t2;
          t2=dep[A];
          int ft=LCA::lca(B,C);
          //cout<<ft<<endl;
          int t3;
          if(ft==B||ft==C)t3=fabs(dep[B]-dep[C]);
          else {
            t3=dep[B]+dep[C]-2*dep[ft];
          }
          t1=dep[C]+t3;
          int f=LCA::lca(A,C);
          if(t1>=t2&&f!=1)cout<<"YES"<<endl;
          else if(t1>t2)cout<<"YES"<<endl;
          else cout<<"NO"<<endl;
      }

  }


}

E题题解：
想想猜测只包含4和7的数字在1e11以内并不多，实际上也是如此，只有几百个，直接先存下来然后排个序，然后从小到大遍历一下就好了。
存于 $cnt$ ，则数字落在 $[cnt[i],cnt[i+1]-1]$ 的范围上产生的贡献为 $cnt[i]$ ，直接扫过去就可以啦。
代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=5e5+7;
const int mod=1e9+7;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
ll a[MX],pre[MX];
vector<ll>cnt;
int main()
{
  ios::sync_with_stdio(0),cin.tie(0);
  set<ll>mp;
  mp.insert(4);
  mp.insert(7);
  ll ans=1e9;
  cnt.push_back(0);
  while(1)
  {
      auto it=mp.begin();
      if(*it>10*ans)break;
      cnt.push_back(*it);
      ll a=1ll*(*it)*10+4;
      ll b=1ll*(*it)*10+7;
      mp.erase(it);
      mp.insert(a);
      mp.insert(b);
  }
  ll sum=0;
  ll l,r;
  cin>>l>>r;
  for(int i=1;i<cnt.size();i++)
  {
     ll rt=min(r,cnt[i]);
     ll lt=max(l,cnt[i-1]+1);
     if(rt>=lt)sum+=cnt[i]*(rt-lt+1);
  }
  cout<<sum<<endl;
}