【黑科技合集】Tech
Enzo2
posted @ 2015年4月15日 22:16
in 未分类
, 302 阅读
黑科技就是处理一些问题的特殊技巧。
【1】两条路径在树上的交【from CF500G】
int depmax(int x, int y){return dep[x] > dep[y] ? x : y;} int pathsection(int a, int b, int c, int d, int &e, int &f) { int u = lca(a, b), v = lca(c, d); if(dep[u] > dep[v]) swap(a, c), swap(b, d), swap(u, v); if(lca(u, v) != u) return 0; e = depmax(lca(a, c), lca(a, d)); f = depmax(lca(b, c), lca(b, d)); if(max(dep[e], dep[f]) < dep[v]) return 0; e = depmax(e, v), f = depmax(f, v); return 1; }
【2】处理\( L\le Dx \le R \) (\(Mod\) \(M\))下的最小自然数解【from CF500G】
LL G(LL M, LL D, LL L, LL R) // L <= Dx <= R (Mod M) { if((L-1)/gcd(D,M) >= R/gcd(D,M)) return -1; if(D+D>M) return G(M, M-D, M-R, M-L); if((L-1)/D < R/D) return (L+D-1)/D; LL t=G(D, (D-M%D)%D, L%D, R%D); return (L+M*t+D-1)/D; }