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(...

題目連結: 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(...

題目連結: http://codeforces.com/problemset/problem/909/C 我不會DP QAQ 本題狀態可以訂成$dp[i][j]$代表到第$i$個statement時有$j$個intent的方法數，那轉移想了想後就可以得到，如果前面是for statement，那顯然現在的東西就只能擺在跟他同一個intent，而若前一個是普通的statement，則我們可以擺到intent比較小的任意一個位置。而這樣的話複雜度會變成$O(N^3)$，但是其實我們可以透過預處理前綴和以達到$O(N^2)$的複雜度。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int MOD = 1000000007; const int N = 5000 + 5; bool arr[N]; lld dp[N][N], sum[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ string ss; cin>>ss; if(ss[0]=='s') arr[i] = 1; else arr[i] = 0; } auto psum = [](int l, int r){ // 0-base [l, r] if(l) return sum[r]-sum[l-1]; else return sum[r]; }; dp[0][0] = 1; for(int i=1;i<=n;i++){ if(arr[i-1]){ sum[0] = dp[i-1][0]; for...

題目連結: http://tioj.infor.org/problems/1134 想了想覺得把1換成-1, 0換成1之後會有好事情，然後似乎可以做類似最大子矩陣的方式，但是我不知道該怎麼用。 被雷了之後才發現其實我只要把兩個問題合在一起就好了，一個是最大子矩陣，一個是某種找有多少大於零的序列的問題。首先我們可以先對一維用前綴和之後枚舉頂跟底，接著就變成一維的問題了，變成一維的問題後就是要問說對於所有大於零的序列中，最長是多少，作法也是考慮枚舉前綴和，每次只要查小於當前前綴和的所有鍵值中最小的值是多少，接著就把當前前綴和當做鍵值，現在的位置當作值插到某種資料結構就好了。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) const int N = 200 + 5; const int INF = 1<<30; class LiSan{ private: vector<int> vv; public: inline void init(){vv.clear();} inline void insert(int x){vv.push_back(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(int x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline int inv_get(int x){return vv[x];} ...

題目連結: http://poj.org/problem?id=1067 我通靈不出來，盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?，而且似乎有個1.6左右的比例，但我就不會了QAQ 正解是這個： 威佐夫遊戲 結論就是只要看符不符合$i 我缺少知識QQ #include <iostream> #include <cmath> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long double TongLing = (sqrt((long double)5)+1)/2; int n, m; while(cin>>n>>m){ if(n > m) swap(n, m); cout << ((int)((m-n)*TongLing) != n) << '\n'; } return 0; }

題目連結: http://codeforces.com/contest/912/problem/E 記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。 #include <bits/stdc++.h> using namespace std; typedef uint64_t llu; #define PB push_back #define ALL(x) begin(x), end(x) const llu C = 1000000000000000000LL; llu primes[20], p1[10], p2[10]; vector<llu> num1, num2; inline llu calc(llu); void dfs(int,llu,llu[],int,vector<llu>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>primes[i]; sort(primes, primes+n); int n1 = 0, n2 = 0; for(int i=0;i<n;i+=2) p1[n1++] = primes[i]; for(int i=1;i<n;i+=2) p2[n2++] = primes[i]; dfs(0, 1, p1, n1, num1); dfs(0, 1, p2, n2, num2); sort(A...

題目連結: http://codeforces.com/problemset/problem/839/D 超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ 首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; const int C = 1000000 + 5; const int MOD = 1000000007; int arr[N], cnt[C]; lld ans[C], two[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; two[0] = 1; for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD; for(int i=0;i<n;i++){ cin>>arr[i]; cnt[arr[i]]++; } for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){ cnt[i] += cnt[i*j]; } lld ret = 0; for(int i=C;i>=2;i--){ if(cnt[i]==0)...