竞赛讨论区 > 小白月赛72题解
头像
_nul
编辑于 2023-05-13 21:14
+ 关注

小白月赛72题解 精

A

只需判断h1h_{1}和hnh_{n}的大小关系即可。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    if (h[1] < h[n])
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

B

不难证明，一个数的因子个数为奇数的充要条件为这个数为完全平方数。

故答案为⌊n⌋\left \lfloor \sqrt{n} \right \rfloor。

本题的数据范围比较小，暴力也可通过。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
void solve()
{
    int n;
    cin >> n;
    cout << floor(sqrt(n)) << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

C

注意到操作前后aa的总和不变，故aa能变成bb的一个必要条件是它们的总和相等。

然后每次找一个ai−bi>0a_{i} - b_{i} > 0的ii和aj−bj<0a_{j} -b_{j}<0的jj做操作即可。

时间复杂度O(n)O(n)。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<LL> a(n), b(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    LL s1 = accumulate(a.begin(), a.end(), 0LL);
    LL s2 = accumulate(b.begin(), b.end(), 0LL);
    if (s1 != s2)
    {
        cout << "-1" << endl;
        return 0;
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i)
        ans += abs(a[i] - b[i]);
    cout << ans / 2 << endl;
    return 0;
}

D

先考虑没有传送门的情况，显然这是一个简单的dp。

设f[i][j]f[i][j]为从(1,1)(1,1)到(i,j)(i,j)所能达到的最大值。

同时设g[i][j]g[i][j]为，从(i,j)(i,j)到(n,m)(n,m)所能达到的最大值。

这两个数组都可以计算出来，具体可以看参考代码。

对于每次询问，可以发现传送门的个数不多，故枚举使用传送门的入口和出口即可。

时间复杂度O(nm+Tk2)O(nm+ Tk^{2})。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
const LL inf = 1e18;
void solve()
{
    int n, m;
    cin >> n >> m;

    vector<vector<LL>> f(n + 10, vector<LL>(m + 10, -inf)), g(n + 10, vector<LL>(m + 10, -inf));
    vector<vector<LL>> a(n + 10, vector<LL>(m + 10));

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    // compute f
    f[0][1] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];

    // compute g
    g[n][m + 1] = 0;
    for (int i = n; i >= 1; --i)
        for (int j = m; j >= 1; --j)
            g[i][j] = max(g[i + 1][j], g[i][j + 1]) + a[i][j];

    int T;
    cin >> T;

    while (T--)
    {
        int k;
        cin >> k;
        vector<pair<int, int>> b(k);
        for (int i = 0; i < k; ++i)
            cin >> b[i].first >> b[i].second;
            
        LL ans = f[n][m];
        for (int i = 0; i < k; ++i)
            for (int j = 0; j < k; ++j)
            {
                if (i == j)
                    continue;
                int x1 = b[i].first, y1 = b[i].second;
                int x2 = b[j].first, y2 = b[j].second;
                ans = max(ans, f[x1][y1] + g[x2][y2]);
            }

        cout << ans << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

E

考虑二分答案。

对于每一个二分的值midmid，我们尝试去计算小于等于midmid的个数。

将aa，bb排序，尝试枚举aia_{i}，而后我们可以使用二分或者双指针来计算bb中小于等于midai\frac{mid}{a_i}中的元素。求出它们的和。

至于题目中的限制，我们可以把所有限制的权值算出后排序，然后二分查找出小于midmid的个数，用上述的和减掉个数，就是小于等于midmid的数的个数。

设M=max⁡(ai)×max⁡(bi)M = \max(a_i) \times \max(b_i) ，则时间复杂度为O(nlog⁡n+mlog⁡m+Qlog⁡M×(nlog⁡m+log⁡k))O(n \log n + m \log m + Q\log M \times(n \log m + \log k))。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
const LL inf = 1e12 + 10;
void solve()
{
    int n, m, k, Q;
    cin >> n >> m >> k >> Q;
    vector<LL> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
        cin >> b[i];
    vector<LL> c(k + 1);
    for (int i = 1; i <= k; ++i)
    {
        LL x, y;
        cin >> x >> y;
        c[i] = a[x] * b[y];
    }
    sort(c.begin() + 1, c.end());
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    while (Q--)
    {
        LL x;
        cin >> x;
        auto check = [&](LL mid) -> bool
        {
            LL sum = 0;
            for (int i = 1; i <= n; ++i)
            {
                LL p = upper_bound(b.begin(), b.end(), mid / a[i]) - b.begin() - 1;
                sum += p;
            }
            sum -= upper_bound(c.begin(), c.end(), mid) - c.begin() - 1;
            return (sum >= x);
        };
        LL l = 0, r = inf;
        while (l < r)
        {
            LL mid = (l + r) / 2;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

F

为了更好的解释问题，在这里定义一下所需的符号。

设随机变量pp为合法的状态，即pp等可能地取到所有的情况；函数f(p)f(p)为pp的最大间隔。

根据期望的定义，我们有

answer=∑x=1mx×P⁡(f(p)=x)=∑x=1mP⁡(f(p)≥x)=∑x=1m(1−P⁡(f(p)<x)) \begin{aligned} answer &= \sum_{x = 1}^{m} x \times \operatorname{P} (f(p) = x) \\ &= \sum_{x = 1}^{m} \operatorname{P} (f(p) \ge x) \\ &= \sum_{x = 1}^{m} (1 - \operatorname{P} (f(p) < x)) \end{aligned}

考虑怎么求P(f(p)<x)P(f(p) < x)，也就是f(p)<xf(p)<x的方案数。

可以发现nn个人会产生n+1n +1个间隔，设第ii个间隔的大小为bib_{i}，于是有

∑i=1n+1bi=m−n\sum_{i = 1}^{n + 1}b_{i} = m - n

其中bi≥0b_{i} \ge 0。

那么f(p)=i=1n+1(bi)f(p) = \max_{i =1 }^{n+1 }(b_{i})。

故对于f(p)<xf(p) < x，要有∀i∈[1,n]\forall i \in [1,n]，有bi<xb_{i} < x。

考虑容斥。设Ai:bi>xA_{i} : b_{i} > x。则有

∣⋂i=1n+1Ai‾∣=∣S∣−∑∣Ai∣+∑∣Ai∩Aj∣+⋯+(−1)n+1∑∣⋂i=1n+1Ai∣=∑i=0n+1(−1)i(n+1i)(m−x×in)\begin{aligned} |\bigcap_{i =1 } ^{n + 1}\overline{A_{i}} | &= |S| -\sum {|A_{i}|} + \sum {|A_{i} \cap A_{j}|} +\cdots + (-1)^{n + 1} \sum|\bigcap_{i =1 } ^{n + 1}A_{i}| \\ &= \sum_{i = 0}^{n + 1} (-1)^{i} \binom{n + 1}{i} \binom{m - x \times i}{n} \end{aligned}

其中(n+1i)\binom{n + 1}{i}为容斥中第ii个Σ\Sigma的个数，(m−x×in)\binom{m - x \times i}{n}可以通过隔板法等方法得到。

注意到只有m−x×i≥0m - x \times i \ge 0时组合数才有意义，即i≤min⁡(n+1,mx)i \le \min(n + 1, \frac{m}{x})。

故总的有意义的项数为∑x=1mmx=O(mlog⁡m)\sum_{x = 1}^{m} \frac{m}{x} = O(m \log m)。

所以时间复杂度为O(mlog⁡m)O(m \log m)。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using i64 = long long;
#define endl '\n'
using db = double;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
constexpr int P = 998244353;
int norm(int x)
{
    if (x < 0)
     x += P;
    if (x >= P)
        x -= P;
    return x;
}
template <class T>
T power(T a, long long b)
{
    T res = 1;for (; b; b /= 2, a *= a){if (b % 2)res *= a;}return res;
}
struct Z
{
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const{return x;}
    Z operator-() const{return Z(norm(P - x));}
    Z inv() const{assert(x != 0);return power(*this, P - 2);}
    Z &operator*=(const Z &rhs){x = i64(x) * rhs.x % P;return *this;}
    Z &operator+=(const Z &rhs){x = norm(x + rhs.x);return *this;}
    Z &operator-=(const Z &rhs){x = norm(x - rhs.x);return *this;}
    Z &operator/=(const Z &rhs){return *this *= rhs.inv();}
    friend Z operator*(const Z &lhs, const Z &rhs){Z res = lhs;res *= rhs;return res;}
    friend Z operator+(const Z &lhs, const Z &rhs){Z res = lhs;res += rhs;return res;}
    friend Z operator-(const Z &lhs, const Z &rhs){Z res = lhs;res -= rhs;return res;}
    friend Z operator/(const Z &lhs, const Z &rhs){Z res = lhs;res /= rhs;return res;}
    friend std::istream &operator>>(std::istream &is, Z &a){i64 v;is >> v;a = Z(v);return is;}
    friend std::ostream &operator<<(std::ostream &os, const Z &a){return os << a.val();}
};

const int N = 2e6 + 100;
vector<Z> fac(N + 1);
vector<Z> invfac(N + 1);
Z binom(int nn, int mm)
{
    if (nn < mm)
        return 0;
    return fac[nn] * invfac[nn - mm] * invfac[mm];
};

int main()
{
    fac[0] = 1;
    for (int i = 1; i <= N; ++i)
        fac[i] = fac[i - 1] * i;
    invfac[N] = 1 / fac[N];
    for (int i = N - 1; i >= 0; --i)
        invfac[i] = invfac[i + 1] * (i + 1); 

    int n, m;
    cin >> n >> m;
    Z ans = 0;
    Z sum = binom(m, n);
    for (int d = 1; d <= m; ++d)
    {
        Z res = 0;
        for (int i = 0; i <= n + 1; ++i)
        {
            LL s = d * i;
            Z sgn = (i % 2) ? -1 : 1;
            res += sgn * binom(n + 1, i) * binom((m + 1) - s - 1, n);
            if (s > m)
                break;
        }
        ans += (1 - res / sum);
    }
    cout << ans << endl;
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
爱奇艺2020校招编程题汇总
快手24秋招游戏引擎岗
哔哩哔哩2021校园招聘移动端方向笔试卷
全部 >
面经
面试常考问题整理
面试真题：经典海量数据处理题最详解析（下）
Springboot全套注解解析《看不懂算我输》
0926腾讯音乐笔试题解
全部 >
内推
员工内推码获取
【精】拼多多2024官方校招 && 2025届实习生招聘
【美团】校招社招内推，所有岗位，进度可查
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(3) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”