2011-09-18 12:40:00Morris
d222. Q11127 Triple-Free Binary Strings
d222. Q11127 Triple-Free Binary Strings
一個 pattern 包含 0, 1 還有星號(*)，星號可以被換成 1 或 0。例如，0**1 可以換成 0001, 0011, 0101, 0111，但是不能換成 1001 或 0000。
/* Problem: d222 "Q11127 Triple-Free Binary Strings" from ACM11127 luckycat翻譯*/
/* Language: C (1800 Bytes) */
/* Result: AC(80ms, 776KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-18 22:17:57 */
/**********************************************************************************/
#include<stdio.h>
#define HAND 131071
struct {
int num, l;
int next;
}NODE[3000];
int size, HASH[HAND+1];
void FreeAll() {
int i;
for(i = 0, size = 1; i <= HAND; i++)
HASH[i] = 0;
}
void insHASH(int n, int l) {
static int m, pre, now;
m = n&HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].num == n && NODE[now].l == l)
return ;
else if(NODE[now].num < n || (NODE[now].num == n && NODE[now].l < l))
pre = now, now = NODE[now].next;
else break;
}
NODE[size].num = n, NODE[size].l = l;
NODE[size].next = now;
if(pre) NODE[pre].next = size;
else HASH[m] = size;
size++;
}
int findHASH(int n, int l) {
static int m, pre, now;
m = n&HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].num == n && NODE[now].l == l)
return 1;
else if(NODE[now].num < n || (NODE[now].num == n && NODE[now].l < l))
pre = now, now = NODE[now].next;
else break;
}
return 0;
}
void Build() {
FreeAll();
int i, j, k, tmp;
for(i = 1; i <= 10; i++) {
k = (1<<i)-1;
for(j = 0; j <= k; j++) {
tmp = j | (j << i) | (j << (2*i));
insHASH(tmp, i*3);
}
}
}
int n, Ans, C = 0;
char s[35];
void DFS(int n, char *s, int idx) {
int i;
for(i = 3; i <= idx; i+=3) {
if(findHASH(n&((1<<i)-1), i))
return;
}
if(*s == '\0') {
Ans++;return;
}
if((*s) == '1' || (*s) == '0') {
DFS((n<<1)|((*s)-'0'), s+1, idx+1);
} else {
DFS((n<<1)|0, s+1, idx+1);
DFS((n<<1)|1, s+1, idx+1);
}
}
main() {
Build();
while(scanf("%d", &n) == 1 && n) {
Ans = 0;
scanf("%s", s);
DFS(0, s, 0);
printf("Case %d: %d\n", ++C, Ans);
}
return 0;
}
內容 ：
Q11127: Triple-Free Binary Strings
二元字串是 0 和 1 組成的。給你一個二元字串 T，如果沒有二元字串 S，使得 SSS(三個 S 字串連起來)是 T 的子字串，那 T 就是 triple-free。一個 pattern 包含 0, 1 還有星號(*)，星號可以被換成 1 或 0。例如，0**1 可以換成 0001, 0011, 0101, 0111，但是不能換成 1001 或 0000。
給你一個 pattern P，它可以換成多少種 triple-free 的字串？
輸入說明 ：
每一行表示一組測資，包含 pattern 的長度 n(0 < n < 31)，還有 pattern P。最多有 35 組測資。
n=0 時表示輸入結束。
n=0 時表示輸入結束。
輸出說明 ：
對每組測資，輸出 case number 和答案，如下所示。
範例輸入 ：
4 0**15 *****10 **01**01**0
範例輸出 ：
Case 1: 2Case 2: 16Case 3: 9
提示 ：
小心超時
出處 ：
ACM11127 luckycat翻譯 (管理：nanj0178)
作法 :
用一個 HASH 把所有的 SSS 存入,
最多 2^10(S的總個數) * 10 (S的長度),
在用 DFS 的時侯, 進行剪枝
/**********************************************************************************/作法 :
用一個 HASH 把所有的 SSS 存入,
最多 2^10(S的總個數) * 10 (S的長度),
在用 DFS 的時侯, 進行剪枝
/* Problem: d222 "Q11127 Triple-Free Binary Strings" from ACM11127 luckycat翻譯*/
/* Language: C (1800 Bytes) */
/* Result: AC(80ms, 776KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-18 22:17:57 */
/**********************************************************************************/
#include<stdio.h>
#define HAND 131071
struct {
int num, l;
int next;
}NODE[3000];
int size, HASH[HAND+1];
void FreeAll() {
int i;
for(i = 0, size = 1; i <= HAND; i++)
HASH[i] = 0;
}
void insHASH(int n, int l) {
static int m, pre, now;
m = n&HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].num == n && NODE[now].l == l)
return ;
else if(NODE[now].num < n || (NODE[now].num == n && NODE[now].l < l))
pre = now, now = NODE[now].next;
else break;
}
NODE[size].num = n, NODE[size].l = l;
NODE[size].next = now;
if(pre) NODE[pre].next = size;
else HASH[m] = size;
size++;
}
int findHASH(int n, int l) {
static int m, pre, now;
m = n&HAND;
pre = 0, now = HASH[m];
while(now) {
if(NODE[now].num == n && NODE[now].l == l)
return 1;
else if(NODE[now].num < n || (NODE[now].num == n && NODE[now].l < l))
pre = now, now = NODE[now].next;
else break;
}
return 0;
}
void Build() {
FreeAll();
int i, j, k, tmp;
for(i = 1; i <= 10; i++) {
k = (1<<i)-1;
for(j = 0; j <= k; j++) {
tmp = j | (j << i) | (j << (2*i));
insHASH(tmp, i*3);
}
}
}
int n, Ans, C = 0;
char s[35];
void DFS(int n, char *s, int idx) {
int i;
for(i = 3; i <= idx; i+=3) {
if(findHASH(n&((1<<i)-1), i))
return;
}
if(*s == '\0') {
Ans++;return;
}
if((*s) == '1' || (*s) == '0') {
DFS((n<<1)|((*s)-'0'), s+1, idx+1);
} else {
DFS((n<<1)|0, s+1, idx+1);
DFS((n<<1)|1, s+1, idx+1);
}
}
main() {
Build();
while(scanf("%d", &n) == 1 && n) {
Ans = 0;
scanf("%s", s);
DFS(0, s, 0);
printf("Case %d: %d\n", ++C, Ans);
}
return 0;
}