题解

139 条题解

  • 5
    @ 2017-05-08 07:53:25

    抄的算法竞赛宝典的题解

    /*
    可以采用一些比较高级的算法,比如解方程之类的,不过通常的
    算法是搜索,这个程序也采用搜索的方法 
    搜索思路:
    1.算式存储方式:A[i][j]表示第j个(从0开始计数)字符串从右往
    左数第i个(从0开始计数)字母 
      如样例:ABCED    对应存储于这些元素中 A[4,3,2,1,0][0]
             BDACE                         A[4,3,2,1,0][1]
             EBBAA                         A[4,3,2,1,0][2]
      如此存储,是因为搜索是一位一位进行枚举的,即每次确定
      同一列的字母,如第一次确定A[0][0],A[0][1],A[0][2]三个
      字母
    2.A[i][2]=(A[i][0]+A[i][1]+u)%n
      对每一位枚举前两个字母可能对应的数字。如果在之前的搜索
      中字母已经被确定,那此次不需再枚举。若未被确定,则需要
      选择一个数字。 
      当前两个字母确定下来时,第三个字母即得到确定,只需判断
      这个结果是否合法(是否同一个字母对应两个数字,或者同一
      个数字被多个字母使用) 
      其中u表示第i-1位的进位,如果从低位向高位搜索(即从右向
      左),那么每一次的进位都是确定的
    3.剪枝:
      1)每个数字只能被一个字母使用,那么给每个数字做上标记,
      避免被重复使用。
      2)如果最高位出现进位,则等式不成立
      3)如果第三个字母对应的数字已经确定,但是并不是前两个
      字母计算后的结果,那等式不成立
      4)如果前两个字母计算后的结果已经被使用,并且不是被第
      三个字母使用,那等式不成立
      5)如果第三个字母未被确定,那么这一位确定下来后,可能
      会对后面的算式造成影响,甚至直接造成矛盾,后者可以直
      接剪掉 
        直接依次枚举之后的每一位 
        a)如果一个数字不确定,那可以通过另外两个数字计算出
        这个数字,如果这个数字被使用,那等式不成立
          (注意进位,如果进位已经确定则直接计算判断即可,
          否则是否进位两种情况都不成立等式才不成立)
        b)如果三个数字都确定了,那需要计算一下该位等式是否
        成立 
    */
    #include <cstdio>
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    
    int n;
    char in[3][30];//存储读入的字符串 
    int A[30][3];//存储算式 
    //标记每个数字是否被使用,1表示被使用,0表示未被使用 
    bool use[30];
    //记录每个字母对应的数字,-1表示未确定
    int num[30]; 
    void Search(int,bool);
    #define RETURN {num[x]=-1;use[c]=0;return;}//宏定义 还原+返回操作 
    
    //处理第p位第q个数字,前两个数字存储在a中,上一位的进位为u 
    void Search2(int p,int q,int a[2],bool u)
    {
      int x=A[p][q];
      if(q==2)
      {
        if(p==n-1 && a[0]+a[1]+u>=n) 
          return;//剪枝2 
        int c=(a[0]+a[1]+u)%n,i,j;
        if(num[x]!=-1 && num[x]!=c) 
          return;//剪枝3 
        if(use[c] && num[x]!=c) 
          return;//剪枝4 
        if(num[x]==-1) 
        {
          num[x]=c;
          use[c]=1;
          int up=(a[0]+a[1]+u)/n;
          for(i=p+1;i<n;i++)//剪枝5) 
          {
            int k1=num[A[i][0]],k2=num[A[i][1]],k3=num[A[i][2]];
            if(k1==-1 || k2==-1 || k3==-1)//a)其中up为进位,若up==-1表示进位不确定 
            {
              if(k1!=-1 && k2!=-1 && ((up==-1 && use[(k1+k2)%n] && use[(k1+k2+1)%n])||(up!=-1 && use[(k1+k2+up)%n])))
                RETURN
              else if(k1!=-1 && k3!=-1 && ((up==-1 && use[(k3+2*n-k1)%n] && use[(k3+2*n-1-k1)%n])||(up!=-1 && use[(k3+2*n-up-k1)%n])))
                RETURN
              else if(k2!=-1 && k3!=-1 && ((up==-1 && use[(k3+2*n-k2)%n] && use[(k3+2*n-1-k2)%n])||(up!=-1 && use[(k3+2*n-up-k2)%n])))
                RETURN
              else up=-1;//有两个以上数不确定的情况下,进位也不确定 
            }
            else if((up==-1 && (k1+k2)%n!=k3 && (k1+k2+1)%n!=k3)||(up!=-1 && (k1+k2+up)%n!=k3))//b)
              RETURN
            else if(i==n-1&&((up==-1&&(k1+k2)/n!=0&&(k1+k2+1)/n!=0)||(up!=-1&&(k1+k2+up)/n!=0)))//剪枝2) 
              RETURN
            else up=((k1+k2)>k3);//三个数都确定的情况下要计算进位 
          }
          Search(p+1,(a[0]+a[1]+u)/n);//递归处理下一位 
          num[x]=-1;
          use[c]=0;
        }
        else
          Search(p+1,(a[0]+a[1]+u)/n);
        return;
      }
        
      if(num[x]==-1)//如果字母未被确定 
      {
        for(int i=n-1;i>=0;i--)//倒着取数,避免一些特殊数据 
        {
          if(use[i]==0)//剪枝1 
          {
            num[x]=i;
            use[i]=1;
            a[q]=i;//确定下来的数字作为参数传递下去,更方便 
            Search2(p,q+1,a,u);
            num[x]=-1;
            use[i]=0;
          }
        }
      }
      else//如果字母在之前的搜索已经被确定 
      {
        a[q]=num[x];
        Search2(p,q+1,a,u);
      }
    }
    
    void Search(int p,bool u)//处理第p位,上一位进位为u 
    {
      if(p>=n)//如果出结果了 
      {
        int i;
        for(i=0;i<n-1;i++)
          cout<<num[i]<<' ';cout<<num[i];
        cout<<endl;
        exit(0);//输出后直接结束程序,节约返回的时间 
      }
      int a[2];
      Search2(p,0,a,u);
    }
    
    int main()
    {
      for(int i=0;i<30;i++)//初始时所有的字母、数字均未定 
        num[i]=-1,use[i]=0;
        
      cin>>n>>in[0]>>in[1]>>in[2];
      for(int i=0;i<n;i++)//将字符串按预定规则预处理至A数组中 
        for(int j=0;j<3;j++)
          A[n-1-i][j]=in[j][i]-'A';
            
      Search(0,0);//从最低位开始搜索,此时没有进位 
      //cout<<"NO"<<endl;//题目保证有且只有一组解 
      return 0;
    }
    
    
  • 1
    @ 2020-03-01 12:13:13
    //c++题解
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<string>
    #include<cstdlib>
    using namespace std;
    char a[30],b[30],c[30];
    int t[300],used[30],p[30],u[30],y;
    int n;
    bool ok_(){
        for(int i=n;i>=1;i--){
            if(t[a[i]]==-1||t[b[i]]==-1||t[c[i]]==-1)continue;
            if((t[a[i]]+t[b[i]])%n!=t[c[i]]){
                if((t[a[i]]+t[b[i]]+1)%n!=t[c[i]])return 0;
            }
        }
        return 1;
    }
    void Try_(){
        int jw=0;
        for(int i=n;i>=1;i--){
            int s=t[a[i]]+t[b[i]]+jw;
            if(t[c[i]]!=s%n)return ;
            jw=s/n;
        }
        cout<<t['A'];
        for(int i='A'+1;i<='A'+n-1;i++)cout<<' '<<t[i];
        exit(0);
    }
    void dfs(int now){
        //产生0到n-1的全排列 
        if(now>n){
            Try_();
            return ;
        }
        for(int i=n-1;i>=0;i--){
            if(used[i])continue;
            t[p[now]+'A'-1]=i;
            if(ok_()){
                used[i]=1;
                dfs(now+1);
                used[i]=0;
            }
        }
        t[p[now]+'A'-1]=-1;
    }
    int main(){
        memset(t,-1,sizeof(t));
        scanf("%d",&n);
        scanf("%s%s%s",a+1,b+1,c+1);
        for(int i=n;i>=1;i--){
            if(!u[a[i]-'A'+1])p[++y]=a[i]-'A'+1,u[a[i]-'A'+1]=1;
            if(!u[b[i]-'A'+1])p[++y]=b[i]-'A'+1,u[b[i]-'A'+1]=1;
            if(!u[c[i]-'A'+1])p[++y]=c[i]-'A'+1,u[c[i]-'A'+1]=1;
        }
        dfs(1);
        return 0;
    }
    
  • 1
    @ 2017-08-24 11:20:02

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int res[26];
    int used[26];
    string a,b,c;
    int flag = 0;
    char pos[26];
    int usedZiMu[26];
    int Check()
    {
    int i;
    for (i=n-1;i>=0;i--)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';
    if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)
    {
    if( (res[a1]+res[b1])%n!=res[c1] &&(res[a1]+res[b1]+1)%n!=res[c1])
    return 0;
    }
    if(res[a1]!=-1 && res[b1]!=-1 && res[c1]==-1)
    {
    int sum1,sum2;
    sum1 = (res[a1]+res[b1])%n;
    sum2 = (res[a1]+res[b1]+1)%n;
    if (used[sum1] && used[sum2])
    return 0;
    }
    if (res[a1]!=-1 && res[b1]==-1 && res[c1]!=-1)
    {
    int js1,js2;
    js1 = (res[c1]-res[a1]+n)%n;
    js2 = (res[c1]-res[a1]-1+n)%n;
    if (used[js1] && used[js2])
    return 0;
    }
    if (res[a1]==-1 && res[b1]!=-1 && res[c1]!=-1)
    {
    int js1,js2;
    js1 = (res[c1]-res[b1]+n)%n;
    js2 = (res[c1]-res[b1]-1+n)%n;
    if (used[js1] && used[js2])
    return 0;
    }

    }
    return 1;
    }
    int OK()
    {
    int i;
    int jinwei=0;
    int jiahe;
    for (i=n-1; i>=0; i--)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';

    jiahe = (res[a1]+res[b1]+jinwei)%n;
    jinwei =( res[a1]+res[b1]+jinwei)/n;
    if (jiahe!=res[c1]) return 0;
    }
    if (jinwei>0) return 0;
    return 1;
    }
    void dfs(int k)
    {
    int i;
    if (flag)
    return;
    if(k==n)
    {
    if (OK())
    {
    for(i=0; i<=n-2; i++) cout<<res[i]<<' ';
    cout<<res[n-1]<<endl;
    flag=1;
    }
    return ;
    }
    for (i=n-1; i>=0; i--)
    {
    if (!used[i]&&Check() )
    {
    used[i]=1;
    res[pos[k]]=i;
    dfs(k+1);
    used[i]=0;
    res[pos[k]]=-1;
    }
    }
    return ;
    }

    int main()
    {
    int k=0,i;
    cin>>n;
    cin>>a>>b>>c;
    memset(res,-1,sizeof(res));
    memset(pos,-1,sizeof(pos));
    for (i=n-1; i>=0; i--)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';
    if (!usedZiMu[a1])
    {
    usedZiMu[a1]=1;
    pos[k++] = a1;
    }
    if (!usedZiMu[b1])
    {
    usedZiMu[b1]=1;
    pos[k++] = b1;
    }
    if (!usedZiMu[c1])
    {
    usedZiMu[c1]=1;
    pos[k++] = c1;
    }
    }
    dfs(0);
    return 0;
    }

  • 0
    @ 2020-04-30 16:58:56

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define maxn 30
    int a[maxn],b[maxn],c[maxn];
    int num[maxn],Next[maxn],n,cnt;
    char s1[maxn],s2[maxn],s3[maxn];
    bool used[maxn];
    bool Judge() {
    for(int i=n-1,x=0;i>=0;i--) {
    int A=num[a[i]],B=num[b[i]],C=num[c[i]];
    if((A+B+x)%n!=C) return false;
    x=(A+B+x)/n;
    }
    return true;
    }
    bool CanPrune() {//prune: 剪枝—百度翻译。
    if(num[a[0]]+num[b[0]]>=n)
    return true;
    for(int i=n-1;i>=0;i--) {
    int A=num[a[i]],B=num[b[i]],C=num[c[i]];
    if(A==-1||B==-1||C==-1) continue;
    if((A+B)%n!=C&&(A+B+1)%n!=C)
    return true;
    }
    return false;
    }
    void Print() {
    for(int i=0;i<n;i++)
    printf("%d ",num[i]);
    exit(0);
    }
    void dfs(int x) {
    if(CanPrune()==true) return;
    if(x==n) {
    if(Judge()==true) Print();
    return;
    }
    for(int i=n-1;i>=0;i--)
    if(used[i]==false) {
    num[Next[x]]=i;
    used[i]=true;
    dfs(x+1);
    num[Next[x]]=-1;
    used[i]=false;
    }
    return;
    }
    inline int id(char c) {
    return c-'A';
    }
    void GetNext(int x) {
    if(used[x]==false) {
    used[x]=true;
    Next[cnt++]=x;
    }
    return;
    }
    int main() {
    scanf("%d",&n);
    scanf("%s%s%s",s1,s2,s3);
    for(int i=0;i<n;i++) {
    a[i]=id(s1[i]);
    b[i]=id(s2[i]);
    c[i]=id(s3[i]);
    num[i]=-1;
    }
    for(int i=n-1;i>=0;i--) {
    GetNext(a[i]);
    GetNext(b[i]);
    GetNext(c[i]);
    }
    for(int i=0;i<n;i++) used[i]=false;
    dfs(0);
    return 0;
    }
    代码看不懂也可以问我qwq

  • 0
    @ 2017-10-31 20:15:39

    一道大搜索,剪枝会比较多

    #include<iostream>
    #include<stdlib.h>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int n;
    char a[4][28];
    int num[27],shu[4][28],jin[27],zimu[27];
    void dfs(int now,int wei)
    {
        int i;
        if(num[shu[1][1]]>=0&&num[shu[2][1]]>=0)
         if(num[shu[1][1]]+num[shu[2][1]]>=n) //首位不能有进位
          return ;
        for(i=1;i<=n;i++) //不加此处判断9号点TLE
        {
            if(num[shu[1][i]]>=0&&num[shu[2][i]]>=0&&num[shu[3][i]]>=0)
                if((num[shu[1][i]]+num[shu[2][i]])%n!=num[shu[3][i]]&&(num[shu[1][i]]+num[shu[2][i]]+1)%n!=num[shu[3][i]])//进位最多为1
                 return ;
        }
        if(now==0)
        {
            for(i=0;i<n;i++)
             cout<<num[i]<<" ";
            exit(0);
        }
        if(wei==1)//分别处理加数,和
        {
        if(num[shu[wei][now]]<0)
         for(i=0;i<n;i++)
         {
            if(zimu[i]<0)
            {
                zimu[i]=shu[wei][now];
                num[shu[wei][now]]=i;
                dfs(now,2);
                zimu[i]=-1;
                num[shu[wei][now]]=-1;
            }
         }
        else
         dfs(now,2);
        }
        if(wei==2)
        {
        if(num[shu[wei][now]]<0)
         for(i=0;i<n;i++)
         {
            if(zimu[i]<0)
            {
                zimu[i]=shu[wei][now];
                num[shu[wei][now]]=i;
                dfs(now,3);
                zimu[i]=-1;
                num[shu[wei][now]]=-1;
            }
         }
        else
         dfs(now,3);
        }
        if(wei==3)
        {
            if(num[shu[wei][now]]<0)
            {
                int temp=num[shu[1][now]]+num[shu[2][now]]+jin[now+1];//快速出和
                 if(zimu[temp%n]>=0)//该和已被用
                  return ;
                 else
                 {
                    jin[now]=temp/n;
                    num[shu[wei][now]]=temp%n;
                    zimu[temp%n]=shu[wei][now];
                    dfs(now-1,1);
                    num[shu[wei][now]]=-1;
                    zimu[temp%n]=-1;
                 }
            }
            else
             if((num[shu[1][now]]+num[shu[2][now]]+jin[now+1])%n==num[shu[3][now]])
             {
              jin[now]=(num[shu[1][now]]+num[shu[2][now]]+jin[now+1])/n;//维护进位
              dfs(now-1,1);
             }
        }
    }
    
    int main()
    {
        memset(zimu,-1,sizeof(zimu));
        memset(shu,-1,sizeof(shu));
        memset(num,-1,sizeof(num));
        int i,k;
        cin>>n;
        cin>>a[1]>>a[2]>>a[3];
        for(k=1;k<=3;k++)
         for(i=0;i<n;i++)
          shu[k][i+1]=a[k][i]-'A';
        dfs(n,1);//搜索
        return 0;
    }
    
  • 0
    @ 2017-08-24 11:36:14

    /include <StdAfx.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <string>
    #include <iostream>
    #include <cstring>
    using namespace std;

    int n;//读入几进制0.1.2.3...n-1
    int res[26];//保存A.B..Z代表的数字
    int used[26];//保存这个对应数字是否被用,因为题目说每个字母只能代表一个数
    string a,b,c;//保存加数1,加数2,和
    int flag = 0;//是否已找到符合条件的唯一解//加上这个多对了2个点//
    //-----最多只能7个点了,原先是从abcd..填字母,改变
    char pos[26];//保存从右往左,从上往下的字母出现顺序,判断的时候也按这个顺序判断
    int usedZiMu[26];//保存该字母是否已经出现

    //剪枝优化函数,来判断当前的字母的数字取法是否可行
    //题目就是一个可行与否的问题
    int Check()
    {
    int i;
    //看是否满足 a+b==c
    for (i=n-1;i>=0;i--)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
    if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)//3个数都知道-----3个点
    {
    if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
    (res[a1]+res[b1]+1)%n!=res[c1])//有进位
    return 0;
    }
    //加上后面这些多对了1个点
    if(res[a1]!=-1 && res[b1]!=-1 && res[c1]==-1)//如果只知道其中2个
    {
    int sum1,sum2;//sum1无进位,sum2有进位
    sum1 = (res[a1]+res[b1])%n;
    sum2 = (res[a1]+res[b1]+1)%n;
    if (used[sum1] && used[sum2])//可能填在c1的数都用了肯定不行
    return 0;
    }
    if (res[a1]!=-1 && res[b1]==-1 && res[c1]!=-1)//和与一个加数知道
    {
    int js1,js2;//js1无进位,js2有进位
    js1 = (res[c1]-res[a1]+n)%n;
    js2 = (res[c1]-res[a1]-1+n)%n;
    if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
    return 0;
    }
    if (res[a1]==-1 && res[b1]!=-1 && res[c1]!=-1)//和与一个加数知道
    {
    int js1,js2;//js1无进位,js2有进位
    js1 = (res[c1]-res[b1]+n)%n;
    js2 = (res[c1]-res[b1]-1+n)%n;
    if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
    return 0;
    }

    }
    return 1;
    }
    /*剪枝策略只这样写,数据只过3个点
    int Check()
    {
    int i;
    //看是否满足 a+b==c
    for (i=0;i<=n-1;i++)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
    if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)
    {
    if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
    (res[a1]+res[b1]+1)%n!=res[c1])//有进位
    return 0;
    }

    }
    return 1;
    }
    */
    //严格判断当前所有字母的填数满足等式否
    int OK()
    {
    int i;
    int jinwei=0;
    int jiahe;
    for (i=n-1; i>=0; i--)
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';

    jiahe = (res[a1]+res[b1]+jinwei)%n;//计算和
    jinwei =( res[a1]+res[b1]+jinwei)/n;//计算进位
    if (jiahe!=res[c1]) return 0;
    }
    if (jinwei>0) return 0;
    return 1;
    }
    void dfs(int k)//深搜,利用系统的堆栈枚举
    {
    int i;
    if (flag) return ;//已找到解
    if (!Check()) return;//现在的方法不合理--从if (!used[i]&&Check())移到这里多了1个点共7个了
    if(k==n)//找到可行解且唯一(题目得知),输出
    {
    if (OK())//如果当前所有字母填数满足等式则输出
    {
    for(i=0; i<=n-2; i++) cout<<res[i]<<' ';
    cout<<res[n-1]<<endl;
    flag=1;
    }
    return ;
    }
    //在第k层,也就是第k个字母所可能取得数为0...n-1中未用值枚举
    for (i=n-1; i>=0; i--)
    {
    //如果i还没被占用,且满足剪枝条件,则进行下层遍历
    if (!used[i] )
    {
    used[i]=1;//i被占用
    res[pos[k]]=i;//第k个字母取数字i
    dfs(k+1);
    used[i]=0;//i被释放,可以被其他字母占用
    res[pos[k]]=-1;//第k个字母释放
    }
    }
    return ;
    }

    int main()
    {
    int k=0,i;
    //读入数据
    cin>>n;
    cin>>a>>b>>c;
    memset(res,-1,sizeof(res));
    memset(pos,-1,sizeof(pos));
    //初始化
    for (i=n-1; i>=0; i--)//从右向左
    {
    char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//全部转成对应数字下标
    if (!usedZiMu[a1]) ///从上往下
    {
    usedZiMu[a1]=1;
    pos[k++] = a1;
    }
    if (!usedZiMu[b1])
    {
    usedZiMu[b1]=1;
    pos[k++] = b1;
    }
    if (!usedZiMu[c1])
    {
    usedZiMu[c1]=1;
    pos[k++] = c1;
    }
    }
    dfs(0);
    return 0;
    }

  • 0
    @ 2017-07-16 21:34:52

    这个程序在洛谷上会 TLE 一个点,不过在这就过了。
    我是从三个数最低位开始dfs,要是可以判断出来(即三个数中两个已经确定)就马上判断出来。
    有一个地方还可以优化,就是枚举位置位上的数时,从 n-1 枚举到 0 会比从 0n-1 更快(快非常多)。

    #include <cstdio>
    #define A(xx,yy) (f[a[xx][yy]]-1)
    int f[30],a[3][30],g[30],jw[30],n,ok,boo;
    char ch;
    void dfs(int x,int y){
        if (ok) return;
        if (y==0){
            if (A(0,1)+A(1,1)+jw[2]==A(2,1)){
                for (int i=0; i<n; i++) printf("%d ",f[i]-1);
                ok=1;
            }
            return;
        }
        if (x<2){
            int k=1-x;
            if (!f[a[x][y]]){
                if (f[a[k][y]] && f[a[2][y]]){
                    if (!g[(A(2,y)-A(k,y)-jw[y+1]+n)%n]){
                        f[a[x][y]]=(A(2,y)-A(k,y)-jw[y+1]+n)%n+1;
                        g[A(x,y)]=1;
                        dfs(x+1,y);
                        if (ok) return;
                        g[A(x,y)]=0;
                        f[a[x][y]]=0;
                    }
                    return;
                }
                for (int i=n-1; i>=0; i--) if (!g[i]){
                    f[a[x][y]]=i+1;
                    g[A(x,y)]=1;
                    dfs(x+1,y);
                    g[A(x,y)]=0;
                    f[a[x][y]]=0;
                }
                return;
            }
            dfs(x+1,y);
            return;
        }
        if (x==2){
            if (!f[a[x][y]]){
                f[a[x][y]]=(A(0,y)+A(1,y)+jw[y+1])%n+1;
                if (!g[A(x,y)]){
                    g[A(x,y)]=1;
                    jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
                    dfs(0,y-1);
                    g[A(x,y)]=0;
                }
                f[a[x][y]]=0;
                return;
            }
            if ((A(0,y)+A(1,y)+jw[y+1])%n==A(2,y)){
                jw[y]=(jw[y+1]+A(0,y)+A(1,y))/n;
                dfs(0,y-1);
            }
            return;
        }
    }
    int main(){
        scanf("%d",&n);
        for (int i=0; i<3; i++){
            while (ch<'A' || ch>'Z') ch=getchar();
            for (int j=1; j<=n; j++) a[i][j]=ch-'A',ch=getchar();
        }
        dfs(0,n);
    }
    
  • 0
    @ 2016-12-17 13:18:56

    这个才是正确答案

  • 0
    @ 2016-12-17 13:17:16
    
    
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    bool vis[100];
    char b[100][100];
    int a[100],c[100]; 
    int n;
    void print()
    {
        int i;
        for (i=65;i<65+n;i++) printf("%d ",a[i]);
        printf("\n");
        return ; 
    } 
    
    bool judge1()
    {
        int i;
        for (i=n;i>0;i--)
            if (a[b[i][1]]!=-1 &&  a[b[i][2]]!=-1&& a[b[i][3]]!=-1  &&
               (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
               (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
        return 1; 
    } 
    
    bool judge2()
    {
        int i,k=0;
        for (i=n;i>1;i--){
            k=a[b[i][1]]+a[b[i][2]]+k;
            if (a[b[i][3]]!=k % n) return false;
            k/=n;  
        }    
        return true; 
    } 
    void DFS(int m)
    {
        int i;
        if (!judge1()) return ; 
        if (a[b[1][1]]+a[b[1][2]]>=n) return ;
        if (m>n){
            if(judge2()){print(); exit(0);}
            else return ;
        }
        else{
            for (i=n-1;i>=0;i--){
                if (vis[i]) {
                    a[c[m]]=i;
                    vis[i]=0;
                    DFS(m+1);
                    a[c[m]]=-1;
                    vis[i]=1;    
                }     
            }
        }
    }
    int main()
    {
        int k=1;
        bool h[100];
        memset(h,1,sizeof(h)); 
        memset(vis,1,sizeof(vis)); 
        memset(a,-1,sizeof(a)); 
        scanf("%d",&n);
        for (int j=1;j<4;j++) 
            for (int i=1;i<=n;i++) { 
               cin>>b[i][j]; 
            }
        for (int i=n;i>0;i--)
            for (int j=1;j<4;j++)
            if (h[b[i][j]]) {
                    c[k++]=b[i][j];
                    h[b[i][j]]=0;
                } 
        DFS(1);
       // system ("PAUSE");
        return 0;
    }
     
    
    
    用户信息
    
    
    ZGZZN
    
    
    
    
     
    
    题目操作
    
     查看 P1099
     查看本题题解
     查看本题递交记录
     
    
    我的记录
    
    
    
    
    
    
    
    12-17
    
    Accepted
    ​
     
    
    
    
    
  • 0
    @ 2016-10-27 21:09:52

    三个剪枝
    1)首先是搜索顺序是按3排字母从右往左的出现顺序(感觉类似靶形数独)
    2)其次当一列的3个数都算出来时判断是否合法即(a+b)%n==c||(a+b+1)%n==c
    3)给字母赋值时从大到小,因为搜索顺序是从右到左,大的值一定靠后,否则在最高位a+b可能造成进位,但a,b,c是等长的
    ```
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    int n,X[5][30],let[30],vis[30]={0},q[30]={0};
    bool check(){
    int i,j,tmp[5][30]={0};
    for(i=1;i<=3;i++){
    for(j=0;j<n;j++){
    tmp[i][j]=let[X[i][j]];
    }

    }
    int k=0,re[30]={0};
    for(i=n-1;i>=0;i--){
    re[i]=tmp[1][i]+tmp[2][i]+k;k=0;
    k=re[i]/n;
    re[i]=re[i]%n;
    }
    if(memcmp(re,tmp[3],sizeof(re))==0) return true;
    else return false;
    }
    bool checkcheck(){
    int i;
    for(i=n-1;i>=0;i--){
    int x=X[1][i],y=X[2][i],z=X[3][i];
    if(let[x]!=-1&&let[y]!=-1&&let[z]!=-1){
    int flag=0;
    if((let[x]+let[y])%n==let[z]) flag=1;
    if((let[x]+let[y]+1)%n==let[z]) flag=1;
    if(!flag) return false;
    }
    }
    return true;
    }
    void dfs(int step){
    int i;
    if(step==n){
    if(check()){
    for(i=0;i<n-1;i++){
    printf("%d ",let[i]);
    }
    printf("%d",let[n-1]);
    exit(0);
    }
    }
    if(!checkcheck()) return; //**剪枝2)**
    for(i=n-1;i>=0;i--){ //**剪枝3)**
    if(!vis[i]){
    let[q[step]]=i;
    vis[i]=1;
    dfs(step+1);
    vis[i]=0;
    let[q[step]]=-1;
    }
    }
    }
    int main(){
    freopen("in.txt","r",stdin);
    int i,j,book[30]={0};
    char ch;
    scanf("%d",&n);
    ch=getchar();
    for(i=1;i<=3;i++){
    for(j=0;j<n;j++){
    scanf("%c",&ch);
    X[i][j]=ch-'A';
    }
    ch=getchar();
    }
    int top=0;
    for(i=n-1;i>=0;i--){
    int x=X[1][i],y=X[2][i],z=X[3][i];
    if(!book[x]){
    q[top++]=x;book[x]=1;
    }
    if(!book[y]){
    q[top++]=y;book[y]=1;
    }
    if(!book[z]){
    q[top++]=z;book[z]=1;
    }
    } //**剪枝1)**
    memset(let,-1,sizeof(let));
    dfs(0);
    return 0;
    }
    ```
    100ms

  • 0
    @ 2016-09-04 16:49:50

    测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 576 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 576 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    Accepted, time = 30 ms, mem = 580 KiB, score = 100
    五个剪枝成就未来

  • 0
    @ 2016-08-27 16:14:11

    各种奇迹淫巧+cheat总算A了这个神题。。
    PS:倒着枚举待放数字快纯属因为两个大数据点为0 1 2 3 4 ..
    代码,太丑就不贴了。。

  • 0
    @ 2016-08-26 08:57:03

    测试数据 #0: TimeLimitExceeded, time = 1203 ms, mem = 580 KiB, score = 0
    测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #3: Accepted, time = 156 ms, mem = 572 KiB, score = 10
    测试数据 #4: TimeLimitExceeded, time = 1203 ms, mem = 576 KiB, score = 0
    测试数据 #5: TimeLimitExceeded, time = 1203 ms, mem = 576 KiB, score = 0
    测试数据 #6: TimeLimitExceeded, time = 1187 ms, mem = 576 KiB, score = 0
    测试数据 #7: TimeLimitExceeded, time = 1203 ms, mem = 572 KiB, score = 0
    测试数据 #8: TimeLimitExceeded, time = 1015 ms, mem = 576 KiB, score = 0
    测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    TimeLimitExceeded, time = 7170 ms, mem = 580 KiB, score = 40
    有点懵逼了。

  • 0
    @ 2015-07-17 15:23:15

    让你的搜索顺序顺应你的剪枝,将剪枝最优化。
    var a:array['A'..'Z'] of longint;
    i:char;
    B:ARRAY[1..100] OF CHAR;
    n,j,k,l:longint;
    S1,S2,S3:STRING;
    P:ARRAY[0..30] OF BOOLEAN;
    PP:ARRAY['A'..'Z'] OF BOOLEAN;
    PROCEDURE FIND(Y,X:LONGINT);
    VAR R,O:LONGINT;
    PPP:BOOLEAN;
    PROCEDURE SUAN;
    VAR R,O:LONGINT;
    I:CHAR;
    X,Y,Z:INT64;
    L1,L2,L3:STRING;
    BEGIN
    L1:=S1; L2:=S2; L3:=S3; O:=0;
    FOR R:=N DOWNTO 1 DO
    BEGIN
    X:=A[S1[R]];
    Y:=A[S2[R]];
    X:=X+Y+O;
    O:=0;
    IF X>=N THEN BEGIN O:=1; X:=X-N; END;
    IF X<>A[S3[R]] THEN EXIT;
    END;
    FOR I:='A' TO CHR(64+N) DO
    WRITE(A[I],' ');
    HALT;
    END;
    BEGIN
    IF ( ( (A[S1[1]]>A[S3[1]]) OR (A[S2[1]]>A[S3[1]]) ) AND(A[S3[1]]<>-1) )OR(A[S2[1]]+A[S1[1]]>=N)OR(A[S1[1]]=N-1)OR(A[S2[1]]=N-1)
    THEN EXIT;
    IF (A[S1[1]]<>-1)AND(A[S2[1]]<>-1)AND(A[S3[1]]<>-1)AND(A[S1[1]]+A[S2[1]]<>A[S3[1]])AND(A[S1[1]]+A[S2[1]]<>A[S3[1]]-1) THEN EXIT;
    FOR R:=2 TO N DO
    IF (A[S1[R]]<>-1)AND(A[S2[R]]<>-1)AND(A[S3[R]]<>-1) THEN
    IF (A[S1[R]]+A[S2[R]]<>A[S3[R]]-1)AND(A[S1[R]]+A[S2[R]]<>A[S3[R]])AND(A[S1[R]]+A[S2[R]]<>A[S3[R]]+N)AND(A[S1[R]]+A[S2[R]]<>A[S3[R]]+N-1) THEN EXIT;
    IF X=N+1 THEN BEGIN SUAN; EXIT; END;
    FOR R:=N-1 DOWNTO 0 DO
    IF P[R] THEN
    BEGIN
    A[CHR(Y)]:=R;
    P[R]:=FALSE;
    INC(K);
    FIND(ORD(B[K]),X+1);
    DEC(K);
    P[R]:=TRUE;
    A[CHR(Y)]:=-1;
    END;
    END;
    begin
    FILLCHAR(PP,SIZEOF(PP),TRUE);
    FILLCHAR(P,SIZEOF(P),TRUE);
    READLN(N);
    READLN(S1);
    READLN(S2);
    READLN(S3); K:=0;
    FOR J:=N DOWNTO 1 DO
    BEGIN
    IF PP[S1[J]] THEN BEGIN
    INC(K);
    B[K]:=S1[J]; PP[S1[J]]:=FALSE;
    END;
    IF PP[S2[J]] THEN BEGIN
    INC(K);
    B[K]:=S2[J]; PP[S2[J]]:=FALSE;
    END;
    IF PP[S3[J]] THEN BEGIN
    INC(K);
    B[K]:=S3[J]; PP[S3[J]]:=FALSE;
    END;
    END; K:=1;
    FOR I:='A' TO CHR(64+N) DO
    A[I]:=-1;
    PP[S1[N]]:=FALSE;
    FIND(ORD(B[K]),1);
    end.

  • 0
    @ 2015-04-14 16:50:52

    我表示不愿意挖坟,但是为了以后来刷这道ws的搜索题的童鞋能更快地过掉,我再总结一下这题的几个强力剪枝吧(也是本人所用的剪枝):
    1、从算式的右侧到左侧、从上到下(从下到上会更快),一列一列地枚举待搜索的字符;
    2、枚举未知字符对应的数字时要从大到小搜;
    3、枚举出任意一个未知字符对应的数字之后,判断一下这一列数的合法性——
    比如说对于某一列数:
     ?1
    +?A <-显然这里A除了取3或4之外没有其他可能
    =?5
    4、同上,应该也判断一下其他列的合法性
    比如:
     ?9
    +?7
    =?A <-假设刚刚确定了7,那么这里A只可能取6或7,如果这两个数字都已经被其他字符选用了,那也是无解的

    第3、4个剪枝很强大,因为本人的程序在没加3、4优化时其他点0ms,第9个点(此乃神点)超时,百思不得其解……加了之后,30ms通过……
    当然,本人的程序是一列一列从上到下搜的,很多人总结出如果从下到上搜会有奇效,童鞋们可自己试试……

  • 0
    @ 2014-12-01 19:33:56

    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    bool u[26];
    char e[3][26];
    double a[26][26],b[26][26],c[26],t,x[26];
    int i,j,k,n,s;
    using namespace std;
    main()
    {
    cin>>n;
    gets(e[0]);
    gets(e[0]);
    gets(e[1]);
    gets(e[2]);
    for(i=0;i<n;i++)
    {
    b[i][i]=1;
    a[i][e[0][i]-'A']++;
    a[i][e[1][i]-'A']++;
    a[i][e[2][i]-'A']--;
    }
    for(i=0;i<n;i++)
    {
    for(j=i+1,k=i,t=a[i][i];j<n;j++)
    if(fabs(a[j][i])>fabs(t))
    {
    t=a[j][i];
    k=j;
    }
    if(k!=i)
    for(j=0;j<n;j++)
    {
    t=a[i][j];
    a[i][j]=a[k][j];
    a[k][j]=t;
    t=b[i][j];
    b[i][j]=b[k][j];
    b[k][j]=t;
    }
    if(fabs(a[i][i]-1)>1e-6)
    for(t=a[i][i],k=0;k<n;k++)
    {
    a[i][k]/=t;
    b[i][k]/=t;
    }
    for(j=i+1;j<n;j++)
    if(fabs(a[j][i])>1e-6)
    for(k=0,t=a[j][i];k<n;k++)
    {
    a[j][k]-=a[i][k]*t;
    b[j][k]-=b[i][k]*t;
    }
    }
    for(i=n-1;i>=0;i--)
    for(j=i-1;j>=0;j--)
    if(fabs(a[j][i])>1e-6)
    for(k=0,t=a[j][i],a[j][i]=0;k<n;k++)
    b[j][k]-=t*b[i][k];
    do
    {
    memset(c,0,sizeof(c));
    memset(u,0,sizeof(u));
    memset(x,0,sizeof(x));
    for(i=0;i<n-1;i++)
    if(s&1<<i)
    {
    c[i]--;
    c[i+1]+=n;
    }
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    if(fabs(b[i][j])>1e-6&&fabs(c[j])>1e-6)
    x[i]+=b[i][j]*c[j];
    if(fabs(x[i]-floor(x[i]+0.5))>1e-6||x[i]<-1e-6||x[i]-n+1>1e-6||u[int(x[i]+0.1)])
    break;
    u[int(x[i]+0.1)]=1;
    }
    }while(s++,i<n);
    for(i=0;i<n;i++)
    cout<<int(x[i]+0.1)<<' ';
    }

  • 0
    @ 2014-10-30 17:14:48

    var
    a:array['A'..'Z']of integer;
    b:array[1..26,1..3]of char;
    p:array['A'..'Z']of boolean;
    n,i,j,m:integer;
    r:array[1..26]of char;
    c:array[0..26]of boolean;
    procedure print;
    var
    i:integer;
    begin
    for i:=1 to n-1 do write(a[chr(64+i)],' ');
    writeln(a[chr(n+64)]);
    halt;
    end;

    function f:boolean;
    var
    i:integer;
    begin
    for i:=n downto 1 do
    if (a[b[i,1]]<>-1)and(a[b[i,2]]<>-1)and(a[b[i,3]]<>-1)
    and((a[b[i,1]]+a[b[i,2]])mod n<>a[b[i,3]])
    and((a[b[i,1]]+a[b[i,2]]+1)mod n<>a[b[i,3]])then
    begin
    f:=true;
    exit;
    end;
    f:=false;
    end;

    function pd:boolean;
    var
    i,j,z:integer;
    begin
    z:=0;
    for i:=n downto 2 do
    begin
    z:=z+a[b[i,1]]+a[b[i,2]];
    if z mod n<>a[b[i,3]]then begin pd:=false;exit;end;
    z:=z div n;
    end;
    z:=z+a[b[1,1]]+a[b[1,2]];
    if z<>a[b[1,3]]then begin pd:=false;exit;end;
    end;

    procedure so(m:integer);
    var
    i:integer;
    begin
    if f then exit;
    if a[b[1,1]]+a[b[1,2]]>=n then exit;
    if m>n then begin
    if pd then print;
    exit;
    end;
    for i:=n-1 downto 0 do
    if c[i]then begin
    a[r[m]]:=i;
    c[i]:=false;
    so(m+1);
    a[r[m]]:=-1;
    c[i]:=true;
    end;
    end;

    begin
    m:=0;
    readln(n);
    fillchar(c,sizeof(c),true);
    fillchar(p,sizeof(p),true);
    for i:=1 to n do
    a[chr(64+i)]:=-1;
    for j:=1 to 3 do
    begin
    for i:=1 to n do
    read(b[i,j]);
    readln;
    end;
    for i:=n downto 1 do
    for j:=1 to 3 do
    if p[b[i,j]] then
    begin
    inc(m);
    r[m]:=b[i,j];
    p[b[i,j]]:=false;
    end;
    so(1);
    end.

  • 0
    @ 2014-10-17 08:17:08

    本机过了在这RE时什么情况QAQ

  • 0
    @ 2014-04-25 20:11:05

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    bool vis[100];
    char b[100][100];
    int a[100],c[100];
    int n;
    void print()
    {
    int i;
    for (i=65;i<65+n;i++) printf("%d ",a[i]);
    printf("\n");
    return ;
    }

    bool judge1()
    {
    int i;
    for (i=n;i>0;i--)
    if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 &&
    (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
    (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
    return 1;
    }

    bool judge2()
    {
    int i,k=0;
    for (i=n;i>1;i--){
    k=a[b[i][1]]+a[b[i][2]]+k;
    if (a[b[i][3]]!=k % n) return false;
    k/=n;

    }

    return true;
    }
    void DFS(int m)
    {
    int i;
    if (!judge1()) return ;
    if (a[b[1][1]]+a[b[1][2]]>=n) return ;
    if (m>n){
    if(judge2()){print(); exit(0);}
    else return ;
    }
    else{
    for (i=n-1;i>=0;i--){
    if (vis[i]) {
    a[c[m]]=i;
    vis[i]=0;
    DFS(m+1);
    a[c[m]]=-1;
    vis[i]=1;

    }

    }
    }
    }
    int main()
    {
    int k=1;
    bool h[100];
    memset(h,1,sizeof(h));
    memset(vis,1,sizeof(vis));
    memset(a,-1,sizeof(a));
    scanf("%d",&n);
    for (int j=1;j<4;j++)
    for (int i=1;i<=n;i++) {
    cin>>b[i][j];
    }
    for (int i=n;i>0;i--)
    for (int j=1;j<4;j++)
    if (h[b[i][j]]) {
    c[k++]=b[i][j];
    h[b[i][j]]=0;
    }
    DFS(1);
    // system ("PAUSE");
    return 0;
    }

    • @ 2016-09-23 16:57:24

      真是帮了大忙啊,我看自己的代码怎么看都找不出错但是就是错的,之后看到了你的程序,发现我们的思路居然特别像!!!!比网上的那些题解都容易看懂!!!之后我经过不断的努力终于发现了自己的错误!!!好开心!!!顺便说一下这是我的第一道自己考虑思路的搜索题,感觉以后会在搜索上自信一点了。。。。。

  • 0
    @ 2013-09-16 11:50:36

    Accepted, time = 15 ms, mem = 824 KiB, score = 100
    倒着搜+一个剪枝

信息

ID
1099
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
4718
已通过
1010
通过率
21%
被复制
21
上传者