2021牛客暑期多校训练营1&2

本文主要是介绍2021牛客暑期多校训练营1&2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目整理：
第一场因为起晚了没赶上前半场（汗）
我参与做的是H和K
H：Hash Function
题意是给出n个数a1~an，求出一个最小的模数p，使得所有ai对p取模互不相同
1≤n≤500000
0≤a i≤500000
并且ai之间互不相等

标算似乎是FFT还是NTT，不太清楚
我们队的做法是先用0.5s删掉不可能的答案
再用剩下的时间找出可行解
已知余数互不相等，且过大的模数不具备意义，那么n<=p<=a[n]+1

对于序列中随机两个数，a[i]和a[j]，如果使得a[i]%p==a[j]%p
则abs(a[i]-a[j])的因数显然可以作为p的取值
那么我们用0.5s的时间，每一次随机选取序列中的两个数，然后做差找出范围内的因数并删掉

然后是暴力查找：
对于给定的一个模数p,在O(n)的时间内判断它是否合题
当给出模数p的时候，我们可以把整个序列扔进桶里：
例如序列：
3
2 5 7
在桶里：

对于一个模数p，将桶序列分成等长的几段，判断每一段对应位置是否只有一个1
比如说选取模数3

对应起来，显然在2和5上起了冲突，因此非法

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
 
const int N = 500000 + 10;
const int RAND = 100000;
 
int a[N];
bool b[N];
bool c[N];
 
void fun(int n) {
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            b[i] = false;
            b[n / i] = false;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);
    for (int i = n; i <= a[n - 1] + 1; ++i) {
        b[i] = true;
    }
    srand(time(nullptr));
    auto t = clock();
    for (int i = 0; i < RAND; ++i) {
        auto t1 = clock();
        if ((t1 - t) / CLOCKS_PER_SEC >= 1)
            break;
        int l = rand() % n;
        int r = rand() % n;
        if (l > r)
            swap(l, r);
        fun(a[r] - a[l]);
    }
    for (int i = 0; i < n; i++)
        c[a[i]] = 1;
    for (int i = n; i <= a[n - 1] + 1; ++i) {
        if (!b[i])
            continue;
        int fl = 0;
        for (int j = 0; j < i; j++) {
            int cnt = 0;
            for (int k = 0; k <= 500000 / i && k * i + j <= 500000; k++)
                if (c[k * i + j] == 1)
                    cnt++;
            if (cnt > 1) {
                fl = 1;
                break;
            }
        }
        if (fl == 0) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

K：Knowledge Test about Match
题意：给定2个序列
A={0，1，2，···，n-1}
B={b0， b1，b2，···，bn-1}
我们要求对B进行重新排序，将以下函数最小化

已知这个差值函数的最小值可能很难求，只要求最后重新排序后B的序列算出来的差值函数与最小值的误差不超过4%
已知B是随机化生成的
10<=n<=1000

我们队的方法：（又是随机化emmm）
我最初提出来的方法是这样：
首先如果bi能和aj对应上，那就优先一一对应，比如说B中有一个0，那么它优先填到第一个位置上
剩下的序列进行随机排序，然后算一下差值函数取一个最小的

因为是瞎想的算法，被hack掉了，队友说不管怎么随机排序，算出来的差值函数还不如直接从小到大排序来的小（哭唧唧）

队友又改了一下随机化算法，过了······

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        srand(time(NULL));
        int n, x;
        cin >> n;
        set<int> a;
        vector<int> b;
        vector<int> c;
        for (int i = 0; i < n; ++i)
            a.insert(i);
        for (int i = 0; i < n; ++i) {
            cin >> x;
            if (a.count(x)) {
                a.erase(x);
            } else {
                b.push_back(x);
            }
        }
        for (auto i : a)
            c.push_back(i);
        sort(b.begin(), b.end());
        for (int j = 0; j < (n / 40000.0) * 10000000.0; ++j) {
            int l = rand() % b.size(), r = rand() % b.size();
            if (sqrt(abs(b[r] - c[l])) + sqrt(abs(b[l] - c[r])) -
                    sqrt(abs(b[l] - c[l])) - sqrt(abs(b[r] - c[r])) <
                0) {
                auto tmp = b[l];
                b[l] = b[r];
                b[r] = tmp;
            }
        }
        int p = 0;
        for (int i = 0; i < n; ++i) {
            if (a.count(i)) {
                cout << b[p++] << " ";
            } else {
                cout << i << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

大概就是，先从小到大排序，然后每一次随机选择两个数，如果说交换这两个数能让差值函数更小，那就交换
奇迹般地水过了（也许不是水过的？）

第二场，我基本上也是以划为主吧······
C题直接n,m都小于等于4，可以直接枚举所有情况，队友猜了一个关于n*m奇偶性的结论，也对了
D题，直接模拟
K题：stack
题目大意：你有一个排列，你想将它依次插入栈中，并在栈不能保持递减的时候出栈，对于每一个时刻栈的大小求一个序列B，给出B中的几个元素，还原出一个满足这个B序列的A排列

这题队长过的，大概是下标从大到小开始计算，对于每一个i，求一个c[i]，如果b[i]已知，那么c[i]=b[i]，否则c[i]=b[i+1]-1
然后，a[i]就是当前序列中第c[i]小的数字，选中数字后还要将其删掉
以上过程可以用平衡树实现：

我们的初始化把自己的红黑树卡掉了，所以只好又写了一个splay，过了······

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
 
using LL = long long;
using Tree = __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>,
                              __gnu_pbds::splay_tree_tag,
                              __gnu_pbds::tree_order_statistics_node_update>;
 
Tree t;
 
int b[1000001], ans[1000001];
 
void init(int n) {
    for (int i = 1; i <= n; ++i)
        t.insert(i);
}
 
int fun(int k) {
    if (k <= 0) {
        return 0;
    }
    auto tmp = t.find_by_order(k - 1);
    int tmp1 = *tmp;
    t.erase(tmp);
    return tmp1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n = 0, k = 0;
    cin >> n >> k;
    int nn = n;
    for (int i = 1; i <= k; ++i) {
        int p, x;
        cin >> p >> x;
        b[p] = x;
    }
    for (n; n; --n) {
        if (b[n]) {
            break;
        } else {
            ans[n] = n;
        }
    }
    init(n);
    int now = 0;
    for (int i = n; i; --i) {
        --now;
        if (b[i] && b[i] < now) {
            cout << "-1\n";
            return 0;
        }
        now = max(now, b[i]);
        if (now > i) {
            cout << "-1\n";
            return 0;
        }
        ans[i] = fun(now);
    }
    for (int i = 1; i <= nn; ++i) {
        if (!ans[i]) {
            ans[i] = fun(1);
        }
        cout << ans[i] << ' ';
    }
    cout << '\n';
    return 0;
}

I题：企鹅
大概就是两张20*20的地图上分别有一只企鹅，当左边的企鹅往右走的时候右边的企鹅往左走，反之亦然，两者可以同时往上走或者往下走，当一方被挡住了不妨碍另一方行走，并且双方必须同时到达终点，给出双方的起点

因为状态数很少，直接写了一个BFS
我被分配这道题的原因是······这道题代码量偏大······
但是写完发现其实没有很大

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int dyA[4] = {-1, 1, 0, 0};
int dxA[4] = {0, 0, -1, 1};
int dyB[4] = {1, -1, 0, 0};
int dxB[4] = {0, 0, -1, 1};
string opt[4] = {"L", "R", "U", "D"};
// L,R,U,D
struct state {
    int a, b, c, d;
} st, en;
queue<state> q;
string k[20][20][20][20];
int step[20][20][20][20];
string as[20][2];
bool judge(int x, int y, int z) {
    if (x < 0 || x >= 20)
        return false;
    if (y < 0 || y >= 20)
        return false;
    if (as[x][z][y] == '#')
        return false;
    return true;
}
bool operator==(state x, state y) {
    return (x.a == y.a) && (x.b == y.b) && (x.c == y.c) && (x.d == y.d);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(step, 0x3f, sizeof(step));
    for (int i = 0; i < 20; i++)
        cin >> as[i][0] >> as[i][1];
    st.a = 19;
    st.b = 19;
    st.c = 19;
    st.d = 0;
    en.a = 0;
    en.b = 19;
    en.c = 0;
    en.d = 0;
    q.push(st);
    step[st.a][st.b][st.c][st.d] = 0;
 
    while (!q.empty()) {
        state tmp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            state nmp = tmp;
            if (judge(tmp.a + dxA[i], tmp.b + dyA[i], 0))
                nmp.a += dxA[i], nmp.b += dyA[i];
            if (judge(tmp.c + dxB[i], tmp.d + dyB[i], 1))
                nmp.c += dxB[i], nmp.d += dyB[i];
            if (nmp == tmp)
                continue;
            int stepnmp = step[nmp.a][nmp.b][nmp.c][nmp.d];
            int steptmp = step[tmp.a][tmp.b][tmp.c][tmp.d] + 1;
            string knmp = k[nmp.a][nmp.b][nmp.c][nmp.d];
            string ktmp = k[tmp.a][tmp.b][tmp.c][tmp.d] + opt[i];
            if (stepnmp > steptmp || (stepnmp == steptmp && knmp > ktmp)) {
                step[nmp.a][nmp.b][nmp.c][nmp.d] = steptmp;
                k[nmp.a][nmp.b][nmp.c][nmp.d] = ktmp;
                q.push(nmp);
            }
        }
    }
    cout << step[en.a][en.b][en.c][en.d] << '\n';
    cout << k[en.a][en.b][en.c][en.d] << '\n';
    // cerr << "mmp" << '\n';
    state tmp = st;
    as[tmp.a][0][tmp.b] = 'A';
    as[tmp.c][1][tmp.d] = 'A';
    string option = k[en.a][en.b][en.c][en.d];
    int len = option.length();
    for (int i = 0; i < len; i++) {
        state nmp = tmp;
        int x;
        if (option[i] == 'L')
            x = 0;
        else if (option[i] == 'R')
            x = 1;
        else if (option[i] == 'U')
            x = 2;
        else
            x = 3;
        if (judge(tmp.a + dxA[x], tmp.b + dyA[x], 0))
            nmp.a += dxA[x], nmp.b += dyA[x];
        if (judge(tmp.c + dxB[x], tmp.d + dyB[x], 1))
            nmp.c += dxB[x], nmp.d += dyB[x];
        tmp = nmp;
        as[tmp.a][0][tmp.b] = 'A';
        as[tmp.c][1][tmp.d] = 'A';
    }
    for (int i = 0; i < 20; i++)
        cout << as[i][0] << ' ' << as[i][1] << '\n';
    return 0;
}

F题，Girlfriend
这个题关键在于读懂：
到一个点距离为到另一个点距离的k倍，这样的点组成一个圆
在三维空间中，这样的点组成一个球

题意即为求两个球的体积交
先通过给出的四个点和两个倍数k求出两个球的球心和半径
体积交的话······
我们其实忘了高数上讲的公式了
用微元法做的
一开始分了1000个微型圆柱体还没算对，后来改了5000个才过了

#include <cmath>
#include <iostream>
using namespace std;
using LD = long double;
 
const LD PI = M_PI;
 
struct P {
    LD x, y, z;
    explicit P(LD x = 0, LD y = 0, LD z = 0) : x(x), y(y), z(z) {}
};
 
struct B {
    P p;
    LD r;
} b0, b1;
 
LD dis(P a, P b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
                (a.z - b.z) * (a.z - b.z));
}
 
LD fun(B a, LD y) {
    LD t1 = a.r * cos(asin(y / a.r));
    LD t = (a.r - t1) / 5000;
    LD ans = 0;
    for (LD i = t1; i <= a.r; i += t) {
        ans += (a.r * a.r - i * i) * PI * t;
    }
    return ans;
}
 
LD fun1(B a, LD y) {
    // return (PI - asin(y / a.r)) * 4 / 3 * a.r * a.r * a.r +
    //        PI * y * y * sqrt(a.r * a.r - y * y) / 3;
    LD t1 = a.r * cos(asin(y / a.r));
    LD t = (a.r - t1) / 5000;
    LD ans = 0;
    for (LD i = t1; i <= a.r; i += t) {
        ans += (a.r * a.r - i * i) * PI * t;
    }
    return 4 * PI * a.r * a.r * a.r / 3 - ans;
}
 
int main() {
    int T;
    cin >> T;
    for (; T; --T) {
        LD ax, ay, az, bx, by, bz;
        cin >> ax >> ay >> az;
        cin >> bx >> by >> bz;
        LD cx, cy, cz, dx, dy, dz;
        cin >> cx >> cy >> cz;
        cin >> dx >> dy >> dz;
        LD k0, k1;
        cin >> k0 >> k1;
        b0.p = P((k0 * k0 * bx - ax) / (k0 * k0 - 1),
                 (k0 * k0 * by - ay) / (k0 * k0 - 1),
                 (k0 * k0 * bz - az) / (k0 * k0 - 1));
        b0.r = sqrt(b0.p.x * b0.p.x + b0.p.y * b0.p.y + b0.p.z * b0.p.z +
                    (ax * ax + ay * ay + az * az -
                     k0 * k0 * (bx * bx + by * by + bz * bz)) /
                        (k0 * k0 - 1));
        b1.p = P((k1 * k1 * dx - cx) / (k1 * k1 - 1),
                 (k1 * k1 * dy - cy) / (k1 * k1 - 1),
                 (k1 * k1 * dz - cz) / (k1 * k1 - 1));
        b1.r = sqrt(b1.p.x * b1.p.x + b1.p.y * b1.p.y + b1.p.z * b1.p.z +
                    (cx * cx + cy * cy + cz * cz -
                     k1 * k1 * (dx * dx + dy * dy + dz * dz)) /
                        (k1 * k1 - 1));
        LD d = dis(b0.p, b1.p);
        if (d >= b0.r + b1.r) {
            cout << "0\n";
        } else if (d <= abs(b0.r - b1.r)) {
            LD t = min(b0.r, b1.r);
            cout << 4 * PI * t * t * t / 3 << '\n';
        } else {
            LD a = dis(b0.p, b1.p);
            LD y = sqrt(2 * (b0.r * b0.r * a * a + b1.r * b1.r * a * a +
                             b0.r * b0.r * b1.r * b1.r) -
                        b0.r * b0.r * b0.r * b0.r - b1.r * b1.r * b1.r * b1.r -
                        a * a * a * a) /
                   2 / a;
            LD rmin = min(b0.r, b1.r), rmax = max(b0.r, b1.r);
            if (d * d + rmin * rmin >= rmax * rmax)
                cout << fun(b0, y) + fun(b1, y) << "\n";
            else {
                if (b0.r < b1.r)
                    swap(b0, b1);
                cout << fun(b0, y) + fun1(b1, y) << "\n";
            }
        }
    }
    return 0;
}

这篇关于2021牛客暑期多校训练营1&2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！