Some of GDUFE

思路1：运用位运算符‘ ^ ’，运用A^B^B=A的原理，直接求解

 1 #include <stdio.h>
 2 int main()
 3 {
 4     int n,i,b,a;
 5     while(scanf("%d",&n)!=EOF&&n!=0)
 6     {
 7         b=0;
 8         for(i=0;i<2*n-1;i++)
 9         {
10             scanf("%d",&a);
11             b=b^a;
12         }
13         printf("%d
",b);
14     }
15     return 0;
16 }

View Code

思路2：全部输入后，sort排序，检索出落单的数字。

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 int ch[100003]={0};
 5 int main()
 6 {
 7     int a,n,i;
 8     while(scanf("%d",&n)!=EOF&&n!=0)
 9     {
10         a=0;
11         for(i=0;i<2*n-1;i++)
12             scanf("%d",&ch[i]);
13           sort(ch,ch+(2*n-1));
14             for(i=0;i<2*n-2;i+=2)
15                 if(ch[i]!=ch[i+1])
16                 {
17                 a=1;
18                 break;
19                 }
20             if(a==0&&i==2*(n-2)) printf("%d
",ch[2*n-2]);
21             else printf("%d
",ch[i]);
22     }
23     return 0;
24 }

View Code

思路3：因为公司人数最大50000，打卡编号也是50000，假设人数50000；假设一一对应，那么直接开ch[50000]={0}，然后将输入的打卡编号对应的数组下标的数组的值+1，最后检索，落单的编号的值是1，其余是2。可得答案。此方法好投机取巧，妙哉。

A^0=A,A^B^B=A 。位运算符还是很有用的。

GOJ1203

思路：快速幂求a^b，然后mod c。因为是随便输入的a，b，所以范围很大，而题目只需求最后三位，所以百位以上的计算不用理了，直接%1000。

 1 #include <stdio.h>
 2 int main()
 3 {
 4     unsigned long long a,b;
 5     while(scanf("%llu%llu",&a,&b)!=EOF)
 6     {
 7         unsigned long long c=1,d=a;
 8         while(b!=0)
 9         {
10         if(b&1!=0)//如果是0则无需计算，因为n*1=n
11             c*=d%1000;
12             d*=d%1000;
13             b>>=1;
14         }
15         if(c%1000>99)
16         printf("%llu
",c%1000);
17         else if(c%1000>9)
18         printf("0%llu
",c%1000);
19         else
20         printf("00%llu
",c%1000);
21     }
22     return 0;
23 }

View Code

Tip：以上mod c是因为怕数字过大爆了，一是因为a的b次mod c，二是因为早晚要mod c，所以早mod 无所谓。

小知识：

快速幂原理：a^b,将b拆成二进制数相加的形式，从而使运算次数减少

Example：a^11=a^(2^0+2^1+2^3)，时间复杂度为O（log11）。

 1 scanf("%d%d",&a,&b)
 2         int c=1,d=a;
 3         while(b!=0)
 4         {
 5         if(b&1!=0)//取b的二进制数的最后一位（相当于b%2!=0）
 6             c*=d;  
 7             d*=d;  //每往右推一位，d倍增，2^0 2^1 2^2……
 8             b>>=1;//将b的二进制数往右推一位（相当于b/=2）
 9         } 
10 printf("%d
",c);//c=a^b

View Code

GOJ1359

思路：先将1-500000的所有素数筛出，并在此过程中筛出含‘33’的数，最后在L到R之间计数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 int ch[500000],ch33[50000],k=0;
 4 
 5 int is33(int l)//筛出包含‘33’的数
 6 {
 7     while(l>32)
 8     {
 9         if(l%100==33)return 1;
10         l/=10;
11     }
12     return 0;
13 }
14 
15 void judge()//判断素数（埃氏筛法）
16 {
17     long long  i,j;
18 memset(ch,-1,sizeof(ch));//将ch所有元素初始化为-1
19     for(i=2;i<=500000;i++)
20         if(ch[i]==-1)
21         {
22             if(is33(i))
23                 {
24                     ch33[k++]=i;//存入ch33数组
25                 }
26         for( j=i*i;j<=500000;j+=i)
27             ch[j]=0;
28         }
29 }
30 
31 int main()
32 {
33     int n,s=0,g,a,L,R,i;
34     judge();
35     while(scanf("%d",&n)!=EOF)
36     while(n--)
37     {
38         s++;
39         scanf("%d%d",&L,&R);
40         for(g=0,a=0;g<k;g++)
41         {
42                 if(ch33[g]>=L&&ch33[g]<=R)a++;
43                 if(ch33[g]>R)break;
44         }
45         printf("Case #%d: %d
",s,a);
46     }
47     return 0;
48 }

View Code

以下是埃氏筛法的示意图：

原理：

1. 根据算术基本定理（百度）：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。

2. 先用2筛，筛走不是素数的数（也就是2的倍数），接着用3,5,7……直到最后一位。

3. 被筛走的可以标记，后面就不再用这个数筛。

Tips：

1.sizeof是判断数据类型或者表达式长度符，用于计算有多少个字节。

sizeof(int)==4。

char ch[10]="abc",sizeof(ch)==10*1。

2.strlen是求字符串（仅字符串）长度的函数。char ch[10]="abc",strlen(ch)==3.

3.memset

void *memset(void *s, int ch, sizeof(n));

解释：将s中当前位置后面的n个字节 (typedef unsigned int size_t)用 ch 替换并返回 s 。

对数组操作时只能用于数组的置0或-1，其他值无效。

memset(ch,-1,sizeof(ch))就是将数组ch中所有元素替换为-1，返回ch。