题解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为偶数

位运算大法好!!!

闲话不多说,下面奉上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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,这样快一些,又短)
//注意:这里使用了位运算!具体方法见上面说明!
}
0%