题目描述
题解1
题目很长，耐心读完题目后，获取以下信息：
磁盘的数据分布单元是条带，而条带又是由多个数据块组成。题中的每两个字符构成一个16进制数，代表一个字带。一个数据块的大小是4个字节即8个字符。校验块从右向左依次选择，到达最左边后，再从最右边开始。而数据存储从校验块相邻的下一磁盘块开始。 观察子任务1，2，3，4，5都满足l = n，我们先仅考虑磁盘未损坏的情况，这时候只需要确定所读的块所在的位置就可以读取信息，不需要利用异或求解。 diskIdx, stripeIdx, checkCnt, checkPos, dataPos;//磁盘号,条带号,前面校验盘的数量,校验盘所处的位置,数据的位置 确定块的位置先要确定哪个磁盘。diskIdx = idx2 / s % n 然后确定它在磁盘的哪个条带（先不考虑校验块）。stripeIdx = idx2 / s / n; 确定该块前面有几个校验条带。
checkPos
= n
- 1 -diskIdx
;
if(stripeIdx
< checkPos
){
checkCnt
= 0;
}
else{
checkCnt
= (stripeIdx
- checkPos
) / (n
- 1) + 1;
}
最后确定块在磁盘的位置。dataPos = (stripeIdx + checkCnt) * s + (idx2 % s); 具体见代码1。
代码1
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std
;
#define MAX 1005
char data
[MAX
][82000];
int main(){
int n
, s
, l
, m
, total
;
int idx1
, idx2
;
string str
;
scanf("%d%d%d", &n
, &s
, &l
);
for(int i
= 0; i
< l
; ++i
){
scanf("%d ", &idx1
);
fgets(data
[idx1
], 82000, stdin);
}
total
= strlen(data
[idx1
]) / 8 * (n
- 1);
scanf("%d", &m
);
for(int i
= 0; i
< m
; ++i
){
scanf("%d", &idx2
);
if(idx2
>= total
){
cout
<< "-" << endl
;
continue;
}
int diskIdx
, stripeIdx
, checkCnt
, checkPos
, dataPos
;
diskIdx
= idx2
/ s
% n
;
stripeIdx
= idx2
/ s
/ n
;
checkPos
= n
- 1 -diskIdx
;
if(stripeIdx
< checkPos
){
checkCnt
= 0;
}
else{
checkCnt
= (stripeIdx
- checkPos
) / (n
- 1) + 1;
}
dataPos
= (stripeIdx
+ checkCnt
) * s
+ (idx2
% s
);
for(int j
= dataPos
* 8; j
<dataPos
* 8 + 8; ++j
){
printf("%c", data
[diskIdx
][j
]);
}
printf("\n");
}
return 0;
}
代码1第一次提交时，使用的是cin，读入字符串数据，只有30％数据过了，提示超时。猜想可能是cin的原因，然后将string换成char *，用scanf读入字符串，这次有70％的数据过了，但仍然提示超时。有点想不懂了，就查看一下别人的博客。 scanf会超时是因为后面的测试点的字符串数据太大，这里要用gets（被弃用了）或者fgets。注意fgets的用法，读入的字符串的长度小于指定的长度，会自动加上\n,输入数字时要将空格接收，不然会被fgets读取。 另外一种解决超时的方法是用cin，然后关闭c++的流同步，防止cin超时。ios::sync_with_stdio(false);
用了fgets后，竟然100％数据通过，我情况还没考虑完全呢?这里说明后台数据有点问题。不信你们可以试一下。
题解2
考虑l<=n的情况，此时如果读取的磁盘块数据出现缺失，需要借助校验块来恢复。主要用到的就是异或的方法。
代码2
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std
;
#define MAX 1005
char data
[MAX
][82000];
bool mark
[MAX
];
int toNum(char ch
){
if(isdigit(ch
)){
return ch
-'0';
}
else{
return ch
- 'A' + 10;
}
}
char toChar(int num
){
if(num
< 10){
return num
+ '0';
}
else{
return 'A' + (num
- 10);
}
}
void deal(int diskIdx
, int n
, int idx
){
if(mark
[diskIdx
]){
for(int j
= idx
; j
< idx
+ 8; ++j
){
printf("%c", data
[diskIdx
][j
]);
}
printf("\n");
}
else{
for(int i
= idx
; i
< idx
+ 8; ++i
){
int res
= -1;
for(int j
= 0; j
< n
; ++j
){
if(diskIdx
!= j
){
if(res
== -1){
res
= toNum(data
[j
][i
]);
}
else{
res
= res
^ toNum(data
[j
][i
]);
}
}
}
printf("%c", toChar(res
));
}
printf("\n");
}
}
int main(){
int n
, s
, l
, m
, total
;
int idx1
, idx2
;
string str
;
memset(mark
, false, sizeof(mark
));
scanf("%d%d%d", &n
, &s
, &l
);
for(int i
= 0; i
< l
; ++i
){
scanf("%d ", &idx1
);
fgets(data
[idx1
], 82000, stdin);
mark
[idx1
] = true;
}
total
= strlen(data
[idx1
]) / 8 * (n
- 1);
scanf("%d", &m
);
for(int i
= 0; i
< m
; ++i
){
scanf("%d", &idx2
);
if(idx2
>= total
){
cout
<< "-" << endl
;
continue;
}
int diskIdx
, stripeIdx
, checkCnt
, checkPos
, dataPos
;
diskIdx
= idx2
/ s
% n
;
if(!mark
[diskIdx
] && l
< n
- 1){
cout
<< "-" << endl
;
continue;
}
stripeIdx
= idx2
/ s
/ n
;
checkPos
= n
- 1 -diskIdx
;
if(stripeIdx
< checkPos
){
checkCnt
= 0;
}
else{
checkCnt
= (stripeIdx
- checkPos
) / (n
- 1) + 1;
}
dataPos
= (stripeIdx
+ checkCnt
) * s
+ (idx2
% s
);
deal(diskIdx
, n
, dataPos
* 8);
}
return 0;
}
github地址
