题解
学OI学傻了，一开始想到一个 O(m^n) 的暴力，显然是过不了的，后面想到一个 O(2^nm) 的做法，就没思路了
其实正解很简单。
我们先取好一组（这里默认就是第一列），如果它的值大于0，那就是答案了，输出即可。
如果不大于0，它的值肯定就为0了，对于每一行，如果能找到一个数与当前所选的数不一致的数，那就选它（因为它们的二进制数肯定不同，当前异或和为0，换一个不一样的数，疑惑和就肯定大于0了）
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <bits/stdc++.h> using namespace std; int ma[503][503]; int sel[501]; int n, m; int cur; void out() { printf("TAK\n"); for (int i = 1; i <= n; i++) printf("%d ", sel[i]); exit(0); } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> ma[i][j]; sel[i] = 1; } cur ^= ma[i][1]; } if (cur >= 1) { printf("TAK\n"); for (int i = 1; i <= n; i++) printf("%d ", sel[i]); exit(0); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (ma[i][j] != ma[i][1]) { sel[i] = j; out(); } } } printf("NIE"); return 0; } |