用户:HermitOvO

这里是慕斯sama！（一直想改名为musesama，但是因为hermit的名称已经在各大论坛上了索性就用这个了）

会点中式建筑，有点红石技艺，浅尝辄止pvp，正在被带领学习中世纪建筑（

不善交际的美少女一枚捏（大概

美少女自用沙盒

• 出没地点：

后土

溯月

日沉阁

bilibili

zth-ria

洛谷

codeforce

AtCoder

Acwing

吾爱论坛

各大群聊

• 记不住的东西：

算法知识点：

FFT 前方检测到核聚变打击，请谨慎打开！

#include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 300000; const double PI = acos(-1); struct Complex { double x, y; Complex operator+ (const Complex& t) const { return {x + t.x, y + t.y}; } Complex operator- (const Complex& t) const { return {x - t.x, y - t.y}; } Complex operator* (const Complex& t) const { return {x * t.x - y * t.y, x * t.y + y * t.x}; } }a[N], b[N]; char s1[N], s2[N]; int res[N]; int rev[N], bit, tot; void fft(Complex a[], int inv) { for (int i = 0; i < tot; i ++ ) if (i < rev[i]) swap(a[i], a[rev[i]]); for (int mid = 1; mid < tot; mid *= 2) { auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)}); for (int i = 0; i < tot; i += mid * 2) { auto wk = Complex({1, 0}); for (int j = 0; j < mid; j ++, wk = wk * w1) { auto x = a[i + j], y = wk * a[i + j + mid]; a[i + j] = x + y, a[i + j + mid] = x - y; } } } } int main() { scanf("%s%s", s1, s2); int n = strlen(s1) - 1, m = strlen(s2) - 1; for (int i = 0; i <= n; i ++ ) a[i].x = s1[n - i] - '0'; for (int i = 0; i <= m; i ++ ) b[i].x = s2[m - i] - '0'; while ((1 << bit) < n + m + 1) bit ++ ; tot = 1 << bit; for (int i = 0; i < tot; i ++ ) rev[i] = ((rev[i >> 1] >> 1)) | ((i & 1) << (bit - 1)); fft(a, 1), fft(b, 1); for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i]; fft(a, -1); int k = 0; for (int i = 0, t = 0; i < tot || t; i ++ ) { t += a[i].x / tot + 0.5; res[k ++ ] = t % 10; t /= 10; } while (k > 1 && !res[k - 1]) k -- ; for (int i = k - 1; i >= 0; i -- ) printf("%d", res[i]); return 0; }

四边形不等式优化DP 前方检测到核聚变打击，请谨慎打开！

#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long double LD; const int N = 100010; int n, L, P; LD f[N]; char str[N][31]; int s[N], opt[N]; struct Node { int j, l, r; }q[N]; int hh, tt; LD val(int j, int i) { LD res = 1, a = abs(s[i] - s[j] + i - j - 1 - L); for (int i = 0; i < P; i ++ ) res *= a; return res + f[j]; } void insert(int i) { int pos = n + 1; while (hh <= tt && val(q[tt].j, q[tt].l) >= val(i, q[tt].l)) pos = q[tt -- ].l; if (hh <= tt && val(q[tt].j, q[tt].r) >= val(i, q[tt].r)) { int l = q[tt].l, r = q[tt].r; while (l < r) { int mid = l + r >> 1; if (val(q[tt].j, mid) >= val(i, mid)) r = mid; else l = mid + 1; } q[tt].r = r - 1; pos = r; } if (pos != n + 1) q[ ++ tt] = {i, pos, n}; } int main() { int T; scanf("%d", &T); while (T -- ) { scanf("%d%d%d", &n, &L, &P); for (int i = n; i >= 1; i -- ) scanf("%s", str[i]); for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + strlen(str[i]); hh = tt = 0; q[0] = {0, 1, n}; for (int i = 1; i <= n; i ++ ) { f[i] = val(q[hh].j, i), opt[i] = q[hh].j; if (q[hh].r == i) hh ++ ; q[hh].l = i + 1; insert(i); } if (f[n] > 1e18) puts("Too hard to arrange"); else { printf("%lld\n", (long long)f[n]); for (int i = n; i; i = opt[i]) { for (int j = i; j > opt[i]; j -- ) { printf("%s", str[j]); if (j != opt[i] + 1) printf(" "); } puts(""); } } puts("--------------------"); } return 0; } }

自适应辛普森积分 前方检测到核聚变打击，请谨慎打开！

#include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const double eps = 1e-12; double f(double x) { return sin(x) / x; } double simpson(double l, double r) { auto mid = (l + r) / 2; return (r - l) * (f(l) + 4 * f(mid) + f(r)) / 6; } double asr(double l, double r, double s) { auto mid = (l + r) / 2; auto left = simpson(l, mid), right = simpson(mid, r); if (fabs(left + right - s) < eps) return left + right; return asr(l, mid, left) + asr(mid, r, right); } int main() { double l, r; scanf("%lf%lf", &l, &r); printf("%lf\n", asr(l, r, simpson(l, r))); return 0; } }

CDQ分治 前方检测到核聚变打击，请谨慎打开！

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010, M = 200010; int n, m; struct Data { int a, b, c, s, res; bool operator< (const Data& t) const { if (a != t.a) return a < t.a; if (b != t.b) return b < t.b; return c < t.c; } bool operator== (const Data& t) const { return a == t.a && b == t.b && c == t.c; } }q[N], w[N]; int tr[M], ans[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i < M; i += lowbit(i)) tr[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } void merge_sort(int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(l, mid), merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) if (q[i].b <= q[j].b) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ]; else q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ]; while (i <= mid) add(q[i].c, q[i].s), w[k ++ ] = q[i ++ ]; while (j <= r) q[j].res += query(q[j].c), w[k ++ ] = q[j ++ ]; for (i = l; i <= mid; i ++ ) add(q[i].c, -q[i].s); for (i = l, j = 0; j < k; i ++, j ++ ) q[i] = w[j]; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); q[i] = {a, b, c, 1}; } sort(q, q + n); int k = 1; for (int i = 1; i < n; i ++ ) if (q[i] == q[k - 1]) q[k - 1].s ++ ; else q[k ++ ] = q[i]; merge_sort(0, k - 1); for (int i = 0; i < k; i ++ ) ans[q[i].res + q[i].s - 1] += q[i].s; for (int i = 0; i < n; i ++ ) printf("%d\n", ans[i]); return 0; }

• 友情链接：

溯月

• 留言板：

留言板