/ BZOJ

BZOJ2017省选推广赛

因为是推广赛,所以这三道题在比完赛之后是公开的:BZOJ4765、BZOJ4766、BZOJ4767。

普通计算姬

看到求子树和,很容易想到ETT。但是ETT的编码不太方便,看有没有可以优化的地方。于是发现树的形态不会变,那么只要用DFS序再用一个区间数据结构维护一下就好了。

省选题目会这么简单吗?当然不会啦。要求子树和之后还要求区间子树和,这个就比较麻烦了。思索了许久之后,想起之前对付这种修改一个数据要更新两段区间和的题目的时候,主要的解决办法是分块。

那么把[1,n][1,n]n\sqrt{n}分块记录子树和的区间和,然后对每个节点用O(n)O(\sqrt{n})预处理出该节点每改变一个单位对每个块的影响。这个很容易做到,因为改变一个节点的权值的时候只会改变到根这条路径上的节点的子树和,所以只要用父亲的影响加上对自己的子树和的影响就可以了。

查询区间[l,r][l,r]的大块用O(n)O(\sqrt{n})扫一遍就能获取大分块的答案。对于边角料,还是要O(2n)O(2\sqrt{n})一一获取的。这里比较要紧的是,获取每一个节点的子树和是要O(logn)O(\log n)时间的。如果这样搞下去的话,单次查询时间复杂度会达到O(2nlogn)O(2\sqrt{n}\log n),这怎么能接受呢?

当时那道要分块的题目还有另外一种做法,但是要用到一个小技巧:调整常数。我也模仿那道题的做法,设每块长度为PP,计算得到:

  • 修改:O(nP)O(\frac{n}{P})
  • 询问:O(nP+2Plogn)O(\frac{n}{P}+2P\log{n})

要让总复杂度降下来,就要平衡这几个东西之间的关系。用均值不等式算出当P=n2lognP=\sqrt{\frac{n}{2\log n}}的时候总体时间复杂度最低,应该是达到O(2nlogn)O(\sqrt{2n\log n})。这个上界比较紧,感觉还是不能接受。但是我实在想不到比这个更优的方法了。

看题解,20分是我首先想到的,70分也想到过,40分的做法太高端真的没想到。毕竟我的可持久化还根本没有写过。然后看到100分做法,发现它的做法时间复杂度没有比我的低!是不是意味着我想到正解了呢?但是我是思考了一整天的呀,在考试的时候能不能想出来还不一定,能不能码出来就更难说了。

答案比我快的一个地方是用差分数组处理区间加,但是时间复杂度没有变化。

文艺计算姬

本来这题完全没有思路,后来发现题目中提到了完全图的生成树个数,想起了在做BZOJ1005的时候用过的Prufer序列和树的形态是一一对应的,那么只要枚举Prufer序列,就相当于枚举了生成树。

考虑对于这道题,一开始生成树中没有边;因为边一定是横跨两边的,所以每加一条边进去就会在左边的节点中度数添加1,在右边的点的度数添加1。

Prufer序列性质:每个点在序列中出现次数为度数减一。设左边点的个数为nn,右边为mm,那么左边只要在序列中出现(n+m1)n=m1(n+m-1)-n=m-1次就可以了。很容易得到

Ans=Cm+n2n1nm1mn1Ans= C_ {m+n-2}^{n-1}n^{m-1}m^{n-1}

排列数又怎么得到?数据范围非常大!

我在网上查了一些资料,看到Lucas定理,可以较快地求出大组合数模PP的值:

Cmn=Cm0n0C_ {m}^{n}=\sum C_ {m_ 0}^{n_ 0}

n0n_ 0m0m_ 0表示nnmmPP进制下的某一位。但是这还是要求O(P2)O(P^2)的预处理,而P1018P\leq 10^{18},放弃。

答案求出来的式子竟然和我求的不一样。答案是:

Ans=nm1mn1Ans= n^{m-1}m^{n-1}

这不就省事了!但是为什么前面不需要选位置呢?我不是很明白。

两双手

考虑最简单的情况,如果没有障碍点,从起点到终点有多少种走法?

因为可以走的两步可以看成两个向量,就好像平面上的两个基底,每一种需要走的步数是确定的,有多少种走法只是哪个先走哪个后走的问题。解一个二元一次方程,再组合一下,就可以得到走的方法了。

再考虑有障碍点。这个问题我折腾了很久,用容斥原理来做的话肯定会爆时间。发现所有的点构成了DAG,那就先拓扑排序然后动归呗!

fuf_ u为从起点到uu的合法路径数量,uvu\rightarrow v是从u到v的路径数量。

fv=(0,0)vuv,u(0,0)fuuvf_ v=(0,0)\rightarrow v-\sum_ {u\rightarrow v,u\neq (0,0)}f_ u\cdot u\rightarrow v

证明大概用容斥原理搞一通,枚举了几个图感觉都是对的,而且用Excel验证了一些例子,那就是对的吧。

星期二写完代码之后提交上去RE,测试一波发现有情况没有考虑。有一些点从起点走不到,但是在计算度数的时候被统计了,导致终点走不到。那么还要先从起点BFS一遍再拓扑排序,但是那时候快到了晚自习的时间,我只能先吃饭。

题解上面直接按照x坐标排序,不理解。这怎么保证答案正确?难道又是奇怪的容斥?

总结

我很久没有体会过这样思考的过程了,尽管我还是认为这样会浪费很多时间。除了第二题我都想到了不亚于题解的解法,我还是挺高兴的。前天看题,昨天做了第三题,昨晚比赛就停止了,没时间把它们都实现,还是挺可惜的。但是后面还有很漫长的训练,又怎么能够拘泥于一次比赛呢?