UOJ Round #2

2015年4月15日1,8675

http://vfleaking.blog.uoj.ac/blog/38

【UR #2】猪猪侠再战括号序列

猪猪侠大神太厉害了

下面俩题怎么这么恶心T T

【UR #2】跳蚤公路

负环能影响一个点v当其与1,v都连通,这个用floyd就好

不等式取整要手写

虽然分析了那个式子写起来还是蛋疼

每个环每个系数k,枚举j,取整范围求并

就能得出所能影响的点的x取值范围,x<=l或x>=r

一个点的x被许多这样的取整范围限定T T

将区间排序一下扫一遍得去其范围即可。。。

【UR #2】树上GCD

题意

定义树上的一条路径\(a,b\)的权值,设a为深度小的点, LCA 为\(a,b\)的最近公共祖先

若a为b的祖先,权值为\(dis(a,b)\),否则权值为\(gcd(dis(a,LCA),dis(b,LCA))\),输出路径权值为i的路径数

\(1<=i<n\)

题解

算法一

枚举两个点 \(u,v\),用 \(O(\log n)\) 时间计算 LCA 和 gcd,并更新答案。复杂度 \(O(n^2\log n)\)。

也可以枚举 LCA,往子树方向进行 bfs,由于计算 gcd 是 \(O(\log n)\)的,所以复杂度还是 \(O(n^2\log n)\)。

可以获得 10 分。

算法二

随机生成的树的树高为 \(O(\log n)\)。

枚举 u,计算以 u 为 LCA 的所有点对的答案。计算时对 \(u\) 的子树 dfs,统计出每个深度 \(h\) 上的结点数量 \(cnt[h]\)。枚举深度 \(h_1, h_2\),并将 \(cnt[h_1]\cdot cnt[h_2]\) 累加到 \(ans[\gcd(h_1,h_2)]\) 中。注意还需把同一个子树内的多余计算给减掉。这样,统计答案的复杂度是 \(O(deg[u]\cdot \log^2 n)\),总和是\(O(n \log^2 n)\)。另外,每个点最多被DFS到 \(O(\log n)\) 次,所以dfs的总复杂度是 \(O(n\log n)\)。

于是总复杂度 \(O(n\log^2 n)\)。可以获得 30 分。

算法三

我们可以把问题转化为,对于每个 d,求出 \(\gcd(h_1,h_2)\) 是 d 的倍数的点对的数量,然后用个\(O(n\log n)\)的暴力就能得出答案。

第4个数据点中,从根结点挂下来若干条链,长度分别为 \(h_1,\cdots,h_k\)。\(u,v\) 属于同一条链的情况可以方便计算;\(u,v\) 不在同一条链上时,LCA即为根结点。对于某个 d,第 i 条链中高度为 d 的倍数的点有 \(\left\lfloor h_i/d\right \rfloor\) 个;我们要统计 k 条链中选出两条来的乘积总和,可以利用恒等式 \((x_1+\cdots+x_k)^2=x_1^2+\cdots + x_k^2 +2\sum_{1\leq i < j\leq k}x_i x_j\) 求得。

其实维护前缀和就行了TAT

复杂度\(O(n\log n)\)。可以获得 40 分。

算法四

考虑点分治,每次取出当前树的中心 c。考虑所有 \(u \rightarrow LCA(u,v) \rightarrow v\) 的路径经过 c 的点对 \((u,v)\) 所产生的贡献,共有两种情况:

1.\(u,v\) 均在 c 的子树内,此时 LCA 即为 c。和算法三类似,只是第 i 条链中高度为 d 的倍数的点的数量需要在处理出 cnt 数组后花 \(hi/d\) 的时间统计,所以复杂度是\(O(n \log n)\)。

2.u 在 c 的子树内,而 v 不在。我们把当前树的根节点记为 root,\(father[c]\) 到 root 的路径为 \(father[c]=a_1,a_2,\cdots,a{k-1},a_k=root\)。记 c 下面的子树高度为 H,\(a_i\) 旁边伸出的子树(即不包含 \(a_{i-1}\) 的子树的高度为 \(h_i\)。枚举 \(a_i=LCA(u,v)\),那么 v 位于 \(a_i\) 旁边的子树中,然后我们仍然枚举 d,用 \(h_i/d\) 的时间求出 \(a_i\) 子树中高度为 d 的倍数的结点数量;但我们还需要知道 c 的子树中有多少点相对于 \(a_i\) 的高度是 d 的倍数,与前者直接相乘计入答案,也就是说我们要在 c 子树的 cnt 数组中查询下标间隔为 d 的子序列中的元素之和\((0<d<=h_i)\)。注意到间隔为 d 时,至多只有 d 种这样的子序列,我们对重复查询进行记忆化。于是对于 \(d<\sqrt{H}\),查询的复杂度不超过 \(d\cdot H/d=H\),总共是 \(\sqrt{H}\cdot H\);对于 \(d>\sqrt{H}\),单次查询的复杂度为 \(H/d<\sqrt{H}\)。

这里可能还要考虑 u 在 c 的子树内,v = \(a_i\)。由于\(a_i\)到 c 的距离是从1开始的一段区间,对于\(ans[i] (0<i<=H+dis(a_i,c))\)的贡献是 cnt 的一段区间和,随着 i 的增长这个区间左右端点单调递增,所以复杂度是\(O(n)\)。

所以一层分治的复杂度是 \(O(n\sqrt{n})\)的。根据主定理,总复杂度就是\(O(n\sqrt{n})\),可以通过所有测试点获得 100 分。

10分

100分

 

  • ACE2015年4月16日 上午8:11 回复

    您居然顺手Hack掉我这么久之前过的题…. 我差点看不懂自己的程序了…

    #1  
    • hzwer2015年4月16日 上午8:20 回复
      admin

      T T 我由于不理解您的代码,就构造数据看中间结果。。。然后发现了奇怪的问题

      #11
      • Ace2015年4月16日 上午8:29 回复

        不不不… 是我以前太弱了(现在也是)… 没有判那些1无法到达的点, 还继续去做… 其实我的程序想法很简单… 就是二分二分二分…

        #12
        • hzwer2015年4月16日 上午8:55 回复
          admin

          就是把解不等式变成二分么。。。

          #13
          • Ace2015年4月16日 上午9:02

            差不多吧… 因为对于每一个点来说, 不会出现那啥balabala路径的区间是连续的. 而对于某一个具体的负环来说, 有一个分界点决定他是成为负环还是不成为负环. 所以分两层二分, 第一层看一下mid会不会有负环, 如果没有, 那好, 分左右两段进入第二层二分, 这时候有单调性了所以没问题. 如果mid有负环, 那么找出一条具体的负环, 看看可行区间是在mid的左边还是右边. 复杂度的保证需要强连通, 把不在强连通的边删掉之后复杂度嗖嗖地从n^4logR变成了n^3logR.

            #14