这道题从题意上来看,好象是一道字符串匹配的题目。不过很变态的是,这道题目进行
匹配的单位竟然是1bit!题目的输入文件是一个二进制文件,而且最大可以到1MB。我目前
还没有想出什么好方法。我用来生成测试数据答案的程序,虽然也加了一些优化,但是对于
一个500多KB的文件也要将近10秒才能出解(机型:P31G/128MBMemory)。请问,有
你分析从一颗卫星获得的遥感数据,并以此作为你研究工作的一部分。从这颗特殊卫星获得
的已处理的数据是可能实现的,不过价格非常昂贵。然而,原始的、未处理的卫星数据却被
你已拥有了关于原始数据格式的文档和可能包含原始数据的数据文件。第一步,你应校
验文件中的数据中。每个文件中的原始数据都以从卫星接收时的形式保存在一个单独的比特
流(编码信息流)。在一个文件中可能存在一段或多段的有效信息,被几段空数据或混乱数
据所分隔开。空数据或混乱数据也可能出现在文件的开端和结尾部分。在最坏情况下,一个
原始数据被分割为若干数据包,每个数据包含80 个字节。每个字节都是从0 开始的数,
相当于8 bit。每个数据包中的第4 到第7 个字节均包含一个独特的、32 bit 的“同步编码”。
同步编码是每个卫星的常量,在校验比特流时,它作为有效的原始数据包的一个特征标志。
数据包第9 到第12 个字节包含一个计数器,表示为1 个32 bit 的无符号整数。然而,在数
据传k8凯发集团输给你之前,并未作任何的字节调整,所以,数据中的字节可能相对于储存在文件中的
字节的字节界限发生“位偏移(bit shift)”。你可以假定数据包的字节界限和原始数据的字节
一个有效的数据包定义为一个完整的、“同步编码”位置正确的数据包。为了论述方便,
我们定义一个无效的数据包是一个80 字节、在正确位置不含有“同步编码”的数据包。鉴
于“同步编码”可能出现在一个比特流的任意一个位置,一个有效数据段的开端定义为 3
个或更多的连续的有效数据包。一旦一个有效数据段的开端被找到,它的末尾就被定义为3
个或更多的连续的无效数据包之前的最后一个有效数据包的末尾(若从有效数据段的开端到
文件末端无3 个连续的无效数据包,则有效数据段的末尾是最后一个无效数据包之前的有效
数据包的末端)。如果一个有效数据段后紧跟着小于3 个(不包含3 个)无效数据包,你应
对于给定的一个输入文件,你的程序应当能将文件中的所有有效数据段定位并报告:
1 数据段第一个bit 的“位偏移量”(如果第一个bit 在文件的第n 个bit ,
则相对于文件开端的“位偏移量”为(n-1) mod 8)。用一个非负整数表示。
一个输入文件大小大于0 字节、最多不超过1MB的二进制文件。卫星的同步编码用16
对于每个有效数据段的报告均单独输出在一行,3 项报告都用10 进制,并用一个空格隔
开。如果你的程序在文件中未发现任何有效数据,则输出“No valid data found”。
注:程序的输入是一个二进制文件。为了阅读方便,样例中的输入表示成16 进制格式