比较神奇的一道树的题。 做法是离线。想了好久的在线啊。 把询问拆成0~l-1和0~r。挨个从0开始加点。加点就是把从根到这个点的所有点权+1，询问就是询问这个点到根的点权和。好机智的做法。 代码还比较舒服。dfs+树链剖分+树状数组。 #include <cstdio> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct query { int p, v, n, c; inline query(int p0 = 0, int v0 = 0, int n0 = 0, int c0 = 0) { p = p0, v = v0, n = n0, c = c0; } }; const int maxn = 50009; const int mod = 201314;...
一堆标记的线段树。 翻过的，没翻过的，都分开记下来。然后还要注意flip标记与set标记的优先级关系和互相之间的影响。然后就完了。 虽说在这个颓废的下午还是花了好一会才调通。 #include <cstdio> #include <algorithm> using namespace std; struct dat { int l, r, s, t, m; }; struct seg { int l, r, f, z; dat d[2]; seg *ls, *rs; }; const int maxn = 100009; seg *rt, *sp; int n, m, a[maxn]; inline dat sgd(int v, int s = 1) { dat r; r. l = s * v; r. r = s * v; r. s = s * v;...
数据结构题总是很令人开心的。 这题据说可以主席树？好麻烦的说。 树链剖分+线段树+treap就好了吧。 #include <cstdio> #include <cstdlib> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, v; seg *ls, *rs; }; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 80009; const int maxv = 1e8; namespace treap {...
啊啊看到动态树被吓尿了。 然后发现动的不是树的形态是点权。 树链剖分+dfs序么。 重点是我TLE了。 最初的写法是直接查询然后把访问过的点打个标记。一个询问做完再标记回去。然后，tle。 参考jason_yu的做法，找出所有dfs序上要询问的区间，合并之后询问，应该不会tle了吧？还是tle。 最后发现是线段树lazy标记的地方写成n^2了。开心啊。 事实证明第一种写法12秒左右，第二种写法3秒多。当然也要考虑我巨丑的常数。 所以我还是太naive了。 代码当然要粘快的。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, a, v; seg *ls, *rs; }; struct rect { int l, r; inline rect(int l0 = 0, int r0 = 0) { l = l0, r = r0; } inline rect operator +(const rect& a) const {...
比较神奇的数学题。 重要的结论是<n且与n素质的数的和是phi(n)*n/2。 所以就枚举一下gcd就好了。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 1000009; qw ans[maxn]; int tp, pn[maxn], phi[maxn]; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr));...
补昨天的题。 比较好想的计算几何。就看每个点在不在另一个颜色的点形成的上凸壳下面，下凸壳上面。这个用二分可以做到单次log。用单调应该也能O(n)。 但是写起来非常坑，要用long long，还有各种等号啥的。 写win32 app来显示点的代码比交上去的代码还长。开心。 #include <cstdio> #include <algorithm> usingnamespacestd; typedeflonglongqw; #define _l (qw) structpoint { intx, y; point (intx0 = 0, inty0 = 0) { x = x0, y = y0; } inlinevoidread() { scanf("%d%d", &x, &y); } }; structvect { intx, y; vect(intx0 = 0, inty0 = 0) { x = x0, y = y0; } vect(constpoint& a, constpoint& b) {...
本来以为是上回那道数正方形的原题的。结果发现不要求边与座标轴平行，于是我就naive了。然后数据结构变身计算几何一堆东西吼吼。 矩形的对角线相等且互相平分（来自初二数学书）。把所有点对的中点找出来，把所有相等且平分的放一起用单调性，有点像旋转卡(qia3)壳(qiao4)的做法。jason_yu说暴力枚举都能过，而且他跑得比我快！ 计算几何也写得比较naive。调了半天啊。 毕竟我弱嘛。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) const double eps = 1e-8; const int maxn = 1509; #define sqr(x) ((x)*(x)) #define dist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y)) #define nextele(_x_) ((_x_+1==r)?(l):(_x_+1)) struct point { qw x, y; point(qw x0 = 0, qw y0 = 0) { x = x0, y = y0; } inline point operator =(const point& a) {...
找到一道水题真是一件令人开心的事情。 最小生成树。完了。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define sqr(x) ((x)*(x)) struct edge { int a, b, v; edge(int a0 = 0, int b0 = 0, int v0 = 0) { a = a0, b = b0, v = v0; } }; const int maxn = 1009; int n, m, a[maxn], t, x[maxn], y[maxn], r[maxn]; edge e[maxn * maxn]; inline bool cmpE(const edge& a, const edge& b) { return a. v < b....
大概也不是很难。毕竟只有做水题的份。 就把原来的土地按x排个序，把能合并的合并，变成一个x单增y单减的序列。 然后就是dp。f[i] = min(f[j] + y[j+1]*x[i])，可以单调的斜率优化。 符号比较郁闷还搞错了好几次。 所以说我太弱了啊怎么办啊。 #include <cstdio> #include <algorithm> using namespace std; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define _f (exf) struct field { int x, y; }; inline bool cmpField(const field& a, const field& b) { return (a. x < b. x) || (a. x == b. x && a. y < b. y); }...
感觉几百年没有刷bzoj了？虽然昨天才写了题，下午也还交了题的。 还是挺水的一道矩阵题。看到数列想得到矩阵，不知道没看到数列能不能想到矩阵。 关键是求和比较不好想。其实新加一行把和记下来就行了。重点就是构造对吧。 然后矩阵快速幂啥的还好。主要是要记得快速乘。（想起了zhx的babysit） #include <iostream> #ifndef ONLINE_JUDGE #include <fstream> #define cin _cin_ std :: ifstream cin("in.txt"); #endif #include <algorithm> using namespace std; typedef long long qw; const int maxn = 19; qw n, b[maxn], c[maxn], x, y, mod; qw modMul(qw a, qw b) { qw s = 0; for (; b; b >>= 1, a = (a << 1) % mod) if (b & 1) s = (s + a) % mod; return s; } class matrix {...