題目連結:
點選打開連結
題目大意:
給出一個二階魔方,判斷這個魔方是否是能夠還原的
題目分析:
首先我們去想一個被還原的魔方,那麼這個魔方的相對的面的顔色是一定的,我們給魔方的每一個小面一個權值,那麼我們選取黃面(随機選取的),那麼與它相對的是白面,對于黃面上的四個點,他們的權值都是0,因為每個小面都是可以通過固定沒有重複的旋轉方向的次數回到它本身所在的面或它所對的面,也就是3次,那麼每次旋轉它,就有一個-1,或者1,用來标記到下一狀态的距離,和回到目前狀态的距離。
初始情況下,到下一狀态的距離是3,到自身狀态的距離是0。是以黃白面所在的小面的權值之和能被3正除
那麼如果我們旋轉了一次,會導緻兩個黃面和兩個白面動,然而不會導緻權值之和與3的倍數關系
因為兩個連續的顔色格,一個相當于到達奇數位狀态遠離了一步,到達偶數位的狀态增加了一步,另一個相反,因為相鄰,是以他們兩個的奇偶性一定不同,是以說最終的權值之和與3的倍數關系不變。
因為每個面到達奇數位和偶數位的距離之和一定是3,而且奇數位和偶數位的數量是一定的,是以如果一個到達偶數位的距離為2,那麼一定存在一個到達偶數位距離為1的面,才能維護這種關系。
盲擰和色向能夠保住了解,可以去魔方的興趣愛好者那裡了解一下。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
char s[10];
int t;
int wh[] = {7,8,13,14,21,22,23,24};
int add[] = {1,4,6,10,11,15,17,20};
int main ( )
{
int c = 1;
scanf ( "%d" , &t );
while ( t-- )
{
int ans = 0;
for ( int i = 1 ; i <= 24 ; i++ )
{
scanf ( "%s" , s );
if ( s[0] == 'w' || s[0] == 'y' )
{
bool flag = true;
for ( int j = 0 ; j < 8 ; j++ )
if ( wh[j] == i )
{
flag = false;
break;
}
else if ( add[j] == i )
{
ans++;
flag = false;
break;
}
if ( flag ) ans--;
}
}
//cout << "YES : " << ans << endl;
printf ( "Case #%d: " , c++ );
if ( ans%3 == 0 ) puts ("YES");
else puts ("NO");
}
}