Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不用拓排,压位+位运算强行模拟亦可 856K 0ms好吧,拓排是个好办法,但是不用拓排亦可。 用一个邻接矩阵F[i,j]记录 字母i是否小于字母j 小于则为True 当我们读入一个操作 字母i<字母j 时 作如下操作 1. F[i,j]置为True 2. 将F[j]的信息更新入F[i] 3. 对于所有满足F[k,i]=True的 将F[i]更新入F[k] 4. 判圈 5. 判唯一 6. 读入新的操作 这其中操作最多的在于2、3、4、5(对于拓排来说尤其是4、5) 我们改用一组Longint(31位二进制)来替代这个原来的布尔数组 那么 1)将一个数组F[i] 更新入F[j] 就可以用一句话表述为 F[j]=F[j] or F[i] 2)满足F[k,i]=True 即为 F[k] and (1 shl i)<>0 3)判圈时 若 F[k] and (1 shl k)=0 则有圈 4)判唯一时 用以下代码求出比第i个字母大的字母有多少个 //伪代码 s=0 t=F[i] do while t<>0 t=t-lowbit(t) s=s+1 loop //伪代码结束 考虑到 如果能够得出唯一的序列 那么对于这N个字母来说 一定有一个字母比N-1个字母小 有一个字母比N-2个字母小...依此类推 一定有一个字母比0个字母小。 用一个数组Q[i] 记录 有i个字母比它大的字母是哪一个 如果出现两个字母有同样多个字母比它们大 那么就不唯一了 如果不存在 那么就有唯一解 Q即为我们要求的字母数列 因为使用了位运算这种底层操作 所以时间效率相当高 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator