题解 P1636 【Einstein学画画】

· · 题解

虽然跟楼上各位写得差不多，但是！

我使用了无敌的位运算！

其实很简单（没什么用……）

在此，先解释一下按位与（&）：,a&b是指将a，b分别转为二进制，然后逐位比较，如两者的同位皆为1，则结果的该位为1，否则为0。

那么，可以看出%2为1的数二进制末尾必为1，否则必为0，1&1为1,0&1为0，那么该数&1的结果即可判断奇偶性。

综上所述：a&1=1，a为奇数，否则，a为偶数

位运算大法好！！！

闲话不多说，下面奉上代码：

#include<cstdio>//位运算大法好 
inline void read(int &a)//快速读入 
{
    int k=1;//系数 
    char c=getchar();a=0;//定义字符，并进行第一次读入 
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}//如果不为数字，继续读入，特判：如为-号，系数变为-1 
    while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}//如果是数字，需将变量*10+当前数字 
    a*=k;//乘上系数 
}
int s,n,m,a,b,f[1010];//定义变量，s为度为奇数点总数，n，m变量见题意，a，b是读入的边的两端点，f数组统计点度数 
int main()
{
    read(n);read(m);//懒得解释 
    for(int i=1;i<=m;i++)
    {
        read(a);read(b);//读入 
        f[a]++;
        f[b]++;//两点的度+1 
    }
    for(int i=1;i<=n;i++)if(f[i]&1)s++;//如果当前点度为奇数，s++ 
    printf("%d",s?s/2:1);//输出s/2（s=0时输出1）（其中s为0或2时，能一笔画，故输出结果为1，这样快一些，又短） 
    //注意：这里使用了位运算！具体方法见上面说明！ 
}