로곡 1666 접두사 단어trie 트리 dp

4563 단어 문자열triedp
제목 링크 제목: n개의 문자열을 줍니다. 몇 개의 문자열을 선택할 때마다 하나의 집합을 형성합니다. 집합의 어떤 문자열도 다른 문자열의 접두사가 되지 않도록 몇 개의 집합이 있는지 물어보십시오.공집도 반드시 조건을 만족시킬 것이다.두 개의 같은 문자열이 나타나지 않을 것을 보증합니다.
문제풀이: NOIP 시뮬레이션에서 나온 문제이기도 하다.그때 트리를 세운 후에 dp(나도 어떻게 생각했는지 잊어버렸다)가 생각났는데 그때 나는 서로 접두사로 계산하기 어려울 것 같아서 집합 총수로 서로 접두사로 존재하는 집합을 빼려고 했는데 그 결과 자신의 dp계수에 오류가 생겨서 폭력만 사귀었다.강평을 듣고 연구한 결과 직접 해도 결코 어렵지 않다는 것을 발견했다.그래서 강평에서 제시한 방법을 말씀드리겠습니다.먼저 모든 문자열에 trie 트리를 세운 다음에 우리는 trie 트리에 유용한 점은 특정한 문자열의 끝으로 표시된 점만 있다는 것을 알 수 있다. 그래서 우리는 trie 트리의 조상 후손들의 관계에 따라 이런 유용한 점에 대해 새로운 나무를 세운다(허근 0호점을 보존한다).이때 우리는 새 나무의 어떤 점이 선택되면 합법적인 집합에서 그 나무 안의 모든 다른 노드가 선택될 수 없다는 것을 생각하기 어렵지 않다.만약에 어떤 노드가 선택되지 않는다면 그의 각 노드가 있는 자수 간의 선택은 서로 방해가 되지 않는다. 즉, x를 선택하지 않을 때 x의 첫 번째 아들이 있는 자수는 합법적인 방안을 선택했고 x의 두 번째 아들이 있는 자수는 합법적인 방안을 선택했다. 그러면 두 아들이 있는 자수가 선택한 점은 반드시 합법적인 것이다.그러면 우리는 dp[i]를 i를 뿌리로 하는 자수 합법적인 방안의 수량으로 설정한다. 같은 뿌리의 서로 다른 아들이 있는 자수 사이에 우리는 곱셈 원리로 방안을 누적할 수 있다. 마지막으로 자수는 모두 i만 선택하는 방안을 선택하지 않고 자수의 방안수이다.dp방정식은 dp[x]=1+∏fa[y]=xdp[y]dp[x]=1+∏fa[y]==xdp[y]이다.마지막 답은 dp[0]-3 1dp[0] -3 1이다. 허근만 선택하는 경우가 없기 때문에 dp[0] dp[0]에는 이미 빈 집합을 선택하는 경우가 포함되어 있다.
코드:
#include 
using namespace std;

int n,cnt,hed[100010],num;
char s[60][60];
long long dp[100010];
struct node
{
    int vis[26],cnt;
}a[100010];
struct edge
{
    int next,to;
}b[100010];
void add(int from,int to)
{
    b[++num].to=to;
    b[num].next=hed[from];
    hed[from]=num;
}
void build(int x)
{
    int ji=0,m=strlen(s[x]+1);
    for(int i=1;i<=m;++i)
    {
        int y=s[x][i]-'a';
        if(!a[ji].vis[y])
        a[ji].vis[y]=++cnt;
        ji=a[ji].vis[y];
    }
    a[ji].cnt=1;
}
void rebuild(int x,int fa)
{
    if(a[x].cnt)
    {
        add(fa,++cnt);
        fa=cnt;
    }
    for(int i=0;i<=25;++i)
    {
        if(a[x].vis[i])
        rebuild(a[x].vis[i],fa);
    }
}
void dfs(int x)
{
    dp[x]=1;
    for(int i=hed[x];i;i=b[i].next)
    {
        int y=b[i].to;
        dfs(y);
        dp[x]*=dp[y];
    }
    dp[x]++;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s[i]+1);
        build(i);
    }
    cnt=0;
    rebuild(0,0);
    dfs(0);
    printf("%lld
",dp[0]-1);
    return 0;
}
[JavaScript] innerHTM, textContent의 차이점
커리잉 언제 써요?

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage