A. Equivalent Prefixes

题意：定义$RMQ(u, l, r)$表示$u_l,u_{l+1},\cdots,u_r$中最小的数的下标，而两个数组相似指的是对于任意的$1\leq l \leq r \leq m(m$表示数组长度$)$都相等，问$a, b$两个数组最长的相似前缀长度

思路：二分数组长度，通过建立笛卡尔树，比较两者的前缀笛卡尔树

#include <bits/stdc++.h>
using namespace std;

#define N 100010
int n, a[N], b[N];

struct Cartesian_Tree {
    struct node {
        int id, val, fa;
        int son[2];
        node() {}
        node (int id, int val, int fa) : id(id), val(val), fa(fa) {
            son[0] = son[1] = 0;
        }
    }t[N];
    int root, l[N], r[N];
    void init() {
        t[0] = node(0, 0, 0);
    }
    void build(int n, int *a) {
        for (int i = 1; i <= n; ++i) {
            t[i] = node(i, a[i], 0);
        }
        for (int i = 1; i <= n; ++i) {
            int k = i - 1;
            while (t[k].val > t[i].val) {
                k = t[k].fa;
            }
            t[i].son[0] = t[k].son[1];
            t[k].son[1] = i;
            t[i].fa = k;
            t[t[i].son[0]].fa = i;
        }
        root = t[0].son[1];
    }
    int DFS(int u) {
        if (!u) return 0;
        l[t[u].id] = DFS(t[u].son[0]);
        r[t[u].id] = DFS(t[u].son[1]);
        return l[t[u].id] + r[t[u].id] + 1;
    }
}t[2];

bool check(int x) {
    t[0].init();
    t[1].init();
    t[0].build(x, a);
    t[1].build(x, b);
    t[0].DFS(t[0].root);
    t[1].DFS(t[1].root);
    for (int i = 1; i <= x; ++i) {
        if (t[0].l[i] != t[1].l[i] || t[0].r[i] != t[1].r[i])
            return 0;
    }
    return 1;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", b + i);
        }
        int l = 1, r = n, res = -1;
        while (r - l >= 0) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

B. Integration

题意:求$\frac{1}{\pi} \cdot \int_{0}^{\infty}\frac{1}{\prod_{i=1}^{n} (a_i^2+x^2)}\mathrm{d}x$

思路:

• $\frac{1}{\pi} \cdot \int_{0}^{\infty} \frac{1}{a^2+x^2} \mathrm{d}x = \frac{1}{2\cdot a}$

• 当$n=2$

  • $\frac{1}{\pi} \cdot \int_{0}^{\infty} \frac{1}{(a_1^2+x^2) \cdot (a_2^2+x^2)} \mathrm{d}x = \frac{1}{\pi} \cdot \int_{0}^{\infty} \frac{A}{a_1^2+x^2}+\frac{B}{a_2^2+x^2} \mathrm{d}x$

  • 发现$A=\frac{1}{a_2^2-a_1^2}, B = \frac{1}{a_1^2-a_2^2}$

• 当$n=3$

  • $\frac{1}{\pi} \cdot \int_{0}^{\infty} \frac{1}{(a_1^2+x^2) \cdot (a_2^2+x^2) \cdot (a_3^2+x^2)} \mathrm{d}x = \frac{1}{\pi} \cdot \int_{0}^{\infty} \frac{A}{a_1^2+x^2}+\frac{B}{a_2^2+x^2} + \frac{C}{a_3^2+x^2} \mathrm{d}x$

  • 发现$A=\frac{1}{(a_2^2-a_1^2)\cdot(a_3^2-a_1^2)}, B = \frac{1}{(a_1^2-a_2^2)\cdot(a_3^2-a_2^2)}, C=\frac{1}{(a_1^2-a_3^2)\cdot(a_2^2-a_3^2)}$

• 大胆推测

  $\frac{1}{\pi} \cdot \int_{0}^{\infty}\frac{1}{\prod_{i=1}^{n} (a_i^2+x^2)} \mathrm{d}x=\frac{1}{\pi}\sum_{i=1}^n\frac{1}{2\cdot \prod_{j\neq i}(a_j^2-a_i^2)\cdot a_i}$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll P = (ll) 1e9 + 7;

#define N 1010

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = res * x % P;
        }
        x = x * x % P;
        n >>= 1;
    }
    return res;
}

int n;
ll arr[N];

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", arr + i);
        }
        ll ans = 0;
        for (int i = 1; i <= n; ++i) {
            ll tmp = 2ll * arr[i];
            for (int j = 1; j <= n; ++j) {
                if (i == j) {
                    continue;
                }
                tmp = tmp * (arr[j] * arr[j] % P - arr[i] * arr[i] % P + P) % P;
            }
            ans = (ans + qpow(tmp, P - 2)) % P;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. Euclidean Distance

题意：求$\sum _{i=1}^{n}(\frac{a_i}{m} ^ 2- p_i^2)$，其中满足

• $p_1,p_2,\cdots, p_n\geq0$
• $p_1 + p_2 + \cdots + p_n = 1$

思路：

将条件改为$p_1+p_2+\cdots +p_n=m$

此时$\sum_{i=1}^{n}(\frac{a_i}{m}^2-p_i^2)=\sum_{i=1}^{n} (\frac{a_i}{m}^2+\frac{p_i}{m}^2)=\frac{1}{m^2}\cdot \sum_{i=1}^{n}(a_i^2-p_i^2)$

$\sum_{i=1}^{n}(a_i^2-p_i^2)$即矩形的高度平方。显然优先降低高度高的矩形。当$A_1$和$A_2$高度相同时看做一个矩形同时降低二者高度，直到不能降低位置，然后计算最后答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 10010

int n;
ll m;
ll arr[N];

struct Frac {
    ll x, y;

    Frac() {}
     
    Frac(ll x, ll y) : x(x), y(y) {}
     
    Frac operator+(const Frac &other) const {
        ll up = x * other.y + y * other.x;
        ll down = y * other.y;
        ll G = __gcd(up, down);
        return {up / G, down / G};
    }
     
    Frac operator-(const Frac &other) const {
        ll up = x * other.y - y * other.x;
        ll down = y * other.y;
        ll G = __gcd(up, down);
        return {up / G, down / G};
    }
     
    Frac operator*(const Frac &other) const {
        ll up = x * other.x;
        ll down = y * other.y;
        ll G = __gcd(up, down);
        return {up / G, down / G};
    }
     
    void out() {
        if (y == 1) {
            printf("%lld\n", x);
        } else {
            printf("%lld/%lld\n", x, y);
        }
    }
};

int main() {
    while (~scanf("%d %lld", &n, &m)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", arr + i);
        }
        sort(arr + 1, arr + 1 + n, greater<ll>());
        ll need = m;
        Frac ans = Frac(0, 1);
        for (int i = 1; i <= n; ++i) {
            if (i < n && (arr[i] - arr[i + 1]) * i <= need) {
                need -= (arr[i] - arr[i + 1]) * i;
            } else {
                ans = ans + Frac((i * arr[i] - need) * (i * arr[i] - need), 1ll * i * m * m);
                for (int j = i + 1; j <= n; ++j) {
                    ans = ans + Frac(arr[j] * arr[j], m * m);
                }
                ans.out();
                break;
            }
        }
    }
    return 0;
}

F. ABBA

题意：对于一个长度为$2\cdot (n+m)$的$AB$串，有多少种方案可以构造出这个$AB$串中有$n$个$AB$子序列，$m$个$BA$子序列

思路：$f[i][j]$表示已经用了$i$个$A$，$j$个$B$

• $f[0]][0]=1$

• 考虑如果加了一个$A$，首先满足$i+1<=n+m$那么优先给$AB$贡献，也就是说$i+1-n\leq j$，意思是即使满足$AB$串后，剩余的$A$要小于$B$的数量，同样的$B$要优先给$BA$串贡献，需要满足$j-m\leq i+1$

• 考虑如果加了一个$B$，首先满足$j+1<=n+m$那么优先给$BA$贡献，也就是说$j+1-m\leq i$，意思是即使满足$BA$串后，剩余的$B$要小于$A$的数量，同样的$A$要优先给$AB$串贡献，需要满足$i-n\leq j+1$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define N 2010

const ll p = (ll) 1e9 + 7;

int n, m;
ll dp[N][N];


int main() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 0; i <= n + m; ++i) {
            for (int j = 0; j <= n + m; ++j) {
                dp[i][j] = 0ll;
            }
        }
        dp[0][0] = 1ll;
        for (int i = 0; i <= n + m; ++i) {
            for (int j = 0; j <= n + m; ++j) {
                if (i + 1 - n <= j && j - m <= i + 1) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % p;
                }
                if (j + 1 - m <= i && i - n <= j + 1) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % p;
                }
            }
        }
        printf("%lld\n", dp[n + m][n + m]);
    }
    return 0;
}

F. Random Point in Triangle

题意：在$\triangle ABC $内等概率分布点$P$,定义$E=max(S_{PAB}, S_{PBC},S_{PCA})$，求$E$的期望的$36$倍，保证为整数

思路：同时乱打表发现$36E=22\cdot S_{ABC}$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct node {
    ll x, y;

    void input() {
        scanf("%lld %lld", &x, &y);
    }
     
    ll operator ^ (const node &other) const {
        return x * other.y - y * other.x;
    }
     
    node operator - (const node &other) const {
        return {x - other.x, y - other.y};
    }
}p[5];

int main() {
    while (~scanf("%lld %lld", &p[1].x, &p[1].y)) {
        p[2].input();
        p[3].input();
        ll ans = abs((p[1] - p[2]) ^ (p[1] - p[3]));
        ans *= 11;
        printf("%lld\n", ans);
    }
    return 0;
}

J. Fraction Comparision

题意：比较$\frac{x}{a}$和$\frac{y}{b}$的大小

思路：签到

while True :
    try :
        x, a, y, b = map(int, input().split())
        A = x * b
        B = y * a
        if A == B :
            print('=')
        elif A < B :
            print('<')
        elif A > B :
            print('>')
    except EOFError :
        break