2021-09-16 20:44 已编辑家里蹲小学 C++

关注

2021牛客多校1 题解

A Alice and Bob

题意

有两堆石子，在其中一堆取 $k$ 个，对应的另一堆取 $s*k$ 个，问谁赢

暴力sg打表 $sg[i][j]$ 表示有石头 $(i,j)$ 个时是否为先手必胜

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
const int N = 5e3 + 7;
ll sg[N][N];
signed main() {
    rep(i, 0, 5000) rep(i, 0, 5000) if (sg[i][j] == 0) {
        for (int k = 1; k + i <= 5000; k++)
            for (int s = 0; s * k + j <= 5000; s++)
                sg[i + k][j + s * k] = 1;
        for (int k = 1; k + j <= 5000; k++)
            for (int s = 0; s * k + i <= 5000; s++)
                sg[i + s * k][j + k] = 1;
    }
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        sg[n][m] ? puts("Bob") : puts("Alice");
    }
    return 0;
}

B Ball Dropping

题意

有一个空心圆台，从大口投入一个半径为R的球，问球是否能穿过圆台，若不能，问球心离底面的距离

侧面图

如果圆能穿过即 $2*r<|DE|$ ，这个很容易，以下讨论不能穿过的情况

通过两次相似可以求得

$\Delta ADH \sim \Delta FOP \ \ \Rightarrow \ \ OP$

$\Delta ABC \sim \Delta CFG \sim \Delta CDE \ \ \Rightarrow \ \ PQ$

这样简单得出了答案

图片说明

#include <bits/stdc++.h>
using namespace std;
signed main() {
    double r, a, b, h;
    scanf("%lf%lf%lf%lf", &r, &a, &b, &h);
    if (2.0 * r < b) {
        puts("Drop");
        return 0;
    }
    double th = atan(h / ((a - b) / 2.0));
    double dis = r * sin(th), d = r * cos(th);
    double H = 1.0 * a * h / (a - b);
    double ds = 2.0 * dis * H / a;
    double ans = ds + d - (H - h);
    puts("Stuck");
    printf("%.10lf\n", ans);
    return 0;
}

D Determine the Photo Position

题意

给一个01矩阵，和一个长度为 m 的只包含字符 ‘2’ 的字符串，让这个字符串放入矩阵中

这个字符串是放入其中一行的一段连续的 0 中，问有多少种插入方式

暴力模拟

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
signed main() {
    int n, m, ans = 0;
    cin >> n >> m;
    string s;
    rep(i, 1, n) {
        cin >> s;
        int cnt = 0;
        rep(j, 0, s.length() - 1) {
            if (s[j] == '1') {
                if (cnt >= m)
                    ans += cnt - m + 1;
                cnt = 0;
                continue;
            }
            if (s[j] == '0')
                cnt++;
        }
        if (cnt >= m)
            ans += cnt - m + 1;
    }
    cin >> s;
    cout << ans << endl;
    return 0;
}

F Find 3-friendly Integers

题意

定义一个 3-friendly number ：在数中连续的一段是否能被3整除

找规律发现在 100 之后的数都是 3-friendly number ~~也可以说是88~~

之后暴力打表前 100 ，然后分类处理即可

~~勇士也可以树形dp~~

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'
#define int ll
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define rrep(i, j, k) for (ll i = (ll)(j); i >= (ll)(k); i--)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long double ld;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const ld pi = acos(-1);
const int mod = 1e9 + 7;
const ll INF = LLONG_MAX;
const int N = 1e5 + 7;
ll a[N];
bool chk(int i) {
    if (i % 3 == 0)
        return 1;
    int t = i;
    while (t) {
        if (t % 10 % 3 == 0)
            return 1;
        t /= 10;
    }
    return 0;
}
void init() {

}
void solve() {
    int l, r;
    cin >> l >> r;
    if (r > 100)
        if (l >= 100)
            cout << r - l + 1 << endl;
        else
            cout << r - 100 + a[100] - a[l - 1] << endl;
    else if (r <= 100)
        cout << a[r] - a[l - 1] << endl;
}
signed main() {
    rep(i, 1, 100) a[i] = chk(i);
    rep(i, 1, 100) a[i] = a[i - 1] + a[i];
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

G Game of Swapping Numbers

题意

给两个数组 $A,B$ ，求 $\sum_{i=1}^n|A_i-B_i|$

这位大佬的题解讲的很清楚了

这里简单讲下我的理解

设 $(a_i,b_i)\ (a_j,b_j),max_i=max(a_i,b_i),min_i=min(a_i,b_i),max_j=max(a_j,b_j),min_j=min(a_j,b_j)$

当 $max_i>min_j$ 的时候交换 $a_i,a_j$ 对答案的贡献是无用的

当 $max_i<min_j$ 的时候交换 $a_i,a_j$ 对答案的贡为 $(min_j-max_i)*2$

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;
const int N = 1e6 + 7;
ll a[N], b[N], minn[N], maxn[N];
void solve() {}
signed main() {
    ll n, k, sum = 0;
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i], sum += abs(a[i] - b[i]);
    rep(i, 1, n) minn[i] = min(a[i], b[i]), maxn[i] = max(a[i], b[i]);
    sort(minn + 1, minn + n + 1, greater<int>());
    sort(maxn + 1, maxn + n + 1);
    for (int i = 1; i <= min(n, k); i++)
        if (maxn[i] < minn[i])
            sum += (minn[i] - maxn[i]) * 2;
    printf("%lld", sum);
    return 0;
}

H Hash Function

题意

给定一个集合，求一个数 mod 使得集合中任意两个数 $a_i \% mod != a_j \% mod$

这里感谢这位大佬的题解

上述问题可以转化为任意的两个数的差对 mod 取余不等于 0

可知任意两个数差值的因子都不能满足条件，即找出最小的非** $\forall i,j\in [1,n],\ |a_i-a_j|$ **的因子

朴素求任意两个数的差时间复杂度为 $O(n^2)$

于是可以考虑用 FFT 加速

将多项式中第 $a_i$ 项系数取值为 1，其余系数为 0 该多项式即为 $A$

对应多项式 $B$ 为第 $-a_i$ 为 1，其余系数为 0，则考虑通过加上一个常数抵消负数

于是 $A*B$ 的结果中，有系数的项 $p_i$ 即表示：集合中任意两个数的差值 $p_i$ 存在

之后从 $n$ 开始枚举因子即可

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
typedef long long ll;

typedef complex<double> cp;
const int lim = 1 << 21;
const double pi = acos(-1);
cp a[lim], b[lim]; // 多项式 A B
int rev[lim];
void fft(cp *a, int n, int inv) {
    int bit = 0;
    while ((1 << bit) < n)
        bit++;
    rep(i, 0, n - 1) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    }
    for (int mid = 1; mid < n; mid *= 2) {
        cp temp(cos(pi / mid), inv * sin(pi / mid));
        for (int i = 0; i < n; i += mid * 2) {
            cp omega(1, 0);
            for (int j = 0; j < mid; ++j, omega *= temp) {
                cp x = a[i + j], y = omega * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
    if (inv == -1)
        for (int i = 0; i < lim; ++i)
            a[i].real(a[i].real() / n);
}

bool vis[lim];
const int P = 500001;
bool check(int x) {
    for (int i = x; i <= P; i += x)
        if (vis[i] == 1)
            return 0;
    return 1;
}

signed main() {
    int t, n, m;
    cin >> n;
    rep(i, 0, n - 1) {
        cin >> t;
        a[t] = {1, 0};
        b[P - t] = {1, 0};
    }
    int num = 1 << 20;
    fft(a, num, 1);
    fft(b, num, 1);
    rep(i, 0, num - 1) a[i] *= b[i];
    fft(a, num, -1);

    rep(i, 0, num) {
        t = floor(a[i].real() + 0.5);
        if (t > 0)
            vis[abs(i - P)] = 1;
    }
    rep(i, n, P) if (check(i)) {
        printf("%d\n", i);
        break;
    }
    return 0;
}

K Knowledge Test about Match

题意

给定两个长度为 $n$ 的序列 $A,B$ ，保证 $a_i=i,b_i\in[0,n-1],0\leq i\leq n-1 ,n\leq 10^3$ 。希望调整序列 $B$ 中的元素顺序，使得调整后的元素顺序为 $sum=\sum_{i=0}^{n-1}\sqrt{b_i-a_i}$ 最小。

正解为KM算法，但时间复杂度为 $O(n^3)$ 。

因此题面不要求取得 $sum$ 最小值，允许存在 4%的误差，此时考虑贪心的解法，凑出 $|b_i-a_i|$ 尽可能小即可。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
const int N = 1e4 + 7;
ll a[N], res[N], buc[N];
bool vis[N];
void solve() {
    mem(res, -1), mem(vis, 0), mem(buc, 0);
    int n, x;
    cin >> n;
    rep(i, 1, n) cin >> x, buc[x]++;
    rep(i, 0, n - 1) {     // 枚举差值
        rep(j, 0, n - 1) { // 看 a_j 是否能够匹配
            if (res[j] != -1)
                continue;
            if (j >= i and buc[j - i]) {
                buc[j - i]--, res[j] = j - i;
            } else if (buc[j + i]) {
                buc[j + i]--, res[j] = j + i;
            }
        }
    }
    rep(i, 0, n - 1) cout << res[i] << (i == n - 1 ? '\n' : ' ');
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

另外还有一种类似冒泡排序的算法：先假定一个可能的序列，然后枚举两两交换后对 $sum$ 的影响，如果两个数交换后 $sum$ 跟小，则交换。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
const int N = 1e4 + 7;
int a[N];
inline long double work(int x, int y) { return sqrt(abs(x - y)); }
void solve() {
    int n;
    cin >> n;
    rep(i, 0, n - 1) cin >> a[i];
    for (int k = 1; k <= 3; ++k) // 注意要多执行几次，一次操作精度不够
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (work(i, a[i]) + work(j, a[j]) > work(j, a[i]) + work(i, a[j]))
                swap(a[i], a[j]);
    for (int i = 0; i < n; ++i)
        cout << a[i] << ' ';
    cout << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}