51Nod 入门计划 4/10

前言

在bzoj的非权限题里面,题目又短有简单的题已经越来越少了。。于是来51Nod里面找点水题做

入门计划

1674 区间的价值 V2

这题的话,很明显地,是让我们把位分开考虑
然后我们考虑两个为 i,j ,也就是 2i 2j ,有多少个序列使得他们相乘。
假设 i 是与里面的, j 是或里面的,那么你就枚举左端点a,然后合法的右端点b,肯定是满足 a ~ b 里面每一个数在第 i 为都是有1的,然后至少有一个数是在第 j 位有1的,然后b是一个区间。你扫出关于 i,j 两个合法端点减一下就可以了。这个显然是单调的,可以O(n)做出来
时间复杂度 (nlog2ai)

1737 配对

两点间的距离: dep[x]+dep[y]2dep[LCA]
容易看出, dep[x]+dep[y] 是不变的
因此,我们只需要让 2dep[LCA] 最小化就可以了
于是考虑贪心策略,以1位根,如果他的所有儿子的LCA都可以是他,那么就结束了,也就是只要重儿子的节点个数不超过我的一半,那么就让子树之前配对就可以了
否则,就记录一个值 o ,表示以 x LCA 的可以有多少个与重儿子配对,然后递归下去重儿子处理
然后以后的重儿子,他的节点个数就可以减去 o 了,因为他多余的可以与祖先匹配
然后就没有了最快 O(1) ,最差 O(n)
贴一部分重要代码

void solve (LL x,LL o)//在哪一个节点,可以节省多少个了 
{
    LL s=son[x];
    if (tot[s]-o<=tot[x]-tot[s])//直接匹配完成 
    {
        ans=ans-(tot[x]-o)*dep[x];
        return ;
    }
    ans=ans-(tot[x]-tot[s])*dep[x]*2;
    solve(s,o+(tot[x]-tot[s]));
}

1829 函数

直接容斥一下就可以了。。
一开始没有线性算阶乘逆元居然T了
真的迷。。不就是 nlogn 嘛。。

1073 约瑟夫环 1074 约瑟夫环 V2

以前我的约瑟夫都是用线段树模拟的,一直觉得很棒棒
首先,这题是有一个 O(n) 的递推的方法的
吧人按0~n-1编号
我们考虑有i个人,先做一次,也就是到了 k1
吧序列排出来,就是 k,k+1,k+2......0,1,2,3.....,k2
重新编号,使得k变成0,那么我们就可以用 f[i1] 来直到谁会或者,然后加上k就可以了
在加上不能超出范围,就可以得到递推式 f[i]=(f[i1]+k)
然后最后那个人,因为是从0开始的,于是要 +1 ,然后第一题就做完了 然后第二题,考虑到n很大,也就是说,有很多情况,都是不用取模的,你可以一直加,所以我们可以一大部分地做,可以省下很多时间,就可以通过了

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院