Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不用拓排,压位+位运算强行模拟亦可 856K 0ms

Posted by szxyj at 2011-04-04 15:36:30 on Problem 1094
好吧,拓排是个好办法,但是不用拓排亦可。

用一个邻接矩阵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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator