华师一附中OI组

标题: UVA253 cube painting 讨论 [打印本页]
作者: admin    时间: 2017-9-27 12:54
标题: UVA253 cube painting 讨论
题目描述很简单，给定两个骰子，每个骰子用6个字符表示每个面的颜色，问这两个骰子是不是同一个。原题：https://uva.onlinejudge.org/inde ... problem&problem=189
这类题目在NOI系列赛场上偶有所见，北京1999有个五骰子问题，给出五个摞在一起的骰子的11个面，问是否可能这样；ctsc1999也有一个罗杰游戏，子程序也是骰子的翻转，对于此类题目，数学建模最重要。我是这样做的：
如原题图中所示：假设标准的骰子最上面的面是1，正前方是2，左边是3，右边是4，后面是5，下面是6的话，记作 123456 。若把2旋转到1的位置，只需要在竖直平面旋转一格，则可能是263415，就是是说2在原来1的位置，6在原来2的位置，3在原来3的位置****，我们表示为2,6,3,4,1,5，当然还可以有其他的，比如2,3,1,6,4,5，和刚才不同时水平面也旋转了一下。所以我们若将一个骰子固定，另外的一个骰子的每个面都先对应到第一个面，然后水平旋转90度。若有一个情况和地一个骰子相等就认为是同一个。
每个骰子最多24个变化，计算量不大就不考虑优化了。
代码如下：
  1. #include <iostream>
  2. using namespace std;
  3. string s,s1,s2;
  4. int i;
  5. int m[6][6]={ {1,2,3,4,5,6},
  6.               {2,6,3,4,1,5},
  7.               {3,2,6,1,5,4},
  8.               {4,2,1,6,5,3},
  9.               {5,1,3,4,6,2},
  10.               {6,5,3,4,2,1} };
  11. bool can(string s1,string s2)
  12. {
  13.     string t;
  14.     char ch;

  16.     int i,j,k;
  17.     for( i=1;i<=6;i++)
  18.     {
  19.         t="";
  20.         for( j=1;j<=6;j++) t=t+s1[m[i-1][j-1]-1];
  21.         ///cout<<t<<endl;

  23.         for( k=1;k<=4;k++)
  24.         {
  25.             ch=t[1];
  26.             t[1]=t[2];
  27.             t[2]=t[4];
  28.             t[4]=t[3];
  29.             t[3]=ch;
  30.             ///cout<<t<<endl;
  31.             if(s2==t) return 1;
  32.         }
  33.     }
  34.     return 0;

  36. }
  37. int main()
  38. {

  40.     while(cin>>s)
  41.     {
  42.         s1=s2="";
  43.         for (i=0;i<=5;i++) s1=s1+s[i];
  44.         for (i=6;i<=11;i++) s2=s2+s[i];


  47.         if(can(s1,s2)) cout<<"TRUE"<<endl;
  48.         else cout<<"FALSE"<<endl;
  49.     }
  50.     return 0;
  51. }
复制代码

作者: admin    时间: 2017-9-27 12:57
这个代码很精妙，第5行的数组是旋转后的位置对应关系。和第20行的代码共同实现固定某个面朝上的一种情况；第23行的循环是水平旋转4次。其他的代码就不一一细说了。
作者: admin    时间: 2018-6-3 11:40
钱鹏宇大牛的做法：
  1. #include<cstdio>
  2. #include<cstring>
  3. using namespace std;
  4. int main()
  5. {
  6.     int i,j,c[3][2]={{0,5},{1,4},{2,3}};
  7.     char a[13],b[13];
  8.     scanf("%s%s",a,b);
  9.     for(int k=0;k<3;k++)
  10.     {
  11.         int n=c[k][0],m=c[k][1];
  12.         if((a[n]==b[n]||a[n]==b[m])&&(a[m]==b[n]||a[m]==b[m]))
  13.         {
  14.             continue;
  15.         }
  16.         else
  17.         {
  18.             printf("NO!");
  19.             return 0;
  20.         }
  21.     }
  22.     printf("YES!");
  23.     return 0;
  24. }
复制代码
作者: 吴语林    时间: 2018-6-27 16:00
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. char a[100];
  14. int ha1[1000][1000],ha2[1000][1000],i;
  15. int main()
  16. {
  17.     while(~scanf("%s",a))
  18.     {
  19.         memset(ha1,0,sizeof(ha1));memset(ha2,0,sizeof(ha2));
  20.         for(i=0;i<=5;i++)
  21.             ha1[a[i]][a[5-i]]++,ha1[a[5-i]][a[i]]++;
  22.         for(i=0;i<=5;i++)
  23.             ha2[a[i+6]][a[11-i]]++,ha2[a[11-i]][a[i+6]]++;
  24.         for(i=0;i<=2;i++)
  25.             if(ha1[a[i]][a[5-i]]!=ha2[a[i]][a[5-i]])
  26.                 break;
  27.         if(i==3) printf("TRUE\n");
  28.         else printf("FALSE\n");
  29.     }
  30.     return 0;
  31. }
复制代码
作者: admin    时间: 2018-6-27 23:11
楼上吴同学这个做法能解释一下吗



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2