2016.3.4测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------------------
题面大概可以在SuperOj上找到
---------------------------------------------------------------
T1:
经典的出题事故题...
标算要用n+2个整数的空间
暴力桶排序只要n个bool的空间233
标算的做法：
若a[i]=x,则看做是i向x连边
因为只有一个点出现多次，所以整个图只有一个点入度大于1
那么从任意一个点出发，要么是一个环，要么是一个ρ，且只有1个ρ
没有入度的点一定是某个ρ的起点，要求的点就是ρ上刚好进入环的那个点
n+1没有入度，因此他一定是某个ρ的起点，设为s
考虑用类似pollard-rho的算法
设两个点x和y，x每次走一步，y每次走两步
设x和y第一次相遇的点为a
再把x设为s,y设为a，他们一起每次走1步
再相遇的点q就是ρ上从链刚好进入环的那个点
这个做法要证明也很简单：
相遇意味着对p同余
考虑第一次相遇，
设x走了k+v*p+b步（k是链长，p是环长，b是多的那一部分）
而y走了k+w*p+b=2（k+v*p+b）
在模域p下，得到：k+b=0
再考虑第二次相遇，
讨论一下，若k小于环长，那么y的出发点离第一次进入环的点刚好k步（因为k+b+k=k)
因此会相遇在q点
若k大于环长，那么y绕几圈之后就会出现x离q还有p步，y在q
然后一起走p步就相遇了，也会相遇在q点
顺便，这个做法好像叫龟兔赛跑算法...
另外标算的空间是O(n)的，但是QJC神犇想出了一个n^0.5空间的做法：
因为只有答案会出现超过一次
那么答案每出现一次都可以看成是另一个数变成他了
所以如果对整数分块，那么有且只有一个块中数的个数超过了块大小，也就是答案所在块
因此考虑分块，设一个n^0.5左右的常数k
用两种方法分块：所有除以k取下整相同的一块，所有对k同余的数分一块
这样两个块的大小都不超过n^0.5
用答案出现的两个块可以还原出答案
---------------------------------------------------------------
T2:
标算竟然没有用到只有四个字符这个性质...
首先假设求出[l,r]这个区间的代价是f(l,r)
那么显然有转移：
f(l,r)<-min{f(l+1,r),f(l,r-1)}+1
另外若[l,r]是一个偶数长度的回文串，还有f(l,r)<-f(l,1+l+((r-l+1)/2))+1
对于非回文串，坑定是从他的某个回文子串转移过来的
对于某个偶数长度的回文串，坑定是从他的某个回文子串转移过来或者从他去掉首位两个字符转移过来
先求出所有本质不同的回文串（这里及以后只考虑偶数长度的回文串）
对于某个回文串x，设s[x]是x的小于其长度一半的最长后缀回文串
那么s[x]可以更新一下x
同时x还可以更新一下a+x+a，其中a是某个字符
所有本质不同的回文串以及s[x]都可以通过回文树求出（其中s[x]是在x的后缀链接上倍增）
然后用所有回文串尝试更新一下总的串就可以了
---------------------------------------------------------------
T3:
据说是一道noip pj难度的题..
据说这个题的难度主要在于读数据...
然而在考场上花了我3h左右..
最后还是找规律优化到n^2的...
我的做法：
首先列一个很naive的DP
f[i][j][k]表示前i个数，用了j个，和为k，方案数
然后就有转移:
f[i][j][k]->f[i+1][j+u][k+u*(i+1)]
u是枚举的
然后发现可以优化：
f[i][j][k]<-f[i-1][j][k]+f[i][j-1][k-i]
然后发现还可以优化:
f[j][k]<-f[j-1][k-i]
然后用找规律大法：
f[j][k]=f[j-1][k-1]+f[j][k-j]
然后就没有然后了
标算的做法：
可以用ferres图证明：
把n个数分成不超过k个数的方案数，等于把n个数分成许多个数，其中最大数为k的方案数
那么就有DP:
f[i][j]表示最大数为i，和为j，方案数
f[i][j]
->f[i][j+i]（再放一个i进去）
->f[i+1][j+i+1]（再放一个i+1进去）
注意这个DP每次只能把最大数放进去，正确性是显然的
---------------------------------------------------------------
评论 (0)
