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

AtCoder Beginner Contest 270

时间：2022-09-24 23:22:22浏览次数：79  
标签：std AtCoder return Beginner int ++ value 270 Modular

咕咕咕。

D - Stones

冲了发贪心，然后 WA 。

然后想了个 DP，就令 \(dp_{n, 0/1}\) 表示石头总数为 \(n\) 时，先手/后手最多能拿多少个石头，然后跑个 \(O(nk)\) 的DP就完事了。

AC代码 
// Problem: D - Stones
// Contest: AtCoder - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest
// 270) URL: https://atcoder.jp/contests/abc270/tasks/abc270_d Memory Limit: 1024 MB Time Limit:
// 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif

using i64 = int64_t;
using u64 = uint64_t;

void Initialize();
void SolveCase(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

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

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

  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2, 0));
  dp[0][0] = 0;
  dp[0][1] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = k - 1; j >= 0; --j) {
      if (i >= a[j]) {
        dp[i][0] = std::max(dp[i][0], dp[i - a[j]][1] + a[j]);
        dp[i][1] = i - dp[i][0];
      }
    }
  }
  logd(dp);

  std::cout << dp[n][0] << "\n";
}

E - Apple Baskets on Circle

记走一圈为一轮，可以把结果相同的轮的贡献合并到一起算，从而加速模拟。

假设 \(a\) 按大小排序后的数组为 \(b\)，那么原过程等价于在 \(b\) 上从左往右走的过程，假设走到了 \(b_i\) ，则现在的一轮一轮等价于 \([i, n]\) 区间减 \(1\) 。假设 \(b_i\) 之前已经走了了 \(d\) 轮，那么接下来 \(\min(\lfloor \frac{k}{n - i} \rfloor, b_i - d)\) 轮的结果相同，这几轮的贡献可以 \(O(1)\) 计算。

现在 \(k\) 可能还有剩余但不足以走完一轮，模拟一下即可。

时间复杂度 \(O(n \log n)\)，瓶颈在于排序，模拟的部分复杂度为 \(O(n)\)。

AC代码 
// Problem: E - Apple Baskets on Circle
// Contest: AtCoder - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest
// 270) URL: https://atcoder.jp/contests/abc270/tasks/abc270_e Memory Limit: 1024 MB Time Limit:
// 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif

using i64 = int64_t;
using u64 = uint64_t;

void Initialize();
void SolveCase(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

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

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

  auto b = a;
  std::sort(b.begin(), b.end());

  i64 d = 0;
  for (int i = 0; i < n; ++i) {
    i64 r = n - i;
    if (k < n - i)
      break;

    i64 x = std::min(k / (n - i), b[i] - d);
    logd(i, x);
    d += x;
    k -= x * r;
  }

  for (int i = 0; i < n; ++i)
    a[i] = std::max(i64(0), a[i] - d);
  logd(a);

  for (int i = 0; i < n; ++i) {
    if (a[i] > 0 && k > 0) {
      --a[i];
      --k;
    }
  }
  ASSERT(k == 0);

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

F - Transportation

把机场和港口也看成节点的话，问题就转化成了的最小生成树问题。

然后可能会有不使用机场和港口的情况，机场和港口都可用可不用，一共 \(4\) 种情况，那就跑 \(4\) 次 Kruskal 最小生成树算法。

AC代码 
// Problem: F - Transportation
// Contest: AtCoder - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest
// 270) URL: https://atcoder.jp/contests/abc270/tasks/abc270_f Memory Limit: 1024 MB Time Limit:
// 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif

using i64 = int64_t;
using u64 = uint64_t;

void Initialize();
void SolveCase(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

void SolveCase(int Case) {
  auto kruskal = [](int n, std::vector<std::array<int, 4>> E) {
    std::sort(E.begin(), E.end());

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

    std::function<int(int)> find = [&](int x) { return x == f[x] ? x : f[x] = find(f[x]); };

    i64 ans = 0;
    for (auto [w, _, u, v] : E) {
      int fu = find(u), fv = find(v);
      if (fu == fv)
        continue;

      f[fu] = fv;

      ans += w;
    }

    for (int i = 0; i < n; ++i)
      if (find(i) != find(0))
        return std::numeric_limits<i64>::max();

    return ans;
  };

  int n, m;
  std::cin >> n >> m;

  std::vector<std::array<int, 4>> E;

  int airport = n, harbor = n + 1;
  std::vector<int> x(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> x[i];
  }
  std::vector<int> y(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> y[i];
  }
  std::vector<int> a(m), b(m), z(m);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    --u, --v;
    a[i] = u, b[i] = v, z[i] = w;
  }

  i64 ans = std::numeric_limits<i64>::max();
  {
    std::vector<std::array<int, 4>> E;
    for (int i = 0; i < n; ++i) {
      E.push_back({x[i], 1, i, airport});
    }
    for (int i = 0; i < n; ++i) {
      E.push_back({y[i], 1, i, harbor});
    }
    for (int i = 0; i < m; ++i) {
      E.push_back({z[i], 0, a[i], b[i]});
    }
    ans = std::min(ans, kruskal(n, E));
  }
  {
    std::vector<std::array<int, 4>> E;
    for (int i = 0; i < n; ++i) {
      E.push_back({y[i], 1, i, harbor});
    }
    for (int i = 0; i < m; ++i) {
      E.push_back({z[i], 0, a[i], b[i]});
    }
    ans = std::min(ans, kruskal(n, E));
  }
  {
    std::vector<std::array<int, 4>> E;
    for (int i = 0; i < n; ++i) {
      E.push_back({x[i], 1, i, airport});
    }
    for (int i = 0; i < m; ++i) {
      E.push_back({z[i], 0, a[i], b[i]});
    }
    ans = std::min(ans, kruskal(n, E));
  }
  {
    std::vector<std::array<int, 4>> E;
    for (int i = 0; i < m; ++i) {
      E.push_back({z[i], 0, a[i], b[i]});
    }
    ans = std::min(ans, kruskal(n, E));
  }

  std::cout << ans << "\n";
}

G - Sequence in mod P

令 \(f(x) = Ax + B\)，则可以算出 \(f^{-1}(x) = Cx + D\) 。

\(X_n = G\) 等价于 \(f^x(S) = G\) ，这个式子和离散对数的式子很相似，考虑类似求解离散对数问题的大步小步算法(BSGS, baby-step giant-step)。

令 \(M = \sqrt{p}\)，则对于所有 \(x\) 都存在 \(0 \le A, B \le \sqrt{p}\) 使得 \(x = AM + B\) 成立，然后就有 \(f^x(S) = G\) 等价于 \(f^{AM}(S) = f^{-B}(G)\)。

由于 \(0 \le A, B \le \sqrt{p}\)，所以可以先枚举等式的一边，记录结果取值以及对应步数；然后再枚举等式的另一边，看是否有结果取值相等的记录，若有则两边的步数相加就是一个可行的 \(x\) 。

AC代码 
// Problem: G - Sequence in mod P
// Contest: AtCoder - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest
// 270) URL: https://atcoder.jp/contests/abc270/tasks/abc270_g Memory Limit: 1024 MB Time Limit:
// 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif

using i64 = int64_t;
using u64 = uint64_t;

void Initialize();
void SolveCase(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

int mod_;
template <typename ValueType, typename SupperType>
class Modular {
  static ValueType normalize(ValueType value) {
    if (value >= 0 && value < mod_)
      return value;
    value %= mod_;
    if (value < 0)
      value += mod_;
    return value;
  }

  static ValueType power(ValueType value, int64_t exponent) {
    ValueType result = 1;
    ValueType base = value;
    while (exponent) {
      if (exponent & 1)
        result = SupperType(result) * base % mod_;
      base = SupperType(base) * base % mod_;
      exponent >>= 1;
    }
    return result;
  }

 public:
  Modular(ValueType value = 0) : value_(normalize(value)) {}

  Modular(SupperType value) : value_(normalize(value % mod_)) {}

  ValueType value() const { return value_; }

  Modular inv() const { return Modular(power(value_, mod_ - 2)); }

  Modular power(int64_t exponent) const { return Modular(power(value_, exponent)); }

  friend Modular operator+(const Modular& lhs, const Modular& rhs) {
    ValueType result = lhs.value() + rhs.value() >= mod_ ? lhs.value() + rhs.value() - mod_
                                                         : lhs.value() + rhs.value();
    return Modular(result);
  }

  friend Modular operator-(const Modular& lhs, const Modular& rhs) {
    ValueType result = lhs.value() - rhs.value() < 0 ? lhs.value() - rhs.value() + mod_
                                                     : lhs.value() - rhs.value();
    return Modular(result);
  }

  friend Modular operator-(const Modular& lhs) {
    ValueType result = normalize(-lhs.value() + mod_);
    return result;
  }

  friend Modular operator*(const Modular& lhs, const Modular& rhs) {
    ValueType result = SupperType(1) * lhs.value() * rhs.value() % mod_;
    return Modular(result);
  }

  friend Modular operator/(const Modular& lhs, const Modular& rhs) {
    ValueType result = SupperType(1) * lhs.value() * rhs.inv().value() % mod_;
    return Modular(result);
  }

  std::string to_string() const { return std::to_string(value_); }

 private:
  ValueType value_;
};
using Mint = Modular<int, int64_t>;

class Binom {
 private:
  std::vector<Mint> f, g;

 public:
  Binom(int n) {
    f.resize(n + 1);
    g.resize(n + 1);

    f[0] = Mint(1);
    for (int i = 1; i <= n; ++i)
      f[i] = f[i - 1] * Mint(i);
    g[n] = f[n].inv();
    for (int i = n - 1; i >= 0; --i)
      g[i] = g[i + 1] * Mint(i + 1);
  }
  Mint operator()(int n, int m) {
    if (n < 0 || m < 0 || m > n)
      return Mint(0);
    return f[n] * g[m] * g[n - m];
  }
};

using Mint = Modular<int, int64_t>;

void SolveCase(int Case) {
  int p, a, b, s, g;
  std::cin >> p >> a >> b >> s >> g;
  mod_ = p;

  if (s == g) {
    std::cout << "0\n";
    return;
  }

  if (a == 0) {
    std::cout << (b == g ? 1 : -1) << "\n";
    return;
  }

  int M = std::sqrt(p);

  std::map<int, int> mp;
  Mint X(g);
  Mint c = Mint(a).inv(), d = Mint(a).inv() * Mint(-b);
  for (int i = 0; i < M; ++i) {
    if (!mp.count(X.value()))
      mp[X.value()] = i;

    X = X * c + d;
  }

  Mint Y(s);
  Mint A(1), B(0);
  for (int i = 0; i < M; ++i) {
    A = A * Mint(a);
    B = B * Mint(a) + Mint(b);
  }
  for (int i = 0; i <= p / M + 1; ++i) {
    if (mp.count(Y.value())) {
      int ans = i * M + mp[Y.value()];
      std::cout << ans << "\n";
      return;
    }

    Y = Y * A + B;
  }

  std::cout << "-1\n";
}

Ex - add 1

To be solved。

标签：std,AtCoder,return,Beginner,int,++,value,270,Modular
From： https://www.cnblogs.com/zengzk/p/16726958.html

相关文章

  • AtCoder Beginner Contest 268(D-E)
    D-UniqueUsername 题意：给出n个字符串，以任意顺序排列，然后在每两个字符串中间加最少一个"_"，然后给出m个字符串，问是否能得出一个字符串，不在这m个字符串中，并且长度在3-16......
  • 关爱2700多万听障者，手语服务助力无声交流
    如果有一天，周遭的世界突然变得很安静，动听美妙的音乐，在你看来只是沉寂；振奋人心的演讲，对你而言只是默剧；大自然的千里莺啼，于你来说也只是画卷。你会不会感到害怕？而有这么一群......
  • AtCoder Beginner Contest 043 题解
    欢迎来到我的算法小屋前言 TaskNameAChildrenandCandies(ABCEdit)BUnhappyHacking(ABCEdit)CBeTogetherDUnbalancedA1）题目描述2......
  • Atcoder 269
    T1:计算（a+b）*(c-d)输出字符串点击查看代码#include<bits/stdc++.h>usingi64=longlong;intmain(){std::ios::sync_with_stdio(false);std::c......
  • AtCoder Beginner Contest 258
    AtCoderBeginnerContest258LinkA-When?模拟即可.点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){intn;......
  • AtCoder Beginner Contest 269
    比赛链接A模拟即可。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inta,b,c,d;signedmain(){ cin>>a>>b>>c>>d; cout<<(......
  • Atcoder 题集
    Atcoder题集E-Lucky7Battle博弈论，对抗性搜索，记忆化搜索#include<bits/stdc++.h>usingnamespacestd;stringt,x;intn;intf[200010][7];intdfs(inti,intr){......
  • AtCoder Regular Contest 148 C Lights Out on Tree
    挺好的一道题，简单写一下题解吧。首先有挺多很naive的结论：每个节点按两遍等于没按。熄灭所有的灯只有一种方案。其实将灯熄灭的方案无非就是从上往下dfs，如果当前灯......
  • AtCoder Beginner Contest 268
    E-ChineseRestaurant(Three-StarVersion)假设旋转\(x\)次时，\(n\)个人失望值的总和为\(c_x\)，那么只要能求出\(c_x,0\lex<n\)就可以包含所有情况，然后再取......
  • AtCoder Beginner Contest 269 （A-F）题解
    A-AnywayTakahashi这里我还是关了ll的C开了忘了关害的F多了一发罚时#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;constintM=9982443......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99