e319: 小王的积木 Again

e319: 小王的积木 Again

題目連結:e319: 小王的积木 Again!

題意：

給你一些數字
這些數字中只有一個只出現1次,其他數字則出現了3次
求這個只出現1次的數字

解法:

C++:

我們可以利用位元運算達到O(N)的複雜度

這題的記憶體限制只有5MB

不能使用<iostream>

time:28ms

memory used:204KB

code:

1. #pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")
2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
3. #include<cstdio>
4. #include<stdint.h>
5. char buf[1<<16],*p1=buf,*p2=buf;
6. inline int getc(){
7. return p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<16,stdin),p1==p2)?EOF:*p1++;
8. }
9. inline int read() {
10. uint_fast64_t ret=0;
11. char ch(getc());
12. while(ch>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0',ch=getc();
13. return ret;
14. }
15. int main(){
16.     uint_fast64_t n,p(0),q(0),b;
17.     n=read();
18.     for(int i(0);i<n;++i){
19.         b=read();
20.         p=q&(p^b);
21.         q=p|(q^b);
22.     }
23.     printf("%d",q);
24. }

本人的分享到此結束
若有更好的想法或建議,請在留言區留言喔