【NOIP 2004】 虫食算

【题目链接】

https://www.luogu.org/problemnew/show/P1092

【算法】

搜索 + 剪枝

直接搜索显然会超时，考虑剪枝

1 ： 优化搜索顺序

2 ： 假设我们已经确定了一组(Ai,Bi,Ci)，那么，如果(Ai + Bi) mod n 和(Ai + Bi + 1) mod n都不等于Ci，可以剪枝

【代码】

#include<bits/stdc++.h>
using namespace std;int i,n,len;
int a[],ord[];
char A[],B[],C[];
bool used[],vis[];
bool solved;inline bool ok()
{
    int i;
    for (i = n; i >= ; i--)
    {
          if (a[A[i]-'A'+] == -) continue;
          if (a[B[i]-'A'+] == -) continue;
          if (a[C[i]-'A'+] == -) continue;
          if ((a[A[i]-'A'+] + a[B[i]-'A'+]) % n == a[C[i]-'A'+]) continue;
          if ((a[A[i]-'A'+] + a[B[i]-'A'+] + ) % n == a[C[i]-'A'+]) continue;
          return false;
    }
    return true;
}
inline void print()
{
    int i;
    for (i = ; i <= n; i++) printf("%d ",a[i]);
    printf("\n");
}
inline bool check()
{
    int t,b = ;
    for (i = n; i >= ; i--)
    {
                t = (a[A[i]-'A'+] + a[B[i]-'A'+] + b) % n;
                if (a[A[i]-'A'+] + a[B[i]-'A'+] + b >= n) b = ;
                else b = ;
                if (a[C[i]-'A'+] == t) continue;
                else return false;
    }
    if (b) return false;
    else return true;
}
inline void dfs(int dep)
{
    int i;
    if (dep > n)
    {
        if (check())
        {
            solved = true;
            print();
        }
        return;
    }
    if (!ok()) return;
    for (i = n - ; i >= ; i--)
    {
        if (!used[i])
        {
            a[ord[dep]] = i;
            used[i] = true;
            dfs(dep+);
            if (solved) return;
            used[i] = false;
            a[ord[dep]] = -;
        }
    }
}int main()
{    memset(a,,sizeof(a));
    scanf("%d%s%s%s",&n,A+,B+,C+);
    for (i = n; i >= ; i--)
    {
        if (!vis[A[i]-'A'+])
        {
              ord[++len] = A[i] - 'A' + ;
              vis[A[i]-'A'+] = true;
        }
        if (!vis[B[i]-'A'+])
        {
            ord[++len] = B[i] - 'A' + ;
            vis[B[i]-'A'+] = true;
        }
        if (!vis[C[i]-'A'+])
        {
            ord[++len] = C[i] - 'A' + ;
            vis[C[i]-'A'+] = true;
        }
    }
    dfs();    return ;}