牛客周赛 Round 151 

by JiuQiin 牛客, 题解on Posted on

一些废话

不喜欢这次的牛客比赛，打得太抽象了，除了题目带给我的感觉很不顺手以外，打的人很少也没什么意思了，不，主要还是自己太🍬了，怎么连一个二维前缀和都想不到呢，妈的，直接卡死在第四题，同时，我感觉这次没什么很有意思的题，真的很想念以前的牛客，倒也没有很久以前，也就前几个月，多有意思啊 (´；д；`)

Contents hide
1 一些废话
2 A 运动会
2.1 题意
2.2 思路
2.3 代码
3 B 数方格
3.1 题意
3.2 思路
3.3 代码
4 C 列竖式
4.1 题意
4.2 思路
4.3 代码
5 D 走迷宫
5.1 题意
5.2 思路
5.3 代码
6 E 跷跷板
6.1 题意
6.2 思路
6.3 代码
7 F 解方程
7.1 题意
7.2 思路
7.3 代码 O(nn)O(n \sqrt n)
7.4 优化代码 O(nlog⁡n)O(n\log n)
7.5 组合数+取模类

A 运动会

题意

给出一段由 ‘_‘， ‘|’， ‘=’ 构成的字符串，分别为跑道，支柱，杆，由两个支柱，中间有若干个非零的杆构成一个栏架，问，一共有多少个合法的栏架

思路

双指针{\color{Yellow}双指针}，每次遇到支柱就往后面找杆，若有连续的杆，紧接着的又是支柱，则为一个合法的栏架

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;

    int ans = 0;
    for (int i = 1, j = 1; i <= n; ++i) {
        if (s[i] != '|')
            continue;
        j = max(i, j);
        while (j < n && s[j + 1] == '=') {
            ++j;
        }
        if (j < n && s[j] == '=' && s[j + 1] == '|') {
            ++ans;
        }
        i = j;
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B 数方格

题意

给出 n 行 m 列的网格和一个数 x，每个网格都有其非负权值，请你选择一行和一列，总共 n + m – 1 个网格，这些网格的权值异或和为 x，你可以最多修改其中一个网格的权值

思路

没啥好说的，直接选第一行第一列，求出除开 a1,1a_{1, 1} 一行一列其余的异或和为 smsm，设 a1,1=ya_{1, 1} = y， 最后要使得 sm⨁y=xsm \bigoplus y = x， 根据异或运算的可逆性，y=sm⨁xy = sm \bigoplus x，然后修改 a1,1a_{1, 1} 即可

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    int n, m, x, ans =0 ;
    cin >> n >> m;
    vector<vector<int>> g(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> g[i][j];
        }
    }
    cin >> x;

    for (int i = 2; i <= n; ++i) {
        ans ^= g[i][1];
    }
    for (int j = 2; j <= m; ++j) {
        ans ^= g[1][j];
    }

    ans ^= x;
    g[1][1] = ans;

    cout << "YES" << endl;
    cout << 1 << " " << 1 << " " << ans << endl;
    cout << 1 << " " << 1 << endl;
    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C 列竖式

题意

给出两个小数，求出这两个数的相加的进位次数，保证数的长度小于等于 10

思路

直接用高精度相加的做法，每次记录一下进位的数字为多少，在下一次加上即可，对了，记得统一位数

这可能就是我不大喜欢这次比赛的原因吧，这种题出的目的是为了啥，有模版直接抄就行，我宁愿你出点陷阱题，把我们当成傻子耍也行啊，我现在都记得 codeforces codeforces 有道题说什么对 66579 取模，但其实答案根本达不了这么大，纯纯误导

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    string s, t;
    cin >> s >> t;

    int sa = 0, sb = 0, ta = 0, tb = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '.') {
            break;
        }
        ++sa;
    }
    for (int i = s.size() - 1; i >= 0; --i) {
        if (s[i] == '.')
        {
            break;
        }
        ++sb;
    }
    for (int i = 0; i < s.size(); ++i)
    {
        if (t[i] == '.')
        {
            break;
        }
        ++ta;
    }
    for (int i = s.size() - 1; i >= 0; --i)
    {
        if (t[i] == '.')
        {
            break;
        }
        ++tb;
    }

    for (int i = 1; i <= 10 - sa; ++i) {
        s = '0' + s;
    }
    for (int i = 1; i <= 10 - sb; ++i) {
        s.push_back('0');
    }
    for (int i = 1; i <= 10 - ta; ++i)
    {
        t = '0' + t;
    }
    for (int i = 1; i <= 10 - tb; ++i)
    {
        t.push_back('0');
    }

    // cout << s << endl;
    // cout << t << endl;

    int m = s.size(), pre =0 , ans = 0;
    for (int i = m - 1; i >= 0; --i) {
        if (s[i] == '.')
            continue;
        int a = s[i] - '0';
        int b = t[i] - '0';
        int c = a + b + pre;
        if (c >= 10) {
            ++ans;
        }
        pre = c / 10;
    }

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D 走迷宫

题意

给出一个 n 行 m 列的网格，起点 S，终点 E，‘.’ 代表可通过的方格，即路，’#’ 代表不可通过的方格，即墙，这道题相对于常规的 BFS 的不同之处在于他还设置了个 a 行 b 列的矩形，起点在此矩形的左上角，每次移动，此矩形要进行相同方向和距离的移动，墙不可在此矩形以内，若最后能使得终点 E 在此矩形的左上角，则输出 Yes，否则输出 No

思路

对于常规的 BFS ，由于每个点可能都要走一遍，从最坏的来看，时间复杂度已经达到 O（n⋅m）O（n \cdot m），而这个每次都要判断一行或者一列中是否有墙，时间复杂度就达到了 O（n⋅m⋅max(a,b)）≈1e9O（n \cdot m \cdot max(a, b)）\approx 1e9，一般上限是 8.3e ，这个肯定是过不了的，我当时就卡在这儿，怎么就没想到 二位前缀和{\color{Yellow}二位前缀和} 呢？直接 O（1）O（1）判断，然后时间复杂度又回到了 O(n⋅m)O(n \cdot m)，包过的

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PII pair<int, int>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void solve() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    vector<vector<int>> s(n + 1, vector<int>(m + 1, 0));

    int sx, sy, tx, ty;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char ch;
            cin >> ch;
            if (ch == 'S') {
                sx = i;
                sy = j;
            }
            if (ch == 'E') {
                tx = i;
                ty = j;
            }
            if (ch == '#') {
                s[i][j] = 1;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i - 1][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            s[i][j] += s[i][j - 1];
        }
    }

    auto area = [&](int x1, int y1, int x2, int y2)
    {
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] > 0;
    };

    auto in = [&](int x, int y)
    {
        return x >= 1 && x <= n && y >= 1 && y <= m;
    };

    vector<vector<int>> vis(n+ 1,vector<int>(m+ 1, 0));

    queue<PII> q;

    q.push({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        if (x == tx && y == ty) {
            cout << "Yes" << endl;
            return;
        }

        if (vis[x][y]) continue;
        vis[x][y] = 1;

        for (int i = 0; i < 4; ++i)
        {
            int fx1 = x + dx[i];
            int fy1 = y + dy[i];
            int fx2 = fx1 + a - 1;
            int fy2 = fy1 + b - 1;
            if (!in(fx1, fy1) || !in(fx2, fy2)) continue;
            if (area(fx1, fy1, fx2, fy2)) continue;
            q.push({fx1, fy1});
        }
    }

    cout << "No" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E 跷跷板

题意

有 nn 个同学在玩跷跷板，木板左端点为 00，右端点为 ll，第 ii 个同学在 xix_i，体重为 wiw_i，要想让跷跷板平衡，需满足以下公式：（pp 为整数）

∑xi<pwi(p−xi)+W⋅pl⋅p2=∑xi>pwi(xi−p)+W⋅(l−p)l⋅l−p2\sum_{x_i < p} w_i (p – x_i) + \frac{W \cdot p}{l} \cdot \frac{p}{2} = \sum_{x_i > p} w_i (x_i – p) + \frac{W \cdot (l – p)}{l} \cdot \frac{l – p}{2}

每次需减少一个同学，让剩余同学仍能让跷跷板平衡，问有多少种方案数

思路

我是傻逼，我当时以为那个求和符号会管到后面所有，也就是 W⋅pl⋅p2\frac{W \cdot p}{l} \cdot \frac{p}{2} 这一部分，右边同理

OK，正确做法就是公式化简

∑xi<pwi(p−xi)+W⋅pl⋅p2=∑xi>pwi(xi−p)+W⋅(l−p)l⋅l−p2\sum_{x_i < p} w_i (p – x_i) + \frac{W \cdot p}{l} \cdot \frac{p}{2} = \sum_{x_i > p} w_i (x_i – p) + \frac{W \cdot (l – p)}{l} \cdot \frac{l – p}{2}
∑i=1nwi⋅p−∑i=1nwi⋅xi=W⋅[(l−p)2−p2]2l\sum_{i = 1}^{n}w_i \cdot p – \sum_{i = 1}^nw_i \cdot x_i = \frac{W \cdot [(l – p)^2 – p^2]}{2 l}

令 S=∑i=1nwi ,T=∑i=1nwi⋅xiS = \sum_{i = 1}^n w_i\ , \quad T = \sum_{i = 1}^n w_i \cdot x_i，得

S⋅p−T=W⋅(l−2p)2S \cdot p – T = \frac{W \cdot (l – 2 p)}{2}
p=W⋅l+2⋅T2⋅(S+W)p = \frac{W \cdot l+ 2 \cdot T}{2 \cdot (S +W)}

所以，只要该式子能被整除，则说明存在可行的 pp

代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;

void solve() {
    LL n, l, W;
    cin >> n >> l >> W;
    vector<LL> x(n+  1, 0), w(n + 1, 0);

    __int128 S = 0, T = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> x[i] >> w[i];
        S += w[i];
        T += x[i] * w[i];
    }

    LL ans = 0;
    for (LL i = 1; i <= n; ++i) {
        __int128 s = S - w[i];
        __int128 t = T - x[i] * w[i];
        __int128 up = W * l + 2 * t;
        __int128 down = (s + W) * 2;
        if (up % down == 0) {
            ++ans;
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LL T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F 解方程

题意

给出一个由 nn 个数构成的数组 aa，给出一个整数 kk，你需要从数组 aa 中选取 kk 个数，求得他们的最大公约数，问，在保证最大公约数尽可能大的情况下有多少种选择方案

思路

我当时第一反应是用二分，先枚举最大公约数是多少，然后看有多少个数满足这个最大公约数的倍数，然后，得满足的个数为 mm，从 m 中选取 kk 个，求 (mk)\binom{m}{k} 即可。在这 mm 个中随便选取 kk 个都是一种方案，不可能会使最大公约数更大或者更小。假设会更大，那么最大公约数就不可能是该数，一定会更大；假设会更小，这些数一定都是最大公约数的倍数，不可能会更小

但是，用二分的话，他的总体是可以二分的，但是并不是说大的可以，比他小的就都可以。因为这是倍数，你不知道哪个约数会出现在答案中，他不是像一个一个加，一个一个减的那种

但是，我们可以利用这种思路，预处理出每个数的约数，时间复杂度为 O（n⋅n）O（n \cdot \sqrt n ），记录约数出现次数，之后有 qq 次询问，预处理出每个 kk 对应的答案，从大到小枚举约数，看第一次约数出现次数大于等于 kk 的约数， 用差分去处理，如果当前出现的次数为 cnticnt_i，则之后出现的cntj>cnti cnt_j > cnt_i 才会更新，因为后面的约数更小，若出现次数也更小，断然不会取他出现的次数，只有后面更小的约数，但出现的次数更大才会被更新， 记录上一次最大次数，然后更新 mx+1 ˜cntimx + 1 \: \~\ \: cnt_i 这段为 cnticnt_i。若出现次数为 mm，答案即为 (mk)\binom{m}{k}，预处理时间复杂度为 O(n)O(n)，整体时间复杂度为 O（n32）O（n^\frac{3}{2}）

代码 O(nn)O(n \sqrt n)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL MAX = 2e5 + 100;


void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 1, 0), cnt(MAX, 0);

    auto pre = [&](int x)
    {
        for (int i = 1; i * i <= x; ++i)
        {
            if (x % i == 0)
            {
                ++cnt[i];
                if (x / i != i)
                {
                    ++cnt[x / i];
                }
            }
        }
    };

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pre(a[i]);
    }

    int mx = 0;
    vector<int> d(MAX + 2, 0);
    for (int i = MAX; i >= 1; --i)
    {
        if (cnt[i] > mx)
        {
            d[mx + 1] += cnt[i];
            d[cnt[i] + 1] -= cnt[i];
        }
        mx = max(mx, cnt[i]);
    }

    vector<int> ans(MAX + 1, 0);
    for (int i = 1; i <= MAX; ++i)
    {
        ans[i] = ans[i - 1] + d[i];
    }

    int q;
    cin >> q;
    while (q--)
    {
        int k;
        cin >> k;
        cout << comb.C(ans[k], k) << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    LL T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

优化代码 O(nlog⁡n)O(n\log n)

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

const int MOD = 1000000007;
const int MAXA = 200000;
int freq[MAXA + 1];
int cnt[MAXA + 1];
int best[200005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }

    // cnt[d] = 能被 d 整除的数的个数
    for (int d = 1; d <= MAXA; d++) {
        for (int j = d; j <= MAXA; j += d)
            cnt[d] += freq[j];
    }

    int ptr = 0;

    for (int d = MAXA; d >= 1; d--) {
        while (ptr < cnt[d]) {
            ++ptr;
            best[ptr] = d;
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int k;
        cin >> k;
        cout << comb.C(cnt[best[k]], k).val() << '\n';
    }

    return 0;
}

组合数+取模类

using i64 = long long;

template <class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b >>= 1, a *= a)
    {
        if (b & 1)
        {
            res *= a;
        }
    }
    return res;
}

template <int P>
struct MInt
{
    int x;

    constexpr MInt() : x(0) {}

    constexpr MInt(i64 v)
    {
        x = v % P;
        if (x < 0)
        {
            x += P;
        }
    }

    constexpr int val() const
    {
        return x;
    }

    constexpr MInt inv() const
    {
        return power(*this, P - 2);
    }

    constexpr MInt &operator+=(const MInt &rhs)
    {
        x += rhs.x;
        if (x >= P)
        {
            x -= P;
        }
        return *this;
    }

    constexpr MInt &operator-=(const MInt &rhs)
    {
        x -= rhs.x;
        if (x < 0)
        {
            x += P;
        }
        return *this;
    }

    constexpr MInt &operator*=(const MInt &rhs)
    {
        x = 1LL * x * rhs.x % P;
        return *this;
    }

    constexpr MInt &operator/=(const MInt &rhs)
    {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator+(MInt a, const MInt &b)
    {
        return a += b;
    }

    friend constexpr MInt operator-(MInt a, const MInt &b)
    {
        return a -= b;
    }

    friend constexpr MInt operator*(MInt a, const MInt &b)
    {
        return a *= b;
    }

    friend constexpr MInt operator/(MInt a, const MInt &b)
    {
        return a /= b;
    }

    friend ostream &operator<<(ostream &os, const MInt &a)
    {
        return os << a.x;
    }

    friend istream &operator>>(istream &is, MInt &a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
};

using Z = MInt<1000000007>;

struct Comb
{
    int n;
    vector<Z> fac_;
    vector<Z> ifac_;
    vector<Z> inv_;

    Comb() : n(0), fac_(1, 1), ifac_(1, 1), inv_(1, 0) {}

    void init(int m)
    {
        if (m <= n)
        {
            return;
        }

        fac_.resize(m + 1);
        ifac_.resize(m + 1);
        inv_.resize(m + 1);

        for (int i = n + 1; i <= m; i++)
        {
            fac_[i] = fac_[i - 1] * i;
        }

        ifac_[m] = fac_[m].inv();

        for (int i = m; i > n; i--)
        {
            ifac_[i - 1] = ifac_[i] * i;
            inv_[i] = ifac_[i] * fac_[i - 1];
        }

        n = m;
    }

    Z fac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return fac_[m];
    }

    Z ifac(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return ifac_[m];
    }

    Z inv(int m)
    {
        if (m > n)
        {
            init(2 * m);
        }
        return inv_[m];
    }

    Z C(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(m) * ifac(n - m);
    }

    Z P(int n, int m)
    {
        if (m < 0 || m > n)
        {
            return 0;
        }
        return fac(n) * ifac(n - m);
    }
};

Comb comb;
「因为失去,所以明白。」
— 漩涡鸣人 · 火影忍者
Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注