Tyrion的矩陣 Time Limit: 1000 ms???Case Time Limit: 1000 ms???Memory Limit: 64 MB
Description Cersei有一個整數序列A = {A1, A2,..., An}, 0<=ai<=10^9;
Jamie有一個整數序列B = {B1, B2,..., Bm}, 0<=bi<=10^9;
Tyrion根據Ceise提供的序列A和Jamie提供的數列B, 得到了一個n*m的矩陣C, 其中C(i, j) = ai xor bj;
現給你Tyrion的矩陣C, 請你看看Tyrion的矩陣可不可能出錯(即存在C(i, j) != ai xor bj).
關于xor運算詳細見hint
Input 多組測試數據.
第1行：測試數據組數t；
接下來依次是這t組數據，對于每一組數據：
第1行：n m; n, m含義如上, 有1<=m,n<=1024;
接下來的n行每行m個數, 描述了Tyrion的矩陣C;
第n+2行: 空行.
Output 一共t行對應t組數據;
對于每組數據, 如果你能確定Tyrion的矩陣出錯了, 請輸出一行"I bet Tyrion made a mistake."(不用輸出雙引號). 否則輸出為兩行, 一行輸出序列A, 一行為序列B, 同一序列的元素之間用一個空格隔開; 如果可能的A, B序列有多個, 請輸出其中序列A的字典序最小的一個.
Sample Input

Original

Transformed

2 2 2 0 0 0 12 2 0 1 0 1
Sample Output

Original

Transformed

I bet Tyrion made a mistake. 0 0 0 1
Hint 關于按位異或運算xor(在C語言中符號為^)：對等長二進制模式下的數，對二進制數的每一位執行邏輯異或操作. 操作的結果是如果某位不同則該位為1, 否則該位為0. 例如二進制下有:
0 xor 0 = 0; 0 xor 1 = 1; 1 xor 0 = 1; 1 xor 1 = 0;
0101(十進制下值為5) xor 0011(十進制下值為3) = 0110(十進制下值為6)。
Source “訊飛輸入法杯”安徽大學第六屆程序設計競賽
————————————————————憂桑的分割線———————————————————— 思路：該題考的是對位運算的理解深度。首先我們簡單化這個題目，假設A{ }，B{ }都是 0 or 1 組成的，那么A1只有兩種可能。 我們假設A1 = 0。之后我們通過給出的C[ ][ ]的第一行經過xor運算得到了B{ }的所有成員。知道了B1，我們通過C[ ][ ]的第一列經過xor運算得到了A{ }的所有成員。這意味著什么？意味著只要我們得知A1，那么所有的數字都清清楚楚明明白白了。 接下來是重點！A1的值我們是假設出來的，畢竟是未知量。但是我們考察一下A1 = 1的情況。（畢竟經過我們之前對問題的簡化之后，A1只有這兩種取值）,我們發現，A1 = 1的時候，整個B{ }的成員全部變成之前的相反數！那么由此可知，A{ }的成員也全部變成相反數。 由此我們知道，在這個情況下，A的取值是0是1都是無所謂的，整個矩陣不會發生改變。這就是位運算當中異或運算的精華部分了。異或運算是強大的： a ^ b = c; a ^ c = b; b ^ c = a; 更進一步地理解它，相當于“不進位的加法”：1 + 1 = 0; 1 + 0 = 1; 0 + 0 = 0; 這意味著什么？無論這個數字是幾位二進制，xor運互不影響。也就是說，我們簡化的情況，恰恰就是任意情況。 代碼如下： #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> int c[1024][1024], a[1024], b[1024]; int main() {int cas;scanf("%d", &cas);while(cas--) {int n, m, flag = 1;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)scanf("%d", c[i]+j);a[0] = 0;//沒關系，就用0代表所有情況，結果一樣for(int j = 0; j < m; j++)b[j] = a[0] ^ c[0][j];//得到b[]for(int i = 1; i < n; i++)a[i] = c[i][0] ^ b[0];//得到a[]for(int i = 1; i < n; i++) {for(int j = 1; j < m; j++)if((a[i]^b[j]) != c[i][j]) {flag = 0;break;}if(!flag) break;//枚舉矩陣，一旦不符合情況，做標記}if(flag) {int i, j;for(i = 0; i < n-1; i++)printf("%d ", a[i]);printf("%d\n", a[i]);for(j = 0; j < m-1; j++)printf("%d ", b[j]);printf("%d\n", b[j]);}else puts("I bet Tyrion made a mistake.");}return 0; }

總結

以上是生活随笔為你收集整理的AOJ-AHU-OJ-670 Tyrion的矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。