2018 German Collegiate Programming Contest (GCPC 18)

题目链接

Problem:

http://codeforces.com/gym/102021/attachments/download/8067/2018-german-collegiate-programming-contest-gcpc-18-en.pdf

Problem B Battle Royale

求两点不经过小圆的最短路径

当两点可以直线段到达时两点距离即为最短距离

当两点中间被小圆阻挡时两切线段加圆上一段小弧为最短距离

#include <bits/stdc++.h>
typedef double db;
const db eps = 1e-9;

namespace Geometry {
  int Sgn(db k) {return fabs(k) < eps ? 0 : (k < 0 ? -1 : 1);}
  int Cmp(db k1, db k2) {return Sgn(k1 - k2);}
  db max(db k1, db k2) {return Cmp(k1, k2) > 0 ? k1 : k2;}
  db min(db k1, db k2) {return Cmp(k1, k2) < 0 ? k1 : k2;}
  struct point {db x, y;};
  point operator + (point k1, point k2) {return (point){k1.x + k2.x, k1.y + k2.y};}
  point operator - (point k1, point k2) {return (point){k1.x - k2.x, k1.y - k2.y};}
  db operator * (point k1, point k2) {return k1.x * k2.x + k1.y * k2.y;}
  db operator ^ (point k1, point k2) {return k1.x * k2.y - k1.y * k2.x;}
  db GetDisP2P(point k1, point k2) {return sqrt((k2 - k1) * (k2 - k1));}
  db GetAng(point k1, point k2) {return fabs(atan2(fabs(k1 ^ k2), k1 * k2));}
  struct line {point s, t;};
  typedef line seg;
  db GetLen(seg k) {return sqrt((k.t - k.s) * (k.t - k.s));}
  db GetDisP2Line(point k1, line k2) {return fabs((k1 - k2.s) ^ (k2.t - k2.s)) / GetLen(k2);}
  db GetDisP2Seg(point k1, seg k2) {
    if (Sgn((k1 - k2.s) * (k2.t - k2.s)) < 0 || Sgn((k1 - k2.t) * (k2.s - k2.t)) < 0) {
      return min(GetDisP2P(k1, k2.s), GetDisP2P(k1, k2.t));
    }
    return GetDisP2Line(k1, k2);
  }
  struct circle {point o; db r;};
}
using namespace Geometry;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);
  std::cout << std::fixed << std::setprecision(10);

  point s, t;
  std::cin >> s.x >> s.y;
  std::cin >> t.x >> t.y;
  circle blue, red;
  std::cin >> blue.o.x >> blue.o.y >> blue.r;
  std::cin >> red.o.x >> red.o.y >> red.r;

  if (Cmp(GetDisP2Seg(red.o, (seg){s, t}), red.r) >= 0) {
    std::cout << GetDisP2P(s, t) << '\n';
    return 0;
  }

  db dis_o2s = GetDisP2P(red.o, s), dis_o2t = GetDisP2P(red.o, t);
  db ang = GetAng(s - red.o, t - red.o) - acos(red.r / dis_o2s) - acos(red.r / dis_o2t);
  db ans = sqrt(dis_o2s * dis_o2s - red.r * red.r) + sqrt(dis_o2t * dis_o2t - red.r * red.r);
  ans += ang * red.r;

  std::cout << ans << '\n';
  return 0;
}

Problem C Coolest Ski Route

求有向图上最长路径

记忆化搜索求达到每个点的最长路径取最大值即可

#include <bits/stdc++.h>

struct edge {int pre, c;};
std::vector<std::vector<edge>> g;
std::vector<bool> vis;
std::vector<int> dis;

int Dfs(int u) {
  if (vis[u]) return dis[u];
  int ret = 0;
  for (auto &e : g[u]) {
    ret = std::max(ret, Dfs(e.pre) + e.c);
  }
  vis[u] = true;
  dis[u] = ret;
  return ret;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, m; std::cin >> n >> m;
  g.resize(n);
  for (int i = 0, u, v, c; i < m; ++i) {
    std::cin >> u >> v >> c;
    --u; --v;
    g[v].push_back((edge){u, c});
  }

  int ans = 0;
  vis.assign(n, false);
  dis.assign(n, 0);
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) ans = std::max(ans, Dfs(i));
  }

  std::cout << ans << '\n';
  return 0;
}

Problem E Expired License

用字符串读取浮点数并转化为长整型(直接读入浮点数再扩大会有精度损失),对两数进行类约分操作判断是否都为素数即可

#include <bits/stdc++.h>
const int maxn = 1e7 + 5;

bool is_prime[maxn];
std::vector<int> prime;

void Sieve() {
  memset(is_prime, true, sizeof(is_prime));
  for (long long i = 2; i < maxn; ++i) {
    if (is_prime[i]) prime.emplace_back(i);
    for (auto &p : prime) {
      if (p * i >= maxn) break;
      is_prime[i * p] = false;
    }
  }
  is_prime[0] = is_prime[1] = false;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  Sieve();

  int t; std::cin >> t;
  for (int cas = 1; cas <= t; ++cas) {
    std::string a, b; std::cin >> a >> b;

    long long n = 0, m = 0;
    for (auto &s : a) if (isdigit(s)) n = n * 10 + (s - '0');
    for (auto &s : b) if (isdigit(s)) m = m * 10 + (s - '0');

    long long gcd = std::__gcd(n, m);
    n /= gcd; m /= gcd;

    if (n == m) std::cout << 2 << ' ' << 2 << '\n';
    else if (is_prime[n] && is_prime[m]) std::cout << n << ' ' << m << '\n';
    else std::cout << "impossible\n";
  }
  return 0;
}

Problem I It's Time for a Montage

$n$ 个 $1\sim n$ 级别的英雄和 $n$ 个 $1\sim n$ 级别的怪兽,高级别英雄可以击败任意低等级怪兽,当级别相同时英雄攻击力大于等于怪兽时才可将其击败,每训练一天英雄攻击力 $+1$ ,求击败怪兽最少训练天数

二分结果(训练天数), 判断是否可以击败怪兽即可

#include <bits/stdc++.h>

int n;
std::vector<int> h;
std::vector<int> v;

bool Check(int x) {
  for (int i = 0; i < n; ++i) {
    if (h[i] + x < v[i]) return false;
    if (h[i] + x > v[i]) return true;
  }
  return true;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  std::cin >> n;
  h.assign(n, 0); v.assign(n, 0);
  for (auto &it : h) std::cin >> it;
  for (auto &it : v) std::cin >> it;

  int l = 0, r = 1e3 + 5, ans;
  while (l <= r) {
    int m = (l + r) >> 1;
    if (Check(m)) {
      ans = m;
      r = m - 1;
    }
    else l = m + 1;
  }

  std::cout << ans << '\n';
  return 0;
}

Problem L Logic Puzzle

$n$ 行 $m$ 列的扫雷棋盘(扩大一圈给出), 求地雷分布图

从棋盘外圈向内圈查找地雷

在每圈中从四个角开始再向中间查找地雷

#include <bits/stdc++.h>

std::vector<std::vector<int>> clue;
std::vector<std::vector<bool>> col;

void Change(int x, int y) {
  for (int i = -1; i < 2; ++i) {
    for (int j = -1; j < 2; ++j) {
      if (clue[x + i][y + j] <= 0) return;
    }
  }
  col[x][y] = true;
  for (int i = -1; i < 2; ++i) {
    for (int j = -1; j < 2; ++j) {
      --clue[x + i][y + j];
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int h, w; std::cin >> h >> w;
  clue = std::vector<std::vector<int>>(h + 2, std::vector<int>(w + 2, 0));
  for (int i = 0; i < h + 2; ++i)
    for (int j = 0; j < w + 2; ++j)
      std::cin >> clue[i][j];

  col = std::vector<std::vector<bool>>(h + 2, std::vector<bool>(w + 2, false));

  int cir = (std::min(h, w) + 1) / 2;
  int l = 1, r = w, t = 1, b = h;
  for (int k = 0; k < cir; ++k) {
    Change(t, l); Change(t, r);
    Change(b, l); Change(b, r);

    int m = (l + r + 1) / 2;

    for (int i = l + 1; i < m; ++i) Change(t, i);
    for (int i = r - 1; i >= m; --i) Change(t, i);
    for (int i = l + 1; i < m; ++i) Change(b, i);
    for (int i = r - 1; i >= m; --i) Change(b, i);

    m = (t + b + 1) / 2;

    for (int i = t + 1; i < m; ++i) Change(i, l);
    for (int i = b - 1; i >= m; --i) Change(i, l);
    for (int i = t + 1; i < m; ++i) Change(i, r);
    for (int i = b - 1; i >= m; --i) Change(i, r);

    if (l != r) {
      ++l;
      --r;
    }
    if (t != b) {
      ++t;
      --b;
    }
  }

  for (int i = 0; i < h + 2; ++i) {
    for (int j = 0; j < w + 2; ++j) {
      if (clue[i][j] > 0) {
        std::cout << "impossible\n";
        return 0;
      }
    }
  }

  for (int i = 1; i <= h; ++i) {
    for (int j = 1; j <= w; ++j) {
      std::cout << (col[i][j] ? 'X' : '.');
    }
    std::cout << '\n';
  }
  return 0;
}
Last modification:April 4th, 2019 at 09:58 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment