前言：

• 該比賽有?？凸俜揭曨l講解——?？椭苜?5視頻講解回放

A - 小紅的字符串切割

思路：

• 分兩半輸出即可

以下是代碼部分

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;


void solve()
{
    string s;
    cin >> s;
    s = '&' + s;
    int i;
    for(i = 1; i <= s.length() / 2; i ++)
        cout << s[i];
    cout << endl;
    for(; i < s.length(); i ++)
        cout << s[i];
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

B - 小紅的數(shù)組分配

思路：

• 從小到大排序，判斷元素大小是否兩兩相等。
  • 若是， 則輸出數(shù)組
  • 否則輸-1

以下是代碼部分

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

#define endl '\n'
using ll = long long;
const int N = 2e5 + 10;

int a[N];

void solve()
{
    int n;
    cin >> n;
  //注意題目是2*n
    n *= 2;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
  //排序
    sort(a + 1, a + n + 1);
  //判斷是否兩兩相等
    for(int i = 1; i <= n; i += 2)
        if(a[i] != a[i + 1])
        {
            cout << -1 << endl;
            return ;
        }
  //分奇偶輸出
    for(int i = 1; i <= n; i++)
        if(i & 1)
            cout << a[i] << ' ';
    cout << endl;
    for(int i = 1; i <= n; i ++)
        if((i & 1) == 0)
            cout << a[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

C-小紅關(guān)雞

思路 1（渣渣的思路）：

• 從小到大排序， 找到比小的最大數(shù)的位置， 算出區(qū)段中的數(shù)的個(gè)數(shù)，并用ans記錄數(shù)量最多的值

以下是代碼部分

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;

ll a[N];
//判斷
bool check(ll x, ll y)
{
    if(x <= y) return true;
    return false;
}
//二分查找
int finds(ll v, int n)
{
    int l = 1, r = n, mid;
    while(l < r)
    {
        mid = (r + l) >> 1;
      //分兩次判斷，使其可以跳出循環(huán)
        if(check(a[mid + 1], v))
            l = mid + 1;
        else if(check(a[mid], v))
        {
            if((r + l) / 2 == l) break;
            l = mid;
        }
        else
            r = mid - 1;
    }
    mid = (r + l) >> 1;
  //返回下標(biāo)
    return mid;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        int temp = finds(a[i] + k, n);
      //記錄最大值
        ans = max(ans, temp - i + 1);
    }
  //輸出概率
    cout << double(ans) / n << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

思路2（思路來(lái)源——LittleXi的題解）：

• 利用雙指針從頭到尾遍歷1次即可
• 判斷區(qū)段內(nèi)的合法數(shù)值的數(shù)量，并統(tǒng)計(jì)最大值即可

以下是代碼部分，代碼參考來(lái)源——GhostLX知乎題解

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;

int a[N];

void solve()
{
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
  //從小到大排序
    sort(a + 1, a + n + 1);
    int l = 1, r = 1;
    int ans = 1;
  //雙指針遍歷
    while(l <= n)
    {
        while(a[r + 1] - a[l] <= k && r < n)
            r ++;
        ans = max(ans, r - l + 1);
        l ++;
    }
  //輸出
    cout << double(ans) / n << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

D-小紅的排列構(gòu)造

思路：

• 首先查找原數(shù)組中有多少個(gè)數(shù)符合排列。
• 后不符合排列的數(shù)都進(jìn)行按照順序修改即可

以下是代碼部分

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;
//儲(chǔ)存原數(shù)組
int a[N];
//儲(chǔ)存需要修改的數(shù)組， key為坐標(biāo)， value為數(shù)值
map<int, int> mp;
//儲(chǔ)存1-n有哪些數(shù)沒(méi)用到
bool vis[N];

void solve()
{
    int n;
    cin >> n;
  //存儲(chǔ)需要修改的數(shù)的個(gè)數(shù)，初始化為n
    int cnt = n;
  //輸入
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        mp[i] = a[i];
    }
    for(int i = 1; i <= n; i ++)
    {
      //大于n，則直接跳過(guò)
        if(a[i] > n) continue;
      //如果數(shù)值a[i]沒(méi)用到過(guò)
        if(!vis[a[i]])
          //標(biāo)記為用過(guò)， 刪除該結(jié)點(diǎn)， 需要修改的數(shù)-1
            vis[a[i]] = true, mp.erase(i), cnt --;
    }
  //輸出需要修改的數(shù)的個(gè)數(shù)
    cout << cnt << endl;
  //迭代器， 初始化迭代器
    auto it = mp.begin();
  //暴力
    for(int i = 1; i <= n; i ++)
      //如果這個(gè)數(shù)值沒(méi)有用到過(guò)
        if(!vis[i])
          //mp中，在這個(gè)坐標(biāo)下的value修改為沒(méi)用過(guò)的值，并使迭代器移到下一位
            it->second = i, it ++;
  //遍歷輸出
    for(auto x : mp)
        cout << x.first << ' ' << x.second << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

代碼參考來(lái)源——長(zhǎng)途

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

const int N=100005;
int a[N];
int n;
bool st[N];
int main()
{
    scanf("%d",&n);
    vector<int> ver;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
      //如果范圍在1~n范圍內(nèi)，則標(biāo)記為true
        if(a[i]>=1&&a[i]<=n&&!st[a[i]])
            st[a[i]]=true;
        else
          //否則把坐標(biāo)放入到ver數(shù)組中
            ver.push_back(i);
    }

    vector<int> ver2;
    for(int i=1;i<=n;i++)
      //如果該數(shù)值未用過(guò)
        if(!st[i])
          //把需要修改后的值放入ver2數(shù)組中
            ver2.push_back(i);
	//輸出需要修改的數(shù)值個(gè)數(shù)
    printf("%d\n", (int)ver.size());
  //輸出即可
    for(int i=0;i<ver.size();i++)
        printf("%d %d\n",ver[i],ver2[i]);
}

E-小紅的無(wú)向圖構(gòu)造

思路：

• 實(shí)際上就是建一個(gè)樹。該樹分層。結(jié)點(diǎn) 在第幾層，則它離頭結(jié)點(diǎn) 的距離為多少。
  • 總而言之，按照距離分層建圖。
• 后若最大的邊數(shù)小于 則為
• 若也輸出
• 其他情況有解

以下是代碼部分，代碼參考來(lái)源——牛客周賽35視頻講解回放

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

#define endl '\n'
const int N = 2e5 + 10;

***[i]的i代表層數(shù)， g[i]的值代表結(jié)點(diǎn)的標(biāo)號(hào)
vector<int> g[N];

int main()
{
    int n, m, maxn = 0;
    cin >> n >> m;
    //建樹，并標(biāo)記最大值
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        maxn = max(maxn, a[i]);
        g[a[i]].push_back(i);
    }
    //已知樹的邊數(shù)為n - 1, 當(dāng)無(wú)法建樹時(shí)
    if(m < n - 1)
        return cout << -1, 0;
    //儲(chǔ)存相連的坐標(biāo)
    vector<pair<int, int>> v;
    //先建樹
    for(int i = 1; i <= maxn; i++)
    {
        //如果有一層為空，則無(wú)法建樹
        if(g[i].empty())
            return cout << -1, 0;
        //如果非空，則把層數(shù)和下標(biāo)存入v中
        for(auto j : g[i])
            v.emplace_back(g[i - 1][0], j);
    }
    //如果建立出樹之后，仍不滿足條件， 求最多多少條邊
    if(v.size() < m)
    {
        //此循環(huán)用來(lái)同層節(jié)點(diǎn)相連
        for(int i = 1; i <= maxn; i++)
        {
            for(int j = 0; j < g[i].size(); j ++)
            {
                for(int k = j + 1; k < g[i].size(); k ++)
                {
                    v.emplace_back(g[i][j], g[i][k]);
                    if(v.size() == m) break;
                }
                if(v.size() == m) break;
            }
            if(v.size() == m) break;
        }
        //該循環(huán)用來(lái)相鄰層的節(jié)點(diǎn)相連
        for(int i = 1; i <= maxn; i ++)
        {
            //注意排除第一個(gè)結(jié)點(diǎn)，因?yàn)橹斑B過(guò)了。
            for(int j = 1; j < g[i].size(); j ++)
            {
                for(auto k : g[i + 1])
                {
                    v.emplace_back(g[i][j], k);
                    if(v.size() == m) break;
                }
                if(v.size() == m) break;
            }
            if(v.size() == m) break;
        }
    }
    //判斷邊的數(shù)量是否滿足條件
    if(v.size() < m)
        return cout << -1, 0;
    //輸出
    for(auto i : v) cout << i.first << ' ' << i.second << endl;

    return 0;
}

F & G - 小紅的子序列權(quán)值和

思路1牛客官方視頻題解：

• ……
• 結(jié)論（需記?。?
  • 那么x的因子數(shù)為……

1. 先把 排除掉，之后再考慮
2. 先利用二項(xiàng)式公式求出取 個(gè) ， 個(gè) 的總共組合數(shù)。再乘以么個(gè)組合的因數(shù)個(gè)數(shù) 3.后是否選擇 狀態(tài)為 , 為 的個(gè)數(shù)。

• 可得出公式——（為數(shù)值為的個(gè)數(shù)， 為的個(gè)數(shù) 為的個(gè)數(shù)）

• 所以可以用乘法逆元快速求出組合數(shù)，再乘權(quán)值即可

以下是代碼部分

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

#define endl '\n'
using ll = long long;
const int N = 1e5 + 10;

// 該數(shù)值的個(gè)數(shù)
int tong[4];
int mod = 1e9 + 7;
//快速冪
ll power(ll base, ll pow)
{
    ll res = 1;
    while(pow)
    {
        if(pow&1) res = res * base % mod;
        pow >>= 1;
        base = base * base % mod;
    }
    return res;
}
//小費(fèi)馬求乘法逆元
ll inv(ll x)
{
    return power(x, mod - 2);
}
ll fac[N] = {1};
//求組合數(shù)
ll C(int n, int m)
{
    return fac[n] * inv(fac[n - m]) % mod * inv(fac[m]) % mod;
}

int main()
{
    int n;
    cin >> n;
    //求階乘
    for(int i = 1; i <= n; i ++)
        fac[i] = fac[i - 1] * i % mod;

    ll temp = 1, c2 = 0, c3 = 0;
    //統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù)
    for(int i = 0; i < n; i ++)
    {
        int x; cin >> x;
        tong[x] ++;
    }
    //temp儲(chǔ)存數(shù)值1的貢獻(xiàn)
    for(int i = 1; i <= tong[1]; i++)
        temp = temp * 2 % mod;
    //每次求出
    for(int i = 0; i <= tong[2]; i ++)
    {
        c2 += C(tong[2], i) * (i + 1) % mod;
        c2 %= mod;
    }
    //每次求出
    for(int i = 0; i <= tong[3]; i ++)
    {
        c3 += C(tong[3], i) * (i + 1) % mod;
        c3 %= mod;
    }
    cout << (c2 * c3 % mod * temp % mod - 1 + mod) % mod << endl;

    return 0;
}

優(yōu)化方案

• 參考來(lái)源smilences的題解

• 

• 用此公式，替換到思路1的代碼中。

• 推導(dǎo)過(guò)程如下

以下是代碼部分

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

using ll = long long;
// 該數(shù)值的個(gè)數(shù)
ll tong[4];
int mod = 1e9 + 7;
//快速冪
ll power(ll base, ll pow)
{
    ll res = 1;
    while(pow)
    {
        if(pow&1) res = res * base % mod;
        pow >>= 1;
        base = base * base % mod;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x; cin >> x;
        tong[x] ++;
    }
    ll ans = 1;
  //利用推導(dǎo)的公式求值為2的情況
    if(tong[2])
        ans *= tong[2] * power(2, tong[2] - 1) % mod + power(2, tong[2]);
    ans %= mod;
  //利用推導(dǎo)的公式求值為3的情況
    if(tong[3])
        ans *= tong[3] * power(2, tong[3] - 1) % mod + power(2, tong[3]);
    ans %= mod;
  //求值為1時(shí)的情況
    ans *= power(2, tong[1]);
    ans %= mod;

    cout << (ans + mod - 1) % mod << '\n';

    return 0;
}