2019年牛客多校第1场赛后总结

A题：Equivalent Prefixes

题意：就是给你两个有n个不同数的串，然后保证1-p区间内任选一个区间，使得区间中最小值的下标相同，找到最大的p值

思路：我的思路是设置两个单调栈，然后每次的第i个数判断大小，放到栈顶（比它大的数弹出栈），当两个栈容量不同时，即不成立。

代码如下:

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

typedef long long ll;
const int maxn = 5e5 + 5;

int a[maxn], b[maxn];
stack<int>s1, s2;

int main(void)
{
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]);

        while (s1.size())    s1.pop();
        while (s2.size())    s2.pop();

        int ans = 1;
        s1.push(a[1]);
        s2.push(b[1]);

        for (int i = 2; i <= n; i++) {
            while (s1.size() && s1.top() > a[i])
                s1.pop();
            s1.push(a[i]);
            while (s2.size() && s2.top() > b[i])
                s2.pop();
            s2.push(b[i]);

            if (s1.size() != s2.size())
                break;
            ans = i;
        }
        cout << ans << endl;
    }

    return 0;
}

B题：Integration

题意：已知 $\int_{0}^{∞} \frac{1}{1 + x_{2}} dx = \frac{\pi}{2}$ ，求 $\frac{1}{\pi } \int_{0}^{∞} \frac{1}{\prod_{i=1}^{n}(a_{i}^{2} + x^{2})}dx$

这道题强行唤醒我的数学…但最终以失败告终…看了好几个巨巨的博客……这里感谢这位大佬的博客：2019牛客网暑期多校第一场B题

$\frac{1}{\prod_{i=1}^{n}(a_{i}^{2} + x^{2})}\,=\,\frac{c_{1}}{a_{1}^{2} + x^{2}}\,+\,\frac{c_{2}}{a_{2}^{2} + x^{2}}\,+...+\frac{c_{n}}{a_{n}^{2} + x^{2}} \\ \, \\ \qquad\quad\quad\;\;\, = \frac{c_{1}\cdot \prod_{i\neq 1 }(a_{i}^{2} + x^{2}) + ...+c_{i}\cdot \prod_{j\neq i }(a_{j}^{2} + x^{2}) + ... + +c_{n}\cdot \prod_{i\neq n }(a_{i}^{2} + x^{2})}{\prod_{i=1}^{n}(a_{i}^{2} + x^{2})}$

我们可以得到: $\sum_{i = 1}^{n}C_{i}\cdot \prod_{j\neq i}(a_{i}^{2} + x^{2})\,=\,1$

由数学归纳法，可得： $C_{i}\,=\,\frac{1}{\prod_{j\neq i}(a_{j}^{2}-a_{i}^{2})}$

又因为 $\int_{0}^{∞} \frac{1}{1 + x_{2}} dx = \frac{\pi}{2}$

$\frac{1}{\pi } \int_{0}^{∞} \frac{1}{\prod_{i=1}^{n}(a_{i}^{2} + x^{2})}dx\,=\,\frac{1}{\pi }\sum_{i=1}^{n}\int_{0}^{∞}\frac{C_{i}}{a_{i}^{2}+x^{2}} dx \\\,\\ \qquad\qquad\qquad\qquad\;=\,\frac{1}{\pi }\sum_{i=1}^{n}C_{i}\int_{0}^{∞}\frac{1}{a_{i}^{2}+x^{2}} dx \\\,\\ \qquad\qquad\qquad\qquad\;=\,\frac{1}{\pi }\sum_{i=1}^{n}\frac{c_{i}}{a_{i}}\cdot \frac{\pi}{2} \\\,\\ \qquad\qquad\qquad\qquad\;=\,\sum_{i=1}^{n}\frac{c_{i}}{2a_{i}} \\\,\\ \qquad\qquad\qquad\qquad\;=\,\frac{1}{2}\sum_{i=1}^{n}\frac{1}{{a_{i}}\cdot \prod_{j\neq i}(a_{j}^{2}-a_{i}^{2})}$

然后进行逆元，费马小定理

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

typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
ll a[maxn];

ll qpow(ll a, ll b)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(void)
{
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);

        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ll res = 1;
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;
                res *= (a[j] * a[j] % mod - a[i] * a[i] % mod);
                res %= mod;
            }
            ans += qpow(2 * a[i] % mod * res % mod, mod - 2);
        }
        ans = (ans % mod + mod) % mod;
        cout << ans << endl;
    }
}

E题：ABBA

题意：有n个＂AB＂,m个＂BA＂，问能结合成多少个序列．这个要求是AB和BA的顺序不变，即A和B的相对位置不变，BA中可以穿插AB，反之亦然

那么我们采用dp，dp[i][j]表示放置i个A和j个B方案数
也就是说我们当前串也就是后面添加A还是添加B的情况

dp[i][j] += dp[i - 1][j];
dp[i][j] += dp[i][j - 1];

当i ≤ n时，A可以随便放；
当j ≤ m时，B可以随便放；
当i > n，如果放A，AB的数量要小于等于n，i - j是至少有多少个AB, i - j ≤ n；
当j > m，如果放B，BA的数量要小于等于m，j - i是至少有多少个BA, j - i ≤ m;
即

if(i - j <= n) d[i][j] += d[i - 1][j];
if(j - i <= m) d[i][j] += d[i][j - 1]];

最终代码如下(PS: 用于数据组过多，memset会卡T，跟缓冲区有关)

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

const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;
int dp[maxn][maxn];

int main(void)
{
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 0; i <= n + m; i++)
            for (int j = 0; j <= m + n; j++)
                dp[i][j] = 0;
        dp[0][0] = 1;

        for (int i = 0; i <= n + m; i++) {
            for (int j = 0; j <= m + n; j++) {
                if (i - j < n)
                    dp[i + 1][j] = (dp[i][j] + dp[i + 1][j]) % mod;
                if (j - i < m)
                    dp[i][j + 1] = (dp[i][j] + dp[i][j + 1]) % mod;
            }
        }
        printf("%d\n", dp[n + m][n + m]);
    }

    return 0;
}

F题：Random Point in Triangle

题意：求三角形内部一个点连三个顶点形成的最大三角形面积的期望，再乘一个36

答案是 11/2 倍三角形 ABC 的面积

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

struct point{
    long long x, y;
}a, b, c;

point AB, BC;

int main(void)
{
    while (cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y) {
        AB.x = b.x - a.x;
        AB.y = b.y - a.y;
        BC.x = c.x - b.x;
        BC.y = c.y - b.y;
        printf("%lld\n",abs((AB.x * BC.y - AB.y * BC.x)) * 11);
    }

    return 0;
}

J题：Fraction Comparision

题意：判断x/a和y/b的大小，其中1 ≤ x, y ≤ 1018， 1 ≤ a, b ≤ 109

签到题，这道题我们直接用的大整数写的，判断x * b和y * a，没什么好说的

其实出题人是想考察数学方面知识的，官方题解是这样的：

先把 $\frac{x}{a}$ 写成 $[\frac{x}{a}] + \frac{x\,mod\,a}{a}$
先比整数部分，分数部分分子分母都在 109 范围内，交叉相乘比较

于是乎，上一下官方题解：

#include <bits/stdc++.h>

static std::pair<uint64_t, uint64_t> fcompare(uint64_t x, uint32_t a, uint64_t y, uint32_t b) {
    uint64_t p = x / a; // p <= (x / a) < p + 1
    uint64_t q = y / b; // q <= (y / b) < q + 1
    if (p != q) {
        return {p, q};
    }
    x %= a;
    y %= b;
    return {x * b, y * a};
}

int main(void)
{
    std::ios::sync_with_stdio(false);
    uint64_t x, y;
    uint32_t a, b;
    while (std::cin >> x >> a >> y >> b) {
        auto result = fcompare(x, a, y, b);
    if (result.first == result.second)
        puts("=");
    else if (result.first < result.second)
        puts("<");
    else
        puts(">");
    }
    return 0;
}