usingnamespace std; using longs = longlong; using ulongs = unsignedlonglong; using uint = unsigned;
inlineintnextInt() { int x = 0, f = 1, ch = getchar(); while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); return x * f; }
const uint N = 1e6 + 5; const uint M = 1e5 + 5; const uint mod = 998244353;
namespace StringHash { using hashArray = vector<ulongs>;
structhashMachine { int base, offset; hashArray pow;
staticintidx(constchar ch){return ch - 'a';}
explicithashMachine(int n, int b = 233, int k = 5): base(b), offset(k) { pow.resize(n); pow[0] = 1; for (int i = 1; i < n; ++ i) pow[i] = pow[i - 1] * base; }
voidmake(constchar *s, hashArray &var)const { int n = strlen(s); for (int i = 1; i <= n; ++ i) var[i] = var[i - 1] * base + idx(s[i - 1]) + offset; }
ulongs get(hashArray &var, int l, int r)const { if (!l) return var[r]; auto len = r - l; return var[r] - var[l] * pow[len]; } }; }
usingnamespace std; using longs = longlong; using uint = unsigned;
inlineintnextInt() { int x = 0, f = 1, ch = getchar(); while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); return x * f; }
fraction() = default; fraction(T u, T v): num(u), den(v) { if (!v) num = 1; elseif (v < 0) num = -u, den = -v; }
constexprstaticconstlongdouble $eps = 0; staticintsgn(longdouble x){return x < -$eps ? -1 : x > $eps;} static T gcd(T a, T b){return a < b ? gcd(b, a) : (!b ? a : gcd(b, a % b));}
autotoNumber()const{ return (longdouble) num / den; } intcompareTo(const fraction &rhs)const{returnsgn(this->toNumber() - rhs.toNumber());} boolequals(const fraction &rhs)const{return den == 0 || rhs.den == 0 ? den == rhs.den : !compareTo(rhs);} fraction &reduce(){ auto x = gcd(num, den); num /= x, den /= x; return *this;} autoatan2()const{return std::atan2(num, den);} fraction reciprocal()const{return {den, num};}
constlongdouble eps = fraction<longs>::$eps; intcompareTo(number x){return x < -eps ? -1 : x > eps;} intcompareTo(number a, number b){returncompareTo(a-b);}
point operator +(const point &rhs) const {return {x + rhs.x, y + rhs.y};} point operator -(const point &rhs) const {return {x - rhs.x, y - rhs.y};} number operator *(const point &rhs) const {return x * rhs.x + y * rhs.y;} point operator *(const number rhs) const {return {rhs * x, rhs * y};} point operator /(const number rhs) const {return {x / rhs, y / rhs};} point &operator +=(const point& rhs) {x += rhs.x; y += rhs.y; return *this;} point &operator -=(const point& rhs) {x -= rhs.x; y -= rhs.y; return *this;} point &operator *=(const number rhs) {x *= rhs; y *= rhs; return *this;} point &operator /=(const number rhs) {x /= rhs; y /= rhs; return *this;} booloperator ==(const point &rhs) const {return x == rhs.x && y == rhs.y;} booloperator !=(const point &rhs) const {return !(rhs == *this);}
number dot(const point &rhs)const{return x * rhs.x + y * rhs.y;} number cross(const point &rhs)const{return rhs.y * x - rhs.x * y;} autolength()const{returnsqrt(dot(*this));} autodistance(const point &b)const{return (*this - b).length();} autodistance(const point &ls, const point &rs)const {returnfabs((ls - *this).cross(rs - *this)) / ls.distance(rs);} point normal()const{return (x || y) ? *this / length() : point(0, 0);} autoangle()const{returnatan2(y, x);} point rotate(number a)const {number c = cos(a), s = sin(a); return {c * x - s * y, s * x + c * y};} point perpendicular()const{return {-y, x};} point symmetry()const{return {-x, -y};} number square()const{ return x * x + y * y; } }; }
using point = Geo::point; using frac = fraction<longs>;
constint N = 2060;
point a[N]; vector<frac> li;
frac cosLemmaSquare(const point &p1, const point &p2) { auto aa = p1.square(), bb = (p2 - p1).square(), cc = p2.square(); longs x = bb + cc - aa, f = sgn(x); return {f * x * x, 4ll * bb * cc}; }
longs n, ans = 1; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++ j) if (a[i].cross(a[j]) > 0) li.push_back(cosLemmaSquare(a[i], a[j])); sort(li.begin(), li.end(), [](frac &a, frac &b){return a.compareTo(b) < 0;}); longs len = li.size(), l = 0; while (l < len) { auto r = l; while (r < len && li[r] == li[l]) ++ r; ans = max(ans, r - l + 1); l = r; } li.clear(); } cout << ans << endl;
return0; }
需要注意的是,如果使用精准比较(“<” 和 “==” 运算符),中间结果可能会爆 long long,所以如果在 Windows 环境下则可以考虑在合适的误差下使用浮点比较(equals 和 compareTo 方法);
usingnamespace std; using longs = longlong; using uint = unsigned;
inlineintnextInt() { int x = 0, f = 1, ch = getchar(); while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); return x * f; }
template <classT> structfraction { T num, den;
fraction() = default; fraction(T u, T v): num(u), den(v) { if (!v) num = 1; elseif (v < 0) num = -u, den = -v; }
constexprstaticconstlongdouble $eps = 0; staticintsgn(longdouble x){return x < -$eps ? -1 : x > $eps;} static T gcd(T a, T b){return a < b ? gcd(b, a) : (!b ? a : gcd(b, a % b));}
autotoNumber()const{ return (longdouble) num / den; } intcompareTo(const fraction &rhs)const{returnsgn(this->toNumber() - rhs.toNumber());} boolequals(const fraction &rhs)const{return den == 0 || rhs.den == 0 ? den == rhs.den : !compareTo(rhs);} fraction &reduce(){ auto x = gcd(num, den); num /= x, den /= x; return *this;}
point operator +(const point &rhs) const {return {x + rhs.x, y + rhs.y};} point operator -(const point &rhs) const {return {x - rhs.x, y - rhs.y};} number operator *(const point &rhs) const {return x * rhs.x + y * rhs.y;} point operator *(const number rhs) const {return {rhs * x, rhs * y};} point operator /(const number rhs) const {return {x / rhs, y / rhs};} point &operator +=(const point& rhs) {x += rhs.x; y += rhs.y; return *this;} point &operator -=(const point& rhs) {x -= rhs.x; y -= rhs.y; return *this;} point &operator *=(const number rhs) {x *= rhs; y *= rhs; return *this;} point &operator /=(const number rhs) {x /= rhs; y /= rhs; return *this;} booloperator ==(const point &rhs) const {return x == rhs.x && y == rhs.y;} booloperator !=(const point &rhs) const {return !(rhs == *this);}
number dot(const point &rhs)const{return x * rhs.x + y * rhs.y;} number cross(const point &rhs)const{return rhs.y * x - rhs.x * y;} number length()const{returnsqrt(dot(*this));} number distance(const point &b)const{return (*this - b).length();} number distance(const point &ls, const point &rs)const {returnfabs((ls - *this).cross(rs - *this)) / ls.distance(rs);} point normal()const{return (x || y) ? *this / length() : point(0, 0);} number angle()const{returnatan2(y, x);} point rotate(number a)const {number c = cos(a), s = sin(a); return {c * x - s * y, s * x + c * y};} point perpendicular()const{return {-y, x};} point symmetry()const{return {-x, -y};} number square()const{ return x * x + y * y; } }; }
using point = Geo::point; using frac = fraction<longs>;
constint N = 2060;
point a[N]; vector<frac> li;
frac getSlope(const point &ll, const point &rr = {0, 0}) { auto ld = ll.square(), rd = rr.square(); if (!ld) ld = 1; if (!rd) rd = 1; return {rr.y * ld - ll.y * rd, rr.x * ld - ll.x * rd}; }
longs n, ans = 1; cin >> n; for (int i = 0; i < n; ++ i) cin >> a[i].x >> a[i].y; for (int i = 0; i < n; ++ i) { frac tmp = getSlope(a[i]); for (int j = i + 1; j < n; ++ j) { frac ff = getSlope(a[i], a[j]); if (ff.equals(tmp)) continue; li.push_back(ff); } sort(li.begin(), li.end()); auto len = li.size(); for (int l = 0, r = 0; l < len;) { r = l; while (r < len && li[r].equals(li[l])) ++ r; ans = max(ans, r - l + 1ll); l = r; } li.clear(); } cout << ans << endl;
inlineintnextInt() { int x = 0, f = 1, ch = getchar(); while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); return x * f; }
usingnamespace std; using longs = longlong; using uint = unsigned;
inlineintnextInt() { int x = 0, f = 1, ch = getchar(); while (!isdigit(ch)) if (ch == '-') f = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); return x * f; }
constint N = 5005; int mat[N][N];
inline longs gcd(longs a, longs b) { if (a < b) gcd(b, a); if (mat[a][b]) return mat[a][b]; if (!b) return mat[a][b] = a; elsereturn mat[a][b] = gcd(b, a % b); }
namespace STtable2D_simple { int log[N], high[N][N]; uint _log; int row, col, sq, _max;
template <classT> T max4(T t1, T t2, T t3, T t4) { returnmax(max(t1, t2), max(t3, t4)); }
autoimport = [] { for (int i = 1; i <= row; ++ i) for (int j = 1; j <= col; ++ j) high[i][j] = mat[i][j]; _log = log[sq]; };
voidinit(uint k) { log[0] = -1; for (uint i = 1; i <= k; ++ i) log[i] = log[i >> 1u] + 1; memset(high, 0x80, sizeof(high)); import(); }
voidmake(uint a, uint b) { for (uint p = 0; p < _log; ++ p) for (int i = 1; i + (1u << p) <= a; ++ i) for (int j = 1; j + (1u << p) <= b; ++ j) high[i][j] = max4<int>( high[i][j], high[i + (1u << p)][j + (1u << p)], high[i + (1u << p)][j], high[i][j + (1u << p)] ); }
autosolve(int n, int m, int k) { row = n, col = m, sq = k; init(k); make(n, m); longs ans = 0; constint $row = n - k + 1, $col = m - k + 1; for (int i = 1; i <= $row; ++ i) for (int j = 1; j <= $col; ++ j) query(i, j), ans += _max; return ans; } }
int n, m, k; cin >> n >> m >> k; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) gcd(i, j); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) mat[i][j] = i * j / mat[i][j]; auto xx = STtable2D_simple::solve(n, m, k); cout << xx << endl;
return0; }
然后发现这个题目似乎并不需要“二维单调队列”,只需要一维单调队列横纵两次就可以了== 毕竟 ST 表都可以偷懒到这种程度,所以可以过也是可以过吧(
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (!Gcd[i][j]) for (int k = 1; k * i <= n && k * j <= m; k ++) Gcd[k * i][k * j] = k, A[k * i][k * j] = i * j * k;
这也是某种筛法,只是出题人也忘记它叫什么名字了== 但是还是看起来就很稳健的记忆化搜索比较好写(
值得一提的是,在比赛的时候有不少人都是“猜测”最大值出现在左下角/右下角 10 步位置内的,也都成功 AC 了。