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

AtCoder Beginner Contest 269

时间:2022-09-18 01:33:05浏览次数:122  
标签:std AtCoder return Beginner int value Modular 269 Mint

咕咕咕咕咕。

F - Numbered Checker

首先矩形容斥,把一个询问拆分成 4 个询问。现在只需要解决:左上角为\((1, 1)\),右下角为 \((x, y)\) 的矩形区域和这一问题。

把列数为奇数和偶数的分开算,以奇数为例,偶数列同理可得。

第 1 列的上的非零元素可以组成一个首项元素为 \(1\) ,公差为 \(2m\), 共 \(\lfloor \frac{x + 1}{2} \rfloor\) 项的等差数列。

把列数为奇数的列,每列求和后,搞成一个一维数组,这又是一个等差数列,首项为第一列的元素和,公差为 \(2 \lfloor \frac{x + 1}{2} \rfloor\) , 共 \(\lfloor \frac{y + 1}{2} \rfloor\) 项。

AC代码
// Problem: F - Numbered Checker
// Contest: AtCoder - UNICORN Programming Contest 2022(AtCoder Beginner Contest 269)
// URL: https://atcoder.jp/contests/abc269/tasks/abc269_f
// Memory Limit: 1024 MB
// Time Limit: 3000 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() {}

template <typename ValueType, ValueType mod_, 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(SupperType value = 0) : 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, 1'000'000'007, int64_t>;
using Mint = Modular<int, 998'244'353, 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];
  }
};

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

  auto S1 = [&](Mint a0, Mint k, Mint d) { return k * a0 + d * (k - 1) * (k) / Mint(2); };

  auto S21 = [&](int x, int y) {
    Mint a0 = S1(1, Mint((x + 1) / 2), Mint(2 * m));
    Mint k = Mint((y + 1) / 2);
    Mint d = Mint(2) * Mint((x + 1) / 2);
    return S1(a0, k, d);
  };

  auto S22 = [&](int x, int y) {
    Mint a0 = S1(Mint(m + 2), x / 2, 2 * m);
    Mint k = Mint(y / 2);
    Mint d = Mint(2) * Mint(x / 2);
    return S1(a0, k, d);
  };

  auto Q = [&](int x, int y) { return S21(x, y) + S22(x, y); };

  for (int _ = 1; _ <= q; ++_) {
    int x1, x2, y1, y2;
    std::cin >> x1 >> x2 >> y1 >> y2;

    Mint ans = Q(x2, y2) - Q(x2, y1 - 1) - Q(x1 - 1, y2) + Q(x1 - 1, y1 - 1);
    std::cout << ans.value() << "\n";
  }
}

G - Reversible Cards 2

转化一下,问题变成一个01背包问题:背包初始装了 \(s\) 单位重量,价值为 \(0\) 的东西,有 \(n\) 件物品,每件物品价值为 \(1\) ,重量为 \(w_i = b_i - a_i\) 单位重量(\(w_i\)可能小于零),问背包装恰好 \(k\) 单位重量的物品的最小代价。

这样直接去 DP 复杂度为\(O(nm)\),直接爆炸。

观察1:所有物品重量的绝对值之和小于等于 \(m\) 。
证明

\[\sum_i |w_i| = \sum_i |b_i - a_i| \le \sum_i |b_i| + |-a_i| = m \]

观察2: 如果把重量相同的物品视为一类,则至多有 \(2 \lceil \sqrt{m} \rceil\) 种物品。或者说至多有\(2\sqrt{m}\)中物品数量大于等于1。
证明: 考虑反证法。假设有\(2 \lceil \sqrt{m} \rceil + 1\)种物品,考虑构造出一种方案使得\(\sum_i |w_i|\)尽可能小,则应该是每种物品数量都为1,然后物品重量值域为\([-\lceil \sqrt{m} \rceil, \lceil \sqrt{m} \rceil]\)。此时有\(\sum_i |w_i| = 0 + 2 \sum_{i = 1}^{\lceil \sqrt{m} \rceil} i = m + \lceil \sqrt{m} \rceil\),与观察1相悖。

观察3: 至多有 \(2 \lceil \frac{\sqrt{m}}{2^t} \rceil\) 种物品数量大于等于\(2^t\)。
证明:类似观察2的证明。

现在问题转化成多重背包问题,可以二进制分组优化搞,假设有\(c\)种物品,第\(i\)种物品有\(k_i\)个,则复杂度为\(O(n + m \sum_{i = 1}^{c} \log k_i)\)。又有

\[\sum_{i = 1} ^ c \log k_i = \sum_{x=0}^{+\infin} \sum_{i=1}^{c} [k_i \ge 2^x] = \sum_{x=0}^{+\infin} 2 \lceil \frac{\sqrt{m}}{2^t} \rceil = O(\sqrt{m}) \]

所以总的时间复杂度为\(O(n + m\sqrt m)\)。

AC代码
// Problem: G - Reversible Cards 2
// Contest: AtCoder - UNICORN Programming Contest 2022(AtCoder Beginner Contest 269)
// URL: https://atcoder.jp/contests/abc269/tasks/abc269_g
// Memory Limit: 1024 MB
// Time Limit: 3000 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, m;
  std::cin >> n >> m;

  std::map<int, int> mp;
  int s = 0;
  for (int i = 0; i < n; ++i) {
    int a, b;
    std::cin >> a >> b;
    ++mp[b - a];
    s += a;
  }

  const int INF = 0x3f3f3f3f;
  std::vector<int> dp(m + 1, INF);
  dp[s] = 0;
  for (auto [d, c] : mp) {
    if (d == 0)
      continue;

    int x = 1;
    while (c) {
      x = std::min(x, c);

      if (d > 0) {
        for (int i = m; i >= x * d; --i)
          dp[i] = std::min(dp[i], dp[i - x * d] + x);
      } else {
        for (int i = 0; i - x * d <= m; ++i)
          dp[i] = std::min(dp[i], dp[i - x * d] + x);
      }

      c = c - x;
      x = x * 2;
    }
  }

  for (int i = 0; i <= m; ++i) {
    if (dp[i] == INF)
      dp[i] = -1;
    std::cout << dp[i] << "\n";
  }
}

Ex - Antichain

To be solved.

标签:std,AtCoder,return,Beginner,int,value,Modular,269,Mint
From: https://www.cnblogs.com/zengzk/p/16704065.html

相关文章

  • AtCoder Beginner Contest 267 题解
    只会\(A\simG\)主观难度:\(A<B<C<E<D<F<G<Ex\)A-Saturday分别对周一到周五判断即可。#include<bits/stdc++.h>usingnamespacestd;inlineintread(){int......
  • AtCoder Beginner Contest 262(D-E)
    D-IHateNon-integerNumber题意:一个长度为n的数组,选择其中的x项,问其中有多少种选择,这x项的和可以被选择的数目整除,比如,选择3个数,和为6,那么6/3=2,就可以被整除。题解:......
  • AtCoder Regular Contest 147
    ProblemA题目大意:由N个正整数组成的序列,我们可以从中取出任意长短序列进行如下操作:序列中(最大值maxn%最小值minn=A),如果A为0则删除maxn,否则用A替换,询问要使得整个序......
  • AtCoder做题记录
    AtCoder大乱炖AtCoder乱做AtCoder随便草ARC147ARC147C发现这个式子当所有\(x_i\)趋近于某一个值时答案比较优,于是可以发现这是一个近似单谷函数,用二分+随机化/特......
  • AtCoder Beginner Contest 265
    E-Warp注意到\(N\)相比\(M\)要小得多。考虑DP,令\(dp_{i,j,k}\)表示一共使用了\(i+j+k\)次操作,且每种操作的使用次数分别为\(i,j,k\)的方案数,然后......
  • AtCoder Beginner Contest 267
    A-Saturday题意:给定今天的日期,问到周六还有几天。分析:暴力判断即可。代码:intmain(){ cin>>s; if(s=="Monday")ans=5; if(s=="Tuesday")ans=4; if(s=="We......
  • AtCoder Beginner Contest 267
    https://atcoder.jp/contests/abc267全部的AC代码:https://atcoder.jp/contests/abc267/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshiE......
  • Atcoder Regular Contest 147
     AtcoderRegularContest147这是本蒟蒻第3次打的\(ARC\),赛时的时候\(B\)题调代码调崩了,\(wa\)了15发。所以来简略的写一下题解A:题目链接题目大意:略题目分析......
  • AtCoder Beginner Contest 267 解题报告
    A-Saturday题意:输入字符串代表周一至周五的某一天,输出这一天离周六还有多少天分析:映射一下,直接输入输出ac代码:#include<iostream>#include<algorithm>#inclu......
  • AtCoder Beginner Contest 267
    E-ErasingVertices2做法1观察可得:对于某个时刻,贪心删当前代价最小的点肯定是最优的。但是删一个点会减少相邻接的点的代价。然后就想到了堆,但是这个堆需要支持decre......