1 条题解

  • 0
    @ 2025-1-7 11:49:15

    C++ :

    /*
      枚举全排列,并且加了来了两个剪枝
      ①当一列竖式中的字母已全部枚举,且不符合要求;
      ②当一列竖式中的字母已枚举2个,另一个数字已被使用;
      (剪枝时注意进位) 
    */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define M 27
    using namespace std;
    char s[4][M];
    int n,now;
    int a[M],b[M],c[M];
    bool goal;
    bool Judge()
    {
         int temp=0,k=0;
         for (int i=n-1;i>=0;--i)
         {
             temp=(b[s[1][i]-'A']+b[s[2][i]-'A']+k)%n;
             k=(b[s[1][i]-'A']+b[s[2][i]-'A']+k)/n;
             if (temp!=b[s[3][i]-'A']) return 0;
         }
         return 1;
    } 
    bool Cleck()//剪枝 
    {
         int temp,t1,t2,t3;
         for(int i=n-1;i>=0;i--)
         {
             t1=s[1][i]-'A',t2=s[2][i]-'A',t3=s[3][i]-'A';
             if(b[t1]!=-1&&b[t2]!=-1&&b[t3]!=-1)
             {
                 if((b[t1]+b[t2]+1)%n==b[t3]||(b[t1]+b[t2])%n==b[t3]) continue; 
                else return 0;
             } 
               
             if (b[t1]!=-1 && b[t2]!=-1)
             {
                temp=(b[t1]+b[t2])%n;
                if (a[temp]==-1||a[(temp+1)%n]==-1)continue; 
                else return 0;
             }
             if (b[t1]!=-1&&b[t3]!=-1)
             {
                temp=b[t3]-b[t1];
                if(temp>=0&&a[temp]==-1)continue;
                temp+=n;
                if(temp>=0&&a[temp]==-1)continue;
                temp=b[t3]-b[t1]-1;
                if(temp>=0&&a[temp]==-1)continue;
                temp+=n;
                if(temp>=0&&a[temp]==-1)continue;
                return 0;
             }
             if (b[t2]!=-1 && b[t3]!=-1)
             {
                temp=b[t3]-b[t2];
                if(temp>=0&&a[temp]==-1)continue;
                temp+=n;
                if(temp>=0&&a[temp]==-1)continue;
                temp=b[t3]-b[t2]-1;
                if(temp>=0&&a[temp]==-1)continue;
                temp+=n;
                if(temp>=0&&a[temp]==-1)continue;
                return 0;
             }
         }
         return 1;
    }
    void DFS(int k)
    {
         if(k>n)
         {
            if (Judge()) goal=1;
            return;
         }
         for(int i=n-1;i>=0;--i)
           if(a[i]==-1)
            {
                a[i]=c[k];
                b[c[k]]=i;
                if(Cleck()) DFS(k+1);
                if(goal) return;
                a[i]=-1;
                b[c[k]]=-1;
             }
    }
    int main()
    {
        scanf("%d",&n);
        scanf("%s",s[1]);
        scanf("%s",s[2]);
        scanf("%s",s[3]);
        memset(a,255,sizeof(a));
        for(int i=n-1;i>=0;i--)
          for(int j=1;j<=3;j++)
            if (b[s[j][i]-'A']==0)
            {
                b[s[j][i]-'A']=-1;
                c[++now]=s[j][i]-'A';
            }
        DFS(1);
        for(int i=0;i<n;i++)
          printf("%d ",b[i]);
        return 0;
    }
    

    信息

    ID
    1089
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者