oToToT的code收藏區

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_e 題目大意: 給定 $c_i$ 代表可以用的數字種類，問在只用 $c_i$ 的情況下有多少 $N$ 位數是 $B$ 的倍數。 原本想暴力數位統計 DP 下去 ，但發現 $N$ 太大不能做，想了很久之後最後跑去看解答，我就爛= = 解答感覺也是一個很套路的東西，因為我們只要求 $N$ 位數而不是特定少於某個 $K$ 的數字，所以其實可以直接對 $N$ 倍增。初始狀態給的是 $1$ 位數的情況，那我們就可以倍增出 $2$ 位數的情況、$4$ 位數的情況、 $8$ 位數的情況...，對於 $N$ 位數，我們考慮它的二進位寫法，假設它是 $2^0 + 2^4 + 2^5$ 那我們就挑 $2^0$ 位數的情況、 $2^4$ 位數的情況、 $2^5$ 位數的情況來合併就好。 具體合併就是背包合併直接暴力枚舉高位跟低位分別模 $B$ 餘多少就好。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; using llu = uint64_t; constexpr int M = 3000 + 5; constexpr int N = 64; constexpr int MOD = 1'000'000'007; static inline int add(int x, int y, int mod = MOD) { return x + y >= mod ? x + y - mod : x + y; } static inline void adde(int &x, int y, int mod = MOD) { x += y; if (x >= mod) x -= mod; } static inline int mul(int64_t x, int64_t y, int mod = MOD) { return static_cast<int>(x * y % mo...

題目連結: http://codeforces.com/problemset/problem/208/E 稍微轉化一下問題就可以得到問節點$i$的子節點們深度為$d$的有那些，轉法也很簡單，對於一組詢問$(v, p)$就直接變成，對於$v$的$p$倍祖先問在$dep[v]$的數字有哪些(問一個人的$p$倍祖先可以直接用個倍增法做到)。轉化成這樣後就可以直接開個map維護每個深度為$k$時有幾個，然後要合併兩子樹就啟發式合併就好了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; typedef pair<int,int> PII; #define PB push_back #define FF first #define SS second class K_anc{ private: vector<int> G[N]; int anc[N][20]; void dfs(int w, int f){ anc[w][0]=f; for(auto i: G[w]) if(i!=f) dfs(i, w); } public: inline void AddEdge(int u, int v){ G[u].PB(v); G[v].PB(u); } void solve(int r, int maxn){ dfs(r, r); for(int j=1;j<20;j++) for(int i=0;i<maxn;i++){ anc[i][j] = anc[anc[i][j-1]][j-1]; ...

題目連結: http://tioj.infor.org/problems/1163 本題看似給定一張無向圖，實在不好求得所有路徑最大值的最小值，但是很明顯可以發現因為是要最小的最大值，所以其實先把最小生成樹找出來後，再在上面求路徑最大值就會是好的，而且如果是寫kruskal演算法，你還可以快速知道兩個點是不是連通的。而要求一棵樹上路徑的最大值，不難發現你可以把路徑拆成a到LCA(a,b)跟b到LCA(a,b) (其中LCA指的是最低共同祖先)，然後通常求LCA時會用倍增法，而這時就會發現其實求路徑最大值也可以用倍增法，一樣每次更新這段的最大值，然後找的時候也差不多。 p.s 比較好的講法可以看 這篇 #include <bits/stdc++.h> using namespace std; #define N 30000 #define logN 16 typedef pair<int,int> PII; int djs[N+5]; int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];} inline void Merge(int a,int b){djs[Query(a)]=Query(b);} struct Edge{ int s,e,p; bool operator>(const Edge& x)const{return p>x.p;} }; vector<PII> Tree[N+5]; int time_in[N+5], time_out[N+5],timer=0; PII ff[N+1][logN+1]; void dfs(int,int,int); inline bool anc(int,int); inline int lca(int,int); inline int getMax(int,int); bitset<N+5> walked; int main(){ ios_base::s...