【题解】牛客练习赛71

如有错误请及时指出~

A

首先需要统计 为奇数的个数，设为 ，显然当 时无解。

如果 ，设个数为奇数的那个的那个数码为 ，那么为了构成一个回文数，显然 需要拿出来一个放在整个数的正中间。

对于剩下的数码，贪心地从小到大放即可，不过要注意不能有前导 。

有一点细节，这里放个核心代码：

int a[10],odd,pos;
int main(){
    for(int i=0;i<10;++i){
        a[i]=read();
        if(a[i]&1)++odd;
    }
    if(odd>1){
        puts("-1");return 0;
    }
    for(int i=1;i<10;++i){
        if(a[i]>1){
            a[i]-=2;
            putchar(i+'0');
            pos=i;
            break;
        }
    }
    if(!pos){
        puts(a[0]==1?"0":"-1");return 0;
    }
    for(int i=0;i<10;++i){
        for(int j=1;j<=(a[i]>>1);++j){
            putchar(i+'0');
        }
    }
    if(odd){
        for(int i=0;i<10;++i){
            if(a[i]&1){
                putchar(i+'0');
                break;
            }
        }
    }
    for(int i=9;i>=0;--i){
        for(int j=1;j<=(a[i]>>1);++j){
            putchar(i+'0');
        }
    }
    putchar(pos+'0');
    return 0;
}

B

考虑分类讨论。 如果给出三个角，判断和是否是 180 度。 如果给出 3 条边，判断两边之和是否大于第三边。 如果给出两角一边，如果角度和 <180 度那么输出 1 否则输出 0 。 如果给出 2 边一夹角，输出 即可。 如果给出 2 边一临角，假设给出的是 。那么当 的时候答案是 0， 或 时答案是 ， 时 答案为 2。

C

设 表示满足 所有前 （ ）个数都不是 的排列的数的 的个数。 那么答案就是 。 的排列共 个，现在我们要去掉不合法的。为了防止重复计算 前 个数不是 的排列 对答案的贡献（除去所有小于 的 的贡献），就是 那么 即可计算出结果。

D

方法应该比较多，这里可能是一个相对好写的（就是常数有点大）。 把路径 拆成 （不拆也可以，但我感觉比较麻烦）。 然后考虑如何计算，假设两条路径长 。 如果两条路径不相交，那么直接 。 如果相交，我的做法是继续拆路径。拆成若干完全不交的和完全重合的，完全重合的（设长度为 ）那么就是 这个预处理一下（或者别的方法算）即可。

E

如果对于每个 求出了形成长度为 的路径的概率，那么问题就解决了。

考虑用点分治进行统计。

分治过程中分别求出当前联通块每个点到根的距离，发现这些到根的路径进行合并其实是个卷积形式，用 NTT 优化即可。

注意还需要容斥一下，即减掉两个端点都在同一颗子树中的不合法情况。

由于每个点最多被分治 次，所以总复杂度是 。

F

对红边组成的图按照最小边权生成树的方法求出 Kruskal 重构树，那么任意询问中红边组成的连通块都是重构树上某个点的子树。

建重构树时顺便求出每个询问对应的是哪个点的子树。按重构树上的 dfs 序给图上所有点重标号，那么任意询问中红边组成连通块的编号是一个连续区间。用线段树维护蓝边构成的连通块，按边权从大到小的顺序处理所有蓝边，两个连通块合并时就是线段树合并，查询时在红边连通块对应区间上进行区间查询。

时间复杂度：。