竞赛讨论区 > 【题解】牛客练习赛71

【题解】牛客练习赛71

头像
Froggygua
编辑于 2020-10-13 14:56:23 APP内打开
赞 4 | 收藏 3 | 回复0 | 浏览1205

如有错误请及时指出~

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 序给图上所有点重标号,那么任意询问中红边组成连通块的编号是一个连续区间。用线段树维护蓝边构成的连通块,按边权从大到小的顺序处理所有蓝边,两个连通块合并时就是线段树合并,查询时在红边连通块对应区间上进行区间查询。

时间复杂度:

0条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐