VP 记录 - 2018 ICPC 亚洲区域赛 (沈阳)

发表于 更新于 分类于 ， ， 合著者：Foi 本文字数： 428 阅读时长 ≈ 2 分钟

比赛链接

题目概览

题号 标题 做法
A Sockpuppets
B Sequences Generator
C Insertion Sort 找规律
D Diameter of a Tree
E The Kouga Ninja Scrolls
F Counting Sheep in Ami Dongsuo
G Best ACMer Solves the Hardest Problem 暴力
H Rainbow Graph
I Distance Between Sweethearts
J How Much Memory Your Code Is Using? 模拟
K Let the Flames Begin Josephus 问题
L Machining Disc Rotors 计算几何
M Renaissance Past in Nancy

A - Sockpuppets

代码参考

Show code

B - Sequences Generator

代码参考

Show code

C - Insertion Sort

代码参考

Show code

C.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define inc(i) (++(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define int long long
using namespace std;
signed main() {
  int T, Case = 0;
  cin >> T;
  while (T--) {
    inc(Case);
    int n, k, P;
    cin >> n >> k >> P;
    k = min(n, k);
    int Ret = 1;
    Rep(i, 1, k)(Ret *= i) %= P;
    Ret = Ret * ((n - k - 1) * (n - k - 1) % P + (k + 1) * (n - k) % P) % P;
    cout << "Case #" << Case << ": " << Ret << '\n';
  }
  return 0;
}

D - Diameter of a Tree

代码参考

Show code

E - The Kouga Ninja Scrolls

代码参考

Show code

F - Counting Sheep in Ami Dongsuo

代码参考

Show code

G - Best ACMer Solves the Hardest Problem

代码参考

Show code

G.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
const int64_t N = 10000001;
const int64_t sqrtN = 3163;
vector<pair<int64_t, int64_t>> con[N];
int64_t mp[6001][6001];
bool flag[6001][6001];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int64_t i = 0; i <= sqrtN; ++i)
    for (int64_t j = i; j <= sqrtN; ++j)
      if (i * i + j * j < N) con[i * i + j * j].emplace_back(i, j);
  auto runif = [&](int64_t x, int64_t y, function<void(int64_t, int64_t)> f) {
    if (0 <= x && x <= 6000 && 0 <= y && y <= 6000 && flag[x][y]) f(x, y);
  };
  auto runf =
    [&](int64_t x, int64_t y, int64_t k, function<void(int64_t, int64_t)> f) {
      for (auto [x0, y0] : con[k]) {
        if (!x0 && !y0) {
          runif(x, y, f);
        } else if (!x0) {
          runif(x, y - y0, f);
          runif(x, y + y0, f);
          runif(x - y0, y, f);
          runif(x + y0, y, f);
        } else if (!y0) {
          runif(x - x0, y, f);
          runif(x + x0, y, f);
          runif(x, y - x0, f);
          runif(x, y + x0, f);
        } else {
          runif(x - x0, y - y0, f);
          runif(x - x0, y + y0, f);
          runif(x + x0, y - y0, f);
          runif(x + x0, y + y0, f);
          if (x0 == y0) continue;
          runif(x - y0, y - x0, f);
          runif(x - y0, y + x0, f);
          runif(x + y0, y - x0, f);
          runif(x + y0, y + x0, f);
        }
      }
    };
  int64_t T;
  cin >> T;
  for (int64_t _ = 1, n, m; _ <= T; ++_) {
    cout << "Case #" << _ << ":\n";
    vector<pair<int64_t, int64_t>> Point;
    cin >> n >> m;
    for (int64_t i = 1, x, y, w; i <= n; ++i) {
      cin >> x >> y >> w;
      mp[x][y] = w;
      flag[x][y] = 1;
      Point.emplace_back(x, y);
    }
    for (int64_t i = 1, op, x, y, lastans = 0; i <= m; ++i) {
      cin >> op >> x >> y;
      x = ((x + lastans) % 6000) + 1;
      y = ((y + lastans) % 6000) + 1;
      switch (op) {
        int64_t k, w;
        case 1:
          cin >> w;
          mp[x][y] = w;
          flag[x][y] = 1;
          Point.emplace_back(x, y);
          break;
        case 2: mp[x][y] = flag[x][y] = 0; break;
        case 3:
          cin >> k >> w;
          runf(x, y, k, [&](int64_t xx, int64_t yy) { mp[xx][yy] += w; });
          break;
        case 4:
          cin >> k;
          lastans = 0;
          runf(x, y, k, [&](int64_t xx, int64_t yy) { lastans += mp[xx][yy]; });
          cout << lastans << '\n';
          break;
      }
    }
    if (!Point.empty())
      for (auto &&[x, y] : Point) mp[x][y] = flag[x][y] = 0;
  }
  return 0;
}

H - Rainbow Graph

代码参考

Show code

I - Distance Between Sweethearts

代码参考

Show code

J - How Much Memory Your Code Is Using?

代码参考

Show code

J.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#define inc(i) (++(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define int long long
using namespace std;
string S;
int getval(string S) {
  int Base, Begin, tot = 0, flag = 0;
  if (S[0] == 'b') Base = 1, Begin = 5;
  if (S[0] == 'c') Base = 1, Begin = 5;
  if (S[0] == 'i') Base = 4, Begin = 4;
  if (S[0] == 'f') Base = 4, Begin = 6;
  if (S[0] == 'd') Base = 8, Begin = 7;
  if (S[0] == 'l' && S[5] == 'l') Base = 8, Begin = 10;
  if (S[0] == '_') Base = 16, Begin = 9;
  if (S[0] == 'l' && S[5] == 'd') Base = 16, Begin = 12;
  Rep(i, Begin, S.size()) {
    if (S[i] == '[') flag = 1;
    if (flag && S[i] >= '0' && S[i] <= '9') tot = tot * 10 + S[i] - '0';
  }
  if (tot == 0) tot = 1;
  return Base * tot;
}
int Solve() {
  int n;
  cin >> n;
  getchar();
  int Ret = 0;
  Rep(i, 1, n) {
    getline(cin, S);
    Ret += getval(S);
  }
  Ret = (Ret / 1024) + (bool)(Ret % 1024);
  return Ret;
}
signed main() {
  int T;
  cin >> T;
  Rep(Case, 1, T) {
    int Ret = Solve();
    cout << "Case #" << Case << ": " << Ret << "\n";
  }
  return 0;
}

K - Let the Flames Begin

代码参考

Show code

K.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define inc(i) (++(i))
#define dec(i) (--(i))
#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))
#define int long long
using namespace std;
int n, m, k;
int Get1(int n, int m) {
  if (m == 1) return (k - 1) % n;
  else return (Get1(n - 1, m - 1) + k) % n;
}
int Get2(int n, int m) {
  if (k == 1) return m - 1;
  int N = n - m + 1, Ret = Get1(N, 1);
  dec(m);
  while (m > 0) {
    int tem = (N - Ret) / (k - 1);
    if (m <= tem) return Ret = (Ret + m * k) % (N + m);
    else {
      Ret = (Ret + tem * k) % (N + tem);
      Ret = (Ret + k) % (N + tem + 1);
      N += tem + 1, m -= tem + 1;
    }
  }
  return Ret;
}
signed main() {
  int T;
  cin >> T;
  Rep(Case, 1, T) {
    int Ret;
    cin >> n >> m >> k;
    if (m <= 2000000) Ret = Get1(n, m) + 1;
    else Ret = Get2(n, m) + 1;
    cout << "Case #" << Case << ": " << Ret << '\n';
  }
  return 0;
}

L - Machining Disc Rotors

代码参考

Show code

L.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using data_t = double;
constexpr data_t EPS = 1e-8;
constexpr ptrdiff_t sgn(data_t lhs) { return lhs < -EPS ? -1 : lhs > EPS; }
constexpr bool is_negative(data_t x) { return sgn(x) & 2; }
constexpr bool is_zero(data_t x) { return !sgn(x); }
constexpr bool is_positive(data_t x) { return (sgn(x) + 1) & 2; }
constexpr ptrdiff_t comp(data_t lhs, data_t rhs) { return sgn(lhs - rhs); }
constexpr bool is_less(data_t lhs, data_t rhs) {
  return is_negative(lhs - rhs);
}
constexpr bool is_equal(data_t lhs, data_t rhs) { return is_zero(lhs - rhs); }
constexpr bool is_greater(data_t lhs, data_t rhs) {
  return is_positive(lhs - rhs);
}
enum RELA_CC { lyingin_cc, touchin_cc, intersect_cc, touchex_cc, lyingout_cc };
enum RELA_CP { outside_cp, onborder_cp, inside_cp };
struct Point {
  data_t x, y;
  constexpr Point(data_t x = data_t{}, data_t y = data_t{}): x(x), y(y) {}
  constexpr Point &operator*=(data_t n) {
    this->x *= n;
    this->y *= n;
    return *this;
  }
  constexpr Point operator*(data_t n) const { return Point(*this) *= n; }
  constexpr Point &operator/=(data_t n) {
    this->x /= n;
    this->y /= n;
    return *this;
  }
  constexpr Point operator/(data_t n) const { return Point(*this) /= n; }
  constexpr Point &operator+=(const Point &rhs) {
    this->x += rhs.x;
    this->y += rhs.y;
    return *this;
  }
  constexpr Point operator+(const Point &rhs) const {
    return Point(*this) += rhs;
  }
  constexpr Point &operator-=(const Point &rhs) {
    this->x -= rhs.x;
    this->y -= rhs.y;
    return *this;
  }
  constexpr Point operator-(const Point &rhs) const {
    return Point(*this) -= rhs;
  }
  constexpr Point operator-() const { return Point{-x, -y}; }
  constexpr bool operator<(const Point &rhs) const {
    auto c = comp(x, rhs.x);
    if (c) return c >> 1;
    return comp(y, rhs.y) >> 1;
  }
  friend constexpr data_t operator^(const Point &lhs, const Point &rhs) {
    return lhs.x * rhs.y - lhs.y * rhs.x;
  }
  friend constexpr data_t cross_mul(const Point &lhs, const Point &rhs) {
    return lhs ^ rhs;
  }
  constexpr auto norm() const { return x * x + y * y; };
  constexpr auto abs() const { return sqrt(norm()); };
  constexpr Point &do_rot90() {
    data_t tmp = x;
    x = -y;
    y = tmp;
    return *this;
  };
  constexpr Point &do_unit() { return *this /= abs(); };
};
constexpr data_t dist_PP(const Point &lhs, const Point &rhs) {
  return std::hypot(lhs.x - rhs.x, lhs.y - rhs.y);
}
constexpr data_t cross(const Point &p1, const Point &p2, const Point &p3) {
  return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
constexpr ptrdiff_t
sgn_cross(const Point &p1, const Point &p2, const Point &p3) {
  return sgn(cross(p1, p2, p3));
}
struct Circle {
  Point o;
  data_t r;
  Circle() = default;
  constexpr Circle(const data_t &c_x, const data_t &c_y, data_t r_)
    : o(c_x, c_y), r(r_) {}
  constexpr RELA_CC relation_C(const Circle &c2) const {
    data_t d = dist_PP(o, c2.o);
    if (is_greater(d, r + c2.r)) return RELA_CC::lyingout_cc;
    if (is_equal(d, r + c2.r)) return RELA_CC::touchex_cc;
    if (is_greater(d, std::abs(r - c2.r))) return RELA_CC::intersect_cc;
    if (is_equal(d, std::abs(r - c2.r))) return RELA_CC::touchin_cc;
    return RELA_CC::lyingin_cc;
  }
  constexpr RELA_CP relation_P(const Point &p) const {
    data_t d = dist_PP(o, p);
    if (is_less(d, r)) return RELA_CP::inside_cp;
    if (is_equal(d, r)) return RELA_CP::onborder_cp;
    return RELA_CP::outside_cp;
  }
};
vector<Point> ins_CC(const Circle &c1, const Circle &c2) {
  assert(!is_equal(c1.o.x, c2.o.x) || !is_equal(c1.o.y, c2.o.y) ||
         !is_equal(c1.r, c2.r));
  auto state = c1.relation_C(c2);
  if (state == RELA_CC::lyingin_cc || state == RELA_CC::lyingout_cc) return {};
  data_t d = std::min(dist_PP(c1.o, c2.o), c1.r + c2.r);
  data_t y = (c1.r * c1.r - c2.r * c2.r + d * d) / (2 * d),
         x = sqrt(c1.r * c1.r - y * y);
  Point dr = (c2.o - c1.o).do_unit();
  Point q1 = c1.o + dr * y, q2 = dr.do_rot90() * x;
  return {q1 - q2, q1 + q2};
}
struct ConvexHull {
  vector<Point> vs;
  size_t next(size_t idx) const { return idx + 1 == vs.size() ? 0 : idx + 1; }
  explicit ConvexHull(const vector<Point> &vs_): vs(vs_) {
    ptrdiff_t sz = vs.size();
    if (sz <= 1) return;
    std::sort(vs.begin(), vs.end());
    vector<Point> cvh(sz * 2);
    ptrdiff_t sz_cvh = 0;
    for (ptrdiff_t i = 0; i < sz; cvh[sz_cvh++] = vs[i++])
      while (sz_cvh > 1 &&
             sgn_cross(cvh[sz_cvh - 2], cvh[sz_cvh - 1], vs[i]) <= 0)
        --sz_cvh;
    for (ptrdiff_t i = sz - 2, t = sz_cvh; ~i; cvh[sz_cvh++] = vs[i--])
      while (sz_cvh > t &&
             sgn_cross(cvh[sz_cvh - 2], cvh[sz_cvh - 1], vs[i]) <= 0)
        --sz_cvh;
    cvh.resize(sz_cvh - 1);
    vs = cvh;
  }
  data_t diameter() const {
    size_t sz = vs.size();
    if (sz <= 1) return data_t{};
    size_t is = 0, js = 0;
    for (size_t k = 1; k < sz; ++k) {
      is = vs[k] < vs[is] ? k : is;
      js = vs[js] < vs[k] ? k : js;
    }
    size_t i = is, j = js;
    data_t ret = dist_PP(vs[i], vs[j]);
    do {
      (++(cross_mul(vs[next(i)] - vs[i], vs[next(j)] - vs[j]) >= 0 ? j : i)) %=
        sz;
      ret = std::max(ret, dist_PP(vs[i], vs[j]));
    } while (i != is || j != js);
    return ret;
  }
};
auto solve([[maybe_unused]] int t_ = 0) -> void {
  i64 n, r;
  cin >> n >> r;
  Circle c0(0, 0, r);
  vector<Circle> vc;
  for (i64 i = 1, xx, yy, rr; i <= n; ++i) {
    cin >> xx >> yy >> rr;
    Circle c1(xx, yy, rr);
    auto ans = c0.relation_C(c1);
    if (ans != RELA_CC::intersect_cc) continue;
    vc.push_back(c1);
  }
  vector<Point> vp1;
  for (auto const &c : vc) {
    auto ps = ins_CC(c0, c);
    for (auto const &p : ps) {
      vp1.push_back(p);
      vp1.push_back(-p);
    }
  }
  vector<Point> vp;
  for (auto const &p : vp1) {
    bool f = 0;
    for (auto const &c : vc)
      if (c.relation_P(p) == RELA_CP::inside_cp) {
        f = 1;
        break;
      }
    if (f) continue;
    vp.push_back(p);
  }
  cout << ConvexHull(vp).diameter() << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  cout << fixed << setprecision(15);
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) {
    cout << "Case #" << i_ + 1 << ": ";
    solve(i_);
  }
  return 0;
}

M - Renaissance Past in Nancy

代码参考

Show code