记录编号	451765	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	0.311 s
提交时间	2017-09-18 12:07:09	内存使用	0.31 MiB

#include<cstdio>
#include "cstdlib"
#include<map>
using namespace std;
 
int n;
inline void printing(char *x){ 
    for(int i=1;i<=n;i++)
        printf("%1d",x[i]);puts("");
}
char a[50],b[50],c[50];
int  d[50];
int num[50];
bool vis[50];
bool used[50];
map<int,int > mp;
 
inline int lowbit(int x){return x&(-x);}
inline bool Judging(int res){
    int x=0,t,p;
    for(int i=n;i;i--){
        if(vis[a[i]]){
            if(vis[b[i]]){
                if(vis[c[i]]){
                    t=num[a[i]]+num[b[i]];
                    if(t>=n)
                        t-=n;
                    if(t+1==n)
                        p=t+1-n;
                    else
                        p=t+1;
                    if(x==-1){
                        if(num[c[i]]!=t&&num[c[i]]!=p)
                            return false;
                        else
                            x=num[a[i]]+num[b[i]]>=n?1:-1;
                    }
                    else    {
              //          printf("tt");
                        if(num[c[i]]!=(x?p:t))
                            return false;
                        else
                            x=num[a[i]]+num[b[i]]+x>=n;
             //           printf("ss\n");
                    }
                }
                else{
                    t=num[a[i]]+num[b[i]];
                    if(t>=n)    t-=n;
                    p=t+1;p=p==n?0:p;
                    if(x==-1){
                        if(used[t]&&used[p])
                            return false;
                        else    
                            x=num[a[i]]+num[b[i]]>=n?1:num[a[i]]+num[b[i]]<n-1?0:-1;
                    }else{
                        if(used[x?p:t])
                            return false;
                        else    
                            x=num[a[i]]+num[b[i]]+x>=n;
                    }
                }
            }else{
                if(vis[c[i]]){//aY bN cY
                  //  printf("in");
                    t=num[c[i]]-num[a[i]];
                    if(t<0) t+=n;
                    p=t-1;
                    p=p<0?p+n:p;
             //       printf("t=%d p=%d\n",t,p);
                    if(x==-1){
                        if(used[t]&&used[p])
                            return false;
                    }else{
                        if(used[x?p:t])
                            return false;
                        else    
                            x=num[c[i]]<num[a[i]]+x;
                    }
               //     printf("out");
                }
                else{x=-1;continue;}
            }
        }else{
            if(vis[b[i]]&&vis[c[i]]){
                t=num[c[i]]-num[b[i]];
                t=t<0?t+n:t;
                p=t-1;
                p=p<0?p+n:p;
                if(x==-1){
                    if(used[t]&&used[p])
                        return false;            
                }else{
                    if(used[x?p:t])
                        return false;
                    else    
                        x=num[c[i]]<x+num[b[i]];
                }
            }
            else{ x=-1;continue;}
        }
    }
    return true;
}
inline void print(){
    for(int i=0;i<n;i++)
        printf("%d%c",num[i],i<n-1?' ':'\n');
  //  exit(0);
}
inline void dfs(int step,int res){
  //  printf("step=%d \n",step);
  //  print();
    if(!Judging(res))
    return ;
    if(step==n+1){
        print();
        exit(0);
    }    
 //   printf("step=%d \n",step);
 //   print();
    for(int i=res,j;i;i-=lowbit(i)){
        j=mp[lowbit(i)];
        used[j]=vis[d[step]]=true;
        num[d[step]]=j;
        dfs(step+1,res^(1<<j));
        num[d[step]]=-1;
        used[j]=vis[d[step]]=false;
    }
}
int main(){
    freopen("alpha.in","r",stdin);
    freopen("alpha.out","w",stdout);
    for(int i=0;i<=30;i++)
        mp[1<<i]=i;
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    bool Y[50]={0};
    scanf("%s",c+1);
    for(int i=n,j=1;i;i--){
        a[i]-='A',b[i]-='A';
        c[i]-='A';
        if(!Y[a[i]])
            d[j++]=a[i],Y[a[i]]=true;
        if(!Y[b[i]])
            d[j++]=b[i],Y[b[i]]=true;
        if(!Y[c[i]])
            d[j++]=c[i],Y[c[i]]=true;
        num[i-1]=-1;
    }
    /*printing(a);
    printing(b);
    printing(c);
    */
    for(int i=0;i<n;i++){
        used[i]=vis[d[1]]=true;
        num[d[1]]=i;
        //printf("i=%d\n",i);
        dfs(2,((1<<n)-1)^(1<<i));
        num[d[1]]=-1;
        used[i]=vis[d[1]]=false;
    }
    printf("\n");
    for(int i=1;i<=n;i++)
        printf("%2d",d[i]);
}