【题目大意】
有n个数或为奇数或为偶数，现在进行m次操作，每次取出部分求和，告诉你这几次操作选取的数和它们和的奇偶性。如果通过这m次操作能得到所有数的奇偶性，则输出进行到第n次时即可求出答案；否则输出无法确定。
【思路】
高斯消元解xor方程组，求最少需要的方程个数或判断无法确定。
无法确定即存在*元，在每次操作中找1的时候判断一下就好了；最小方程个数，就是记录下每次找到的最小的1的位置，最后输出最大值即可。
【错误】
忘记把ans改为-1了（见程序注释）
【备注】
P.S.我看别人在高斯消元的过程中都是当前行和所有行xor一遍，而不是从下一行开始；然后结果就不需要回代了只需直接输出第n+1列即可？？不适合呢明白？？？？
在莫涛和proverbs那里找到答案了：
考虑系数矩阵，每行是一个方程，每列是一个未知数在各个方程中的系数（将第i行的方程的所有系数状压到一个数 a[i]里，可以用bitset）。
我们分析一下消元之后各个方程系数的状况：
由于我们每次选择最大的一个 a[i]，并且找到它最高位上的1，把其它所有方程（包含当前行以上的方程）这一位的系数全部消去，也就是说对于每个方程，它的系数 a[i]最高位上的1所在的那一列，仅有这一个1，其余的都是0。再进一步，如果方程个数n足够多的话，那么消元之后系数矩阵的每一行仅有一个1，并且这个1所在的那一列也仅有这一个1。
/*回代的做法*/
/**************************************************************
Problem: 1923
Language: C++
Result: Accepted
Time:244 ms
Memory:1556 kb
****************************************************************/ #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int MAXN=+;
const int MAXM=+;
bitset<MAXN> map[MAXM];
int n,m;
int times=-; void Gauss()
{
for (int i=;i<=n;i++)
{
int t=i;
for (;t<=m && !map[t][i];t++);
if (t>m)
{
times=-;//这里times要清成-1
return;
}
if (t!=i) swap(map[i],map[t]);
times=max(times,t);
for (int j=i+;j<=m;j++)
if (map[j][i])
map[j]^=map[i];
} } void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<m;i++)
{
char str[MAXN];
int mapans;
scanf("%s%d",str,&mapans);
map[i+][n+]=mapans;
for (int j=;j<n;j++) map[i+][j+]=str[j]-'';
}
} void print_ans()
{
if (times==-) cout<<"Cannot Determine"<<endl;
else
{
printf("%d\n",times);
for (int i=n;i>=;i--)
for (int k=i+;k<=n;k++)
if (map[i][k])
{
int tmp=map[i][n+]^map[k][n+];
map[i][n+]=tmp;
}
for (int i=;i<=n;i++)
puts((map[i][n+])?"?y7M#":"Earth");
}
} int main()
{
init();
Gauss();
print_ans();
}
额变慢了……仿佛被欺骗了感情……谁来告诉我一下??!!
/*不回代的做法*/
/**************************************************************
Problem: 1923
Language: C++
Result: Accepted
Time:284 ms
Memory:1556 kb
****************************************************************/ #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int MAXN=+;
const int MAXM=+;
bitset<MAXN> map[MAXM];
int n,m;
int times=-; void Gauss()
{
for (int i=;i<=n;i++)
{
int t=i;
for (;t<=m && !map[t][i];t++);
if (t>m)
{
times=-;//这里times要清成-1
return;
}
if (t!=i) swap(map[i],map[t]);
times=max(times,t);
for (int j=;j<=m;j++)
if (i!=j && map[j][i])
map[j]^=map[i];
} } void init()
{
scanf("%d%d",&n,&m);
for (int i=;i<m;i++)
{
char str[MAXN];
int mapans;
scanf("%s%d",str,&mapans);
map[i+][n+]=mapans;
for (int j=;j<n;j++) map[i+][j+]=str[j]-'';
}
} void print_ans()
{
if (times==-) cout<<"Cannot Determine"<<endl;
else
{
printf("%d\n",times);
for (int i=;i<=n;i++)
puts((map[i][n+])?"?y7M#":"Earth");
}
} int main()
{
init();
Gauss();
print_ans();
}