ACM萌新第一次写题解。请各位多加批评指正。

A 小红的合数寻找

纯签到题。 $n>1$ 时， $2n$ 必定是合数，否则无解。

scanf("%d",&n);
printf("%d",n==1?-1:2*n);

B 小红的小球染色

可以发现一次染色会将白球数量 $-2$ ，次数越多，白球越少。此问题转化为剩余白球数量的问题。

对于最小值，我们就要找白球剩余最多的方案。当不能再操作时，不会再有相邻的两个白球，只会有单独的一个白球，所以我们要让单独的白球尽可能多。容易证明每 $3$ 个相邻的球中最多剩余 $1$ 个白球。那么我们把球分成三个一组，每组先是一个白球，然后是两个连着的红球。观察余下的球，如果是 $2$ 个，排在哪都没法和其他白球隔开，那么必须再操作一次；如果是 $1$ 个，那么让它排在最后成为单独的白球。总结就是 $min=\lfloor\frac{(n+1)}{3}\rfloor$ 。

对于最大值，我们可以发现如果把小球分成两个一组，然后把它们两两相邻排列，那么每一组就可以操作一次，总共可以操作 $\lfloor \frac{n}{2}\rfloor$ 次，剩下的不管是 $1$ 个还是 $0$ 个都不能再操作了，这样操作剩下的白球数量是最少的，即 $max=\lfloor\frac{n}{2}\rfloor$ 。

scanf("%d",&n);
printf("%d %d",(n+1)/3,n/2);

时间复杂度 $O(1)$

C 小红的二叉树

题目给了图，没给的话还是要自己画一下，方便猜结论。

由于是完全二叉树，所以每一层的节点数是上一层的 $2$ 倍，并且它们全部等价。发现这点处理就方便许多。

设节点深度为 $l$ 。

经过一个节点的长度为 $2$ 的路径有以下几种情况：
1.如果该节点有儿子（也就是 $n-l\geq1$ ），那么左儿子经过本节点到右儿子的路径是 $1$ 条符合条件的路径；
2.如果该节点有孙子（也就是 $n-l\geq2$ ），那么自己到四个孙子的简单路径就是 $4$ 条符合条件的路径；
3.该节点到爷爷的路径，这个在爷爷辈那里已经算过一次，所以不考虑；
4.其儿子节点到父亲节点的路径，也算过了，不考虑。

也就是说，我们可以按层遍历该树，每层只需要知道节点数量 $m$ 和层深度l即可。若 $n-l\geq1$ ，答案加 $m$ ；若 $n-l\geq2$ ，答案加 $4m$ 。由于 $m$ 的增长比例固定，最终答案可以直接计算，即 $ans=4*(2^{n-2}-1)+2^{n-1}-1$ 。但是因为数据过大需要取模，所以还是要一步一步算。

scanf("%lld",&n);
m=1;res=0;
while(n){
    if(n>=3){
        res=(res+m*5)%mod;
    }
    else if(n==2) res=(res+m)%mod;
    m=m*2%mod;
    n--;
}
printf("%lld",res);

时间复杂度 $O(n)$

D 小红的“质数”寻找

由于数据很大，用字符串读入。我们要判断的数不会超过 $1e6$ ，考虑暴力。但是暴力的做法非常的麻烦，这里我用特殊值法。

对于小于 $10$ 的数，由于只有一位，没有配对空间，我们直接手打一个表输出。

对于两位以上的数字：

如果最高位数字是 $2,3,...,8$ ，将该数字最高位 $+1$ ，其他位更改为 $0$ ，最后一位改为 $11-a$ （ $a$ 代表更改后的最高位数字），这样的数必定在区间内，而且 $11$ 是质数，输出这个数即可；

如果是 $1$ ，该数字最高位变为 $2$ ，其他位更改为 $0$ ，这样的数字必定在区间内，而且 $2$ 是质数，输出这个数即可；

如果是 $9$ ，那么加一位，前两位变为 $11$ ，后面全为 $0$ ，这样的数字必定在区间内，而且 $2$ 是质数，输出这个数即可。

scanf("%s",x);
len=strlen(x);l=len;
if(len==1&&x[0]<'9'){ if(x[0]=='1')printf("2\n");
    if(x[0]=='2')printf("2\n");
    if(x[0]=='3')printf("3\n");
    if(x[0]=='4')printf("5\n");
    if(x[0]=='5')printf("5\n");
    if(x[0]=='6')printf("7\n"); if(x[0]=='7')printf("7\n");
    if(x[0]=='8')printf("11\n");
    continue;
}
if(x[0]<'9') s[0]=x[0]+1,g=s[0]-'0',p=1;
else len++,s[0]='1',s[1]='1',g=2,p=2;
if(l>1){
    if(g!=2)s[len-1]='0'+11-g;
    else s[len-1]='0';
}
while(p<len-1)s[p]='0',p++; s[len]='\0';
printf("%s\n",s);

E 小红的好排列

一个排列有 $\lfloor\frac{n}{3}\rfloor$ 个位置的下标是 $3$ 的倍数，为了让排列中 $a_{i}\cdot i$ 的值有一半是 $3$ 的倍数，也就意味着要让 $\frac{n}{2}-\lfloor\frac{n}{3}\rfloor$ 个 $3$ 的倍数的数不在下标为 $3$ 的倍数的位置上，剩余的 $3$ 的倍数在下标为 $3$ 的倍数的位置上。也就是说，我们要从 $3$ 的倍数和不是 $3$ 的倍数的数中选出 $\frac{n}{2}-\lfloor\frac{n}{3}\rfloor$ 个数交换，然后两部分分别全排列。

也就是说我们要的答案就是：先在 $3$ 的倍数中选取 $\frac{n}{2}-\lfloor\frac{n}{3}\rfloor$ 个组合，再在不是 $3$ 的倍数的数中选取同样数量的数组合，然后分别对 $3$ 的倍数位置上和不在 $3$ 的倍数位置上的数全排列，得答案为 $\left(\begin{matrix} n-\lfloor\frac{n}{3}\rfloor \\ \frac{n}{2}-\lfloor\frac{n}{3}\rfloor \\ \end{matrix} \right) \cdot\left(\begin{matrix} \lfloor\frac{n}{3}\rfloor \\ \frac{n}{2}-\lfloor\frac{n}{3}\rfloor \\ \end{matrix} \right)\cdot(\lfloor\frac{n}{3}\rfloor)!\cdot(n-\lfloor\frac{n}{3}\rfloor)!$

记得取模。

其他等价的算法也是可以的。

int C(int n,int m){
    if(m==0)return 0;
    int ans=1;
    for(int i=n;i>n-m;i--){
        ans*=i;
        ans%=mod;
        if(ans<0)ans+=mod;
    }
    for(int i=1;i<=m;i++){
        ans*=inv[i];
        ans%=mod;
        if(ans<0)ans+=mod;
    }
    return ans;
}
int A(int n){
    ans=1;
    for(int i=1;i<=n;i++){
        ans=ans*i%mod;
    }
    return ans;
}
signed main(){
    inv[1]=1;
    for(int i=2;i<=1000005;++i){
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    scanf("%lld",&n);
    c3=n/3;
    cn3=n-c3;
    ans=C(cn3,n/2-c3)*C(c3,n/2-c3)%mod*A(c3)%mod*A(cn3)%mod;
    printf("%lld",ans);
return 0;
}

时间复杂度 $O(n)$

F 小红的小球染色期望

输出要求里包含了乘法逆元相关知识，这一部分是离散数学相关内容，可以移步OI Wiki学习。

小红第一次染色时随机选择一个位置，然后将两个球染成红色，那么这两个球会把剩下的白球分成左右两部分，这两部分可以看作是与第一次染色相同，但是规模更小的问题。用分治的思想，我们把它转换成了一个dfs问题。但是这题我记忆化dfs超时了（dfs时间复杂度不会算），于是考虑进一步优化。

我们考虑一次染色的所有情况，会发现由于选择随机，左右分割出现所有情况都是等可能的，而且左右的所有子问题分别恰好都是从规模为 $0$ 到规模为 $n-2$ （ $n$ 为当前问题规模）各 $\frac{1}{n-1}$ 的概率，它们期望之和 $+1$ 就是当前问题的答案。设当前规模问题的解为 $F(n)$ ，那么就可以得到递推式： $F(n)=1+\frac{2}{n-1}\sum_{i=0}^{n-2}{F(i)}$ 。我们可以按规模从小到大计算 $F(n)$ 的值，小于等于 $3$ 直接出答案，否则递推，同时维护前缀和，利用前缀和一次递推就是 $O(1)$ ，最终就可以得到线性复杂度。记得取模。

scanf("%lld",&n);
for(int i=1;i<=n;i++){
    ex[i]=-1;
    prf[i]=0;
}
ex[0]=0;ex[1]=0;ex[2]=1;ex[3]=1;
prf[2]=1;prf[3]=2;
for(int i=4;i<=n;i++){
    ex[i]=(prf[i-2]*2%mod+i-1)*inv[i-1]%mod;
    prf[i]=(prf[i-1]+ex[i])%mod;
}
printf("%lld",ex[n]);

时间复杂度 $O(n)$

牛客周赛Round 79题解（A-F）

A 小红的合数寻找

B 小红的小球染色

C 小红的二叉树

D 小红的“质数”寻找

E 小红的好排列

F 小红的小球染色期望