The Site of laekov

BZOJ1455 罗马游戏

<div class="post_brief"><p> 左偏树+并查集的一眼题嘛。然后合并的时候搞忘了如果两个人已经在同一个团里要跳过，于是左偏树自交去了。</p> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define szof(p) ((p)?(p->sz):0) struct node { int sz, vl, id; node *ls, rs; node() {} node(int v, int i) { vl = v; id = i; sz = 1; ls = rs = 0; } inline void update() { if (szof(ls) < szof(rs)) swap(ls, rs); } }; node merge(node p, node q) { if (!p) return q; else if (!...

BZOJ1295 [SCOI2009]最长距离

<div class="post_brief"><p> 多老的省选题了。</p> 就处理一下任意两个格子之间最少要经过几个1，如果小于等于t就更新答案。 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; #define mkword(x,y) (((x)<<16)|(y)) #define hiword(x) ((x)>>16) #define loword(x) ((x)&0x0000ffff) const int maxn = 33; const int maxnd = 909; const int movx[4] = {0, 0, 1, -1}; const int movy[4] = {1, -1, 0, 0}; typedef pair <int, int> dpr; inline int sqr(int x) { return x * x; } int n, m, t, d[maxn][maxn], ans; int mp[maxn][maxn]; dpr hp[maxnd << 2];...

BZOJ3757 苹果树

<div class="post_brief"><p> 今天晚上的效率比白天高啊。</p> 树上莫队的另一道题。比糖果公园好写到哪里去了。然后手写链表丑掉了导致调试半天+RE了一发。我还是太年轻了。 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef struct node { int t; node *next; } edge; const int maxn = 50009; const int maxm = 100009; const int maxl = 17; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { if (a....

BZOJ1415 [Noi2005]聪聪和可可

<div class="post_brief"><p> 最近很颓啊。</p> 这题很久之前看过。当时以为是高消就没管。然后开坑之神idy做了之后仔细一想才知道不是。这题的做法是dp。首先因为边数少所以不用floyd，直接bfs预处理出所有t[i][j]表狼在i，兔子在j的时候狼下一步去哪。然后有一个结论是每一步两个玩意的距离至少缩短1，所以状态是不会有环的，这也是为啥可以不用高消。然后坑点是不能直接开状态队列，因为那不是拓补序。要先把每个点的入度算出来再跑dp。结局是我的代码超长。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; #define mkword(x,y) (((x)<<16)|(y)) #define hiword(x) ((x)>>16) #define loword(x) ((x)&0x0000ffff) const int maxn = 1009; const int maxst = 1000009; const int inf = 0x3f3f3f3f; int n, m, st, te, deg[maxn], d[maxn], t[maxn][maxn], ind[maxn][maxn]; edge elst[maxn << 1], *ep(elst), *head[maxn]; double f[maxn][maxn], g[maxn][maxn], c[maxn], ans;...

BZOJ3052 [wc2013]糖果公园

<div class="post_brief"><p> 盯idy发现的题，之前想学然后放弃了，于是今天几乎写了一天。有种紧迫感啊。然后发现好多认识的人都是最近过的。</p> 思路比较简单，树上莫队。因为要修改，所以要把块的大小变成n2/3，然后用1086的方法分块。好像也可以直接按dfs序分块。两个端点和时间为三个关键字跑莫队。复杂度可以感受一下反正我也不会证。要注意千万要控制LCA的用量，必需只能是O(n)级别的。在爬树的时候必需O(1)。我就是在移动时间的时候不小心手贱每次用一遍LCA，然后去检查在移动端点花了好久的时间。比较不开心的是发现mac没法改栈空间？有两个点始终暴栈。而且拿另一台电脑的openSUSE跑，结果发现它的cpu没有mac好，跑得还比mac快！我猜是操作系统在捣鬼。mac还是比较坑啊不开心。然后在bzoj上跑的时间几乎是本地的5倍也是比较厉害啊。 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; const int maxl = 19; typedef struct node { int t; node *next; } edge; node nlst[maxn], *np(nlst); struct chain { int sz; node *hd, *tl; chain() { hd = tl = 0; sz = 0; } inline void clear() { hd = tl = 0; sz = 0; } inline void push(int x) { np-> t = x; np-> next = 0; if (sz) { tl-> next = np; tl = np; } else { hd = np; tl = np; } ++ np; ++ sz; } inline void merge(chain a) { sz += a....

BZOJ2916 [Poi1997]Monochromatic Triangles

<div class="post_brief"><p> 每日一水。不过这题还比较有意思。最初没看清题，觉得没法数总三角形个数。</p> 同色=总-不同色。对于一个不同色，会有两个顶点的两边颜色不同。直接按照顶点统计一下不同色的边组数，然后减一下就完了。说好的糖果呢。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1009; int n, m, t, c, w[maxn]; int main() { #ifndef ONLINE_JUDGE //freopen(“in.txt”, “r”, stdin); #endif scanf("%d%d", &n, &m); memset(w, 0, sizeof(w)); t = n * (n - 1) * (n - 2) / 6; for (int i = 0; i < m; ++ i) { int u, v; scanf("%d%d", &u, &v); ++ w[u]; ++ w[v]; } c = 0; for (int i = 1; i <= n; ++ i) c += w[i] * (n - w[i] - 1); c >>= 1; printf("%d\n", t - c); }

BZOJ1180 [CROATIAN2009]OTOCI & BZOJ2843 极地旅行社

<div class="post_brief"><p> 难得的水水的双倍题。</p> 看上去是想考lct然后忘强制在线了么？那就直接预处理出形态然后链剖呗。当然我还没有达到mhy这种认为lct比tcd好写的水平。中间还把修改写挂了一次，然后1180的询问数是2843的3倍又re了一次。晕。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; struct seg { int l, r, s[2]; seg *ls, *rs; }; struct query { char o; int a, b, s; }; const int maxn = 30009; const int maxm = 300009; int n, m, r[maxn], d[maxn], v[maxn], u[maxn]; int fa[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn]; int qret[2]; seg slst[maxn << 2], *sp(slst), *rt[maxn]; edge elst[maxn << 1], *ep(elst), *head[maxn]; query q[maxm];...

BZOJ1822 [JSOI2010]Frozen Nova 冷冻波

<div class="post_brief"><p> 简单的算几+网络流么。然后花了将近两天。最近总和算几过不去啊。</p> 判断线段和圆是否有交还是比较简单的。反正不要让我用解析。先找下垂线，然后找下垂足，然后点乘一下搞定。然后错得不知道怎么死的。搞了很久。然后二分网络流水水水水水水水水。感觉mac好卡啊，gdb巨卡，bash也非常卡。难道我又没有搞对打开方式？ #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; inline long double sqr(long double x) { return x * x; } typedef struct geo_obj { double x, y; geo_obj() {} geo_obj(double x0, double y0) { x = x0, y = y0; } inline void read() { scanf("%lf%lf", &x, &y); } inline geo_obj rev() { return geo_obj(-y, x); } inline double len() { return sqrt(sqr(x) + sqr(y)); } inline double sqLen() { return sqr(x) + sqr(y); } } point, vect; inline geo_obj operator +(const geo_obj& a, const geo_obj& b) { return geo_obj(a....

BZOJ2157 旅游

<div class="post_brief"><p> 去找水题于是找到这么一道恶心的代码题。其实应该可以用函数指针来优化一下代码量，不过懒得了。虽然复制粘贴导致调试了老半天。</p> 水水的链剖+线段树。然后tag打一打就好了。最近是装备了高超的开坑技巧啊。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct seg { int l, r, s, a, b, rv; seg *ls, *rs; inline void update() { if (l + 1 < r) { s = ls-> s + rs-> s; a = min(ls-> a, rs-> a); b = max(ls-> b, rs-> b); if (rv) { s = -s; swap(a, b); a = -a; b = -b; } } else a = b = s; } inline void chgTag() { s = -s; swap(a, b); a = -a; b = -b; rv ^= 1; } inline void downTag() { if (rv) { rv = 0; if (l + 1 < r) { ls-> chgTag(); rs-> chgTag(); } } } }; struct edge { int t, v; edge *next; };...

BZOJ1845 [Cqoi2005] 三角形面积并

<div class="post_brief"><p> 比较基础的算几。当是hwd在wc的时候讲的东西拿来练练吧。（都过去多久了）</p> 算几的板比较长。然后记得还有道半平面交精度题至今没过！？什么效率。这题的思路比较简单。找出所有的关键x，分段。每段内都是一堆边不相交的梯形，那么答案=∑(▵x*∑中位线并的长度)。总时间复杂度到了O(n3)。不过n才100显然可过。至于n等于1000的题暂时不会啊。我太弱了。然后这题也有神奇的精度误差，答案要-1e-7才能过。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const double eps = 1e-7; inline int sgn(double x) { return (x > eps) - (x < -eps); } inline double sqr(double x) { return x * x; } typedef struct geo_obj { double x, y; inline geo_obj() {} inline geo_obj(double x0, double y0) { x = x0, y = y0; } inline void read() { scanf("%lf%lf", &x, &y); } } point, vect; inline geo_obj operator +(const geo_obj& a, const geo_obj& b) { return geo_obj(a....