技术教程 编程教程 2020 Multi-University Training Contest 1 部分题解 正文

2020 Multi-University Training Contest 1 部分题解

2023-03-15,,

目录
Cookies
Distinct Sub-palindromes
Fibonacci Sum
Finding a MEX
Leading Robots
Math is Simple
Minimum Index
Mow

Cookies

先简单二分出最后查的是哪个标号。

然后发现这个可以快速处理出一段区间的答案，分段打表即可。

注意代码长度限制不要爆了我就白打了 10min

Code

ll n, k, a[N];

ll S[4001] = { ... };

int m;

inline ll cal(ll x) {

  for (ri i = 1; i <= m && x >= k; ++i) x -= x / a[i];

  return x;

}

inline ll Cal(ll l, ll r) {

  static int divv[Bas + 5], len;

  len = r - l;

  for (ri i = 0; i <= len; ++i) divv[i] = 1;

  for (ri i = 2; (ll) i * i <= r; ++i) for (ri j = max((ll) i, (l + i - 1) / i) * i - l; j <= len; j += i)

  divv[j] = i;

  ll res = 0;

  for (ri i = 0; i <= len; ++i) res += divv[i];

  return res;

}

namespace Biao {

  inline void get_Biao() {

    cout << "ll S[] = { 0";

    ll l = 1, r = Bas;

    for (ri i = 1; i <= 4000; ++i, l += Bas, r += Bas) cout << ", " << Cal(l, r);

    cout << " };\n";

    exit(0);

  }

}

int main() {

  //Biao:: get_Biao();

  for (ri i = 1; i <= 4000; ++i) S[i] += S[i - 1];

  n = readl(), m = read(), k = readl();

  for (ri i = 1; i <= m; ++i) a[i] = readl();

  if (cal(n) < k) { puts("-1"); continue; }

  ll L = 0, R = n, p = n;

  while (L <= R) {

    ll mid = (L + R) >> 1;

    if (cal(mid) >= k) p = mid, R = mid - 1;

    else L = mid + 1;

  }

  if (cal(n) < k) {

    cout << -1 << '\n';

    continue;

  }

  if (p % Bas <= Bas / 2) {

    ll res = Cal(p / Bas * Bas + 1, p);

    res += S[p / Bas];

    cout << res << '\n';

  }

  else {

    ll res = -Cal(p + 1, (p / Bas + 1) * Bas);

    res += S[p / Bas + 1];

    cout << res << '\n';

  }

  return 0;

}

Distinct Sub-palindromes

签到，发现长度 \(>3\) 只能形如 \(abcabcabc...\)，算下 \(3\) 的答案即可。

Code

int main() {

  ans[1] = 26, ans[2] = 26 * 26, ans[3] = 26 * 25 * 24 + 26 * 25 + 26 * 25 + 26 * 25 + 26;

  for (ri tt = read(); tt; --tt) {

    int n = read();

    if (n <= 3) cout << ans[n] << '\n';

    else cout << 26 * 25 * 24 << '\n';

  }

  return 0;

}

Fibonacci Sum

等比数列求和，要特判 \(1\)。

场上过了的赛后被卡常了...卡了一波终于过了。

Code

int main() {

  A = mul(iv2, add(1, bas)), B = mul(iv2, dec(1, bas));

  init(100000);

  for (ri tt = read(), tp = mul(Inv(A), B); tt; --tt) {

    n = readl(), c = readl() % (mod - 1), k = read();

    int res = 0, n1 = (n + 1) % (mod - 1), n2 = (n + 1) % mod;

    int mt = ksm(tp, c), Mt = ksm(ksm(A, c), k);

    for (ri t, i = 0; i <= k; ++i) {

      if (Mt == 1) t = n2;

      else t = mul(dec(ksm(Mt, n1), 1), Inv(dec(Mt, 1)));

      (i & 1 ? Dec : Add) (res, mul(t, C(k, i)));

      Mul(Mt, mt);

    }

    cout << mul(res, pw[k]) << '\n';

  }

  return 0;

}

Finding a MEX

写了个根号分治套 \(\text{set}\) 居然过了是我没想到的，不过由于实现不好会被重边卡，调了一年...

实际上可以用链表做到优美的 \(O(n\sqrt n)\)比赛的时候假胡了一下没实现，如果不行不要喷我

Code

inline void ins(int x, int v) {

  if (v > n) return;

  ++cnt[x][v];

  if (cnt[x][v] > 1) return;

  set <pii> :: iterator it = sg[x].upper_bound(pii(v, n));

  --it;

  pii t = *it;

  sg[x].erase(it);

  if (t.fi < v) sg[x].insert(pii(t.fi, v - 1));

  if (v < t.se) sg[x].insert(pii(v + 1, t.se));

}

inline void del(int x, int v) {

  if (v > n) return;

  --cnt[x][v];

  if (cnt[x][v]) return;

  set <pii> :: iterator it = sg[x].upper_bound(pii(v, n));

  int l = v, r = v;

  if (it != sg[x].begin()) {

    --it;

    if (it -> se == v - 1) l = it -> fi;

    ++it;

  }

  if (it != sg[x].end()) {

    if (it -> fi == v + 1) r = it -> se;

  }

  sg[x].erase(pii(l, v - 1));

  sg[x].erase(pii(v + 1, r));

  sg[x].insert(pii(l, r));

}

inline void upd(int x, int v) {

  for (ri i = 1; i <= tot; ++i) if (vs[i][x]) {

    del(i, a[x]);

    ins(i, v);

  }

  a[x] = v;

}

inline int qry(int x) {

  static bool vs[N];

  if (id[x]) {

    x = id[x];

    return sg[x].begin() -> fi;

  }

  else {

    for (ri i = 0; i <= blo; ++i) vs[i] = 0;

    for (ri i = 0; i < e[x].size(); ++i) {

      int v = a[e[x][i]];

      if (v <= blo) vs[v] = 1;

    }

    for (ri i = 0; i <= blo; ++i) if (!vs[i]) return i;

  }

}

int main() {

  n = read(), m = read();

  for (ri i = 1; i <= n; ++i) a[i] = read(), e[i].clear(), id[i] = 0;

  for (ri i = 1, u, v; i <= m; ++i) {

    u = read(), v = read();

    e[u].pb(v), e[v].pb(u);

  }

  tot = 0;

  int mx = 0;

  for (ri i = 1; i <= n; ++i) mx = max(mx, (int) e[i].size());

  for (ri i = 1; i <= n; ++i) {

    sort(e[i].begin(), e[i].end());

    e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());

    if (e[i].size() >= blo) {

      id[i] = ++tot, sg[tot].clear();

      for (ri j = 0; j <= n; ++j) cnt[tot][j] = vs[tot][j] = 0;

      sg[tot].insert(pii(0, n));

      for (ri j = 0; j < e[i].size(); ++j) {

        int v = a[e[i][j]];

        vs[tot][e[i][j]] = 1;

        ins(tot, v);

      }

    }

  }

  for (ri tt = read(), op, x; tt; --tt) {

    op = read(), x = read();

    if (op == 1) upd(x, read());

    else cout << qry(x) << '\n';

  }

  return 0;

}

Leading Robots

模拟题意，对给出的二次函数维护出最大值的轮廓就行了。

Code

inline db Cross(int x, int y) { return (B[y] - B[x]) / (K[x] - K[y]); }

inline bool chk(int x, int y, int z) {

  db x_0 = Cross(x, y);

  return K[x] * x_0 + B[x] <= K[z] * x_0 + B[z];

}

inline bool cmp(int x, int y) { return B[x] < B[y] || (B[x] == B[y] && K[x] < K[y]); }

int main() {

  scanf("%d", &n);

  for (ri i = 1; i <= n; ++i) scanf("%lf%lf", &B[i], &K[i]), id[i] = i, ban[i] = 0;

  sort(id + 1, id + n + 1, cmp);

  top = 0;

  for (ri i = 1, p; i <= n; ++i) {

    p = id[i];

    if (top) {

      if (make_pair(K[p], B[p]) == make_pair(K[q[top]], B[q[top]])) {

        ban[p] = ban[q[top]] = 1;

        continue;

      }

      while (top > 1 && chk(q[top], q[top - 1], p)) --top;

      if (top == 1 && K[top] >= K[q[top]]) --top;

    }

    q[++top] = p;

  }

  int res = 0;

  for (ri i = 1; i <= top; ++i) if (!ban[q[i]]) ++res;

  cout << res << '\n';

  return 0;

}

Math is Simple

\(\large{\text{Math is not Simple}}\)

设题目要求的是 \(f_n\)，然后 \(g_n=\sum\limits_{1\le a<b\le n,\gcd(a,b)=1,a+b=n}\frac1{ab}\)，将 \(f_n\) 和 \(f_{n-1}\) 做差。

发现 \(f_n=f_{n-1}+g_n-g_{n-1}=\cdots=g_n+\frac12\)

这个 \(g\) 可以莫反算，这题就解决了。

Code

int main() {

  int Lm = 1e8, _Lm = 10000;

  inv[1] = 1;

  for (ri i = 2; i <= Lm; ++i) inv[i] = mul(inv[mod - mod / i * i], mod - mod / i);

  for (ri i = 2; i <= Lm; ++i) Add(inv[i], inv[i - 1]);

  for (ri i = 2; i <= _Lm; ++i) {

    if (!vs[i]) pri[++tot] = i;

    for (ri j = 1; j <= tot && i * pri[j] <= _Lm; ++j) {

      vs[i * pri[j]] = 1;

      if (i == i / pri[j] * pri[j]) break;

    }

  }

  int iv2 = (mod + 1) >> 1;

  n = read();

  int x = n;

  vector <int> divv;

  for (ri i = 1; i <= tot && pri[i] * pri[i] <= x; ++i) if (x == x / pri[i] * pri[i]) {

    divv.pb(pri[i]);

    while (x == x / pri[i] * pri[i]) x /= pri[i];

  }

  if (x ^ 1) divv.pb(x);

  int res = 0, lm = 1 << divv.size();

  vector <int> Divv(lm);

  if (n > 2) for (ri s = 0; s < lm; ++s) {

    Divv[s] = s ? Divv[s - (s & -s)] * divv[__builtin_ctz(s)] : 1;

    int Miu = __builtin_popcount(s) & 1 ? mod - 1 : 1;

    Add(res, mul(mul(Miu, inv[n / Divv[s]]), dec(inv[Divv[s]], inv[Divv[s] - 1])));

  }

  cout << add(mul(res, dec(inv[n], inv[n - 1])), iv2) << '\n';

  return 0;

}

Minimum Index

边做 \(\text{Lyndon}\) 分解边统计答案即可。

Code

int main() {

  n = Read(s);

  int ss = 0;

  for (ri i = 1; i <= n; ++i) vs[i] = 0;

  for (ri i = 1, iv = Inv(1112), j, k, mt = 1; i <= n; ) {

    j = i, k = i + 1;

    if (!vs[i]) len[i] = 1, vs[i] = 1, Add(ss, mul(mt, i)), Mul(mt, 1112);

    for (; k <= n && s[j] <= s[k]; ++k) {

      j = s[j] < s[k] ? i : j + 1;

      if (!vs[k]) {

        vs[k] = 1;

        if (i == j) len[k] = k - i + 1;

        else len[k] = len[j - 1];

        Add(ss, mul(mt, k - len[k] + 1)), Mul(mt, 1112);

      }

    }

    for (; i <= j; i += k - j);

  }

  cout << ss << '\n';

  return 0;

}

Mow

维护一下半平面交即可。

调了半个上午都没调出来，最后发现好像是 \(\text{hdu}\) 不支持用 \(\text{printf}\) 输出 \(\text{long double}\) 类型的答案...

Code

inline bool cmp(Line x, Line y) { return x.ang < y.ang; }

inline pt Cross(Line a, Line b) {

  db s1 = (a.a - b.a) * (a.b - b.a), s2 = (a.b - b.b) * (a.a - b.b), t = s1 / (s1 + s2);

  return b.a + (b.b - b.a) * t;

}

inline bool chk(Line x, Line y, Line z) {

  pt tp = Cross(x, y);

  return (z.b - z.a) * (tp - z.a) <= 0;

}

const db pi = acosl(-1.0);

inline db calc() {

  static int q[N], hd, tl;

  static pt A[N];

  sort(L + 1, L + n + 1, cmp);

  hd = 1, tl = 0;

  for (ri i = 1; i <= n; ++i) {

    while (hd < tl && chk(L[q[tl]], L[q[tl - 1]], L[i])) --tl;

    while (hd < tl && chk(L[q[hd]], L[q[hd + 1]], L[i])) ++hd;

    q[++tl] = i;

  }

  while (hd < tl && chk(L[q[tl]], L[q[tl - 1]], L[q[hd]])) --tl;

  while (hd < tl && chk(L[q[hd]], L[q[hd + 1]], L[q[tl]])) ++hd;

  if (tl - hd + 1 < 3) return 0;

  q[tl + 1] = q[hd];

  int ct = 0;

  for (ri i = hd; i <= tl; ++i) A[++ct] = Cross(L[q[i]], L[q[i + 1]]);

  A[ct + 1] = A[1];

  db res = 0, ss = 0;

  for (ri i = 1; i <= ct; ++i) res += A[i] * A[i + 1], ss += (A[i + 1] - A[i]).mod();

  res *= 0.5l, res += ss * R;

  return res + pi * R * R;

}

int main() {

  n = read(), R = read(), A = read(), B = read();

  for (ri i = 1; i <= n; ++i) a[i].x = read(), a[i].y = read();

  a[n + 1] = a[1];

  db S = 0, res;

  for (ri i = 1; i <= n; ++i) S += a[i] * a[i + 1];

  S *= 0.5l;

  if (S < 0) {

    S = -S;

    reverse(a + 1, a + n + 1);

    a[n + 1] = a[1];

  }

  res = S * A;

  if (A <= B) {

    cout << fixed << setprecision(20) << res << '\n';

    continue;

  }

  for (ri i = 1; i <= n; ++i) {

    pt tp = a[i + 1] - a[i];

    db ang = atan2l(tp.y, tp.x);

    tp = pt(-tp.y, tp.x);

    tp /= tp.mod(), tp *= R;

    L[i] = (Line) { a[i] + tp, a[i + 1] + tp, ang };

  }

  res -= (A - B) * calc();

  cout << fixed << setprecision(20) << res << '\n';

  return 0;

}

2020 Multi-University Training Contest 1 部分题解的相关教程结束。

《2020 Multi-University Training Contest 1 部分题解.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!