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

AtCoder Beginner Contest 274

时间：2022-10-23 00:22:22浏览次数：81  
标签：std AtCoder return Beginner int ++ vector 274 operatorname

E - Booster

TSP问题变种，典中典。

AC代码 
// Problem: E - Booster
// Contest: AtCoder - キーエンスプログラミングコンテスト2022（AtCoder Beginner
// Contest 274） URL: https://atcoder.jp/contests/abc274/tasks/abc274_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;
using i128 = __int128_t;
using u128 = __uint128_t;

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

int main(int argc, char* argv[]) {
  CPPIO;

  Initialize();

  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

template <typename T, typename... Args>
auto n_vector(size_t n, Args&&... args) {
  if constexpr (sizeof...(args) == 1) {
    return std::vector<T>(n, args...);
  } else {
    return std::vector(n, n_vector<T>(args...));
  }
}

void SolveCase(int Case) {
  int n, m;
  std::cin >> n >> m;
  int sz = n + m + 2;

  std::vector<std::pair<int, int>> p;
  p.reserve(sz);
  p.push_back({0, 0});
  for (int i = 0; i < n; ++i) {
    int x, y;
    std::cin >> x >> y;
    p.push_back({x, y});
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    std::cin >> x >> y;
    p.push_back({x, y});
  }
  p.push_back({0, 0});

  auto D = [&](int i, int j) {
    auto [x1, y1] = p[i];
    auto [x2, y2] = p[j];
    double x = x1 - x2;
    double y = y1 - y2;
    return std::sqrt(x * x + y * y);
  };

  std::vector<std::vector<double>> f(sz, std::vector<double>(sz, 1e18));
  for (int i = 0; i < sz; ++i) {
    f[i][i] = 0;
    for (int j = 0; j < sz; ++j) {
      f[i][j] = f[j][i] = D(i, j);
    }
  }

  int towns = 0;
  for (int i = 1; i <= n; ++i)
    towns |= (1 << i);
  towns |= (1 << 0);
  towns |= (1 << (sz - 1));
  int chests = ((1 << sz) - 1) ^ towns;

  auto dp = n_vector<double>(1 << sz, sz, 1e18);
  dp[1][0] = 0;
  for (int mask = 0; mask < (1 << sz); ++mask) {
    for (int i = 0; i < sz; ++i) {
      if (mask >> i & 1) {
        int prev_mask = mask ^ (1 << i);
        for (int j = 0; j < sz; ++j) {
          if (prev_mask >> j & 1) {
            int k = __builtin_popcount(prev_mask & chests);
            dp[mask][i] =
                std::min(dp[mask][i], dp[prev_mask][j] + f[j][i] / (1 << k));
          }
        }
      }
    }
  }

  double ans = 1e18;
  for (int mask = 0; mask < (1 << sz); ++mask) {
    if ((mask & towns) < towns)
      continue;

    ans = std::min(ans, dp[mask][sz - 1]);
  }
  std::cout << std::fixed << std::setprecision(10) << ans << "\n";
}

F - Fishing

观察可得：最优情况下，网的左端点一定有鱼。

枚举左端点的鱼，现在其他鱼位于网内的时间区间就可以算出来了，然后就是区间覆盖问题了，典中典。

AC代码 
// Problem: F - Fishing
// Contest: AtCoder - キーエンスプログラミングコンテスト2022（AtCoder Beginner
// Contest 274） URL: https://atcoder.jp/contests/abc274/tasks/abc274_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;
using i128 = __int128_t;
using u128 = __uint128_t;

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

int main(int argc, char* argv[]) {
  CPPIO;

  Initialize();

  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

struct frac {
  i64 u_, d_;
  frac(i64 u, i64 d) : u_(u), d_(d) {
    i64 g = std::gcd(u_, d_);
    if (g) {
      u_ /= g;
      d_ /= g;
    }
    if (u_ < 0) {
      u_ *= -1;
      d_ *= -1;
    }
  }

  bool operator<(const frac& f) const {
    if (d_ * f.d_ > 0)
      return u_ * f.d_ < f.u_ * d_;
    return u_ * f.d_ > f.u_ * d_;
  }

  bool operator==(const frac& f) const { return u_ == f.u_ && d_ == f.d_; }

  bool operator!=(const frac& f) const { return u_ != f.u_ || d_ != f.d_; }
};

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

  std::vector<std::array<int, 3>> a(n);
  for (int i = 0; i < n; ++i) {
    int w, x, v;
    std::cin >> w >> x >> v;
    a[i] = {w, x, v};
  }

  int ans = 0;
  auto work = [&]() {
    int gain = a[0][0];
    std::vector<std::pair<frac, int>> p;
    for (int i = 1; i < n; ++i) {
      if (a[i][2] - a[0][2] != 0) {
        frac s(-a[i][1] + a[0][1], a[i][2] - a[0][2]);
        frac t(-a[i][1] + a[0][1] + A, a[i][2] - a[0][2]);

        if (t < s)
          std::swap(s, t);

        if (t < frac(0, 1))
          continue;

        if (s < frac(0, 1))
          p.push_back({frac(0, 1), a[i][0]});
        else
          p.push_back({s, a[i][0]});

        p.push_back({t, -a[i][0]});
      } else {
        if (a[0][1] <= a[i][1] && a[i][1] <= a[0][1] + A)
          gain += a[i][0];
      }
    }

    std::sort(p.begin(), p.end(),
              [](const std::pair<frac, int>& lhs,
                 const std::pair<frac, int>& rhs) -> bool {
                if (lhs.first != rhs.first)
                  return lhs.first < rhs.first;
                return lhs.second > rhs.second;
              });

    int temp = gain;
    for (int i = 0; i < p.size(); ++i) {
      gain += p[i].second;
      temp = std::max(temp, gain);
    }
    ans = std::max(ans, temp);
  };

  for (int i = 0; i < n; ++i) {
    std::swap(a[i], a[0]);
    work();
  }

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

G - Security Camera 3

观察可得：向上的监控可以等价替换为向下的监控，向左的监控可以等价替换为向右的监控，所以考虑向下和向右的监控即可。

此外，对于向下的监控，一定是放在往上一步就出界或者有障碍的格子最优。向右的类似。

此时，有对于某个格子 \((i, j)\) ，以下两个条件至少要满足一个：

  1. 假设 \((i, j)\) 往左最远可达的格子为 \(\operatorname{leftmost(i, j)}\) ， \(\operatorname{leftmost(i, j)}\) 装了向右的监控。
  2. 假设 \((i, j)\) 往上最远可达的格子为 \(\operatorname{topmost(i, j)}\) ， \(\operatorname{topmost(i, j)}\) 装了向下的监控。

这种模型可以转化为最小割问题，具体就是按照以下方式建图：

  1. 对于每个格子 \((i, j)\) ，假设点 \(\operatorname{right(i, j)}\) 对应图中一个节点。从源点 \(S\) 往 \(\operatorname{right(i, j)}\) 连一条容量为 \(1\) 的边，割掉这条边表示在格子 \((i, j)\) 处安一个向右的监控。
  2. 对于每个格子 \((i, j)\) ，假设点 \(\operatorname{down(i, j)}\) 对应图中一个节点。从 \(\operatorname{down(i, j)}\) 往汇点 \(T\) 连一条容量为 \(1\) 的边，割掉这条边表示在格子 \((i, j)\) 处安一个向下的监控。
  3. 对于每个格子 \((i, j)\) ，从 \(\operatorname{right(\operatorname{leftmost(i, j)})}\) 向 \(\operatorname{down(\operatorname{topmost}(i, j))}\) 连一条容量为 \(1\) 的边，表示 \(S \to \operatorname{right(\operatorname{leftmost(i, j)})}\) 和 \(\operatorname{down(\operatorname{topmost}(i, j))} \to T\) 这两条边至少割一条，也即前面说的两个条件至少满足一个。

建出来的图源点到汇点的最大流就是答案，就是 Dinic 最大流最小割了，由于是单位网络，时间复杂度为 \(O((nm)^{1.5})\)。

AC代码 
// Problem: G - Security Camera 3
// Contest: AtCoder - キーエンスプログラミングコンテスト2022（AtCoder Beginner
// Contest 274） URL: https://atcoder.jp/contests/abc274/tasks/abc274_g 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;
using i128 = __int128_t;
using u128 = __uint128_t;

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

int main(int argc, char* argv[]) {
  CPPIO;

  Initialize();

  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    SolveCase(t);
  }
  return 0;
}

void Initialize() {}

template <typename CapacityType>
class MaxFlowGraph {
  struct Edge {
    int from, to;
    CapacityType capacity, flow;
    Edge() {}
    Edge(int _from, int _to, CapacityType _capacity, CapacityType _flow)
        : from(_from), to(_to), capacity(_capacity), flow(_flow) {}
  };

  int n_;
  int m_;
  std::vector<Edge> edges_;
  std::vector<std::vector<int>> adjacent_;

 public:
  explicit MaxFlowGraph(int n) : n_(n), m_(0), edges_(0), adjacent_(n) {}

  void AddEdge(int from, int to, CapacityType capacity) {
    assert(0 <= from and from < n_);
    assert(0 <= to and to < n_);

    edges_.emplace_back(from, to, capacity, 0);
    adjacent_[from].push_back(m_);
    ++m_;

    edges_.emplace_back(to, from, 0, 0);
    adjacent_[to].push_back(m_);
    ++m_;
  }

  CapacityType Dinic(int src, int dst) {
    const static CapacityType INF = std::numeric_limits<CapacityType>::max();
    std::vector<int> level(n_);
    std::vector<int> start_index(n_);

    std::function<bool()> bfs = [&]() -> bool {
      std::fill(level.begin(), level.end(), -1);

      std::queue<int> q;
      q.push(src);
      level[src] = 0;

      while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int edge_id : adjacent_[u]) {
          auto [from, to, capacity, flow] = edges_[edge_id];
          CapacityType residual_capacity = capacity - flow;
          if (residual_capacity > 0 && level[to] == -1) {
            level[to] = level[u] + 1;
            if (to == dst)
              break;
            q.push(to);
          }
        }
      }

      return level[dst] != -1;
    };

    std::function<CapacityType(int, CapacityType)> dfs =
        [&](int u, CapacityType max_augment) -> CapacityType {
      if (u == dst)
        return max_augment;

      if (max_augment == 0)
        return 0;

      CapacityType total_augment = 0;
      int i = start_index[u];
      for (; i < (int)adjacent_[u].size(); ++i) {
        int edge_id = adjacent_[u][i];
        auto [from, to, capacity, flow] = edges_[edge_id];
        if (level[to] == level[u] + 1) {
          CapacityType residual_capacity = capacity - flow;
          CapacityType new_augment =
              dfs(to, std::min(max_augment, residual_capacity));
          if (new_augment <= 0)
            continue;

          max_augment -= new_augment;
          total_augment += new_augment;
          edges_[edge_id].flow += new_augment;
          edges_[edge_id ^ 1].flow -= new_augment;

          if (max_augment == 0)
            break;
        }
      }
      start_index[u] = i;

      if (total_augment == 0)
        level[u] = -1;

      return total_augment;
    };

    CapacityType max_flow = 0;
    while (bfs()) {
      std::fill(start_index.begin(), start_index.end(), 0);
      CapacityType new_flow = dfs(src, INF);
      logd(new_flow);
      max_flow += new_flow;
    }

    return max_flow;
  }
};

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

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

  auto id = [&](int x, int y) { return x * m + y; };

  auto leftmost = [&](int i, int j) {
    while (j - 1 >= 0 && s[i][j - 1] == '.')
      --j;
    return id(i, j);
  };

  auto topmost = [&](int i, int j) {
    while (i - 1 >= 0 && s[i - 1][j] == '.')
      --i;
    return id(i, j);
  };

  auto right = [&](int x) { return x; };
  auto down = [&](int x) { return x + n * m; };

  MaxFlowGraph<int> g(2 * n * m + 2);
  int src = 2 * n * m, dst = src + 1;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (s[i][j] == '.') {
        g.AddEdge(src, right(id(i, j)), 1);
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (s[i][j] == '.') {
        g.AddEdge(right(leftmost(i, j)), down(topmost(i, j)), 1);
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (s[i][j] == '.') {
        g.AddEdge(down(id(i, j)), dst, 1);
      }
    }
  }

  std::cout << g.Dinic(src, dst) << "\n";
}

Ex - XOR Sum of Arrays

To be solved.

标签：std,AtCoder,return,Beginner,int,++,vector,274,operatorname
From： https://www.cnblogs.com/zengzk/p/16817694.html

相关文章

  • AtCoder Beginner Contest 263 Erasing Prime Pairs
    AtCoder传送门洛谷传送门题意有\(i\)种数，第\(i\)种数是\(a_i\)，有\(b_i\)个。每次可以选择两个数\(x,y\)满足\(x+y\)为质数，将它们删除。问最多能删多少次。......
  • AtCoder Regular Contest 151 C. 01 Game
    题目链接：https://atcoder.jp/contests/arc151/tasks/arc151_c1/*2博弈3归纳法，先开始处理单个情况，01是相对的40....1：必败50....0：必胜策略：在0边上放......
  • AtCoder Regular Contest 151
    A如果\(S\)和\(T\)的某一位相同，那么\(U\)无论怎么填都无法影响答案，为了字典序最小，一定填\(0\)。只考虑\(S\)和\(T\)不同的位置，假设有\(k\)位不同，易知\(k\)......
  • AtCoder Regular Contest 150
    A考虑枚举每一个区间，考虑如何\(\mathcalO(1)\)判断。如果区间符合条件当且仅当区间内没有\(0\)，区间外没有\(1\)。维护一个前缀和即可。点击查看代码#include<b......
  • atcoder ARC C 01-Game （博弈， Grundy数）
    https://atcoder.jp/contests/arc151/tasks/arc151_c题意：有1*n的的网格，有一些位置填有0和1，现在A和B进行游戏，往网格上填0/1，要保证相邻两个格子不能相同。A先手，问最后谁赢......
  • AtCoder Beginner Contest 273
    A-ARecursiveFunction签到题#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intread(){intx=0,f=1,ch=getchar();whil......
  • Atcoder Educational DP Contest 部分做题记录
    G.LongestPath拓扑排序dp#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intdp[100010],d[100010];voidsolve(){intn,m;scanf("%d......
  • [题解] Atcoder Regular Contest ARC 151 A B C D E 题解
    点我看题昨天刚打的ARC，题目质量还是不错的。A-EqualHammingDistances对于一个位置i，如果\(S_i=T_i\)，那么不管\(U\)的这个位置填什么，对到\(S\)和\(T\)的海明距离增量......
  • AtCoder Beginner Contest 273 题解
    第一次AtCoder体验，不是很好。ARecursiveFunction原题链接大水题。只要会递归就会做。点击查看代码#include<cstdio>#include<iostream>#definelllonglong......
  • AtCoder Regular Contest 150 B Make Divisible 贪心 整除分块
    给出一个A和B想要找到一个X和Y使得\(A+X|B+Y\).同时使得X+Y最小求出X+Y的最小值。值域是\([1,10^9]\)直接枚举X不太行会被某种数据卡掉。考虑正解：先固定K另\(\frac{B......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99