比赛 |
20120919dfs |
评测结果 |
AAAAAAAAAA |
题目名称 |
虫食算 |
最终得分 |
100 |
用户昵称 |
Makazeu |
运行时间 |
0.095 s |
代码语言 |
C++ |
内存使用 |
3.13 MiB |
提交时间 |
2012-09-19 20:19:12 |
显示代码纯文本
- /*
- * Problem : alpha
- * Contest : NOIP2004
- */
- #include <cstdlib>
- #include <cstdio>
- #include <cstring>
- #include <string>
- #include <iostream>
- #include <algorithm>
- #define Undef -1
- using namespace std;
- const int MAXN=30;
- int N,num[3][MAXN];
- string str[3];
- int order[MAXN]; /*Record the Search Order*/
- int ans[MAXN]; /* Answer */
- int Used[MAXN];
-
- inline void init()
- {
- scanf("%d\n",&N);
- for(int k=0;k<=2;k++) {str[k].clear(); cin>>str[k];}
- for(int i=1;i<=N;i++)
- for(int j=0;j<=2;j++)
- num[j][i]=str[j][i-1]-'A'+1;
- int used[MAXN]={0}; int top=0;
- for(int i=N;i>=1;i--)
- for(int j=0;j<=2;j++)
- if(!used[num[j][i]])
- order[++top]=num[j][i],used[num[j][i]]=1;
- }
-
- inline bool check()
- {
- int next=0;
- for(int i=N;i>=1;i--)
- {
- if((ans[num[0][i]]+ans[num[1][i]]+next)%N!=ans[num[2][i]]) return false;
- next=(ans[num[0][i]]+ans[num[1][i]]+next)/N;
- }
- return (next==0);
- }
-
- inline bool jian()
- {
- for(int i=N;i>=1;i--)
- {
- if((ans[num[0][i]]==Undef) || (ans[num[1][i]]==Undef) || (ans[num[2][i]])==Undef ) continue;
- if((ans[num[0][i]]+ans[num[1][i]])%N==ans[num[2][i]]) continue;
- if((ans[num[0][i]]+ans[num[1][i]]+1)%N==ans[num[2][i]]) continue;
- return false;
- } return true;
- }
-
- void dfs(int k)
- {
- if(k>N)
- {
- bool flag=check();
- if(!flag) return;
- for(int i=1;i<=N-1;i++) printf("%d ", ans[i]);
- printf("%d\n",ans[N]); exit(0);
- }
- bool flag;
- for(int i=N-1;i>=0;i--)
- {
- if(Used[i]) continue;
- ans[order[k]]=i; flag=jian();
- if(!flag) { ans[order[k]]=-1; continue;}
- Used[i]=1; dfs(k+1); Used[i]=0; ans[order[k]]=-1;
- }
- }
-
- inline void solve()
- {
- for(int i=1;i<=N;i++) ans[i]=Undef;
- dfs(1);
- }
-
- int main()
- {
- freopen("alpha.in","r",stdin);
- freopen("alpha.out","w",stdout);
- init(); solve();
- return 0;
- }