首页 > 其他分享 >AtCoder Beginner Contest 279

AtCoder Beginner Contest 279

时间:2022-11-27 15:55:25浏览次数:57  
标签:std AtCoder Beginner int void cin ++ 279 include

咕咕咕。

D - Freefall

三分求极值,注意下标得是整数,所以最后再搜索三分结果附近的整数。

直接求导应该也可以。

AC代码
// #define MULTIPLE_TASK
#include "hira/main.cpp"

void Initialize() {}

void SolveCase(int Case) {
  double a, b;
  std::cin >> a >> b;

  auto f = [&](double x) { return x * b + a / std::sqrt(1 + x); };

  const double eps = 1e-8;
  double l = 0, r = a, ml, mr, fl, fr;
  int limit = 128;
  while (r - l > eps) {
    logd(std::to_string(l), std::to_string(r), std::to_string(r - l));
    ml = l + (r - l) / 3;
    mr = r - (r - l) / 3;

    fl = f(ml);
    fr = f(mr);

    if (fl > fr)
      l = ml;
    else
      r = mr;

    --limit;
    if (limit == 0)
      break;
  }

  double ans = f(0);
  for (int i = -32; i <= 32; ++i) {
    i64 x = l + i;
    if (x >= 0)
      ans = std::min(ans, f(x));
  }

  std::cout << std::fixed << std::setprecision(10) << ans << "\n";
}


E - Cheating Amidakuji

操作的前缀和很容易维护,但是操作的后缀和不好维护。

假设仅操作前 \(i\) 个操作之后,\(i\) 位于 \(p_i\) 处, \(x_i\) 表示 \(i\) 的位置,即 \(x_{p_i} = i\) 。

结论:\(p\) 和 \(s\) 互为对方的逆,即交换 \(p\) 和 \(s\)相当于把操作顺序翻转。

现在后缀和也能维护了。

AC代码
// #define MULTIPLE_TASK
#include "hira/main.cpp"

void Initialize() {}

void SolveCase(int Case) {
  int n, m;
  std::cin >> n >> m;

  std::vector<int> a(m);
  for (int i = 0; i < m; ++i)
    std::cin >> a[i], --a[i];

  std::vector<int> b(n);
  std::iota(b.begin(), b.end(), 0);

  auto p = b;
  auto s = b;
  for (int i = 0; i < m; ++i) {
    std::swap(p[a[i]], p[a[i] + 1]);
  }

  std::vector<int> x(n);
  for (int i = 0; i < n; ++i)
    x[p[i]] = i;

  std::vector<int> y(n);
  for (int i = 0; i < n; ++i)
    y[i] = i;

  std::vector<int> ans(m);
  for (int i = m - 1; i >= 0; --i) {
    std::swap(x[p[a[i]]], x[p[a[i] + 1]]);
    std::swap(p[a[i]], p[a[i] + 1]);

    logd(p, s);
    ans[i] = s[x[0]];

    std::swap(y[s[a[i]]], y[s[a[i] + 1]]);
    std::swap(s[a[i]], s[a[i] + 1]);
  }
  logd(p, x);

  for (int i = 0; i < m; ++i)
    std::cout << ans[i] + 1 << "\n";
}

F - BOX

并查集,额外维护集合代表元素和其所属容器的双射即可。

AC代码
// #define MULTIPLE_TASK
#include "hira/main.cpp"

#include "hira/ds/dsu.h"

void Initialize() {}

void SolveCase(int Case) {
  int n, q;
  std::cin >> n >> q;

  int k = n - 1;
  ds::DSU d(n + q);
  std::vector<int> c(n + q, -1), p(n + q, -1);
  for (int i = 0; i < n; ++i) {
    c[i] = i;
    p[i] = i;
  }
  for (int i = 0; i < q; ++i) {
    int op;
    std::cin >> op;

    if (op == 1) {
      int x, y;
      std::cin >> x >> y;
      --x, --y;

      if (c[y] == -1)
        continue;

      if (c[x] == -1) {
        c[x] = c[y];
        p[c[x]] = x;
        c[y] = -1;
      } else {
        d.f_[c[y]] = c[x];
        p[c[y]] = -1;
        c[y] = -1;
      }
    } else if (op == 2) {
      int x;
      std::cin >> x;
      --x;

      ++k;

      if (c[x] == -1) {
        c[x] = k;
        p[k] = x;
      } else {
        d.f_[k] = c[x];
      }
    } else if (op == 3) {
      int x;
      std::cin >> x;
      --x;

      x = d.leader(x);
      std::cout << p[x] + 1 << "\n";
    }
  }
}

G - At Most 2 Colors

假设 \(dp_{i, j}\) 表示前 \(i\) 的元素,上一个和 \(a_i\) 不同的元素为 \(a_j\)。

然后有以下几种转移:

  • \(a_i = a_{i - 1}\): \(\forall j < i, dp_{i, j} \to dp_{i + 1, j}\)
  • \(a_i = a_{j}\): \(\forall j < i, dp_{i, j} \to dp_{i + 1, i}\)
  • \(a_i \ne a_{i - 1}\) 且 \(a_i \ne a_{j}\): \(\forall j \le i - k, dp_{i, j} \to dp_{i + 1, i}\)

复杂度为 \(O(nk)\),但是可以用树状数组优化到 \(O(n \log n)\)。

第一种转移相当于复制,但是其实可以不用操作,直接复用即可。

第二种转移就是求个和然后加到位置 \(t_i\) 上。

第三种转移也是求个和然后加到位置 \(t_i\) 上,但是要特判此前只用了一种颜色的情况。

AC代码
// #define MULTIPLE_TASK
#include "hira/main.cpp"

#include "hira/math/modular/mod_int.h"
using mint = math::ModInt998;

#include "hira/ds/fenwick_tree.h"

void Initialize() {}

void SolveCase(int Case) {
  int n, k, c;
  std::cin >> n >> k >> c;

  ds::FenwickTree<mint> t(n + 1, mint(0),
                          [](const mint& x, const mint& y) { return x + y; });
  t.Update(1, c);
  for (int i = 2; i <= n; ++i) {
    mint x = t.Query(2, i - 1);

    mint y = t.Query(1, 1) * (c - 1);

    mint z = i - k + 1 >= 2 ? t.Query(2, i - k + 1) * (c - 2) : 0;

    t.Update(i, x);
    t.Update(i, y);
    t.Update(i, z);

    logd(i, t, x, y, z);
  }

  mint ans = t.Query(n);

  std::cout << ans.value() << "\n";
}

Ex - Sum of Prod of Min

To be solved.

标签:std,AtCoder,Beginner,int,void,cin,++,279,include
From: https://www.cnblogs.com/zengzk/p/16929833.html

相关文章

  • AtCoder Beginner Contest 279
    A-wwwvvvvvv原题链接题意给出仅由v和w组成的字符串\(S\)。输出\(S\)中有多少个尖点(一个v有一个尖点,一个w有两个尖点)。分析输入字符串,遍历每个字符。如果这个......
  • 题解 [ABC279F] BOX
    这种合并集合的操作使我们想到并查集,因此我们在并查集算法的基础上进行改造来解决问题。这里使用路径压缩实现的并查集。在记录并查集的父亲数组的同时,我们还需要记录两个......
  • 题解 [ABC279E] Cheating Amidakuji
    曾经总结过一类分治套路,没想到竟然派上用场了。这种每个操作依次缺席的问题可以通过分治来解决。设solve(l,r)表示缺席的操作在\([l,r]\)之间时求出它们的答案。设......
  • TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279)A-D题(暂定)
    A,w是两个v是一个送分题#include<bits/stdc++.h>usingnamespacestd;#definemaxn400100#defineintlonglongintread(){intans=0,f=1;charch......
  • AtCoder Beginner Contest 278
    《F-Shiritori 》博弈   首先在这个博弈题中有个很重要的结论:1.如果一个点,走一步,能够到达的点如果其中有一个为先手必胜点,那么这个点必然是先手必败点......
  • AtCoder Beginner Contest 237 Ex Hakata
    洛谷传送门AtCoder传送门下文令\(|S|=n\)。引理:一个字符串中本质不同的回文串数量\(\len\)。证明:考虑每在字符串末尾添加一个字符,本质不同回文串数量最多增加......
  • AtCoder Grand Contest 025B - RGB Coloring
    题解:一开始想把AA,BB,AA+B......
  • Atcoder ABC 277 A - E
    **A^{-1}**题意:给定一个序列,和一个指定值,输出这个值在序列中的位置(序列的下标从1开始)思路:签到题时间复杂度:O(n)代码:#include<bits/stdc++.h>usingnamespacestd;......
  • AtCoder 题解集
    虽然暂时不知道会不会从XCPC中退役,但还是想把这个题解集给维护下去。\(created\;at\;2022/6/24\;by\;Roshin\)目录AGCARCABCABC138F.Coincidence(结论,数位DP)AB......
  • AtCoder Beginner Contest 278
    Preface刚打完就来写题解,热乎的很这周CF没Div2,Atcoder的ARC和微积分考试撞了打不了所以和ztc一起打一下Div3和ABC,顺便锻炼一波解释题目的能力做到G的时候还有30min的,然......