oToToT的code收藏區

題目連結: http://codeforces.com/problemset/problem/766/E 貌似是某種樹DP的東東，看到xor就要先想到把bit拆開，這樣的話問題就被轉化成說給你一堆0, 1的節點，問你所有路徑的和。這樣的話有個好處就是，因為只有0跟1，所以我們其實只要計算他的奇偶，然後偶爾交換一下之類的。接下來發現要枚舉所有路徑，其實枚舉lca就好了，所以就先走下去，把子樹算一算，之後提上來的時候稍微看一下自己是0還是1再把大家乘一乘之類的就好了。(想睡覺，可能有點不知所云 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; int arr[N]; vector<int> G[N]; lld ans = 0; PII dfs(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } for(int i=0;i<20;i++) dfs(1, 1, i); cout<<ans<<'\n'; return 0; } PII dfs(int w, int f, int d){...

題目連結: http://codeforces.com/problemset/problem/842/D 寫過類似的題目，一看到就認出來了XD。考慮把所有數字塞到bitwise的trie上，這樣xor一個數字時就變成交換左右子樹了，而且其實也不用真的把每個子樹都換過一遍，只要再走下去的時候看一下要誰當左右子樹即可。那這樣就只要在一棵樹上找mex值就好了，這也不難，只要維護一下每個子節點的大小，先看左子樹是不是空的，若是就直接回傳0，因為表示往左走都沒東東了，再看一下左子樹是不是滿的，若是就只能走右邊，不然就繼續走左子樹即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 300000 + 5; const int MEM = 20*N; class Trie{ private: struct node{ node *l, *r; int size; node(){l=r=nullptr;size=0;} }; node *root, pool[MEM]; int _mem; node* newnode(){ assert(_mem<MEM); pool[_mem]=node(); return &pool[_mem++]; } int size(node *x){return x?x->size:0;} void insert(int x, node *&cur, int d){ if(!cur) cur=newnode(); ...

題目連結: http://tioj.infor.org/problems/1513 一開始用unordered_map秒過去，可是傳上去後發現速度似乎有點慘，而且記憶體也比大家高，後來才發現其實把所有數字xor起來就會是答案，因為被關掉的編號一定是出現偶數次，而一個數字xor偶數次後必定就會變成0(也就是那個數字就會消失)。 unordered_map版本 #include <bits/stdc++.h> using namespace std; #define FF first #define SS second int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ unordered_map<unsigned int,int> mm; for(int i=0;i<n;i++){ unsigned int x;cin>>x; mm[x]++; } for(auto i:mm) if(i.SS&1) cout<<i.FF<<'\n'; } return 0; } xor版本 #include <cstdio> int main(){ int n; while(scanf("%d",&n)!=EOF){ unsigned int k=0; for(int i=0;i<n;i++){ unsigned int x;scanf("%u",&x); k^=x; } printf("%u\n",k); }...