gym105182

https://codeforces.com/gym/105182

A

观察性质，然后疑似是用 BIT 什么维护一下就好了。

B

队友写的。

C

$\sum i^2 = \frac{n(n+1)(2n+1)}{6}$

D

一段 0 再一段 1。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e9;
void solve() {
  int n;
  cin >> n;

  vector<int> x(n), y(n);
  // 0-white
  // 1-black
  int max_white = 0;
  int max_black = 0;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    int white = x[i] - y[i];
    int black = y[i];

    max_white = max(max_white, white);
    max_black = max(max_black, black);
  }

  string ans = string(max_black, '1') + string(max_white, '0');

  cout << (int)ans.size() << "\n";
  cout << ans << "\n";

  for (int i = 0; i < n; i++) {
    int black = y[i];
    cout << max_black - black << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1;
  while (t--) {
    solve();
  }
}

E

队友写的

F

队友写的。

启发式合并，自下向上，依次考虑每个点是否要合并到当前点 $u$。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,a[N],f[N],g[N],ft[N]; double p[N]; vector<int>v[N];
struct node{
  long double a,b;
};
bool operator < (node A,node B){
  return A.a/(1-A.b)<B.a/(1-B.b);
}
priority_queue<node>F[N];
int merge(int a,int b){
  if(F[a].size()<F[b].size()) swap(a,b);
  while(F[b].size()) F[a].push(F[b].top()),F[b].pop();
  return a;
}
void dfs(int u){
  node c; c.a=a[u]*p[u],c.b=p[u]; ft[u]=u;
  for(int x:v[u]){
    dfs(x);
    ft[u]=merge(ft[x],ft[u]);
  }
  while(F[ft[u]].size()&&(c<F[ft[u]].top())){
    c.a=c.a+F[ft[u]].top().a*c.b;
    c.b=c.b*F[ft[u]].top().b;
    F[ft[u]].pop();
  }
  F[ft[u]].push(c);
  
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
  for(int i=2;i<=n;i++) scanf("%d",&f[i]),v[f[i]].push_back(i);
  dfs(1);
  node c; c.a=0,c.b=1;
  while(F[ft[1]].size()){
    c.a=c.a+F[ft[1]].top().a*c.b;
    c.b=c.b*F[ft[1]].top().b;
    F[ft[1]].pop();
  }
  printf("%.12Lf\n",c.a);
}

G

考虑一个最基础的 $dp$，就是一个子树 $u$ 选择一条链作为 $u$ 能直接跳到的点。那个点的字符串表示放入 cache 的，然后字典序比他小的直接计算 $\sum dep_i \times cnt_i$，比他大的直接计算 $\sum dp_i$。

#include <bits/stdc++.h>
using namespace std;

int n, a, b;
const int N = 262144;
long long C[N];
vector<int> g[N];
long long dep[N];
long long sum[N];
long long dp[N];

void dfs(int u) {
  sum[u] = dep[u] * C[u];
  for (auto v : g[u]) {
    dep[v] = dep[u] + a;
    dfs(v);
    sum[u] += sum[v];
  }
}

template<class T> void cmin(T &x, const T&y) {
  if (x > y) x = y;
}
namespace noya {
#define int long long
int rt[N], ls[N << 5], rs[N << 5], id[N << 5], cnt = 0;
struct Line {
  int k, b; inline int val(int x) { return k * x + b; }
} s[N << 5];
int line_cnt = 0;
int add_line(int k, int b) {
  line_cnt++;
  s[line_cnt] = {k, b};
  return line_cnt;
}
int add_line(Line a, int b) {
  line_cnt++;
  s[line_cnt] = {a.k, a.b + b};
  return line_cnt;
}
void ins(int &p, int l, int r, int num) {
  if(!p) { p = ++cnt; id[p] = num; return; }
  int mid = l + r >> 1, &x = num, &y = id[p];
  int midx = s[x].val(mid), midy = s[y].val(mid);
  if(midx < midy) { x ^= y ^= x ^= y; }
  int lx = s[x].val(l), ly = s[y].val(l);
  int rx = s[x].val(r), ry = s[y].val(r);
  if(lx >= ly && rx >= ry) return;
  if(lx < ly) ins(ls[p], l, mid, num);
  else ins(rs[p], mid + 1, r, num);
}
int qry(int p, int l, int r, int pos) {
  if(!p) return 1e18;
  if(l == r) { return s[id[p]].val(pos); }
  int mid = l + r >> 1, ans = s[id[p]].val(pos);
  if(pos <= mid) { cmin(ans, qry(ls[p], l, mid, pos)); }
  else { cmin(ans, qry(rs[p], mid + 1, r, pos)); }
  return ans;
}
#undef int
}

using namespace noya;
vector<long long> lines[N];
long long add_tag[N];

const int L = 2e9;
void dfs2(int u) {
  for (auto v : g[u]) {
    dfs2(v);
  }
  auto merge = [&](int u, int v, long long tag) {
    // cout << u << " " << v << " " << tag << endl;
    if (lines[u].size() > lines[v].size()) {
      long long add = add_tag[v] + tag - add_tag[u];
      for (auto id : lines[v]) {
        int cur = add_line(s[id], add);
        ins(rt[u], 0, L, cur);
        lines[u].push_back(cur);
      }
    } else {
      long long add = add_tag[u] - tag - add_tag[v];
      for (auto id : lines[u]) {
        int cur = add_line(s[id], add);
        ins(rt[v], 0, L, cur);
        lines[v].push_back(cur);
      }
      swap(rt[u], rt[v]);
      swap(lines[u], lines[v]);
      add_tag[u] = tag + add_tag[v];
    }
  };
  long long cur = 0;
  for (auto v : g[u]) cur += dp[v];
  {
    int id = add_line(C[u], cur);
    lines[u].push_back(id);
    ins(rt[u], 0, L, id);
  }

  long long prefix = 0;
  for (auto v : g[u]) {
    cur -= dp[v];
    merge(u, v, cur + prefix + C[u] * dep[u]);
    prefix += sum[v];
  }

  dp[u] = min(sum[u], qry(rt[u], 0, L, dep[u] + b) + add_tag[u]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> a >> b;

  for (int i = 1; i <= n; i++) {
    int c, k;
    cin >> c >> k;
    C[i] = c;
    for (int j = 0; j < k; j++) {
      int x;
      cin >> x;
      g[i].push_back(x);
    }
  }

  dfs(1);
  memset(dp, 0x3f, sizeof dp);
  dfs2(1);
  cout << dp[1] << "\n";
  return 0;
}

H

考虑肯定是倒着做。

先考察如果同一时间来，也就是有 $n$ 个相同的 $t_i$，那么这 $n$ 个数字一定要取后缀最大值。

如果 $t_i$ 不相同，那么就是可以弹出第一个数字。

那么就直接做完了。

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> t(n), a(n);

  for (int i = 0; i < n; i++) {
    cin >> t[i];
  }

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  priority_queue<int> q;

  long long ans = 0;

  for (int i = n - 1; i >= 0; i--) {
    if (!q.empty()) {
      int c = t[i + 1] - t[i];
      while (!q.empty() && c) {
        ans += q.top();
        c--;
        q.pop();
      }
    }
    int u = a[i];
    if (!q.empty()) {
      u = max(u, q.top());
    }
    q.emplace(u);
  }

  int c = t[0];
  while (!q.empty() && c) {
    ans += q.top();
    c--;
    q.pop();
  }

  if (!q.empty()) {
    cout << -1 << "\n";
  } else {
    cout << ans << "\n";
  }
}

I

直接模拟这个过程就好。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e9;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  long long s = 0;
  priority_queue<long long, vector<long long>, greater<long long>> q;
  long long cur = 0;
  for (int i = 0; i < n; i++) {
    q.emplace(a[i]);
    s += a[i];
    cur = max(cur, a[i]);
  }
  long long t = (s + 1) / 2;
  int cnt = 0;
  while (true) {
    if (cur >= t) {
      if (cnt % 2 == 0) {
        cout << "YES\n";
      } else {
        cout << "NO\n";
      }
      return;
    }
    long long u = q.top();
    q.pop();
    long long v = q.top();
    q.pop();
    cnt += 1;
    q.emplace(u + v);
    cur = max(cur, u + v);
  }

  assert(0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
}

J

诈骗题。

$val(S1) - val(S2) = \sum_{i \in S1,1 \leq j \leq n} dist(i, j) - \sum_{i \in S2, 1 \leq j \leq n} dist(i, j)$

考虑维护 $f(i) = \sum_{1 \leq j \leq n} dist(i, j)$，贪心即可。

K

诈骗题，$n-1$ 个数字做乘法其实等价于单点乘法。

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e9;
void solve() {
  int n;
  cin >> n;
  vector<long long> a(n);

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int c = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == a[0]) c++;
  }

  if (c == n) {
    cout << n << "\n";
  } else {
    cout << n - 1 << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}