B、Boundary
参考兰子大佬的题解
问题大概就是给你二维平面的n个点，坐标都是整数，问你选取某一个点为圆心（这个点不一定要是给出的n个点中一个）使得在这个点为圆心过原点的情况下覆盖到给出的n点中最多的点，问最多覆盖几个点！
其实知道方法是可以写出来的，比赛的时候最开始看到0/80+……就觉得这玩意不简单，而且英语小白的我一开始没读出加粗的那句话，直接二重枚举认为给出的点才可能是圆心，WA的理所当然。。听说map计数给卡了常数太大了。。用了二元组去排序计算，还有知识点就是知道三个点的平面坐标求圆心坐标。。这玩意直接推式子再用克莱姆法则替换也能算到，涉及线性代数的知识）马上大二了哎嘿。这里用的是兰子大佬的求法，看起来比较好记，而且和克莱姆法则推出来的是差不多的。这样把全部的圆心计算出来再排下序，根据圆心重合的情况下去统计次数，每重合一个圆心说明选取这个圆心覆盖的点就+1，取最大值即可。)果然我的话有待提高
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<double, double>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
#define x first
#define y second
const int N = 2e6 + 7;
const double eps = 1e-6;
pai s[2005], p[N];
pai yuanxin(pai a, pai b, pai c) { //已知三点求圆心坐标下面有仔细的步骤，用了克莱姆法则
double A1 = 2 * b.x - 2 * a.x, B1 = 2 * a.y - 2 * b.y, C1 = a.y * a.y + b.x * b.x - a.x * a.x - b.y * b.y;
double A2 = 2 * c.x - 2 * b.x, B2 = 2 * b.y - 2 * c.y, C2 = b.y * b.y + c.x * c.x - b.x * b.x - c.y * c.y;
pai center;
center.x = (C1 * B2 - C2 * B1) / (A1 * B2 - A2 * B1);
center.y = (A1 * C2 - A2 * C1) / (A1 * B2 - A2 * B1);
return center;
}
int main() {
int n = read(), k = 0;
for (int i = 1; i <= n; ++i) s[i].x = read(), s[i].y = read();
pai z = { 0,0 };
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (fabs(s[i].x * s[j].y - s[i].y * s[j].x) > eps) { //和原点三点不共线
pai tmp = yuanxin(s[i], s[j], z);
p[++k] = tmp;
}
if (!k) return cout << 1, 0;
sort(p + 1, p + 1 + k);
int cnt = 1, ans = 1;
for (int i = 1; i < k; ++i)
if (fabs(p[i].x - p[i + 1].x) < eps and fabs(p[i].y - p[i + 1].y) < eps)
++cnt, ans = max(ans, cnt); //同一个圆心的话，这个圆心统计的点数+1
else cnt = 1; //否则归1，cnt来到算到这个圆心的点这里
for (int i = 1; i <= n; ++i)
if (i * (i - 1) == ans * 2) return cout << i, 0;
return 0;
}
/*
通过三个点到圆心距离相等建立方程：
(pt1.x-center.x)²-(pt1.y-center.y)²=radius² 式子(1)
(pt2.x-center.x)²-(pt2.y-center.y)²=radius² 式子(2)
(pt3.x-center.x)²-(pt3.y-center.y)²=radius² 式子(3)
式子(1)-式子(2)得：
pt1.x²+pt2.y²-pt1.y²-pt2.x²+2*center.x*pt2.x-2*center.x*pt1.x+2*center.y*pt1.y-2*center.y*pt2.y-=0
式子(2)-式子(3)得：
pt2.x²+pt3.y²-pt2.y²-pt3.x²+2*center.x*pt3.x-2*center.x*pt2.x+2*center.y*pt2.y-2*center.y*pt3.y-=0
整理上面的两个式子得到：
(2*pt2.x-2*pt1.x)*center.x+(2*pt1.y-2*pt2.y)*center.y=pt1.y²+pt2.x²-pt1.x²-pt2.y²
(2*pt3.x-2*pt2.x)*center.x+(2*pt2.y-2*pt3.y)*center.y=pt2.y²+pt3.x²-pt2.x²-pt3.y²
令：
A1=2*pt2.x-2*pt1.x B1=2*pt1.y-2*pt2.y C1=pt1.y²+pt2.x²-pt1.x²-pt2.y²
A2=2*pt3.x-2*pt2.x B2=2*pt2.y-2*pt3.y C2=pt2.y²+pt3.x²-pt2.x²-pt3.y²
则上述方程组变成一下形式：
A1*center.x+B1*center.y=C1；
A2*center.x+B2*center.y=C2
联立以上方程组可以求出：
center.x = (C1*B2 - C2*B1) / (A1*B2 - A2*B1);
center.y = (A1*C2 - A2*C1) / (A1*B2 - A2*B1);
（为了方便编写程序，令temp = A1*B2 - A2*B1）
*/
D、Duration
签到题，没看到关键字同一天直接按60进制进位减掉求绝对值即可。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
int main() {
int h1, h2, m1, m2, s1, s2;
scanf("%d:%d:%d", &h1, &m1, &s1);
scanf("%d:%d:%d", &h2, &m2, &s2);
int ans1 = h1 * 3600 + m1 * 60 + s1, ans2 = h2 * 3600 + m2 * 60 + s2;
printf("%d", abs(ans2 - ans1));
return 0;
}
F、Fake Maxpooling
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5000 + 7;
int a[N][N], q[N], b[N];
int GCD[N][N];
int n, m, k;
void find_row(int j) {
int head = 1, tail = 0;
for (int i = 1; i <= n; ++i) {
while (head <= tail and q[head] + k <= i) ++head;
while (head <= tail and a[i][j] > a[q[tail]][j]) --tail;
q[++tail] = i;
if (i >= k)
b[i - k + 1] = a[q[head]][j];
}
for (int i = 1; i <= n - k + 1; ++i)
a[i][j] = b[i];
}
void find_col(int i) {
int head = 1, tail = 0;
for (int j = 1; j <= m; ++j) {
while (head <= tail and q[head] + k <= j) ++head;
while (head <= tail and a[i][j] > a[i][q[tail]]) --tail;
q[++tail] = j;
if (j >= k)
b[j - k + 1] = a[i][q[head]];
}
for (int j = 1; j <= m - k + 1; ++j)
a[i][j] = b[j];
}
int main() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; ++i) // O(n*m)预处理矩阵
for (int j = 1; j <= m; ++j)
if (!GCD[i][j])
for (int k = 1; i * k <= n and j * k <= m; ++k)
GCD[i * k][j * k] = k, a[i * k][j * k] = i * j * k;
for (int i = 1; i <= m; ++i)
find_row(i); //固定列把这一列中近可能大的行放在前面
for (int i = 1; i <= n; ++i)
find_col(i); //之前基础上固定行把尽可能大的列放在前面
ll ans = 0;
for (int i = 1; i <= n - k + 1; ++i)
for (int j = 1; j <= m - k + 1; ++j)
ans += a[i][j];
print(ans);
return 0;
}
京公网安备 11010502036488号