查看“︁用户:HermitOvO”︁的源代码

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

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

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

* '''<big>出没地点：</big>'''

[https://wiki.ria.red/wiki/%E5%90%8E%E5%9C%9F%E6%B4%B2 后土]

溯月

[https://wiki.ria.red/wiki/%E6%97%A5%E6%B2%89%E9%98%81 日沉阁]

[https://www.bilibili.com/ bilibili]

[[bbs:|zth-ria]]

[https://www.luogu.com.cn/ 洛谷]

[http://codeforces.com/ codeforce]

[https://atcoder.jp/ AtCoder]

[https://www.acwing.com/ Acwing]

[https://www.52pojie.cn/ 吾爱论坛]

各大群聊

* '''<big>记不住的东西：</big>'''

算法知识点：
{| class="mw-collapsible mw-collapsed wikitable" 
|-
! colspan=3 | FFT 前方检测到核聚变打击，请谨慎打开！
|-
| <code>
 #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;
} </code>


|}
{| class="mw-collapsible mw-collapsed wikitable" 
|-
! colspan="3" |四边形不等式优化DP 前方检测到核聚变打击，请谨慎打开！
|-
|<code>
 #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;
}

} </code>


|}
{| class="mw-collapsible mw-collapsed wikitable" 
|-
! colspan="3" |自适应辛普森积分 前方检测到核聚变打击，请谨慎打开！
|-
|<code>
 #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;

}
} </code>


|}
{| class="mw-collapsible mw-collapsed wikitable" 
|-
! colspan="3" |CDQ分治 前方检测到核聚变打击，请谨慎打开！
|-
|<code>
 #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;
}

|}

* '''<big>留言板：</big>'''

都看到这了就留言吧QAQ——hermitOvO/musesama/慕斯
[[category:玩家]]