百度笔试3.28 A卷

#软件开发2023笔面经#

A. 两种颜色R和B，两两组合权值为对应点权乘积，求所有方案之和

#include<bits/stdc++.h>

#define all(x) (x.begin(), x.end())

using vi = std::vector<int>;
using pii = std::pair<int, int>;
using i64 = long long;

const int mod = 1e9 + 7;
int A[1000005];
void solve() {
  int n;
  std::cin >> n;
  std::string s;
  for (int i = 0; i < n; i++) {
    std::cin >> A[i];
  }
  std::cin >> s;
  i64 sum = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'R') {
      sum = (sum + A[i]) % mod;
    }
  }
  i64 ans = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'B') {
      ans = (ans + sum * A[i] % mod) % mod;
    }
  }
  std::cout << ans << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

B. 给一个小于1的正浮点数，有些数字可以删除，求能得到的最大小数是多少，需要删除末尾0

等价于求最大字典序

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define debug(x) std::cerr << "debug:" << x << '\n';

using vi = std::vector<int>;
using pii = std::pair<int, int>;
using i64 = long long;

const int mod = 1e9 + 7;

vi G[22];
void solve() {
  std::string s;
  std::cin >> s;
  int n = s.size();
  for (int i = 2; i < n; i++) {
    G[s[i] - '0'].push_back(i);
    //std::cerr << s[i] - '0' << ' ' << i << ' ' << G[s[i] - '0'].size() << '\n';
  }
  std::string ans = "0.";
  int now = 0;
  for (int i = 9; i >= 1; i--) {
    if (G[i].size()) {
      std::cerr << i << ' ' << G[i].size() << '\n';
      while (true) {
        auto pos = std::lower_bound(all(G[i]), now);
        if (pos == G[i].end()) {
          break;
        }
        debug(*pos + 1);
        ans += char(i + '0');
        now = (*pos) + 1;
      }
    }
  }
  std::cout << ans << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

C. 给一棵树，q个操作，每次把一个子树的值都乘上一个数字，求1到n每个子树乘积末尾0的个数。

dfs序+线段树模板题，开两个线段树一个计算区间2的个数，一个计算区间5的个数。

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define debug(x) std::cerr << "debug:" << x << '\n';

using vi = std::vector<int>;
using pii = std::pair<int, int>;
using i64 = long long;

const int mod = 1e9 + 7;

class SegTree {
  private:
  struct Node {
    int l, r;
    i64 sum, lazy;
  };
  std::vector<Node> t;
  public:
  void push_up(int rt) {
    t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;
  }
  void push_down(int rt) {
    if (t[rt].lazy) {
      t[rt << 1].sum += 1LL * (t[rt << 1].r - t[rt << 1].l + 1) * t[rt].lazy;
      t[rt << 1 | 1].sum += 1LL * (t[rt << 1 | 1].r - t[rt << 1 | 1].l + 1) * t[rt].lazy;
      t[rt << 1].lazy += t[rt].lazy;
      t[rt << 1 | 1].lazy += t[rt].lazy;
      t[rt].lazy = 0;
    }
  }
  void build(int rt, int l, int r) {
    t[rt].l = l, t[rt].r = r;
    t[rt].sum = 0;
    if (l == r) {
      return ;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    push_up(rt);
  }
  SegTree(int n) {
    t.resize(n * 4 + 1);
    build(1, 1, n);
  }
  void update(int rt, int ql, int qr, int val) {
    if (ql <= t[rt].l and qr >= t[rt].r) {
      t[rt].sum += 1LL * (t[rt].r - t[rt].l + 1) * val;
      t[rt].lazy += val;
      return ;
    }
    push_down(rt);
    int mid = (t[rt].l + t[rt].r) >> 1;
    if (ql <= mid) {
      update(rt << 1, ql, qr, val);
    }
    if (qr > mid) {
      update(rt << 1 | 1, ql, qr, val);
    }
    push_up(rt);
  }
  i64 query(int rt, int ql, int qr) {
    if (ql <= t[rt].l and qr >= t[rt].r) {
      return t[rt].sum;
    }
    push_down(rt);
    int mid = (t[rt].l + t[rt].r) >> 1;
    i64 res = 0;
    if (ql <= mid) {
      res += query(rt << 1, ql, qr);
    }
    if (qr > mid) {
      res += query(rt << 1 | 1, ql, qr);
    }
    return res;
  }
};

int A[100005], L[100005], R[100005], tot;
vi G[100005];

void dfs(int u, int par) {
  L[u] = ++tot;
  for (auto v : G[u]) {
    if (v == par) {
      continue;
    }
    dfs(v, u);
  }
  R[u] = tot;
}
void solve() {
  int n;
  std::cin >> n;
  SegTree T2(n), T5(n);
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i];
  }  
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  dfs(1, 0);
  auto change = [&](int l, int r, int x) {
    int cnt2 = 0, cnt5 = 0;
    while (x % 2 == 0) {
      x /= 2;
      ++cnt2;
    }
    while (x % 5 == 0) {
      x /= 5;
      ++cnt5;
    }
    T2.update(1, l, r, cnt2);
    T5.update(1, l, r, cnt5);
  };
  for (int i = 1; i <= n; i++) {
    change(L[i], L[i], A[i]);
  }
  for (int i = 1; i <= n; i++) {
    //std::cerr << "dbeug:" << i << ' ' << L[i] << ' ' << R[i] << ' ' << T2.query(1, L[i], R[i]) << ' ' << T5.query(1, L[i], R[i]) << '\n';
    //std::cout << std::min(T2.query(1, L[i], R[i]), T5.query(1, L[i], R[i])) << " \n"[i == n];
  }

  int q;
  std::cin >> q;
  while (q--) {
    int x, y;
    std::cin >> x >> y;
    change(L[x], R[x], y);
  }
  for (int i = 1; i <= n; i++) {
    //std::cerr << "dbeug:" << i << ' ' << L[i] << ' ' << R[i] << ' ' << T2.query(1, L[i], R[i]) << ' ' << T5.query(1, L[i], R[i]) << '\n';
    std::cout << std::min(T2.query(1, L[i], R[i]), T5.query(1, L[i], R[i])) << " \n"[i == n];
  }
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

/*
5
1 2 6 3 1
1 2
1 3
2 4
2 5
1
3 5

5
1 1 1 1 1
1 2
1 3
2 4
2 5
1 
1 10
*/