2012-06-30 08:00:24Morris
[PTC] 201206E Circular Codes 最小表示法
Problem E
Circular Codes
Input le: testdata.in
Time limit: 10 seconds
Problem DescriptionCircular Codes
Input le: testdata.in
Time limit: 10 seconds
The Circular Intelligence Agency stores all secret information in the follow-
ing circular codes. Each encrypted string is an N-bit binary string c =
c0c1 ... cN-1. We say that binary string a = a0a1 ... aN-1 is a circular
rotation of c if there exists an index k with 0≦k ≦ N-1 such that
ci = a(i+k) mod N holds for each i = 0,1, ..., N-1. The message d =
d0d1 dN-1 to be decrypted is the bit-wise exclusive-OR of a = a0a1 aN1
and b = b0b1 ... bN-1, where
a is the circular rotation of c such that the binary number represented
by a (if treated as a nonnegative integer) is the maximum, and
b is the circular rotation of c such that the binary number represented
by b (if treated as a nonnegative integer) is the minimum.
For instance, if c = 11001, then a = 11100, b = 00111, and d = 11011.
Technical Speci cation
1 N 300000
Input Format
In the rst line of the input le there is an integer C, indicating the number
of distinct test cases to be followed. Each of the next C lines stands for a
test case. For each test case, there is an integer N, followed by an N-bit
binary string.
Output Format
Output should be C lines. The binary string in the j-th line is the decrypted
message for the j-th test case.
Sample Input
5
5 10101
6 111111
7 0000000
6 110110
25 1101001011100100111010101
Sample Output
10001
000000
0000000
101101
1100110110111110001110011
題目的意思 : 有一個環狀的 code, 請找出一個最大表示法的 a, 最小表示法的 b
兩個取 xor 即可, 預知詳細者, 請參考 周源最小表示法
#include <stdio.h>
#include <stdlib.h>
int MinExp(const char *s, const int slen) {
int i = 0, j = 1, k = 0, x, y, tmp;
while(i < slen && j < slen && k < slen) {
x = i + k;
y = j + k;
if(x >= slen) x -= slen;
if(y >= slen) y -= slen;
if(s[x] == s[y]) {
k++;
} else if(s[x] > s[y]) {
i = j+1 > i+k+1 ? j+1 : i+k+1;
k = 0;
tmp = i, i = j, j = tmp;
} else {
j = i+1 > j+k+1 ? i+1 : j+k+1;
k = 0;
}
}
return i;
}
int MaxExp(const char *s, const int slen) {
int i = 0, j = 1, k = 0, x, y, tmp;
while(i < slen && j < slen && k < slen) {
x = i + k;
y = j + k;
if(x >= slen) x -= slen;
if(y >= slen) y -= slen;
if(s[x] == s[y]) {
k++;
} else if(s[x] < s[y]) {
i = j+1 > i+k+1 ? j+1 : i+k+1;
k = 0;
tmp = i, i = j, j = tmp;
} else {
j = i+1 > j+k+1 ? i+1 : j+k+1;
k = 0;
}
}
return i;
}
char str[300005];
int main() {
int t, n, i;
scanf("%d", &t);
while(t--) {
scanf("%d %s", &n, str);
int a = MinExp(str, n);
int b = MaxExp(str, n);
for(i = 0; i < n; i++) {
printf("%d", (str[a]-'0')^(str[b]-'0'));
a++, b++;
if(a >= n) a-=n;
if(b >= n) b-=n;
}
puts("");
}
return 0;
}