头像

Protein

OIer




离线:1小时前



Protein
4小时前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png

代码

#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 2000010;
const double eps = 1e-8;
int n, stk[N], top;
struct PDD { double x, y; } P[N];
bool PDD_cmp(PDD a, PDD b) { return (a.x != b.x) ? a.x < b.x : a.y < b.y; }
PDD operator+(PDD a, PDD b) { return (PDD) { a.x + b.x, a.y + b.y }; }
PDD operator-(PDD a, PDD b) { return (PDD) { a.x - b.x, a.y - b.y }; }
double cro(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
double dot(PDD a, PDD b) { return a.x * b.x + a.y * b.y; }
double area(PDD a, PDD b, PDD c) { return cro(b - a, c - a) / 2; }
// 求斜率, 注意特判斜率不存在的情况, 返回INF即可
double get_k(PDD a, PDD b) { return (a.x == b.x) ? 1e18 : (a.y - b.y) / (a.x - b.x); }
// 求函数 f, 注意特判, 如果 k <= 0, 不合法不要算, 防止更新错误答案
double f(PDD a, double k) { return k > 0 ? (a.x + a.y + a.x * k + a.y / k) : 1e18; }
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &P[i].x, &P[i].y);
    sort(P + 1, P + n + 1, PDD_cmp);
    for (int i = 1; i <= n; stk[++top] = i, i++) // 求个凸包
        while (top >= 2 && area(P[stk[top - 1]], P[stk[top]], P[i]) >= 0) top--;
    double res = 1e18;
    for (int i = 1; i <= top; i++) {
        PDD A = P[stk[i]], B = P[stk[i - 1]], C = P[stk[i + 1]];
        double k = sqrt(A.y / A.x), k1 = get_k(B, A), k2 = get_k(C, A);
        // 以下不要忘记带负号
        if ((i == 1 || -k <= k1) && // 要么 i = 1, 没有前驱节点, 要么比 k1 小
            (i == top || -k >= k2)) // 要么 i = top, 没有后继节点, 要么比 k2 大
                res = min(res, f(A, k)); // 这样满足 k 的条件, 更新答案 
        else if (i > 1) res = min(res, f(A, -k1)); 
        else if (i < top) res = min(res, f(A, -k2));
    }
    printf("%.4lf", res);
    return 0;
}



Protein
2天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, w[N], maxv = 0, idx;
int a[N], root[N];
struct NODE { int l, r, s[2], c; } tr[N * 20];
void pushup(int u) { tr[u].c = tr[tr[u].s[0]].c + tr[tr[u].s[1]].c; }
int build(int l, int r) {
    int v = ++idx, mid = l + r >> 1; 
    tr[v].l = l, tr[v].r = r;
    if (l == r) return v;
    tr[v].s[0] = build(l, mid);
    tr[v].s[1] = build(mid + 1, r);
    return pushup(v), v;
}
int update(int u, int x) {
    int v = ++idx, mid = tr[u].l + tr[u].r >> 1;
    tr[v] = tr[u];
    if (tr[u].l == tr[u].r) return tr[v].c++, v;
    if (x <= mid) tr[v].s[0] = update(tr[u].s[0], x);
    else tr[v].s[1] = update(tr[u].s[1], x);
    return pushup(v), v;
}
int query(int u, int v, int l, int r) {
    int k = tr[v].c - tr[u].c;
    if (r < tr[u].l || l > tr[u].r || k == 0) return 0; // 判断一下, 防止越界
    if (tr[u].l >= l && tr[u].r <= r) return k;
    int cnt = 0, mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cnt += query(tr[u].s[0], tr[v].s[0], l, r);
    if (r > mid) cnt += query(tr[u].s[1], tr[v].s[1], l, r);
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (register int i = 1; i <= n; i++)  // 找个最大值, 作为值域
        cin >> a[i], maxv = max(maxv, a[i]);
    root[0] = build(1, maxv); // 把空树建出来
    for (register int i = 1; i <= n; i++)    
        root[i] = update(root[i - 1], a[i]); // 依次插入
    for (register int b, x, l, r; m-- && cin >> b >> x >> l >> r; ) {
        int ans = 0;
        for (register int i = 18; i >= 0; i--) {
            int p = query(root[l - 1], root[r], ans - x, ans - x + (1 << i) - 1);
            int q = query(root[l - 1], root[r], ans - x + (1 << i), ans - x + (1 << (i + 1)) - 1);
            if (!(b >> i & 1) && q) ans += (1 << i);
            if (b >> i & 1 && !p) ans += (1 << i);
        }
        cout << (ans ^ b) << endl;
    }
    return 0;
}



Protein
2天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, w[N], maxv = 0, idx;
int a[N], root[N];
struct NODE { int l, r, s[2], c; } tr[N * 20];
void pushup(int u) { tr[u].c = tr[tr[u].s[0]].c + tr[tr[u].s[1]].c; }
int build(int l, int r) {
    int v = ++idx, mid = l + r >> 1; 
    tr[v].l = l, tr[v].r = r;
    if (l == r) return v;
    tr[v].s[0] = build(l, mid);
    tr[v].s[1] = build(mid + 1, r);
    return pushup(v), v;
}
int update(int u, int x) {
    int v = ++idx, mid = tr[u].l + tr[u].r >> 1;
    tr[v] = tr[u];
    if (tr[u].l == tr[u].r) return tr[v].c++, v;
    if (x <= mid) tr[v].s[0] = update(tr[u].s[0], x);
    else tr[v].s[1] = update(tr[u].s[1], x);
    return pushup(v), v;
}
int query(int u, int v, int l, int r) {
    int k = tr[v].c - tr[u].c;
    if (r < tr[u].l || l > tr[u].r || k == 0) return 0;
    if (tr[u].l >= l && tr[u].r <= r) return k;
    int cnt = 0, mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) cnt += query(tr[u].s[0], tr[v].s[0], l, r);
    if (r > mid) cnt += query(tr[u].s[1], tr[v].s[1], l, r);
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (register int i = 1; i <= n; i++) 
        cin >> a[i], maxv = max(maxv, a[i]);
    root[0] = build(1, maxv);
    for (register int i = 1; i <= n; i++)    
        root[i] = update(root[i - 1], a[i]);
    for (register int b, x, l, r; m-- && cin >> b >> x >> l >> r; ) {
        int ans = 0;
        for (register int i = 18; i >= 0; i--) {
            int p = query(root[l - 1], root[r], ans - x, ans - x + (1 << i) - 1);
            int q = query(root[l - 1], root[r], ans - x + (1 << i), ans - x + (1 << (i + 1)) - 1);
            if (b >> i & 1 && !p) ans += (1 << i);
            if (!(b >> i & 1) && q) ans += (1 << i);
        }
        cout << (ans ^ b) << endl;
    }
    return 0;
}



Protein
2天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png
4.png
5.png
6.png

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 2e7 + 10, mod = 20170408;
int n, m, p, P[M], V[M], idx, cnt[N];
struct MATRIX { int a[N][N]; };
MATRIX operator*(MATRIX A, MATRIX B) {
    static MATRIX C;
    memset(C.a, 0, sizeof C.a);
    for (int i = 0; i < p; i++)
        for (int j = 0; j < p; j++)
            for (int k = 0; k < p; k++)
                C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j]) % mod;
    return C;
}
void init(int n) {
    V[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!V[i]) P[++idx] = i;
        for (int j = 1; P[j] <= n / i; j++) {
            V[P[j] * i] = true;
            if (i % P[j] == 0) break;
        }
    }
}
MATRIX qmi(MATRIX A, int b) {
    static MATRIX C;
    memset(C.a, 0, sizeof C.a);
    for (int i = 0; i < p; i++) C.a[i][i] = 1;
    for (; b; b >>= 1, A = A * A)
        if (b & 1) C = C * A;
    return C;
}
MATRIX work(int inv) {
    static MATRIX A, F;
    memset(cnt, 0, sizeof cnt);
    memset(F.a, 0, sizeof F.a);
    for (int i = 1; i <= m; i++)
        if (inv == 1) cnt[i % p]++;
        else if (inv == 2 && V[i]) cnt[i % p]++;
    for (int i = 0; i < p; i++) 
        for (int j = 0; j < p; j++)
            A.a[i][j] = cnt[(j - i + p) % p];
    F.a[0][0] = 1;
    return F * qmi(A, n);
}
int main() {
    init(M - 10);
    cin >> n >> m >> p;
    cout << ((work(1).a[0][0] - work(2).a[0][0]) % mod + mod) % mod << endl;
    return 0;
}



Protein
3天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png
4.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
int n, m, f[N][20];
// k 是倍增自带的, 忽略 k 就和普通并查集一模一样了
int find(int x, int k) { return f[x][k] != x ? (f[x][k] = find(f[x][k], k)) : f[x][k]; }
void merge(int x, int y, int k) { f[find(x, k)][k] = f[find(y, k)][k]; }
int main() {
    cin >> n >> m;
    for (int j = 0; j <= 19; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = i;
    for (int a, b, c, d; m-- && cin >> a >> b >> c >> d; )
        for (int i = 19; i >= 0; i--)
            if (a + (1 << i) - 1 > b) continue; // 比右边区间大的就跳过
            else merge(a, c, i), a += 1 << i, c += 1 << i; // 倍增跳
    for (int j = 20; j >= 1; j--) // 注意 >= 1
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            merge(i, find(i, j), j - 1),  // 推到两个子区间
            merge(i + (1 << (j - 1)), find(i, j) + (1 << (j - 1)), j - 1);
    int cnt = 0, res = 9;
    for (int i = 1; i <= n; i++) cnt += (f[i][0] == i); // 判断几个集合
    for (int i = 1; i <= cnt - 1; i++) res = 1ll * res * 10 % mod; // 暴力算就行
    cout << res << endl;
    return 0;
}



Protein
3天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 20010;
int n, m, B[N][61], P[N][61];
int h[N], ptr[N << 1], val[N << 1], idx;
int base[N], f[N][21], dep[N], w[N];
void add(int a, int b) { val[idx] = b, ptr[idx] = h[a], h[a] = idx++; }
void insert(int u, int B[], int P[]) {
    int x = w[u];
    for (int i = 60; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!B[i]) { B[i] = x, P[i] = u; break; } // 不存在线性基
        if (dep[u] > dep[P[i]]) swap(P[i], u), swap(x, B[i]); // 比较一下深度
        x ^= B[i];
    }
}
void DFS(int u, int fa) {
    f[u][0] = fa, dep[u] = dep[fa] + 1;
    for (int i = 1; i <= 20; i++) // LCA 预处理父亲
        f[u][i] = f[f[u][i - 1]][i - 1]; 
    for (int i = 0; i <= 60; i++) // 复制父亲信息
        P[u][i] = P[fa][i], B[u][i] = B[fa][i];
    insert(u, B[u], P[u]);        // 用自己更新一下
    for (int i = h[u]; i != -1; i = ptr[i])
        if (val[i] != fa) DFS(val[i], u);
}
int LCA(int a, int b) { // 倍增LCA
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 20; i >= 0; i--)
        if (dep[f[a][i]] >= dep[b]) a = f[a][i];
    if (a == b) return a;
    for (int i = 20; i >= 0; i--)
        if (f[a][i] != f[b][i]) 
            a = f[a][i], b = f[b][i];
    return f[a][0];
}
int query(int a, int b) {
    int t = LCA(a, b);
    for (int i = 60; i >= 0; i--) // 首先把 a 到 LCA 的线性基全复制过来
        (dep[P[a][i]] >= dep[t]) ? base[i] = B[a][i] : base[i] = 0;
    for (int i = 60; i >= 0; i--) { 
        if (dep[P[b][i]] < dep[t]) continue; 
        int x = B[b][i]; // 暴力插入 b 到 LCA 的线性基
        for (int j = 60; j >= 0; j--)
            if (!(x >> j & 1)) continue;
            else if (!base[j]) { base[j] = x; break; }
            else x ^= base[j];
    }
    int res = 0; // 最大值
    for (int i = 60; i >= 0; i--)
        res = max(res, base[i] ^ res);
    return res;
}
signed main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1, a, b; i < n; i++)
        cin >> a >> b, add(a, b), add(b, a);
    DFS(1, 0);
    for (int a, b; m-- && cin >> a >> b; ) 
        cout << query(a, b) << endl;
    return 0;
}


新鲜事 原文

Protein
4天前
呜呜呜呜呜 差两分进省队 -------------- 我 NOIP 133 作为省最后一名 如果我再得两分, 135 到了全国基准线 就有一个学校只能进 1 / 3 的限制 吉林省是 7 个 省队, 也就是说东北师大附中只能进 2 个, 再加上一个女生也就三个 现在没有限制, 他们进了六个!!! 我是可怜的第八名(只算高中生), A卷191 / 600 ------------- 学OI满一年零半个月祭



Protein
4天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;
const int N = 1000010;
const double eps = 1e-7;
int n, cnt = 0;
PDD P[N], ans[N];
struct LINE { PDD st, ed; } L[N];
inline PDD operator-(PDD a, PDD b) { return make_pair(a.x - b.x, a.y - b.y); }
inline PDD operator+(PDD a, PDD b) { return make_pair(a.x + b.x, a.y + b.y); }
inline PDD operator*(PDD a, double c) { return make_pair(a.x * c, a.y * c); }
inline int cmp(double a, double b) { return (fabs(a - b) < eps) ? 0 : ((a < b) ? -1 : 1); }
inline double cro(PDD a, PDD b) { return a.x * b.y - a.y * b.x; }
inline double area(PDD a, PDD b, PDD c) { return cro(b - a, c - a); }
inline double get_angle(LINE a) { return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x); }
// get_line_intersection 得到直线交点
inline PDD GLI(PDD p, PDD v, PDD q, PDD w) { return p + v * (cro(w, (p - q)) / cro(v, w));}
inline PDD GLI(LINE a, LINE b) { return GLI(a.st, a.ed - a.st, b.st, b.ed - b.st); }
inline bool on_right(LINE a, LINE b, LINE c) {  return cmp(area(a.st, a.ed, GLI(b, c)), 0) < 0; }
inline double get_area(PDD P[], int n) {
    double res = 0;
    for (int i = 2; i + 1 <= n; i++)
        res += cro(P[i] - P[1], P[i + 1] - P[i]);
    return res / 2;
}
inline bool LINE_cmp(LINE a, LINE b) { 
    double A = get_angle(a), B = get_angle(b);
    if (cmp(A, B) == 0) return area(a.st, a.ed, b.ed) < 0;
    else return A < B;
}
int q[N];
inline double HPI() {
    sort(L + 1, L + cnt + 1, LINE_cmp);
    int hh = 0, tt = -1, k = 0;
    for (int i = 1; i <= cnt; i++) {
        if (i != 1 && !cmp(get_angle(L[i]), get_angle(L[i - 1]))) continue;
        while (hh + 1 <= tt && on_right(L[i], L[q[tt - 1]], L[q[tt]])) tt--;
        while (hh + 1 <= tt && on_right(L[i], L[q[hh + 1]], L[q[hh]])) hh++;
        q[++tt] = i;
    }
    while (hh + 1 <= tt && on_right(L[q[hh]], L[q[tt - 1]], L[q[tt]])) tt--;
    while (hh + 1 <= tt && on_right(L[q[tt]], L[q[hh + 1]], L[q[hh]])) hh++;
    q[++tt] = q[hh];
    for (int i = hh; i < tt; i++) ans[++k] = GLI(L[q[i]], L[q[i + 1]]);
    return get_area(ans, k);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> P[i].x >> P[i].y;
    P[n + 1] = P[1]; // 处理一下, 方便后面
    for (int i = 1; i <= n; i++) L[++cnt] = (LINE) { P[i], P[i + 1] };
    for (int i = 2; i <= n; i++) {
        double A = P[1].y - P[2].y + P[i + 1].y - P[i].y;
        double B = P[2].x - P[1].x + P[i].x - P[i + 1].x;
        double C = -P[2].x * P[1].y + P[1].x * P[2].y + P[i + 1].x * P[i].y - P[i].x * P[i + 1].y;
        if (cmp(B, 0) == 0) L[++cnt] = (LINE) { (PDD){ -C / A, 0 }, (PDD) { -C / A - B, A } };
        else L[++cnt] = (LINE) { (PDD) { 0, -C / B }, (PDD) { -B, -C / B + A }};
    }   
    // 概率就是合法面积除以总面积
    printf("%.4Lf", HPI() / get_area(P, n));
    return 0;
}



Protein
5天前

Blog

题目

Luogu
LOJ
Acwing

思路

1.png
2.png
3.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, A[N], B[N];
char C[N];
struct NODE { int l, r, a, b, s, c; } tr[N << 2];
inline void init(int u, int c) {
    if (c == 0) tr[u].a = tr[u].b = tr[u].c = tr[u].s = 0;
    else tr[u].a = tr[u].b = tr[u].c = 1, tr[u].s = 0;
}
inline NODE operator+(const NODE &l, const NODE &r) { // 运算符重载
    NODE u = (NODE) { l.l, r.r };
    u.c = l.c + r.c, u.s = l.s + r.s;
    u.a = l.a, u.b = r.b;
    if (l.c && r.c && (!l.b || !r.a)) u.s++;
    return u;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return init(u, B[l]), void(0);
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
void modify(int u, int x, int c) {
    if (tr[u].l == tr[u].r) return init(u, c), void(0);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) modify(u << 1, x, c);
    else modify(u << 1 | 1, x, c);
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
}
NODE query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int md = (tr[u].l + tr[u].r) >> 1;
    if (r <= md) return query(u << 1, l, r);
    else if (l > md) return query(u << 1 | 1, l, r);
    else return query(u << 1, l, r) + query(u << 1 | 1, l, r); // 注意讨论
}
int calc(int x) { return ((C[x] == '+') ? (A[x] + A[x - 1]) : (A[x] * A[x - 1])) % 10; }
inline void modify(int pos, int num, char opt) {
    A[pos] = A[pos + n] = num, C[pos] = C[pos + n] = opt;
    if (pos > 1) modify(1, pos, calc(pos)); // 如果是开头, 不用计算
    modify(1, pos + n, calc(pos + n));
    modify(1, pos + 1, calc(pos + 1));
    if (pos < n) modify(1, pos + n + 1, calc(pos + n + 1)); // n + pos + 1 超出长度, 不用算
}
bool check(int mid, int pos) { return query(1, pos + mid, n + pos - mid).s; }
inline int query(int pos) {
    // 这两行注释了也能过, 样例都过不了......
    if (A[pos] == 0 && query(1, pos + 1, pos + n - 1).s == 0) return 0; // 特判 0
    if (query(1, pos, pos + n).s == 0) return -1; // 特判 -1
    modify(1, pos, A[pos]), modify(1, pos + n, A[pos]);
    int l = 0, r = n >> 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (query(1, pos + mid, n + pos - mid).s) l = mid;
        else r = mid - 1;
    }
    if (pos > 1) modify(1, pos, calc(pos));
    modify(1, pos + n, calc(pos + n));
    return l + 1; // 注意加 1
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> A[i] >> C[i];
    for (int i = 1; i <= n; i++) A[i + n] = A[i], C[i + n] = C[i];
    for (int i = 2; i <= n << 1; i++) B[i] = calc(i);
    build(1, 1, n << 1);
    char opt;
    for (int op, pos, num; m-- && cin >> op >> pos; ) // 由于从 1 开始, 下标需要加 1 
        if (op == 2) cout << query(pos + 1) << endl;
        else cin >> num >> opt, modify(pos + 1, num, opt);
    return 0;
}



Protein
6天前

Blog

题目

Lougu
LOJ
Acwing

思路

1.png
2.png
3.png
4.png
5.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100010, M = 600010;
int n, tr[M][26], flag[M], idx_t;       // trie
string str[N];
int h[M], ptr[N], val[N], sz[M], idx_g; // 链式前向星
void insert(string str) {           
    int p = 0, c = str[0] - 'a';
    for (int i = 0; i < (int)str.size(); i++, c = str[i] - 'a')
        p = ((tr[p][c]) ? tr[p][c] : (tr[p][c] = ++idx_t));
    flag[p] = true; // 标记结尾
}
// 加边函数
void add(int a, int b) { val[idx_g] = b, ptr[idx_g] = h[a], h[a] = idx_g++; }
void update(int p, int top) {
    // 如果 v 是结尾,加边
    for (int i = 0; i < 26; i++) 
        if (flag[tr[p][i]]) add(top, tr[p][i]);
    for (int i = 0; i < 26; i++) 
        if (flag[tr[p][i]]) update(tr[p][i], tr[p][i]);
        else if (tr[p][i]) update(tr[p][i], top);
}
long long res = 0;
void DFS(int u) {
    // 计算子树大小
    sz[u] = 1;
    for (int i = h[u]; i != -1; i = ptr[i]) 
        DFS(val[i]), sz[u] += sz[val[i]];
    // 贪心计算答案
    vector<int> temp;
    for (int i = h[u]; i != -1; i = ptr[i])
        temp.push_back(sz[val[i]]);
    sort(temp.begin(), temp.end());
    int delta = 1; // 偏移量
    for (int i = 0; i < (int)temp.size(); i++)
        res += delta, delta += temp[i];
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> str[i];
    for (int i = 1; i <= n; i++) reverse(str[i].begin(), str[i].end()); // 翻转
    for (int i = 1; i <= n; i++) insert(str[i]);                        // 插入
    memset(h, -1, sizeof h); 
    update(0, 0), DFS(0);
    cout << res << endl;        
    return 0;
}