比赛 20120919dfs 评测结果 AAAAAAAAAA
题目名称 虫食算 最终得分 100
用户昵称 Makazeu 运行时间 0.095 s
代码语言 C++ 内存使用 3.13 MiB
提交时间 2012-09-19 20:19:12
显示代码纯文本
  1. /*
  2. * Problem : alpha
  3. * Contest : NOIP2004
  4. */
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <string>
  9. #include <iostream>
  10. #include <algorithm>
  11. #define Undef -1
  12. using namespace std;
  13. const int MAXN=30;
  14. int N,num[3][MAXN];
  15. string str[3];
  16. int order[MAXN]; /*Record the Search Order*/
  17. int ans[MAXN]; /* Answer */
  18. int Used[MAXN];
  19.  
  20. inline void init()
  21. {
  22. scanf("%d\n",&N);
  23. for(int k=0;k<=2;k++) {str[k].clear(); cin>>str[k];}
  24. for(int i=1;i<=N;i++)
  25. for(int j=0;j<=2;j++)
  26. num[j][i]=str[j][i-1]-'A'+1;
  27. int used[MAXN]={0}; int top=0;
  28. for(int i=N;i>=1;i--)
  29. for(int j=0;j<=2;j++)
  30. if(!used[num[j][i]])
  31. order[++top]=num[j][i],used[num[j][i]]=1;
  32. }
  33.  
  34. inline bool check()
  35. {
  36. int next=0;
  37. for(int i=N;i>=1;i--)
  38. {
  39. if((ans[num[0][i]]+ans[num[1][i]]+next)%N!=ans[num[2][i]]) return false;
  40. next=(ans[num[0][i]]+ans[num[1][i]]+next)/N;
  41. }
  42. return (next==0);
  43. }
  44.  
  45. inline bool jian()
  46. {
  47. for(int i=N;i>=1;i--)
  48. {
  49. if((ans[num[0][i]]==Undef) || (ans[num[1][i]]==Undef) || (ans[num[2][i]])==Undef ) continue;
  50. if((ans[num[0][i]]+ans[num[1][i]])%N==ans[num[2][i]]) continue;
  51. if((ans[num[0][i]]+ans[num[1][i]]+1)%N==ans[num[2][i]]) continue;
  52. return false;
  53. } return true;
  54. }
  55.  
  56. void dfs(int k)
  57. {
  58. if(k>N)
  59. {
  60. bool flag=check();
  61. if(!flag) return;
  62. for(int i=1;i<=N-1;i++) printf("%d ", ans[i]);
  63. printf("%d\n",ans[N]); exit(0);
  64. }
  65. bool flag;
  66. for(int i=N-1;i>=0;i--)
  67. {
  68. if(Used[i]) continue;
  69. ans[order[k]]=i; flag=jian();
  70. if(!flag) { ans[order[k]]=-1; continue;}
  71. Used[i]=1; dfs(k+1); Used[i]=0; ans[order[k]]=-1;
  72. }
  73. }
  74.  
  75. inline void solve()
  76. {
  77. for(int i=1;i<=N;i++) ans[i]=Undef;
  78. dfs(1);
  79. }
  80.  
  81. int main()
  82. {
  83. freopen("alpha.in","r",stdin);
  84. freopen("alpha.out","w",stdout);
  85. init(); solve();
  86. return 0;
  87. }