AtCoder Beginner Contest 274

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)\) ，以下两个条件至少要满足一个：

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

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

对于每个格子 \((i, j)\) ，假设点 \(\operatorname{right(i, j)}\) 对应图中一个节点。从源点 \(S\) 往 \(\operatorname{right(i, j)}\) 连一条容量为 \(1\) 的边，割掉这条边表示在格子 \((i, j)\) 处安一个向右的监控。
对于每个格子 \((i, j)\) ，假设点 \(\operatorname{down(i, j)}\) 对应图中一个节点。从 \(\operatorname{down(i, j)}\) 往汇点 \(T\) 连一条容量为 \(1\) 的边，割掉这条边表示在格子 \((i, j)\) 处安一个向下的监控。
对于每个格子 \((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.

原文地址：http://www.cnblogs.com/zengzk/p/16817694.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性

AtCoder Beginner Contest 274

E – Booster

F – Fishing

G – Security Camera 3

Ex – XOR Sum of Arrays

排行榜展示

3D打印机glb模型下载-机械glb模型

树glb模型下载-树2

水稻glb模型下载-水稻1

变电箱1glb模型下载-机械glb模型

树glb模型下载-树3

模型

3D打印机glb模型下载-机械glb模型

树glb模型下载-树3

树glb模型下载-树2

树glb模型下载-树1

变电箱1glb模型下载-机械glb模型

水稻glb模型下载-水稻1

AtCoder Beginner Contest 274

排行榜展示

标签

模型