出题人题解

出题人题解， 若题解有修改，第一时间见： 传送门

继上一套练习赛$104104$，这一套卷子依旧是我和$ZZ$巨组队一起出的。然后还是我端茶倒水，然后帮$ZZ$巨完成了最后一块拼图（确信）。 我出了$A,B,C,EA,B,C,E$，然后Z巨出了$DD$。最后Z巨想出了$FF$题的$95\mathrm{\%}95\backslash \%$的idea，我帮其完成了剩余的$5\mathrm{\%}5\backslash \%$的数位DP思想找具体的那$\mathcal{O}(\log S)\backslash mathcal\{O\}(\backslash log\; S)$个区间的部分。

然后比赛那天的下午，跟验题人商量了一下临时加强了$EE$，范围从$10^5\to 10^{9}10^5\backslash rightarrow10^9$（原本甚至想$10^{18}10^\{18\}$），以至于赛时的难度$E>FE>F$

除了$CC$题过于经典，整套卷子质量海星，指的是$E,FE,F$海星（雾

A、切蛋糕的贝贝

题意：将一个正$n(1\le n\le 10^9)n(1\backslash le\; n\backslash le\; 10^9)$边形分成面积之比为$1:1:4:5:1:41:1:4:5:1:4$最少需要几刀

因为$1+1+4+5+1+4=161+1+4+5+1+4=16$，即判断$nn$是否为$1616$的倍数，如果不是，则无解。

是的话，则最少仅需$55$刀即可达到目标，切法如下：

• 第一刀切穿过重心的对角线，左右两边$8:88:8$
• 然后第二刀将左边的等分即切出$4:44:4$
• 第$3,4,53,4,5$刀，将右边的分为$1:1:1:51:1:1:5$

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

int n;

int main()
{
    cin >> n;
    cout << (n % 16 ? -1 : 5);
}

B、抱歉，这没有集美

题意：求解长度为$n(1\le n\le 10^6)n(1\backslash le\; n\backslash le\; 10^6)$的排列$pp$中，至少存在一个位置满足$\text{gcd}(p_i,i)\backslash text\{gcd\}(p\_i,i)$为偶数的排列数量。

本题理论上有相当一部分选手会使用$next\mathrm{\_}permutationnext\backslash \_permutation$打表，然后推出结论

逆向思维，考虑一个序列，不存在一个$ii$满足$gcd(p_i,i)gcd(p\_i,i)$是偶数，也就是所任意偶数只能放在奇数位置，所以分开考虑奇数位置和偶数位置即可。然后我们对$nn$的奇偶性进行分类讨论：

• 当$nn$为奇数时，${\displaystyle \frac{n+1}{2}}\backslash cfrac\{n+1\}\{2\}$个奇数位置需要放${\displaystyle \frac{n-1}{2}}\backslash cfrac\{n-1\}\{2\}$个偶数和$11$个奇数，我们从${\displaystyle \frac{n+1}{2}}\backslash cfrac\{n+1\}\{2\}$个数中选出一个奇数，然后两种位置分别全排列，总方案为$C_{\frac{n+1}{2}}^1({\displaystyle \frac{n+1}{2}})!({\displaystyle \frac{n-1}{2}})!=(({\displaystyle \frac{n+1}{2}})!{)}^{2}C\_\{\backslash frac\{n+1\}\{2\}\}^\{1\}(\backslash cfrac\{n+1\}\{2\})!(\backslash cfrac\{n-1\}\{2\})!=((\backslash cfrac\{n+1\}\{2\})!)^2$
• 当$nn$为偶数时，两种位置分别全排列，总方案数为$({\displaystyle \frac{n}{2}})!({\displaystyle \frac{n}{2}})!=(({\displaystyle \frac{n}{2}})!{)}^2(\backslash cfrac\{n\}\{2\})!(\backslash cfrac\{n\}\{2\})!=((\backslash cfrac\{n\}\{2\})!)^2$

故，不存在一个$ii$满足$gcd(p_i,i)gcd(p\_i,i)$是偶数的排列方案有$(\lfloor {\displaystyle \frac{n+1}{2}}\rfloor !{)}^2(\backslash lfloor\; \backslash cfrac\{n+1\}\{2\}\backslash rfloor\; !)^2$

综上，总的方案为$n!-(\lfloor {\displaystyle \frac{n+1}{2}}\rfloor !{)}^{2}n!-(\backslash lfloor\; \backslash cfrac\{n+1\}\{2\}\backslash rfloor\; !)^2$，可以计算阶乘$\mathcal{O}(n)\backslash mathcal\{O\}(n)$求解答案。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
typedef long long LL;

constexpr int N = 1e6 + 10, md = 1e9 + 7;

LL fac[N];
void init()
{
    fac[0] = 1;
    rep(i, 1, 1000000)
        fac[i] = fac[i - 1] * i % md;
}
int main()
{
    int i;
    cin >> i;
    init();
    LL ans = fac[i] - fac[(i + 1) / 2] * fac[(i + 1) / 2] % md;
    ans %= md;
    if(ans < 0)
        ans += md;
    cout << ans;
}

C、打牌的贝贝

题意： 两人都持有$n(1\le n\le 10^6)n(1\backslash le\; n\; \backslash le\; 10^6)$张牌，且每张牌的数字都不同。共$nn$回合，每轮都是$BeiBeiBeiBei$攻击，$NingNingNingNing$防守。每回合$BeiBeiBeiBei$出一张牌，$NingNingNingNing$必须出一张比当前回合他出的大的牌。如果$nn$轮$NingNingNingNing$都成功防御则其获胜，反之$BeiBeiBeiBei$获胜。共$T(1\le T\le 10^6)T(1\backslash le\; T\; \backslash le\; 10^6)$组样例，输出二人各自获胜的情况种类。

首先声明下，本题不是博弈题，这不是二者轮流操作的公平组合游戏。

容易得到，先手打出一张牌$xx$时候，后手一定会打出他目前已有的手牌中，最小的大于$xx$的牌。

先考虑给定$nn$时，共有多少种分牌方案，即在$2n2n$个位置中选取出$nn$个位置当作先手的牌（位置的编号即是大小，也就已经排序好了），剩余的位置即是后手的牌，即总共的方案数量为$C_{2n}^{n}C\_\{2n\}^\{n\}$。考虑后手获胜的情况，我们把先手的牌所处的位置，都换成左括号，后手的牌的位置都换成右括号。这样我们就得到了一个括号序列，当且仅当这是一个合法的括号序列时，后手才能获胜，故后手获胜的情况为卡特兰数$Catala{n}_{n}Catalan\_n$，易得卡特兰数可以$\mathcal{O}(n)\backslash mathcal\{O\}(n)$预处理出来，然后$\mathcal{O}(1)\backslash mathcal\{O\}(1)$询问回答。

于是就得到了先手获胜的方案数为$C_{2n}^n-Catala{n}_{n}C\_\{2n\}^n-Catalan\_n$，我们通过递推式$Catala{n}_{n+1}={\displaystyle \frac{4n+2}{n+2}}Catala{n}_{n}Catalan\_\{n+1\}=\backslash cfrac\{4n+2\}\{n+2\}Catalan\_n$可以计算出卡特兰数。再此之前，我们需要计算出$n+2n+2$的逆元，这个先$\mathcal{O}(n)\backslash mathcal\{O\}(n)$预处理阶乘和阶乘的逆元，然后$\mathcal{O}(1)\backslash mathcal\{O\}(1)$求解，而$C_{2n}^{n}C\_\{2n\}^\{n\}$这个数也可以由$2n2n$的阶乘和$nn$的阶乘的逆元$\mathcal{O}(1)\backslash mathcal\{O\}(1)$计算出来。

当然用卡特兰数的这个递推式也是同样的效果$C_{2n}^n-C_{2n}^{n-1}C\_\{2n\}^\{n\}-C\_\{2n\}^\{n-1\}$。

总的时间复杂度为$\mathcal{O}(n+T)\backslash mathcal\{O\}(n+T)$。出题人认为阶乘逆元的预处理复杂度不是该题想考查的重点，故处理阶乘逆元的复杂度放宽到$\mathcal{O}(n\log n+T)\backslash mathcal\{O\}(n\backslash log\; n+T)$也能通过，即$nn$最大仅为$10^{6}10^6$。

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

#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--)

typedef long long LL;

constexpr int N = 1e6 + 10, md = 1e9 + 7;

int T, n, m;
LL f[N], fac[2 * N], ifac[N], inv[N];

LL fpow(LL a, int b)
{
    LL res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % md;
        a = a * a % md;
        b >>= 1;
    }
    return res;
}

LL finv(int i)
{   
    return fpow(i, md - 2);
}

void init()
{
    int R = N - 8; // 1e6 + 2
    fac[0] = 1;
    rep(i, 1, 2 * R) //阶乘逆元
        fac[i] = fac[i - 1] * i % md;
    ifac[R] = fpow(fac[R], md - 2);
    dwn(i, R, 2) //阶乘倒数逆元
        ifac[i - 1] = ifac[i] * i % md;
    rep(i, 1, R) //倒数逆元
        inv[i] = fac[i - 1] * ifac[i] % md;
    f[0] = 1;
    R -= 2;//最大的i + 2也被算出来了
    lop(i, 0, R)
    { //计算卡特兰数
        f[i + 1] = f[i] * (4 * i + 2) % md * inv[i + 2] % md;
        //这是一个很坑的点i+2
    }
}

LL C(LL n, LL m)
{//n选m
    return fac[n] * ifac[m] % md * ifac[n - m] % md;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(false);
    init();
    cin >> T;
    while (T--)
    {
        cin >> n; 
        LL ans1 = ((C(2 * n, n) - f[n]) % md + md) % md;
        cout << ans1 << ' ' << f[n] << el;
    }
}

D、点分治分点

题意：给定一个 $nn$ 个点, $mm$ 条带权的边的有向图，定义一条简单路径的 $lowlow$ 值为其路径上的边权的最小值，$d(u,v)d(u,\; v)$ 为从 $uu$ 到 $vv$ 所有简单路径的最大 $lowlow$ 值。对于给定的$ss$，$uu$ 从 $11$ 到 $nn$ 输出 $d(s,u)d(s,\; u)$，如果没有任何一条简单路径则输出 $-1-1$。

1. 我们先把边按照权值排序，从大到小加边。

2. 每次加一条边 $(u_i,v_i,w_i)(u\_i,\; v\_i,\; w\_i)$，如果 $u_{i}u\_i$ 与 $ss$ 连通，我们就从 $u_{i}u\_i$ 开始跑一次 $BFSBFS$，对于在该次 $BFSBFS$ 中连通的点，它的答案就是 $w_{i}w\_i$。

3. 我们对每个跑过的点打个标记，由于每个点每条边都只会被遍历一次，因此我们计算答案的复杂度为 $\mathcal{O}(n+m)\backslash mathcal\{O\}(n+m)$

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

constexpr int N = 1e5 + 10, M = 1e7;

int vis[N], ans[N]; // 答案
vector<int> g[N]; // 存边

struct Edge {
    int u, v, w;
    bool operator < (const Edge &t) const {
        return w > t.w;
    }
} E[N];

void bfs(int s, int w)
{
    vis[s] = 1;
    ans[s] = w;
    queue<int> q;
    q.push(s);
    while(q.size())
    {
        int u = q.front(); q.pop();
        for (auto &v : g[u])
        {
            if(vis[v]) continue;
            vis[v] = 1;
            ans[v] = w;
            q.push(v);
        }
    }
}

void solve()
{
    int n, m, s; // n个点, m条边
    cin >> n >> m >> s;
//     n = m = 1e5,s=1;
    for (int i = 1; i <= m; i ++ )
    {
        int u, v, w;
        cin >> u >> v >> w;
//         u=1,v=i,w=i;
        E[i] = {u, v, w};
    }

    sort(E + 1, E + m + 1); // 按照边权降序

    vis[s] = 1;
    memset(ans, -1, sizeof ans);
    for (int i = 1; i <= m; i ++ )
    {
        auto &[u, v, w] = E[i];
        g[u].push_back(v); // 加边
        // 寻找是否拥有新可达点
        if(vis[u] == 1 && vis[v] == 0) bfs(v, w);
    }

    ans[s] = -1;
    for (int i = 1; i <= n; i ++ )
        cout << ans[i] << " \n"[i == n];
}

int main()
{
//     ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    while (t -- ) solve();
    return 0;
}

E、角剖分剖角

牛客编辑器有字数上限，剩余部分见知乎： 传送门

F、胖头鱼头胖

牛客编辑器有字数上限，剩余部分见知乎： 传送门