牛客周赛_35

A 小红的字符串切割

• 提示：vector理解成数组即可.

A

题意

一个长度为偶数的字符串，切割成长度相等的两部分

解题思路

因为长度为偶数，直接对半输出即可

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

void solve() {
    string s;
    cin >> s;
    string a = "", b = "";
    for (int i = 0; i < s.size(); i ++ ) {
        if (i < s.size() / 2) a += s[i];
        else b += s[i];
    }
    cout << a << endl << b;
}

int main() {
    solve();
    return 0;
}

B 小红的数组分配

B

题意

一个长度为2 * n 的数组，需要把所有元素平分到两个数组a 和 b 中，需要满足两个数组的数一一对应相等

解题思路

直接使用map统计每个数出现的次数，如果是偶数，就平分到两个数组中，如果存在奇数次，就无法平分，也就是无法构造

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(2 * n);
    map<int,int> mp;
    vector<int> b, c;
    for (int i = 0; i < 2 * n; i ++ ) {
        cin >> a[i];
        mp[a[i]] ++ ;
    }
    for (auto [x, y]: mp) {
        if (y % 2 == 1) {
            cout << -1 << endl;
            return ;
        }
        for (int i = 1; i <= y / 2; i ++ ) {
            b.push_back(x);
            c.push_back(x);
        }
    }
    for (int i = 0; i < b.size(); i ++ ) {
        cout << b[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < c.size(); i ++ ) {
        cout << c[i] << " ";
    }
}

int main() {
    solve();
    return 0;
}

C 小红关鸡

C

题意

有n个鸡窝，每个鸡窝位于坐标轴上某一点，有一只小鸡会随机在一直鸡窝中出现。
现在可以放两个栅栏，如果小鸡出现在栅栏中间，那就可以关住。
给出两个栅栏最大距离，问关住鸡的最大概率。

解题思路

存储鸡窝位置后，先进行排序，使得鸡窝的位置有序化。
之后只需要卡住左右的鸡窝即可，如果当前距离小于最大距离，就计算概率。
如果可以卡住，就有右区间点++，如果超出了最大距离，就左区间点++。
如何计算概率呢？就是当前卡住的鸡窝的数量 / 总的鸡窝数量。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

void solve() {
    double n, k;
    cin >> n >> k;
    vector<double> a(n);
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    double l = 0.0, r = 1.0;
    double ans = 0.0;
    while (r < n && l < n) {
        if (l >= r) r ++ ;
        else if (a[r] - a[l] <= k) {
            double now = (r - l + 1) / n;
            ans = max(ans, now);
            r ++ ;
        } else {
            l ++ ;
        }
    }
    printf("%.6lf\n", ans);
}

int main() {
    solve();
    return 0;
}

D 小红的排列构造

D

题意

给定一个数组，需要修改最少的元素，使得数组变成一个排列。

排列的定义：一个长度为 n 的数组，其中 1 ~ n 每个元素恰好出现一次。

解题思路

最少的修改次数，也就是，如果这个数本身就是1 ~n 中的元素，那就无需修改。但是如果重复出现，依旧需要修改；以及如果不再1 ~ n 的范围内的数，也需要修改。

总而言之，对于1~n中的数，如果第一次出现，就不用修改，不然就需要修改。

依旧用到了map，关于 STL容器，打算法竞赛的必修课，一定要去熟练掌握。不了解的就多去学习。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
    }
    map<int,int> mp;
    vector<int> c;
    for (int i = 1; i <= n; i ++ ) {
        if (a[i] <= n) {
            if (mp[a[i]] == 0) {
                mp[a[i]] = 1;
            } else {
                c.push_back(i);
            }
        } else {
            c.push_back(i);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (mp[i] == 0) {
            cnt ++ ;
        }
    }
    cout << cnt << endl;
    int id = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (mp[i] == 0) {
            cout << c[id] << " " << i << endl;
            id ++ ;
        }
    }
}

int main() {
    solve();
    return 0;
}

E 小红的无向图构造

E

题意

需要构造一个无向连通图，共有n个点m条边。
限制条件为第 i 号节点到 1 号节点的最短长度为 $a_i$

解题思路

先考虑如何构造，根据长度排列，去构造一棵树，边数为 n - 1 。然后再去凑 m 条边。

两种凑边的方法，一种是长度相等的边内互连，另一种是和长度相差为 1 的点去连边。这两种方法可以保证在不改变最短路的情况下去加边。

无解的情况：

• m小于n-1
• 凑不够 m 条边

在构造树的时候，优先和长度小1的第一个点去连边，方便后面的凑边。如图：

代码

• 抱着要debug的心态，可是一遍过了（
• 因为m的范围在1e5，也就是总边数并不多，循环次数不会很大，所以即使跳出循环就不会超时。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<int> g[n + 1];
    int ma = 0;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        ma = max(a[i], ma);
        g[a[i]].pb(i);
    }
    if (m < n - 1) {
        cout << -1 << endl;
        return ;
    }
    for (int i = 1; i <= ma; i ++ ) {
        if (g[i].size() == 0) {
            cout << -1 << endl;
            return ;
        }
    }
    vector<PII> v;
    g[0].pb(1);
    for (int i = 1; i <= ma; i ++ ) {
        for (int &b : g[i]) {
            v.pb({g[i - 1].front(), b});
        }
    }
    for (int i = 1; i <= ma; i ++ ) {
        for (int j = 0; j < g[i].size(); j ++ ) {
            for (int k = j + 1; k < g[i].size(); k ++ ) {
                v.pb({g[i][j], g[i][k]});
                if (v.size() >= m) break;
            }
            if (v.size() >= m) break;
        }
        if (v.size() >= m) break;
    }
    for (int i = 2; i <= ma; i ++ ) {
        for (int j = 0; j < g[i].size(); j ++ ) {
            for (int k = 1; k < g[i - 1].size(); k ++ ) {
                v.pb({g[i - 1][k], g[i][j]});
                if (v.size() >= m) break;
            }
            if (v.size() >= m) break;
        }
        if (v.size() >= m) break;
    }
    if (v.size() < m) {
        cout << -1 << endl;
        return ;
    }
    for (auto [x, y] : v) {
        cout << x << " " << y << endl;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

F 小红的子序列权值和（easy）

F

题意

给定一个数组，求左右非空子序列的权值之和。
权值定义为：数组中所有元素乘积的因子数量。

解题思路

$f() 2^{cnt1} \sum_0^{cnt2}C(cnt2, i) * \sum_0^{cnt3}C(cnt3, j)$

其中$f()=\sum_0^{cnt2}\sum_0^{cnt3}(i + 1) * (j + 1)$

$cntx$ 为 x 出现的次数

$f()$的值是怎么来的呢，根据$x=p1^{q1}p2^{q2} ……$ 其中 p 为质因子，q 为质因子出现的次数，

感觉实质也就是排列吧。作为结论要记住。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e5 + 10, inf = 1 << 30, mod = 1e9 + 7;

ll fact[N], infact[N];

ll qmi(ll a, ll k) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = a * ans % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int iniv(int x) {
    return qmi(x, mod - 2);
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * iniv(i) % mod;
    }
}

ll C(ll n, ll m) {
    if (n < m) return 1;
    return fact[n] * infact[n - m] % mod * infact[m] % mod;
}

void solve() {
    init();
    int n;
    cin >> n;
    vector<int> tong(4);
    for (int i = 0; i < n; i ++ ) {
        int x;
        cin >> x;
        tong[x] ++ ;
    }
    ll cnt = 1;
    for (int i = 1; i <= tong[1]; i ++ ) {
        cnt = cnt * 2 % mod;
    }
    ll ans = 0;
    for (int i = 0; i <= tong[2]; i ++ ) {
        for (int j = 0; j <= tong[3]; j ++ ) {
            ans += C(tong[2], i) * C(tong[3], j) % mod * (i + 1) % mod * (j + 1) % mod * cnt % mod;
            ans %= mod;
        }
    }
    //不包含空序列
    cout << (ans - 1 + mod) % mod << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}

G 小红的子序列权值和（hard)

G

题意

相比于F，只增加了 n 的数据范围。

解题思路

$（i+1)(j+1) 2^{cnt1} \sum_0^{cnt2}C(cnt2, i) \sum_0^{cnt3}C(cnt3, j)$ 这一步

可以写成 $2^{cnt1} \sum_0^{cnt2}C(cnt2, i) (i+1) \sum_0^{cnt3}C(cnt3, j)(j+1)$
也就是分别将 i 和 j 的部分拆开，将双层 for 循环改为两个单层 for 循环。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e5 + 10, inf = 1 << 30, mod = 1e9 + 7;

ll fact[N], infact[N];

ll qmi(ll a, ll k) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = a * ans % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int iniv(int x) {
    return qmi(x, mod - 2);
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * iniv(i) % mod;
    }
}

ll C(ll n, ll m) {
    if (n < m) return 1;
    return fact[n] * infact[n - m] % mod * infact[m] % mod;
}

void solve() {
    init();
    int n;
    cin >> n;
    vector<int> tong(4);
    for (int i = 0; i < n; i ++ ) {
        int x;
        cin >> x;
        tong[x] ++ ;
    }
    ll cnt = 1;
    for (int i = 1; i <= tong[1]; i ++ ) {
        cnt = cnt * 2 % mod;
    }
    ll ans = 0;
    ll c1 = 0;
    for (int i = 0; i <= tong[2]; i ++ ) {
        c1 += C(tong[2], i) * (i + 1) % mod;
        c1 %= mod;
    }
    ll c2 = 0;
    for (int i = 0; i <= tong[3]; i ++ ) {
        c2 += C(tong[3], i) * (i + 1) % mod;
        c2 %= mod;
    }
    cout << c1 * c2 % mod * cnt % mod - 1 + mod % mod;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}