博客原题解地址：https://zhuanlan.zhihu.com/p/685066445

A

输出s.substr(0, len)和s.substr(len, len)即可。

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    string s;
    cin >> s;
    int len = s.size() / 2;
    cout << s.substr(0, len) << el;
    cout << s.substr(len, len);
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

B

统计每个数字出现的次数

显然有数字出现次数为奇数，则不行。然后就是每种数字均分给a,b即可。

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
int a[N], b[N], c[N];
void solve()
{
    cin >> n;
    map<int, int> mp;
    int x;
    rep(i, 1, 2 * n)
    {
        cin >> x;
        ++ mp[x];
    }
    int cnt = 0;
    for(auto [u, v] : mp)
    {
        if(v & 1)
        {
            cout << -1 << el;
            return ;
        }
        int len = v / 2;
        rep(i, 1, len)
        {
            a[ ++ cnt] = u;
            b[cnt] = u;
        }
    }
    rep(i, 1, n)
    {
        if(i > 1)
            cout << ' ';
        cout << a[i];
    }
    cout << el;
    rep(i, 1, n)
    {
        if(i > 1)
            cout << ' ';
        cout << a[i];
    }
    cout << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

C

因为只有一只鸡会出生，显然能围住的鸡窝越多越好。

最终答案就是最多能围住的鸡窝 / n。两个挡板最大距离不超过k，显然双指针跑一遍即可。

（本场我唯一的WA，没有对初始数组排序）

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
int k;
int a[N];
void solve()
{
    cin >> n >> k;
    rep(i, 1, n)
    {
        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 ++;
    }
    double res = 1.0 * ans / n;
    cout.setf(ios::fixed);
    cout << fixed << setprecision(10) << res << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

D

显然原本为 $1\sim n$ 的数字最多保留一个，将其标记掉。

用set存储哪些 $1\sim n$ 的数字还没有，对没标记的数字依次赋值。

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
int a[N];

bool vis[N]; //数字
void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    set<int> st;
    rep(i, 1, n)
    {
        st.insert(i);
    }
    vector<int> pos;

    rep(i, 1, n)
    {
        // cerr << i << el;
        if(a[i] <= n)
        {
            if(st.find(a[i]) != st.end())
            {
                st.erase(a[i]);
                // debug(a[i]);
            }
            else {
                pos.push_back(i);
            }
        }
        else {
            pos.push_back(i);
        }
    }
    vector<PII> ans;
    int cnt = 0;
    for(int v : st)
    {
        ans.push_back({pos[cnt ++], v});
    }
    cout << ans.size() << el;
    for(auto [u, v] : ans)
    {
        cout << u << ' ' << v << el;
    }

}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

E

算是一道构造好题。

考虑分层图，按照距离划分。显然只能在相邻的层、同一层内连边，否则距离只会更小。

按距离将每个点分类e[dis]。显然e[dis] > 0时，必然有e[dis - 1] > 0。并且除了a[1] = 0外不允许其余a[i] = 0。

然后将下一层所有点都连接到本层第一个点e[dis][0]。

这样之后，就可以保证构造出a数组的最小连边数，如果超过了m，则输出无解。

如果使用的边数，依旧小于m怎么办，那就在相邻的层、同一层内连边，直至边数为 $m$ 。

时间复杂度为 $O(n+m)$ 。

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
vector<int> e[N];
int a[N];

bool check()
{
    LL tmp = 1LL * n * (n - 1) / 2;
    if (m > tmp)
        return false;
    rep(i, 2, n)
    {
        if (a[i] == 0)
            return false;
    }

    dwn(i, n - 1, 1)
    {
        if (e[i].size() > 0 && e[i - 1].size() == 0)
        {
            return false;
        }
    }
    return true;
}

void outE()
{
    cout << -1 << el;
    exit(0);
}
void solve()
{
    cin >> n >> m;
    int x;
    rep(i, 1, n)
    {
        cin >> a[i];
        e[a[i]].push_back(i);
    }
    if (check() == false)
    {
        outE();
    }
    int mx = *max_element(a + 1, a + n + 1);
    // debug(mx);
    vector<PII> ans;
    rep(dis, 1, mx)
    {
        int u = e[dis - 1][0];
        for (auto v : e[dis])
        {
            ans.push_back({u, v});
        }
    }
    if (ans.size() > m)
        outE();

    m -= ans.size();
    bool flag = false;

    if (m > 0)
    {
        rep(dis, 1, mx)
        {
            for (int i = 0; i < (int)e[dis].size(); i++)
            {
                int u = e[dis][i];
                // debug(i);
                for (int j = i + 1; j < (int)e[dis].size(); j++)
                {
                    // debug(j);
                    int v = e[dis][j];
                    ans.push_back({u, v});
                    m--;
                    if (m == 0)
                        break;
                }
                if (m == 0)
                    break;
            }
        }
    }
    if (m > 0)
    {
        rep(dis, 2, mx)
        {
            if (e[dis - 1].size() == 1)
                continue;
            for (int i = 1; i < (int)e[dis - 1].size(); i++)
            {
                int u = e[dis - 1][i];
                for (auto v : e[dis])
                {
                    ans.push_back({u, v});
                    m--;
                    if (m == 0)
                        break;
                }
                if (m == 0)
                    break;
            }
        }
    }
    // cerr << "tt";
    if (m > 0)
        outE();
    for (auto [u, v] : ans)
    {
        cout << u << ' ' << v << el;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

F、G

假设一个数为 $x=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ ，乘法原理得其约数个数为 $\prod_{i=1}^k (e_i+1)$ 。

可以观察到 $1\le a_i\le 3$ ，设 $a_i$ 出现的次数为 $n[a_i]$ 。

所以一个数约数个数也就为 $(n_2+1)(n_3+1)$ 。

而对于所有子序列的方案数之和，这种问题。有个很明显的特征就是跟位置无关。

我可以直接将 $a_i$ 数组升序排序，那么得到的答案最终一模一样。

$n_1$ 只会影响我们方案数的数量，并不会影响约数的大小，我们仅仅考虑 $2,3$ ，最后将答案乘以一个 $2^{n_1}$ 即可。

那么怎么考虑 $2,3$ 呢，考虑 $2^i\cdot 3^j$ 能构造出乘积为这个数的方案数为多少， $\dbinom {n_2} i \times \dbinom {n_3} j$ 。

答案为 $\sum_{i=0}^{n_2}\sum_{j=0}^{n_3}\dbinom {n_2} i (i+1)\times \dbinom {n_3} j (j+1)$ 。

可以发现 $2,3$ 没有任何的相互约束，将其分离 $\sum_{i=0}^{n_2}\dbinom {n_2} i (i+1)\times \sum_{j=0}^{n_3}\dbinom {n_3} j (j+1)$ 。

此时复杂度即为 $O(n)$ ，最后答案需要扣除掉所有数均不选择的方案，也就是空集为 $1$ 。

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

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

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

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

LL fac[N], ifac[N];

LL fpow(LL a, LL b)
{
    LL res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % md;
        b >>= 1;
        a = a * a % md;
    }
    return res;
}
void init(int n)
{
    fac[0] = 1;
    rep(i, 1, n)
        fac[i] = fac[i - 1] * i % md;
    ifac[n] = fpow(fac[n], md - 2);
    dwn(i, n - 1, 0)
        ifac[i] = ifac[i + 1] * (i + 1) % md;
    // rep(i, 0, n)
    // {
    //     debug(fac[i]);
    //     debug(ifac[i]);
    // }
    assert(ifac[0] == 1);
}

LL C(int n, int m)
{
    if(n < m)
        return 0;
    if(m < 0 || m < 0)
        return 0;
    return fac[n] * ifac[m] % md * ifac[n - m] % md;
}

LL n[4];
LL sum[4];

LL getSum(int n)
{
    LL sum = 0;
    rep(i, 0, n)
    {
        sum += C(n, i) * (i + 1) % md;
        sum %= md;
    }
    return sum;
}
void solve()
{
    init(1e5);
    int len;
    cin >> len;
    rep(i, 1, len)
    {
        int x;
        cin >> x;
        ++ n[x];
    }
    LL ans = getSum(n[2]) * getSum(n[3]) % md;
    ans = fpow(2, n[1]) * ans % md;
    ans = (ans - 1 + md + md) % md;
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

牛客周赛35题解

A

B

C

D

E

F、G