Last active
January 31, 2017 03:15
-
-
Save ss1h2a3tw/d87e3ebf67a08d631c6fd8fcabf2e08f to your computer and use it in GitHub Desktop.
UVA 13154
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| UVA13154 Extreme XOR Sum | |
| 給你一串數列長度10^4 元素<10^9 | |
| 定義區間內XOR sum 為將左右鄰居兩兩相XOR | |
| 然後將結果做同樣操作 直到只剩一個元素即為XOR sum | |
| 會有30000個區間查詢 | |
| 思路: | |
| 先觀察區間 XOR的行為 | |
| 1 2 3 | |
| 1^2 2^3 | |
| 1^2^2^3 | |
| 其中 1 被 XOR 1 次,2 2次,3 1次 | |
| 在1~4則為 1 1次,2 3次,3 3次,4 1次 | |
| 其實就是Pascal三角形第幾行對應上去 | |
| 然後考律XOR偶數次為0 | |
| 所以將Pascal奇數設為1 偶數設為0 | |
| 我們會的到一個Sierpinski triangle | |
| https://en.wikipedia.org/wiki/File:Sierpinski_triangle.svg | |
| 然後因為他是碎形 例如第五行的第一個可以對應到第一行的第一個 | |
| 所以我們可以在log n 內知道這一個在三角形內是1或0 | |
| 套用後 O(nqlgn) => TLE | |
| 但是這樣還不夠 | |
| 所以再做觀察 在n < 10000 三角形內01區間不超過1024個 | |
| 所以先預處理三角形的01區間 | |
| 然後前綴合優化即可通過 | |
| */ | |
| #include <cstdio> | |
| #include <algorithm> | |
| #include <vector> | |
| using namespace std; | |
| int a[10010]; | |
| int n,q; | |
| bool p[10010][10010]; | |
| vector<pair<int,int>> v[10000]; | |
| int psum[10010]; | |
| void gen(){ | |
| for(int i = 1 ; (1 << (i-1)) < 10000 ; i ++){ | |
| for(int j = (1 << (i-1))+1 ; j <= 10000 && j <= (1<<i) ; j ++){ | |
| for(int k = 0 ; k < j ; k ++){ | |
| p[j][k]=p[j-(1<<(i-1))][k>=j/2?j-k-1:k]; | |
| } | |
| } | |
| } | |
| for(int i = 1 ; i <= 10000 ; i ++){ | |
| int head=0; | |
| bool finding=false; | |
| for(int j = 0 ; j < i ; j ++){ | |
| if(!finding&&p[i][j]==0){ | |
| v[i].push_back({head,j-1}); | |
| finding=true; | |
| } | |
| else if(finding&&p[i][j]==1){ | |
| head=j; | |
| finding=false; | |
| } | |
| } | |
| v[i].push_back({head,i-1}); | |
| } | |
| } | |
| int main (){ | |
| p[1][0]=1; | |
| gen(); | |
| int T; | |
| scanf("%d",&T); | |
| for(int I = 1 ; I <= T ; I ++){ | |
| fill(psum,psum+10010,0); | |
| printf("Case %d:\n",I); | |
| scanf("%d",&n); | |
| for(int i = 0 ; i < n ; i ++){ | |
| scanf("%d",a+i); | |
| psum[i+1]=a[i]^psum[i]; | |
| } | |
| scanf("%d",&q); | |
| for(int J = 0 ; J < q ; J ++){ | |
| int b,c; | |
| scanf("%d%d",&b,&c); | |
| int sum = 0; | |
| for(const auto& x:v[c-b+1]){ | |
| sum ^= psum[b+x.first]^psum[b+x.second+1]; | |
| } | |
| printf("%d\n",sum); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment