牛客算法周周练1

比赛地址：

https://ac.nowcoder.com/acm/contest/5086#question

A Maximize The Beautiful Value

基本思路：

我们只要注意数组是非递增排列的,然后我们观察就可以发现,我们每多往前移动一位就一定是亏的;然后我们将第i位的元素往前移动k位,其实就是将[i - k,i - 1]范围的数再加一遍，然后将第i位的元素a[i]减k次,所以我们将每个能移的都往前移k个位置,取一下最少的减少量就能算出答案,我们预处理一下前缀和就能在O(n)范围内解决问题。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
int n,k,a[maxn],sum[maxn];
signed main() {
  IO;
  int t;
  cin >> t;
  while (t-- > 0) {
    cin >> n >> k;
    int ans = 0;
    rep(i, 1, n){
      cin >> a[i];
      ans += a[i] * i;
    }
    sum[0] = 0;
    rep(i, 1, n) sum[i] = sum[i - 1] + a[i];
    int mx = -INF; // 初始设小一点;
    rep(i,k+1,n){
      int l = i - k,r = i - 1;
      int now = (sum[r] - sum[l - 1]) - a[i] * k;
      mx = max(mx,now);
    }
    //cout << mx << endl;
    cout << ans + mx << endl;
  }
  return 0;
}

B 身体训练

基本思路：

感觉就是个小学数学题增加了一点点难度,因为每种顺序的概率完全相等,所以我们枚举每位士兵的n种顺序,将从这样顺序时当前士兵的最大速度和跑到最前面的时间计算出来,然后就能算出时间总和,将这个总时间除以n就是期望时间了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int signed long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1010;
int n;
double v,u;
double c[maxn],d[maxn];
signed main() {
  cin >> n;
  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){
      double now_c = c[i] - ((double)(j - 1) * d[i]); // 这种顺序时的最大速度;
      ans += ((double)n * u / (now_c - v)); //这种顺序时跑到最前的时间;
    }
  }
  ans /= (double)n;
  printf("%.3lf\n",ans);
  return 0;
}

C Borrow Classroom

基本思路：

基本上看一眼就知道是个lca和树上距离乱搞的裸题了,就是这个老师到底是怎么拦截的实在是令人难以理解,导致我WA傻了也没对(我以为老师会到处围追堵截,还能站一个地方不动QAQ);
其实拦截就两种情况:1.老师在根节点处等同学,2.老师和同学要刚好碰到;

首先 dist(1, C) + dist(B,C) 和 dist(1,A) 来比我们应该能想到;
如果 dist(1, C) + dist(B,C) > dist(1,A) 那么老师一定能拦截成功;
如果 dist(1, C) + dist(B,C) < dist(1,A) 那么老师一定不能拦截成功;
而当 dist(1, C) + dist(B,C) == dist(1,A) 时,如果lca(A,C) == 1 的话由于小Q手速快,所以老师抓不到,否则就抓的到。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int signed long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
int n,q,A,B,C;
struct edge {
    int next, v;
}edges[maxn*2];
int cnt;
int head[maxn];
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0;
}
void add_edge(int u,int v) {
  edges[cnt].next = head[u];
  edges[cnt].v = v;
  head[u] = cnt++;
}
int dep[maxn];
int f[maxn][21];
void dfs(int u,int fa) {
  dep[u] = dep[fa] + 1;
  for (int i = 0; i <= 19; i++)
    f[u][i + 1] = f[f[u][i]][i];
  for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa)
      continue;
    f[v][0] = u;
    dfs(v, u);
  }
}
int lca(int x,int y) {
  if (dep[x] < dep[y])
    swap(x, y);
  for (int i = 20; i >= 0; i--) {
    if (dep[f[x][i]] >= dep[y])
      x = f[x][i];
    if (x == y)
      return x;
  }
  for (int i = 20; i >= 0; i--) {
    if (f[x][i] != f[y][i]) {
      x = f[x][i];
      y = f[y][i];
    }
  }
  return f[x][0];
}
int dist(int a,int b) {
  return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
signed main() {
  int t;
  cin >> t;
  while (t-- > 0) {
    n = read(), q = read();
    init();
    mset(dep,0);
    mset(f,0);
    rep(i, 1, n - 1) {
      int u, v;
      u = read(), v = read();
      add_edge(u, v);
      add_edge(v, u);
    }
    dfs(1, 0);
    while (q-- > 0) {
      A = read(), B = read(), C = read();
      int k1 = dist(1, C) + dist(B,C);
      int k2 = dist(1,A);
      if (k2 < k1) cout << "YES" << endl;
      else if(k2 > k1) cout << "NO" << endl;
      else{
        if(lca(C,A) == 1) cout << "NO" <<endl;
        else cout << "YES" <<endl;
      }
    }
  }
  return 0;
}

E 幸运数字Ⅱ

基本思路：

这题好像和上场Atcode的D有点像,因为满足这种条件的数不会很多,所以我们直接dfs把这些数全部打出来存在数组里面,然后对于[l,r]如果我们暴力二分查找的话会TLE,但是我们很容易发现规律在l,r之间出现的数字被计算的次数其实就是这个数字和之前的出现的数字的差,这一点大家可以在纸上画一下很容易就能看出来,注意在l,r这两个边界上要特殊判断一下,然后我们二分找到l,r在打表数组里对应的位置,再计算就是了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int signed long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
vector<int> vec;
int n,pw[11];
void dfs(int s,int sum) {
  if (s == n) {
    vec.push_back(sum);
    return;
  }
  dfs(s + 1, sum + 4 * pw[s]);
  dfs(s + 1, sum + 7 * pw[s]);
}
signed main() {
  IO;
  pw[0] = 1;
  for(int i = 1; i <= 10 ; i++) pw[i] = pw[i-1] * 10;
  for (n = 1; n <= 10; n++) dfs(0, 0);//打表;
  sort(vec.begin(), vec.end());
  int l,r;
  cin >> l >> r;
  int pos1 = lower_bound(vec.begin(),vec.end(),l) - vec.begin();
  int pos2 = lower_bound(vec.begin(),vec.end(),r) - vec.begin();
  int next = l;// 左边卡一下位置
  int ans = vec[pos1];
  for(int i = pos1 ; i <= pos2 ; i++){
    //cout << vec[i] << endl;
    if(i == pos2) ans += (r - next) * vec[i]; //右边也要卡一下位置;
    else {
      ans += (vec[i] - next) * vec[i];//计算次数就是前后差;
      next = vec[i];
    }
  }
  cout << ans << endl;
  return 0;
}