[NOIP 2004] [CODEVS 1064] 충 식 산 (검색 | 고 스 소원)

제목 설명
전송 문
해제
이것 이 바로 검색 문 제 잖 아 요. 고 스 소원 이 야 말로 도장 을 푸 는 것 이 라 고 하 던 데 이 검색 기술 은 아직도 많아 서 저 에 게 유용 한 것 을 배 웠 습 니 다. ① 한 숫자 를 찾 을 때마다 합 법 적 인지 판단 해 야 합 니 다.이렇게 보면 매번 O (n) 를 한 번 씩 쓸 어야 하 는 것 처럼 보이 지만 효과 가 매우 좋아 서 대량의 폐 지 를 잘 라 낼 수 있다.판단 에 대해 저 는 처음에 진 위 를 하지 않 은 부분 만 생각 했 고 진 위 를 가 진 부분 은 판단 하지 않 았 습 니 다. 그러면 사실은 매우 쓸모 가 없습니다.그렇다면 진 위 를 고려 하려 면 A + B = C, (A + B)% n! =C 및 (A + B + 1)% n! =C. 그러면 ABC 는 합 법 적 인 해석 이 아 닐 겁 니 다.또한 ABC 중 두 개 를 알 게 되면 세 번 째 를 계산 할 수 있 고 진위 와 불 진위 두 가지 상황 으로 나 눌 수 있다. 만약 에 두 가지 상황 이 계산 한 수 를 모두 사용 했다 면 이 해 는 합 법 적 이지 않다.② 합 법 적 인 판단 방식 은 모든 항목 에 대해 ABC 가 많이 알 면 알 수록 가지치기 가 쉽다 는 것 을 일 깨 워 준다.그러면 검색 순 서 를 바 꾸 고 알파벳 이 오른쪽 에서 왼쪽으로 나 오 는 순서대로 검색 할 수 있다.이 효과 도 매우 뚜렷 하 다.③ 숫자 를 채 울 때 는 역순 검색 이 역순 검색 보다 훨씬 빠르다.why?
코드

#include
#include
#include
#include
using namespace std;

char a[30],b[30],c[30],s[100];
int n,len,ans[30];
bool vis[30];

bool check()
{
    int last=0,aa,bb,cc;
    for (int i=n-1;i>=0;--i)
    {
        aa=ans[a[i]-'A'+1],bb=ans[b[i]-'A'+1],cc=ans[c[i]-'A'+1];
        if (aa==-1||bb==-1||cc==-1) {last=-1;continue;}
        if (last==-1)
        {
            if ((aa+bb)%n!=cc&&(aa+bb+1)%n!=cc) return false;
        }
        else
        {
            if ((aa+bb+last)%n!=cc) return false;
            last=(aa+bb+last)/n;
        }   
    }
    if (last!=-1&&last!=0) return false;
    return true;
}
void dfs(int dep)
{
    if (dep==len+1)
    {
        if (check())
        {
            for (int i=1;i<=n;++i) printf("%d%c",ans[i]," 
"[i==n]);
            exit(0);
        }
        return;
    }
    int now=s[dep]-'A'+1;
    if (ans[now]!=-1) dfs(dep+1);
    else
        for (int i=n-1;i>=0;--i)
            if (!vis[i])
            {
                ans[now]=i;
                vis[i]=true;
                if (check())
                    dfs(dep+1);
                ans[now]=-1;
                vis[i]=false;
            }
}
int main()
{
    scanf("%d
",&n);
    gets(a); gets(b); gets(c);
    for (int i=n-1;i>=0;--i)
    {
        if (!vis[a[i]-'A'+1]) vis[a[i]-'A'+1]=true,s[++len]=a[i];
        if (!vis[b[i]-'A'+1]) vis[b[i]-'A'+1]=true,s[++len]=b[i];
        if (!vis[c[i]-'A'+1]) vis[c[i]-'A'+1]=true,s[++len]=c[i];
    }
    memset(ans,-1,sizeof(ans)); memset(vis,0,sizeof(vis));
    dfs(1);
}

총결산
① 성질 분석!성질 분석!성질 분석!아주 중요 해!!