1樓：天象
要是我的話，肯定會加乙個總體圖元都一樣，但是有幾步用的是映象而不是旋轉，得到的影象，專門坑這些用最小表示法的。不過，看來微軟沒有這麼黑心。
我覺得應該是需要乙個特殊的，遞迴的，複雜度為O(n)的，以及還有乙個最重要的條件，旋轉90度之後其值不變的，hash函式，就能在O(n)時間內完成。所謂「旋轉之後按照字典序的最小表示」其實就是這樣乙個函式，但是這個函式的效率太低了。
暫時想到乙個更短的函式：將四個子塊的hash值順時針差分然後乘在一起。
明天我再考慮證明乙個更短的。
想出來乙個更短的：把差分之後的值按位異或
2樓：
寫完三題只剩40分鐘了，看了一下題發現暴力做法時間複雜度是O(n
^2log(n))。來不及想更好的方法，直接遞迴搜尋，稍微注意一下常數就可以AC了。
3樓：唐hz
諸位的解法都是找乙個中間狀態，通過能否達到中間狀態來確定；
請看這樣是否可行：
因為是乙個矩陣N，如果N能被2整除，依次在對四個小塊遞迴旋轉對於乙個矩陣
A|BC|D
可以看到無論怎樣旋轉，它們的相對位置都是不變的，又由於是對A,B,C,D四個子矩陣進行旋轉，所以它們的內部可能會發生改變，但不會出現A的乙個值和B的乙個值交換的情況；
所以 如果N是奇數，旋轉矩陣看能否匹配（4次）如果N是偶數，把矩陣劃分成A,B,C,D,四塊，依次求出四塊數的和，變成了兩個2*2的矩陣，判斷它們能否通過旋轉得到（4次）。否，失敗；是，成功，依次對對應的四塊進行上面的操作（遞迴）。（這裡最好的情況是四個和剛好不同可以一一對應，最壞的情況是四個值都相等。
）遞迴此過程直到全部找到對應，是；或中途失敗，否。
如例子4123
1234
2341
3412
3441
2312
1443
就先轉化成
8|12
12|8
和12|8
8|12
是然後就是
3423 和
2334
....
最後，是。
這樣不用太多次旋轉矩陣，不過重複計算太多了。
（可以用動態規劃改進）。
（應該沒錯吧？）
fancy image
#include
#include
using namespace std;
#define clk0 1
#define clk1 2
#define clk2 4
#define clk3 8
struct matrix
matrix(const matrix &a)int *operator(const int n)constint *operator(const int n)matrix &operator=(const matrix &m)~matrix()
bool operator ==(const matrix& a)現在複雜度是O(n^2*logn)如果把求和記錄下來大概可以到O（n*logn）；
4樓：歐文韜
感覺直接暴力搜尋直接ok啊。加密次數最多log2(n)，每次4個數，一起就是4^log2(n)=2n。每次dfs操作矩陣為n*n，那麼複雜度就是n^3。
n只有100。n^3=一百萬1秒內妥妥地。10個case，10秒內妥妥的哇。
5樓：狼大人
[d] * p for p is 2 or odd
[m] * 2^k for k in N
對於 [d] 的情況沒什麼好做的，數字自己不會變。
對於 [d] * 2/3 的情況，處理方法是一樣的：把矩陣按照螺旋順序拆開，如
可以拆開成 array = [1, 2, 4, 3]。
# 展開矩陣的演算法到處都是
def spiral_index(N)
# 如：http://blog.csdn.net/handsomekang/article/details/10165925
# 偷懶，用了 numpy.array 的索引語法
def expand(m):
return m[spiral_index(N)]
拆開後的這個列表可以方便的列舉出所有可能的轉換：
＃寫這裡的時候只考慮了 2x2 的情況，其他情況都是不對的……所以目前只能解 2^k 邊長的
# arrays - How to rotate a matrix 90 degrees without using any extra space? 正解在這裡，轉 4 次。
def permutations(array):
for i in range(0, len(array)):
yield array[i:] + array[:i]
定義排序關係：（我估計這個地方對於 [m] * 2^k 的遞迴矩陣情況有問題
def less_than(a1, a2):
if isinstance(a1, int) and isinstance(a2, int):
return cmp(a1, a2) # possible result: -1, 0, 1
for i in range(0, len(a1)):
r = less_than(a1[i], a2[i])
if r != 0:
return r
else:
return 0
找到最小的乙個：
min_array = lambda array: sorted(permutations(array), cmp=less_than)[0]
min_matrix = lambda m: min_array(expand(m))
那麼兩個矩陣是否可以轉換的判斷就是
def transformable(m1, m2):
return min_matrix(m1) == min_matrix(m2)
對於 [m] * 2^k 的情況，遞迴分解即可：
def split_matrix(m, N):
newsize = N / 2
if newsize * 8 == len(m):
# 分成四個象限
return [
m[i * newsize : (i+1) * newsizem[(i+2) * newsize : (i+3) * newsize]
for i in range(4) ]
return m
def matrix_transformable(m1, m2, N):
return transformable(
split_matrix(m1),
split_matrix(m2))
6樓：天馬
說下某砂的想法..(此砂絕不是本蒟蒻←_←(我就不說是我好不容易問到能讓我聽得懂的地步了→_→(總之以下是按我的理解按我的表述粗略講下..
記圖的邊長為2^a*b,2|b-1或b=2.
判斷兩個無法細分的塊(邊長為2或奇數的)是否能通過旋轉相互轉化的演算法就不說了.
對於原題,遞迴:
a=0的邊界情況就不說了,否則把倆圖都分成4^a個b*b的小塊(倆圖共2^(2a+1)個塊).
以"能通過旋轉匹配"為等價關係,將這些塊分成若干個等價類.
用等價類的編號代替這些塊,於是圖的邊長相當於縮小為1/b.(ps.此處可剪枝:倆圖的編號(有重)集必須相同.)
對這個新的小圖,遞迴..
7樓：pyj philippica
沒資格參加微軟校招的蒟蒻,只會暴力的做法：
對於n為奇數的矩陣直接暴力判斷是否是對應塊rotate來的;對於n為偶數的矩陣,每個（n/2）*(n/2)的子矩陣rotate４次判斷與對應塊的數字是否相同（用multiset判斷一下就好）然後就可以確定對應順序遞迴下去
時間複雜度的話Ｔ（N）=4*T(N/2)+N^2 用主定理可以得到時間複雜度是N)）
不保證正確性及時間複雜度ＴＴ
如何評價微軟Connect 2015？
hillin 關於 Connect 2015 1.請找出以下產品中與其他型別不同的乙個 A.Visual Studio Enterprise B.Visual Studio Dev Essentials C.Visual Studio Code D.Visual Studio Community 2...
如何評價微軟 Build 2015 開發者大會？
Battlebooom 其實我一直在想office和打車軟體為什麼會有聯絡。還不如和wechat之類的聯絡一下。我對windowsphone的發展有些擔憂，會不會打擊現在wp開發商開發modern應用的積極性，希望這是杞人憂天。不過這回只要手機硬體 指外觀 特色功能 黑科技等等 給力，會吸引不少顧客...
如何評價E起上岸校招群？
電氣的別給他洗了，你們要的人多，還能上岸，電子資訊的網申都過不了。不是說滿足條件一半就能過麼，不是說網申的志願不重要，現場還會填一次的麼。結果人家就是按照報考地區進行篩選。不是所有全部篩選。在群裡關注到這個事，我也說兩句吧，這個人已經全額退款了，也跟我們大家誠懇道了歉，算是為他的行為買了單。他確實營...