牛客周赛 Round 111题解

A 小红的阶梯

判一下即可。

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if (c - b == 1 && b - a == 1) cout << "Yes" << "\n";
    else cout << "No" << "\n";
}

B 小红的数组取数

化简一下式子， $S = (Sum(a)-n\times a_x)-(Sum(b)-n\times b_y)$ ，很显然在 $a$ 找最小值，在 $b$ 找最大值即为答案。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    cout << min_element(all(a)) - a.begin() + 1 << " " << max_element(all(b)) - b.begin() + 1 << "\n";
}

C 小红抽卡

首先可以看出， $x$ 次操作之后，数组会复原 $\rightarrow$ $k = k\ mod\ x$

然后对前 $x$ 个元素循环移位即可。

void solve() {
    ll n, k, x;
    cin >> n >> k >> x;
    k %= x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < x; ++i) cout << a[(i - k + x) % x] << " ";
    for (int i = x; i < n; ++i) cout << a[i] << " ";
    cout << "\n";
}

D 小红的好数对

如果 $a$ 和 $b$ 拼接后的值是 $11$ 的倍数的，有

a\times 10^{len(b)} + b\ \%\ 11 =0

等价于

b\ \%\ 11= (-a\times 10^{len(b)})\ \%\ 11

用 $freq[i][j]$ 表示数位为 $i$ 且对 $11$ 取模为 $j$ 的数字个数，对于每个 $a_i$ ，检查在每一个长度下的目标余数的个数即可。

需要检查有没有把自己算进去。

注意会爆 $int$ 。

vector<ll> p10(12);
 
void init() {
    p10[0] = 1;
    for (int i = 1; i <= 11; ++i) p10[i] = (p10[i - 1] * 10) % 11;
}
 
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n), sz(n);
    vector<vector<ll>> freq(12, vector<ll>(11, 0));
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sz[i] = to_string(a[i]).size();
        freq[sz[i]][a[i] % 11]++;
    }
 
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= 11; ++j) {
            ll t = (((-a[i] * p10[j]) % 11 + 11 ) % 11);
            ans += freq[j][t];
        }
        if ((((-a[i] * p10[sz[i]]) % 11 + 11 ) % 11) == a[i] % 11) ans--;
    }
    cout << ans << "\n";
}

E 小芳的排列构造

首先发现，如果一个数的左边和右边均有比它大的数字，当前数字对答案就没有贡献。那么，对于任何一种排列，最大值会被计算两遍，次大值会被计算一遍。

在此基础上，我们只需要从 $1\sim n-2$ 中选择数字，使其和为 $k-3\times n - 1$ 即可。

之后从左到右、从小到大排列这些数字，使得他们均有效，再用 $n$ 和 $n-1$ 把剩下的用不到的数字卡掉即可。

void solve() {
    ll n, k;
    cin >> n >> k;
    if (n == 1 && k == 2) {
        cout << 1 << "\n";
        return;
    }
    vector<int> ap;
    k -= n + n + n - 1;
    vector<bool> vis(n + 1);
    for (int i = n - 2; i >= 1; --i) {
        if (k >= i) {
            k -= i;
            ap.pb(i);
            vis[i] = 1;
        }
        if (k <= 0) break;
    }

    if (k != 0) {
        cout << -1 << "\n";
        return;
    }
    for (int i = ap.size() - 1; i >= 0; --i) {
        cout << ap[i] << " ";
    }
    cout << n - 1 << " ";
    for (int i = 1; i <= n - 2; ++i) {
        if (!vis[i]) cout << i << " ";
    }
    cout << n << "\n";
}

F 小红的排列构造

把排序看成一个置换，记 $c$ 为轮换个数，有 $k = n-c$ 。

构造 $c-1$ 个 $2-循环$ ，剩下的构成一个循环即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 30; i >= 0; --i) {
        int cand = ans | (1 << i), prev = 0;
        bool ok = false;
        unordered_set<int> vis;
        vis.insert(0);
        for (int i = 0; i < n; ++i) {
            prev ^= a[i];
            int t = prev & cand;
            if (vis.find(ca***is.end()) {
                if (i == n - 1) ok = true;
                vis.insert(t);
            }
        }
        if (ok) ans = cand;
    }
    cout << ans << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

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

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}