over 1 year ago

ZJOI终于出了一套比较能做的题了(雾
由于篇幅所限就不在这里贴题面和代码了……大家可以在UOJ上找到。我的ID是InvUsr。


1. 仙人掌

1.1 40pts

先从给出的图是一棵树的特殊情况入手。

考虑仙人掌的性质:“每条边最多属于一个简单环”。我们对这个性质稍加改变,将每条不在环上的边变成一个长度为2的环,就可以看作每条边恰好在一个简单环上。也就是说,对于原树的每一棵子树,必然有一条边从子树内延伸到子树外。

有了这个性质,就可以做树的情况了。记为以节点为根的子树内,所有边都被恰好一条环边覆盖的方案数(我们并不需要知道延伸出去的边指向了哪里)。对于节点,假设它的度数为,则对于的每一个儿子所在的子树以及所在子树以外的部分,考虑它们延伸到子树外的那条边,这些边必然将这些连通块两两配对(如果是从子树的根节点指向它的父亲的边,则可以看作它与自己配对)。记将个子树配对的方案为,则可以通过一个简单的递推算出:

根据乘法原理:

upd: 答案就是…我sb了…

该算法可以通过测试点4-7,获得40分。

1.2 100pts

首先如果给出的图不是树/仙人掌,那么答案显然为0。

对于原图中的任意一对点,如果它们之间任意一条简单路径上存在环边,那么显然不能在这两点之间连边。因此我们可以把所有的环边删除,这样原图就变成了若干棵树,且每一棵树的方案独立。我们对每一颗树应用40分算法,将得到的结果相乘即可。


2. 树状数组

听说这是ZJOI近年来最sb的一个题?
2.1 50pts

首先稍微转化一下问题,可以变成单点异或1,以及询问区间的异或和。

根据人生经验(雾)可以发现,题目中给的“打错的树状数组”其实实现的是单点异或1,以及询问后缀异或和的功能。注意当时,find(x)返回的并不是后缀异或和,而是常数0。

那么考虑询问区间时正确的条件。记为第个位置上的数值,

  • 时,query(L, R)返回的是,此时回答正确当且仅当,即
  • 时,query(L, R)返回的是,此时回答正确当且仅当,即

因此,我们维护使等式左边的值不发生改变的概率,考虑每个修改区间对询问区间答案的贡献,很明显只有修改了才会是等式左边发生改变。。若覆盖了中的一个,则发生改变的概率为;若同时覆盖了,则改变的概率为。显然这个概率可以很轻易地合并(要么同时改变,要么同时不变)。

时间复杂度,期望得分50。

2.2 100pts

观察上式可以发现,如果我们把修改区间看成二位平面上的点,那么对答案产生贡献的修改必然在若干个矩形区域内。于是原问题就转化成了一个动态二维数点问题,使用CDQ分治或各种二维数据结构维护即可。

注意我们维护的概率信息可加但不可减(考虑概率等于的情况),因此无法使用树状数组,可以使用二维线段树或K-D Tree代替。二维线段树有MLE的风险。

时间复杂度(二维线段树或CDQ分治)或(K-D Tree),期望得分100.


3. 多项式

3.1 30pts

容易发现若,则。因为对于这一项的系数显然是偶数,在意义下就被消掉了。

基于这个结论,可以考虑使用快速幂。若为偶数,则递归算出,并且把每一项的指数乘;否则递归计算,然后将计算出的结果与暴力相乘即可。

时间复杂度,期望得分30。

3.2 50pts

对于测试点4、5,满足。我们考虑对于,计算出,即一项的系数。

  • 为偶数且为奇数,则
  • 为偶数且为偶数,则
  • 为奇数,记,则

,则需要计算的状态数为,使用map进行记忆化即可。

可以通过测试点4、5,配合上一个算法可以获得50分。

3.3 100pts

不会QAQ

搬迁公告 →