ZOJ 3494 BCD 코드AC 로봇 + 디지털 DP
바로 현재 0~9에 대응하는 BCD 코드(대응하는 4자리의 이진법)가 있고, n열(0<=n<=1000)이 나올 수 없는 열(0과 1만 포함)을 제시했는데, 숫자 A에서 B 사이에 몇 개의 수가 BCD 코드로 변환되어 표시되지 않았는지 묻는다. 1<=A<=B<=10^200
대략적인 사고방식:
먼저 A와 B의 범위를 고려하면 폭력은 불가능하다. 여기서 디지털 DP, 즉 위치별로 확정된 사상을 사용해야 한다. 먼저 AC자동기로 상태 i에서 출발하여 다음 단계가 0~9로 각각 도달할 수 있는 상태이거나 갈 수 없는 상태를 계산한 다음에 위치별로 각 위치의 값을 정하면 된다. 기억화 검색이 효율을 높일 수 있다는 것을 시사한다. 이 디지털 DP는 매우 간단하다. 선도 0의 문제에 주의하면 된다.
코드는 다음과 같습니다.
Result : Accepted Memory : 3676 KB Time : 210 ms
/*
* Author: Gatevin
* Created Time: 2014/11/27 10:18:15
* File Name: Kagome.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;
const lint mod = 1000000009LL;
int n;
char num[210];
int bit[210];
int bcd[2010][10];
//bcd[i][j] AC i , j , -1
lint dp[2010][210];
//dp[i][j] AC i , j ,
struct Trie
{
int next[2010][2], fail[2010];
bool end[2010];
int L, root;
int newnode()
{
for(int i = 0; i < 2; i++)
next[L][i] = -1;
end[L++] = 0;
return L - 1;
}
void init()
{
L = 0;
root = newnode();
return;
}
void insert(char *s)
{
int now = root;
for(; *s; s++)
{
if(next[now][*s - '0'] == -1)
next[now][*s - '0'] = newnode();
now = next[now][*s - '0'];
}
end[now] = 1;
return;
}
void build()
{
queue <int> Q;
fail[root] = root;
Q.push(root);
while(!Q.empty())
{
int now = Q.front();
Q.pop();
if(end[fail[now]]) end[now] = 1;//
for(int i = 0; i < 2; i++)
if(next[now][i] == -1)
next[now][i] = now == root ? root : next[fail[now]][i];
else
{
fail[next[now][i]] = now == root ? root : next[fail[now]][i];
Q.push(next[now][i]);
}
}
return;
}
};
Trie AC;
void BCD()// bcd
{
for(int i = 0; i < AC.L; i++)
for(int j = 0; j < 10; j++)
{
bcd[i][j] = i;
if(AC.end[bcd[i][j]])
{
bcd[i][j] = -1;
continue;
}
for(int k = 3; k >= 0; k--)
{
if(j & (1 << k))
bcd[i][j] = AC.next[bcd[i][j]][1];
else
bcd[i][j] = AC.next[bcd[i][j]][0];
if(AC.end[bcd[i][j]])
{
bcd[i][j] = -1;
break;
}
}
}
return;
}
/*
* L , AC pos ,
* bound bit
* lead , 0 ( )
*/
lint dfs(int L, int pos, bool bound, bool lead)// ....
{
if(L == 0 && lead) return 1;
if(L == 0 && !lead) return 0;
if(dp[pos][L] != -1 && !bound && lead) return dp[pos][L];
lint ret = 0;
if(!lead)//
{
ret = (ret + dfs(L - 1, pos, false, false)) % mod;//
if(bound)//
{
for(int i = 1; i < bit[L]; i++)// ,
if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
if(bcd[pos][bit[L]] != -1) ret = (ret + dfs(L - 1, bcd[pos][bit[L]], true, true)) % mod;//
}
else
for(int i = 1; i < 10; i++)// ,
if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
}
else
{
if(bound)
{
for(int i = 0; i < bit[L]; i++)
if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
if(bcd[pos][bit[L]] != -1) ret = (ret + dfs(L - 1, bcd[pos][bit[L]], true, true)) % mod;
}
else
for(int i = 0; i < 10; i++)
if(bcd[pos][i] != -1) ret = (ret + dfs(L - 1, bcd[pos][i], false, true)) % mod;
}
if(lead && dp[pos][L] == -1 && !bound) dp[pos][L] = ret;//
return ret;
}
// 0 N
lint solve(int len)
{
if(len == 0) return 0;
for(int i = 0; i < len; i++)
bit[len - i] = num[i] - '0';
return dfs(len, AC.root, true, false);
}
int main()
{
int t;
char ts[22];
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
AC.init();
while(n--)
{
scanf("%s", ts);
AC.insert(ts);
}
AC.build();
BCD();
scanf("%s", num);
int len = strlen(num);
/*
* 1
*/
if(num[len - 1] > '0')
{
int tmp = len - 1;
if(len == 1 && num[len - 1] == '1') len = 0;
num[tmp] = num[tmp] - 1;
}
else
{
num[len - 1] = '9';
int now = len - 2;
while(num[now] == '0')
{
num[now] = '9';
now--;
}
if(num[now] == '1' && now == 0)
{
for(int i = 0; i < len; i++)
num[i] = num[i + 1];
len--;
}
else
num[now] = num[now] - 1;
}
memset(dp, -1, sizeof(dp));
lint A = solve(len);
scanf("%s", num);
len = strlen(num);
lint B = solve(len);
printf("%lld
", (B - A + mod) % mod);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.