本题
（1）首先2进制运算，结果只为0或1
（2）最后的结果为所有a（ij）*a（pq）的和的形式
（3）对于aij，若i==j，即为对角线时，出现1次，若i!=j时，出现2次。则结果之和对角线有关。对应法1.
（4）因为第i行只会和第i列相乘，不会和其它列元素相关；对于列亦如是。则最后的结果可以看成n个子结果之和，每个子结果为第i行和第i列的结果。
题目中只有翻转行和列操作，对于特定的i行，i列，共有4中组合，所以也可以预处理结果。对应法2,。显然法1最优。
法1：
int n;
int q;
int ans = 0;
int main ()
{
cin >> n;
int x, y;
ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
RI(x);
if (i == j) ans ^= x;
}
}
RI(q);
while (q--)
{
RI(x);
if (x == 3) printf("%d", ans);
else if (x == 1 || x == 2)
{
RI(y);
ans ^= 1;
}
}
puts("");
return 0;
}int a[1010][1010];
int t[1010];
int flg[1010];
int st[1010][4];
int n;
int q;
int ans = 0;
int main ()
{
cin >> n;
int x, y;
ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
RI(a[i][j]);
if (i == j) t[i] = a[i][j], ans ^= a[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j) continue;
st[i][0] ^= a[i][j] * a[j][i];
st[i][1] ^= (!a[i][j]) * a[j][i];
st[i][2] ^= a[i][j] * (!a[j][i]);
st[i][3] ^= (!a[i][j]) * (!a[j][i]);
}
st[i][0] = (st[i][0] + st[i][0]) % 2;///!!!
st[i][1] = (st[i][1] + st[i][1]) % 2;
st[i][2] = (st[i][2] + st[i][2]) % 2;
st[i][3] = (st[i][3] + st[i][3]) % 2;
}
RI(q);
while (q--)
{
RI(x);
if (x == 3)
printf("%d", ans);
else
{
RI(y); y--;
int dx = 0;
if (flg[y] == 0)
{
dx += st[y][x] - st[y][0];
dx = (dx + 8) % 2;
flg[y] = x;
}
else if (flg[y] == 3)
{
dx += st[y][3 - x] - st[y][3];
dx = (dx + 8) % 2;
flg[y] = 3 - x;
}
else
{
if (flg[y] == x)
{
dx += st[y][0] - st[y][x];
dx = (dx + 8) % 2;
flg[y] = 0;
}
else
{
dx += st[y][3] - st[y][3 - x];
dx = (dx + 8) % 2;
flg[y] = 3;
}
}
// dx = (dx + dx) % 2;///!!!
ans += dx + (!t[y]) - t[y];
ans = (ans + 8) % 2;
t[y] = !t[y];
}
}
puts("");
return 0;
}
题目最后没想出来，看了别人的代码发现，是利用数据具有的对称性构造的答案。
学习cxlove的代码
分析参考：http://blog.csdn.net/wty__/article/details/21873913
分析：对于A中的一个数ai，如果能够在B中找到和ai等价一个数1000000-ai+1，则即可。
若果找不到，即ai和1000000-ai+1都在A中，关键要发现，这里有：两数相加和为1000001.这可以通过另一个不在A中的2个数bi和1000000-bi+1来等价。
最后可以得到，数据是对称的结构。
const int maxn = 1000010;
int n;
vector<int>a, b;
int vis[maxn];
///!!!数据是对称的
int main ()
{
cin >> n;
int x, y;
int m = 0;
for (int i = 0; i < n; i++)
{
RI(x);
vis[x - 1]++;
}
for (int i = 0; i < 500000; i++)
{
int j = 999999 - i;
if (!vis[i] && !vis[j])
b.push_back(i), b.push_back(j);
else if (!vis[i] && vis[j]) a.push_back(i);
else if (vis[i] && !vis[j]) a.push_back(j);
}
printf("%d\n", n);
int bn = b.size(), an = a.size();
int p = 0;
for (int i = 0; i < an; i++)
{
if (p) printf(" "); else p = 1;
printf("%d", a[i] + 1);
}
for (int i = 0; i < n - an; i++)///保证有解
{
if (p) printf(" "); else p = 1;
printf("%d", b[i] + 1);
}
puts("");
return 0;
}
本来将题目看成树来做的，dfs即可。
是图的话，则需要判重，因为是求的边，所以判断的也是边。
ps;一开始想的是利用时间戳来处理的，但是还是会有重复边，改成判断边就对了
const int maxn = 500010;
vector<int>adj[maxn];
struct node{
int x, y, z;
node(int x, int y, int z):x(x), y(y), z(z){}
};
vector<node>ans;
set<pair<int, int> >S;
bool vis[maxn];
int dfs(int u)
{
if (vis[u]) return -1;
vis[u] = 1;
int a = -1;
int un = adj[u].size();
for (int r = 0; r < un; r++)
{
int v = adj[u][r];
if (S.find(make_pair(v, u)) == S.end() )
{
S.insert(make_pair(v, u));
S.insert(make_pair(u, v));
int b = dfs(v);
if (b != -1) ans.push_back(node(u, v, b));
else if (a == -1) a = v;
else
{
ans.push_back(node(v, u, a));
a = -1;
}
}
}
return a;
}
int main ()
{
int n, m;
int x, y;
RII(n, m);
for (int i = 0; i < m; i++)
{
RII(x, y);
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1);
if (ans.size() * 2 == m)
{
int ansn = ans.size();
for (int i = 0; i < ansn; i++)
{
node tmp = ans[i];
printf("%d %d %d\n", tmp.x, tmp.y, tmp.z);
}
}
else puts("No solution");
return 0;
}
原文：http://blog.csdn.net/guognib/article/details/21873495