比赛链接

题目概览

题号

标题

做法

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

代码参考

B - Sequences Generator

代码参考

C - Insertion Sort

代码参考

C.cppview raw1234567891011121314151617181920#include #define inc(i) (++(i))#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))#define int long longusing 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

代码参考

E - The Kouga Ninja Scrolls

代码参考

F - Counting Sheep in Ami

Dongsuo

代码参考

G - Best ACMer Solves

the Hardest Problem

代码参考

G.cppview raw1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include using namespace std;const int64_t N = 10000001;const int64_t sqrtN = 3163;vector> 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 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 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> 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

代码参考

I - Distance Between

Sweethearts

代码参考

J - How Much Memory Your

Code Is Using?

代码参考

J.cppview raw1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #define inc(i) (++(i))#define Rep(i, a, b) for (int i = (a), i##Limit = (b); i <= i##Limit; inc(i))#define int long longusing 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

代码参考

K.cppview raw1234567891011121314151617181920212223242526272829303132333435363738#include #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 longusing 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

代码参考

L.cppview raw123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199#include 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_tsgn_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 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 vs; size_t next(size_t idx) const { return idx + 1 == vs.size() ? 0 : idx + 1; } explicit ConvexHull(const vector &vs_): vs(vs_) { ptrdiff_t sz = vs.size(); if (sz <= 1) return; std::sort(vs.begin(), vs.end()); vector 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 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 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 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

代码参考