VP 记录 - 2021 ICPC Asia Taiwan Online Programming Contest

比赛链接

题目概览

题号	标题	做法
A	Olympic Ranking	模拟
B	Aliquot Sum	质因数分解 打表
C	A Sorting Problem	逆序对
D	Drunk Passenger	概率
E	Eatcoin	二分
F	Flip	线段树
G	Garden Park	DP
H	A Hard Problem	网络流
I	ICPC Kingdom
J	JavaScript	签到

---

官方题解

Show backup

---

---

Announcements

1. Problem I. ICPC Kingdom

   Additional restrictions:

   1 <= x_i <= m 1 <= b_i <= m

A - Olympic Ranking

代码参考

Show code

A.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define N 320
int n;
struct node {
  int b[3];
  string country;
} a[N];
bool operator<(node x, node y) {
  return x.b[0] > y.b[0] || (x.b[0] == y.b[0] && x.b[1] > y.b[1]) ||
         (x.b[0] == y.b[0] && x.b[1] == y.b[1] && x.b[2] > y.b[2]);
}
string s;
int main() {
  cin >> n;
  getline(cin, s);
  for (int i = 1; i <= n; ++i) {
    int cnt = 0;
    int len = 0;
    getline(cin, s);
    a[i].b[0] = a[i].b[1] = a[i].b[2] = 0;
    while (cnt != 3) {
      if (s[len] == ' ') {
        ++cnt;
      } else a[i].b[cnt] = a[i].b[cnt] * 10 + s[len] - '0';
      string::iterator it = s.begin();
      s.erase(it);
    }
    a[i].country = s;
  }
  sort(a + 1, a + n + 1);
  cout << a[1].country;
  return 0;
}

B - Aliquot Sum

代码参考

Show code

B.cppview raw

#include <bits/stdc++.h>
using namespace std;
using u32 = std::uint32_t;
#define for_(i, l, r, vars...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vars; i <= i##end; ++i)
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
const u32 OFFSET = 5;
const u32 N = 1e6 + OFFSET;
int divsum[N];
const auto STATIC__ = []() {
  divsum[1] = 0;
  for_(i, 2, N - OFFSET) {
    for (int j = 1, sqn = sqrt(i); j <= sqn; ++j) {
      if (i % j == 0) {
        divsum[i] += j;
        if (j == i / j) continue;
        if (i % (i / j) == 0) divsum[i] += i / j;
      }
    }
    divsum[i] -= i;
  }
  return 0;
}();
auto solve(int t_) -> void {
  read_var_(int, n);
  for_(i, 1, n, x) {
    cin >> x;
    cout << (x == divsum[x] ? "perfect" :
             x > divsum[x]  ? "deficient" :
                              "abundant")
         << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve(0);
  return 0;
}

C - A Sorting Problem

代码参考

Show code

C.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ll long long
int n, t[N], a[N];
ll ans = 0;
void add(int x) {
  for (; x <= n; x += x & (-x)) t[x]++;
}
int query(int x) {
  int y = 0;
  for (; x; x -= x & (-x)) y += t[x];
  return y;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ans += 1ll * (i - 1 - query(a[i]));
    add(a[i]);
  }
  cout << ans;
  return 0;
}

D - Drunk Passenger

代码参考

Show code

D.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
auto solve(int t_) -> void {
  read_var_(int, n);
  cout << fixed << setprecision(12) << 1. * n / (2 * (n - 1)) << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve(0);
  return 0;
}

E - Eatcoin

代码参考

Show code

E.pyview raw

def f(n, p, q):
    return n * n * (n + 1)**2 * (2 * n * n + 2 * n - 1)//12 * q - p * n


def get_root(val, p, q):
    l, r = 1, 114514 * 19 ** 19 + 810
    ans = r
    while l <= r:
        mid = (l + r)//2
        res = f(mid, p, q)
        if res == val:
            ans = mid
            break
        elif res > val:
            ans, r = mid, mid - 1
        else:
            l = mid + 1
    return ans


p, q = map(int, input().split())
r0, r1 = get_root(0, p, q), get_root(10 ** 99, p, q)
if r0 > 1:
    print(p + max([-f(i, p, q)for i in range(1, r0)]))
else:
    print(p)
print(r1)

F - Flip

代码参考

Show code

F.cppview raw

#include <bits/stdc++.h>
#define int long long
#define inc(i) (++(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
using ll = long long;
using namespace std;
const int N = 200000 + 7;
int n, q;
int A[N];
struct Node {
  int l, r, ll, rl, w, flag, Sz;
  Node(int _l = 0,
       int _r = 0,
       int _ll = 0,
       int _rl = 0,
       int _w = 0,
       int _flag = 0,
       int _Sz = 0)
    : l(_l), r(_r), ll(_ll), rl(_rl), w(_w), flag(_flag), Sz(_Sz) {}
  friend Node operator+(const Node &A, const Node &B) {
    if (A.Sz == 0) return B;
    if (B.Sz == 0) return A;
    Node C;
    C.w = A.w + B.w, C.l = A.l, C.r = B.r;
    C.ll = A.ll, C.rl = B.rl;
    C.Sz = A.Sz + B.Sz;
    if (A.r == B.l ^ 1) {
      C.w += A.rl * B.ll;
      if (A.rl == A.Sz) C.ll = B.ll + A.Sz;
      if (B.ll == B.Sz) C.rl = A.rl + B.Sz;
    }
    return C;
  }
} T[N << 2];
void Build(int x, int l, int r) {
  if (l == r) {
    T[x] = Node(A[l], A[r], 1, 1, 1, 0, 1);
    return;
  }
  int Mid = (l + r) >> 1;
  Build(x << 1, l, Mid), Build(x << 1 | 1, Mid + 1, r);
  T[x] = T[x << 1] + T[x << 1 | 1];
}
void Pushdown(int x) {
  if (T[x].flag) {
    T[x].flag = 0;
    T[x << 1].l ^= 1, T[x << 1].r ^= 1, T[x << 1].flag ^= 1;
    T[x << 1 | 1].l ^= 1, T[x << 1 | 1].r ^= 1, T[x << 1 | 1].flag ^= 1;
  }
}
void Update(int x, int l, int r, int L, int R) {
  if (L <= l && R >= r) {
    T[x].l ^= 1, T[x].r ^= 1, T[x].flag ^= 1;
    return;
  }
  Pushdown(x);
  int Mid = (l + r) >> 1;
  if (Mid >= L) Update(x << 1, l, Mid, L, R);
  if (Mid < R) Update(x << 1 | 1, Mid + 1, r, L, R);
  T[x] = T[x << 1] + T[x << 1 | 1];
}
Node Query(int x, int l, int r, int L, int R) {
  if (L <= l && R >= r) return T[x];
  Pushdown(x);
  int Mid = (l + r) >> 1;
  Node Ans;
  if (Mid >= L) Ans = Query(x << 1, l, Mid, L, R);
  if (Mid < R) Ans = Ans + Query(x << 1 | 1, Mid + 1, r, L, R);
  return Ans;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> q;
  Rep(i, 1, n) cin >> A[i];
  Build(1, 1, n);
  int opt, l, r;
  Rep(i, 1, q) {
    cin >> opt >> l >> r;
    if (opt == 1) Update(1, 1, n, l, r);
    else cout << Query(1, 1, n, l, r).w << '\n';
  }
  return 0;
}

G - Garden Park

代码参考

Show code

G.cppview raw

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ll long long
int n, num, h[N];
ll ans, f[N][2], g[N][2];
struct Edge {
  int to, nxt, z;
} e[N << 1];
void ins(int x, int y, int z) {
  e[++num].to = y;
  e[num].nxt = h[x];
  e[num].z = z;
  h[x] = num;
  e[++num].to = x;
  e[num].nxt = h[y];
  e[num].z = z;
  h[y] = num;
}
struct node {
  int x;
  ll f1, f2;
} a[N];
bool operator<(node x, node y) { return x.x < y.x; }
void dfs(int x, int fa, int c) {
  f[x][0] = 1ll;
  f[x][1] = 1ll;
  int now = 0;
  for (int i = h[x]; i; i = e[i].nxt) {
    int y = e[i].to;
    if (y == fa) continue;
    dfs(y, x, e[i].z);
    ++now;
    if (e[i].z > c) f[x][0] += f[y][0];
    if (e[i].z < c) f[x][1] += f[y][1];
  }
  if (now) {
    now = 0;
    for (int i = h[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (y == fa) continue;
      a[++now] = (node){e[i].z, f[y][0], f[y][1]};
    }
    sort(a + 1, a + now + 1);
    int m = 0;
    for (int i = 1; i <= now; ++i) {
      if (i != 1 && a[i].x == a[i - 1].x) {
        g[m][0] += a[i].f1;
        g[m][1] += a[i].f2;
      } else {
        g[++m][0] = a[i].f1;
        g[m][1] = a[i].f2;
      }
    }
    ll res = 0;
    for (int i = 1; i <= m; ++i) { res += g[i][0] + g[i][1]; }
    for (int i = 2; i <= m; ++i) { g[i][1] += g[i - 1][1]; }
    for (int i = 2; i <= m; ++i) { res += g[i - 1][1] * g[i][0]; }
    ans += res;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    ins(x, y, z);
  }
  dfs(1, 0, 0);
  printf("%lld\n", ans);
  return 0;
}

H - A Hard Problem

代码参考

Show code

I - ICPC Kingdom

代码参考

Show code

J - JavaScript

代码参考

Show code

J.cppview raw

#include <bits/stdc++.h>
using namespace std;
int main() {
  string s, t;
  cin >> s >> t;
  if (any_of(s.begin(), s.end(), [](const char &ch) { return !isdigit(ch); }) ||
      any_of(t.begin(), t.end(), [](const char &ch) { return !isdigit(ch); })) {
    cout << "NaN\n";
    return 0;
  }
  stringstream ss;
  int a, b;
  ss << s << ' ' << t;
  ss >> a >> b;
  cout << a - b;
  return 0;
}