<div class="post_brief"><p> 我以为是最大权闭合子图来着。然后好像就直接最小割就行了吧。突然觉得我的网络流好弱。</p>   建源汇，分别连每个作物。对于每个组合建两个点分别边源汇，然后中间像源汇一样连它的成员。如果全在一边，那么会有一条边不用割。这也是一个集合都选对答案有贡献的建图方式。   然后就完了。建图和dinic都写得有些丑，所以调了半天。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, c; edge *next, *rv; }; const int maxn = 3009; const int inf = 0x3f3f3f3f; int n, m, c, d[maxn], t, st, te; edge *head[maxn]; inline edge* newEdge(int u, int v, int c) { edge* e(new edge); e-> t = v; e-> c = c; e-> next = head[u]; return head[u] = e; } inline void addEdge(int u, int v, int c) { edge *a(newEdge(u, v, c)), *b(newEdge(v, u, 0)); a-> rv = b; b-> rv = a; }...

<div class="post_brief"><p> usaco的银组都开始考这种题了么。其实还是挺水的，不过题号比较好。</p>   就按y排序，挨个把时间轴上的东西扔掉就完了。写离散可能还没有直接写smt快呢。   然后线段有一边要减1有点坑。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) struct cow { int y; int ta, tb; }; struct node { int l, r, w; node ls, rs; }; typedef pair <node, node > npr; const int maxn = 50009; inline bool operator <(const cow& a, const cow& b) { return a....

<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 (!...

<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];...

<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....

<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;...

<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....

<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", &amp;n, &amp;m); memset(w, 0, sizeof(w)); t = n * (n - 1) * (n - 2) / 6; for (int i = 0; i &lt; m; ++ i) { int u, v; scanf("%d%d", &amp;u, &amp;v); ++ w[u]; ++ w[v]; } c = 0; for (int i = 1; i &lt;= n; ++ i) c += w[i] * (n - w[i] - 1); c &gt;&gt;= 1; printf("%d\n", t - c); }

<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];...

<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....