oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1696 看來我對重心剖分的理解還不夠QQ，一直想成重心樹的父子關係會跟原本的樹一樣。 我對於每個重心樹上的點維護他重心子樹們中$ dis \leq i, \forall 0 \leq i \leq D_{max} $的人有幾個(其中dis代表在原樹上的距離)，以及扣掉某個小孩的子樹後的這坨值。接著對於每個人就當做一個詢問，從葉子往上走訪重心樹，同時查詢不走剛剛來的那個點的子樹，距離好的點有幾個。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) #define PB push_back #define SZ(x) ((int)(x).size()) const int N = 100000 + 5; struct node{ int cur, dis; node(int a=-1,int b=0):cur(a),dis(b){} }; vector<node> path[N]; vector<int> sum[N], fa_sum[N]; bool done[N]; int sz[N], M[N], fa[N], dis[N], que[N], cen[N]; vector<int> G[N]; int CenDe(int); int Query(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 >> que[i]; for(int i=0;i<n-1;i++){ int u, v; cin >> u >> v; G[u].PB(v); G[v].PB(u); } int cent = CenDe(1); partial_sum(ALL(sum[cent]), sum[cent].begin()); for(int i=1;i<=n;i++) cout << Que

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){