UOJ Round总结
#22. 【UR #1】外星人
一开始随便搞出第一问答案,很显然的性质对$x$有变化的$a$一定是递减的,就拿一个桶直接记录可以达到的值
然后我开始想第二问,一开始想直接在这个桶上统计答案,然后发现不行,之后再想,如果利用上面的性质,在选取了一个$a_i \leq x$时,会有一段区间的$a$可以随便插入到$a_i$之后,然后就被一些组合数学的细节绕晕,没有想清楚,这一段区间是$(x \mod a_i,x]$,并且要在$a_i$中挑一个出来放在最前面,然后会发现$x \mod a_i$是一个子问题,搞出来这个合法方案排列数后,将$(x \mod a_i,x]$中的数,插入排列中,方案数$(sum[x \mod a_i]+1)(sum[x \mod a_i]+2)...(sum[x]-1)$,即$\frac{sum[x-1]!}{sum[x \mod a_i]!}$
那么就设$dp[i]$为当前$x=i$时最大答案,$f[i]$为$x=i$且满足最大答案时的方案数
$dp[i]=\max dp[i \mod a_j]$ $(a_j \leq i)$
然后f[i]由那些可以得到最大答案的$f[i \mod a_j]$根据上面的更新得到
#33. 【UR #2】树上GCD
首先考虑枚举$LCA$,那么就是统计统计利用不同子树各个深度的信息来统计答案,由于是深度信息,那么考虑利用长链剖分来维护这个信息,首先常规套路是继承重儿子信息,暴力维护轻儿子信息
先假设有两个数组$a,b$其中$a[i],b[i]$分别表示以该选定的$LCA$为根时,某一棵子树内深度为$i$的点的个数
考虑枚举答案$k$,那么开始推式子
$\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)=k]a[i]*b[j]$
$\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i,j)=1]a[ik]b[jk]$
$\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} a[ik]b[jk] \sum_{d|gcd(i,j)} \mu (d)$
$\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor} a[ikd]b[jkd]$
$\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) (\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor} a[ikd]) (\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor} b[jkd])$
在维护答案的时候,会产生对于一个数组下标为kd倍数的个数和,并且可以发现$a,b$数组可以简单的维护,只是每次重儿子继承上来的信息不能每一次都遍历一遍(轻儿子可以)
那么考虑根号分治
对于$> \sqrt n$的询问直接暴力查询,每一次查询是$\sqrt n$的时间复杂度,最终均摊时间复杂度为$O(n\sqrt n)$
对于$< \sqrt n$的询问,这样进行考虑,由于每一次dfs下去之后,进行重儿子继承的是一段重链不断向上更新,那么考虑记$dp[i][j]$表示当前重链继承上来深度$%i=j$的个数有多少,每次询问时$O(1)$,轻儿子合并时,更新$dp$值就可以了,然后如果更新到重链顶时,就清空$dp$数组(注意不能直接把所有的dp值都清空,只能清空用过的$dp$值,否则时间复杂度不对)那么均摊复杂度也为$O(n\sqrt n)$
#32. 【UR #2】跳蚤公路
首先题目的意思就是让我们找出负环,解出$x$在环上不等式的解集
然后可以发现一个环的解集一定是一个形如$kx+b \geq 0$的形式,那么对于某一个点,其解集一定是一个连续的区间$[L,R]$,这样可以二分出来,注意这里先需要找出合法区间内的一个合法解,之后再能两次二分出左右端点,求一个合法解的方法也是二分,二分出$mid$后,如果不存在负环,那么说明这一定是一个合法解直接返回即可,如果有负环,那么用spfa跑出来之后,看是$+1$还是$-1$的边使得当前的图存在负环,只要记录一下到每一个点的$+1/-1$之和,如果为正,那么需要变大,如果为负,那么需要变小
那么最暴力的方法对于每一个点直接二分出这个区间,这样复杂度为$O(n^2mlogw)$
考虑强连通分量缩点,那么负环只有可能存在于强连通分量中,缩点后的图是一个DAG,最终某一个点的答案一定是1号点到这个点在DAG上走过所有强连通分量解集的交
那么有效的环一定是在某一个强连通分量中,只要对每一个强连通分量二分求出其合法区间即可,那么这个算法的上界是$O(nmlogw)$
那么最后合并答案的时候,只要进行拓扑序,然后上界取$min$,下界取$max$即可
题解中给出另外一种做法
考虑在spfa结束后,什么样的节点是在负环上的
设$f(n,i)$表示经过$n$轮之后到达$i$的最小路径
对于节点$i$,$i$在负环上的充要条件是
$f(n,i) \leq f(n-1,i)$
现在设$g(n,i,k)$表示经过$n$轮之和到达$i$并且到到这个节点的不等式$x$前的前的系数为$k$最短路径
$f(n,i)=\min\{g(n,i,k)+kx\}$
带入到上式得$ \min\{g(n,i,k)+kx\} \leq \min\{g(n-1,i,j)+jx\}$
解这个不等式即可
代码我只写了我的那个做法
最新文章
- 【去除NSString 字符串中的空格换行符】
- 介绍 .Net工具Code Snippet 与 Sql Server2008工具SSMS Tools Pack
- 在Linux命令行下令人惊叹的惊叹号(!)
- 20160808_Linux服务
- Oracle GoldenGate 12c 新特性
- Softerra LDAP Browser 使用及配置 有图有真相
- 服务器网页GZIP压缩怎么配置
- poj 2723 2-SAT问题
- (转)solr排序OOM解决方法
- Lua开发环境搭建(Mac)
- 代码:Masonry 第三方框架
- The type java.lang.String cannot be resolved. It is indirectly referenced from required .class files
- Linux驱动开发cdev驱动分层设计
- Flask源码解读(一)
- 一个web项目在myeclipse中add deployment时无法被识别出来的原因
- PAT (Advanced Level) 1062. Talent and Virtue (25)
- MBProgressHUD1.0.0源码解析
- [luogu3412]仓鼠找sugar II
- 基于 DataLakeAnalytics 做跨地域的数据分析
- Linux常用基础操作命令大全(超实用精心整理)