优化方法暑假的时候zhx讲过，我居然还记得好感动。 Mobius反演加些奇异的东西。（不会用公式编辑器是不是已经落伍了） 两个优化-> sqrt(n)^2 == n。 跑得飞慢 。而且中间那坨又长又丑。 久了不写都快忘了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int maxn = 10000009; const int mod = 20101009; int pn[maxn], mu[maxn], smu[maxn], tp; bool pr[maxn]; void pre(int maxn) { memset(pr, 0, sizeof(pr)); tp = 0; mu[1] = 1; for (int i = 2; i <= maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; mu[i] = -1; } for (int j = 0; j < tp && i * pn[j] <= maxn; ++ j) {...

题意：求n!在b进制下的位数（n<=2^31）。 好像要高精！？好像会TLE！？根本不会做！ 然后想到answer=∑log(k,i) 然后积分？∫ln(x) dx = xln(x) - x 小数据直接跑，过之。试个极限数据，差了3！？ 仔细一想，对数函数是凹的，这样算答案当然会偏小。 百度了一下，发现有个公式：n!≈√(2*π*n)*(n/e)^n。 拆开之后发现就是比原来的积分多了个ln(2*π*n) #include <cstdio> #include <cmath> const double pi = asin(1) * 2.0; double calc(double n, double k) { double ans = 0; if (n < 100000) { for (int i = 1; i <= n; ++ i) ans += log(i); ans /= log(k); } else { ans = (0.5 * log(pi * n * 2) + log(n) * n - n) / log(k); } return ans + 0.5; }...

好像数学都退化了。 其实一直没有用过中国剩余定理。虽然好像也不是太麻烦，不过要记住。 然后这题也比较裸吧。把C(n,m)中的阶乘分解成t*p^k的样子就好了。ORZ JASON_YU #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int mod = 999911659; const int pn[4] = {2, 3, 4679, 35617}; const int maxb = 50009; int n, g, fac[maxb], tf, s[4]; int t[maxb]; int modPow(int a, int x, int mod) { int s = 1; for (a %= mod; x; x >>= 1, a = _l a * a % mod)...

异常欢乐的并查集。馒头染色法。均摊O(n)的时间。 离线，先把每个染色操作会染黑哪些边算出来，把黑色子节点并到白色父节点里。 然后倒着处理，询问就直接用并查集问白色子节点顶上的黑色父节点最近是谁。染色操作再染回来。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, i; edge *next; }; struct query { int t, v, ans; int *b; }; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ _s_ = 0; \ while (!isdigit(_d_ = getchar())); \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 1000009; int n, m, d[maxn], fa[maxn], v[maxn], c[maxn], r[maxn];...

The input contains several test cases. 虽然我没看到这句话但也A了，什么情况。 a到b的路径xor=(a到根xor b到根) 水 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; const int maxn = 100009; const int maxl = 33; int n, v[maxn], fa[maxn], tr[maxn * maxl][2], tn; edge *head[maxn], *ep; inline void addEdge(int u, int v, int w) { ep-> t = v; ep-> v = w; ep-> next = head[u]; head[u] = ep ++;...

平衡树维护序列的老题。之前用SMT写过，不过在bzoj上就tle了。splay大法好。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } #define readStr(_s_) { \ char* _i_ = _s_; \ while (!islower(_d_ = getchar())); \ while ((*(_i_ ++) = _d_), islower(_d_ = getchar())); \ *(_i_) = 0; \ } #define _l (long long int) const int maxn = 300009; const int mod = 20130426;...

CDQ重构图。听上去比CDQ还高档的样子。 就是每层重新标号，把没有询问到的边拿来跑并查集。 最初是分开考虑然后可修复的并查集就T傻了。 #include <cstdio> #include <cstring> #include <cctype> #include <set> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 100009; const int maxm = 200009; const int maxl = 19; struct edge { int a, b, i; }; struct dset { int r[maxn], hp[maxn * 5], hv[maxn * 5], cnt;...

离散，然后树状数组+莫队。 最初用的是直接粘过来的1488的sbt，然后极限随机数据要跑14s。好郁闷。 然后改用数状数组就变1s了。是我再次把sbt写丑了还是它常数够厉害TT #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct query { int i, l, r, pl, pr; }; typedef unsigned int uint; const int maxn = 50009; #define update(_p_) (sz[_p_]=sz[ls[_p_]]+sz[rs[_p_]]+1) inline bool cmpQry(const query& a, const query& b) { return a. pl < b. pl || (a. pl == b. pl && a. pr > b. pr); } inline bool cmpP(int* a, int* b) { return *a < *b; } int n, m, bsz, a[maxn], *r[maxn], maxa, t[maxn];...

据说是男人八题。 状态太差调了一节宝贵的晚自习，严重不开心。 异常裸的点分治。然后里面还是套的sbt。 卡空间比较丧病，不能开nlogn，要想办法开到n。其实就是找重心分治完再bfs一遍。最初没有写，所以mle爽，在poj上还显示的是re。 然后各种逗的错误调啊调。把代码调得怪丑。我还是naive啊。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; const int maxn = 40009; int n, k, ans; int d[maxn], tvis, vis[maxn], vd[maxn], sz[maxn], qu[maxn]; edge *ep, *head[maxn], elst[maxn * 2]; #define update(_p_) (sz[_p_]=sz[ls[_p_]]+sz[rs[_p_]]+1) namespace sbt { const int maxnd = maxn * 2; const int balc = 5; int nst[maxnd], tn; int ls[maxnd], rs[maxnd], vl[maxnd], sz[maxnd]; inline void lRot(int& p) {...

jason_yu表示是kd-tree的裸题。 拿个堆维护一下答案，然后剪剪枝啥的，写起来轻松愉快还比lct短。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; typedef pair <qw, int> hele; #define _l (qw) int _d_; bool _nag_; #define readInt(_x_) { \ int &_s_ = _x_; \ _s_ = 0; \ _nag_ = 0; \ while (!isdigit(_d_ = getchar())) \ if (_d_ == '-') \ _nag_ = 1; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ if (_nag_) \ _s_ = - _s_;\ } const int maxn = 100009;...