<div class="post_brief"><p> 计算几何题。别人都用simpson搞。然后我决定不水一发，用hwd神犇在wc上讲的关键点法做。</p>   然后就搞到了12点半。发现坑数次。还专门用js写了个画圆的。当然我现在知道怎么画圆了。过两天去把oj7的统计图改一改。   思路是把所有圆的左右端点和所有圆的两两交的x提出来，unique一发（不然会tle显然的）。这样两个x之间的部分的圆弧是不会有交的。那么就可以视为一堆弓形和梯形了。然后扫描一下中位线的有效长度算梯形。每次新进入一个连通区域和出来的时候加相应弓形的面积。   需要注意按y排序的时候是按弓形与竖线的交点的y，而不是梯形的y，否则会有非常神奇的精度误差。另外算弓形面积必需要用反三角函数（至少我没研究出怎么不用）。如果用acos的话会暴精度暴得很惨。要用atan2来提高精度。   然后这样写连样例都会tle。仔细感受一下发现好像如果有一堆同心圆的话都会tle。然后考虑去掉包含的圆之后似乎就快了。然后就交了，然后居然跑过了。   然后来欣赏一下我的时间巨大，空间巨大，长度巨大。挤在一堆simpson里显得特别郁闷的代码。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const double eps = 1e-8; const double pi = acos(-1); 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; geo_obj() {} geo_obj(double xo, double yo) { x = xo, y = yo; } inline void read() { scanf("%lf%lf", &x, &y); } inline geo_obj vertical() { return geo_obj(-y, x); } inline double len() { return sqrt(sqr(x) + sqr(y)); } } point, vect; inline geo_obj operator +(const geo_obj& a, const geo_obj& b) { return geo_obj(a....

<div class="post_brief"><p> 比较神奇的数学题。首先你要知道这个函数的意思是把它的二进制flip。至于怎么来的我也是听说的。然后推一下发现的确是这么回事。</p>   于是就变成数位dp了。然后我发现数位dp常常可以用奇奇怪怪的方法水过去。然后又发现数组从0开始标号也会造成麻烦。+1-1啥的最讨厌了。   于是这题就变成高精度练习题了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 409; struct BigInt { int l, a[maxn], base; BigInt(int b = 10) { l = 0; base = b; } void push() { for (int i = 0; i < l - 1; ++ i) { a[i + 1] += a[i] / base; a[i] %= base; } for (; a[l - 1] >= base; ++ l) { a[l] = a[l - 1] / base; a[l - 1] %= base; } } void pull() { for (; l && !...

<div class="post_brief"><p> 第六百道题一定要不水！虽然离第一页还有几十道题的距离。</p>   很早之前见过的题吧。然后一直觉得特别难写所以都没写。以前写点不重复的仙人掌都觉得挺痛苦，更不要说这个了。   现在想想还行，因为我yy出了化简的方法。先搞出dfs树。然后一个顶点如果是一个环里深度最浅的，那么称它为这个环的头。可以证明一个顶点最多在一个不以它为头的环上。把这个环记下来，其它的环都从这个顶点去找边来找就行了。这样的话可以比较节省代码量，写起来也比较明了。虽然还是比mhy长。   然后因为我在最后一步dp的时候写了一个static的f数组，所以光荣了。debug了好久。晕。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, av; edge *next, *rv; }; struct ball { int l, *a, h; }; const int maxn = 50009; const int maxm = 200009; const int maxarr = 400009; int n, m, cb, fb[maxn], d[maxn]; int f[maxn], ans, fd[maxn], fe[maxn]; int stc[maxn], tst; int ibuf_arr[maxarr], *ibuf(ibuf_arr); bool vis[maxn]; edge elst[maxm], *ep(elst), *head[maxn]; ball b[maxm];...

<div class="post_brief"><p> 最初感觉好多状态怎么做。</p>   然后发现（其实是瞟了一下题解）如果把一个数分成2a*3b*c，那么c只影响上界。2a*3b中a最大是16，b最大是10，列一张17*11的表出来，然后发现右下方还有很多空东西。于是直接像插头一样状压一下轮廓线呗。反正对一个数有影响的只有它的上面和左边。最近写插头写得有点疯啊。其实它的很多思想都是可以推广出来用的。比如最小表示啥的。   于是如果直接这样写的话大概要跑30000多次dp，还是比较悬。然后再想想发现只有表里能取的数的形状发生改变的时候才会改变dp的答案。表里面的数很少所以改变次数也应该很少。所以记一下上一次的形状是什么然后比较相不相同，相同就直接沿用。   然后跑得飞快。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) #define pow2(x) (1<<(x)) const int maxn = 19; const int maxm = 15; const int maxv = 100000; const int maxst = pow2(11) + 9; const int mod = 1e9 + 1; int f[2][maxst], vl[maxn][maxm], n, m, v; int dis[maxn], ldis[maxn], lans, ans; void pre() { for (int i = 0; i < maxn; ++ i) { vl[i][0] = (1 << i); if (vl[i][0] > maxv) vl[i][0] = -1; for (int j = 1; j < maxm; ++ j) if (vl[i][j - 1] > -1) { vl[i][j] = vl[i][j - 1] * 3; if (vl[i][j] > maxv) vl[i][j] = -1; } else vl[i][j] = -1; } }...

<div class="post_brief"><p> 好吧我的本意是想学习一下dp的。然后发现了这道纠结了一年半还多的题。</p>   首先把环找出来。然后环上会长一些树。先把树的答案求了，因为它很好求。   然后考虑环，那么答案应该是随便断一条边之后答案的最小值（而不是最大值）。于是乎记录一下每个点按某个方向到起点的距离，记为d[i]。算一下每个点的树的深度，记为l[i]。于是每次要最大化l[i]+l[j]+|d[i]-d[j]|。反正是最大化所以顺序是没有关系的，但是不能自交。这是个比较容易错的地方。于是就去写个线段树来维护吧。只查询不修改让我总有能线性搞的想法，虽然没想清楚具体怎么实现。   #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; struct edge { int t, v; edge *next; }; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 100009; edge elst[maxn << 1], *ep(elst), *head[maxn]; int n, fa[maxn], df[maxn], ol[maxn], d[maxn]; int tlp, lp[maxn << 1]; dint lv[maxn << 1], le[maxn << 1], md[maxn], ans;...

<div class="post_brief"><p> 看上去比较不可做的DP。好像别人写的记搜跑得飞快。</p>   我看我是写最小表示写上瘾了。   压一下状态，有点像今天第二题。算每种值的有多少。然后直接跑。   感觉废状态比较多啊，跑得好慢。另外用memset清空高维数组会比较快。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int mod = 1e9 + 7; const int maxn = 17; const int maxst = 16009; #define mbit(a,b) ((a)<<((b)<<2)) #define gbit(a,b) (((a)>>((b)<<2))&0xf) #define _l (long long int) int m, c[maxn], n, mt, tots, slst[maxst]; int f[2][7][maxst]; void dfsState(int t, int l, int v) { if (l == mt + 1) { slst[tots ++] = v | t; } else { for (int i = 0; i <= t; ++ i) dfsState(t - i, l + 1, v | mbit(i, l)); } }...

<div class="post_brief"><p> 今天考试题的弱化版。只用求LCA是谁，不用求它的深度。所以直接用线段树找下区间最值就搞定了。然后long的范围有负数坑了一发。</p>   好像在不平衡的平衡树上的题也比较热啊。而且我还做得比较少。是要补一补。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef pair <int, int> vpr; typedef pair <bool, vpr> dpr; struct seg { int l, r; dpr d; seg *ls, *rs; }; struct query { int t, a, b; }; const int maxn = 400009; int n, m, vl[maxn], tv; vpr a[maxn]; query q[maxn]; seg slst[maxn * 3], *sp(slst), *rt; inline int gpos(int x) { return lower_bound(vl, vl + tv, x) - vl; }...

<div class="post_brief"><p> 我的第二道插头DP。差不多纠结了一天。</p>   这道题网上的题解都讲的好简略啊。最后还得自己yy。没有用括号序列法让我觉得自己比较厉害。   考虑轮廓线上的m个格子，有3种情况：没有插头，有且只能往一边走，有且要往两边走。对于第二种，要用最多3个不同的值来记录连通性。还要有两个不同的值来表示第一种情况和第三种情况。我比较懒，所以直接用一个八进制数去表示，然后每次二分找编号。   考虑转移，分一堆情况进行讨论。默认从左上朝右下走。   首先是要走当前格子的情况。   如果左边和上面都有插头，那么看它们是否连通。如果不连通则把它们连通，如果已经连通，看是否还有其它插头。没有就更新答案，否则忽略。   如果只有左边有插头，再分类。如果它是第二种，那么这个格子可以新建一个第三种插头，或者把左边格子的插头接过来。如果它是第三种那么它必需把左边格子接过来。   如果只有上面有插头，那么必需把上面的插头接上来。   如果左边和上面都没有插头，那么可以新建一个第三种插头。   然后如果不走这个格子的话，要求上面没有插头，且左边不是第三种插头。   按mhy的话说，插头dp就是写起来很麻烦。的确。不过写出来也还是挺高兴的。   然后代码丑到不能看了。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 109; const int maxm = 9; const int maxst = 50009; const int inf = 0x3f3f3f3f; #define pow8(x) (1<<(x)<<(x)<<(x)) #define mbit(x,y) ((x)<<(y)<<(y)<<(y)) #define gbit(x,y) (((x)>>(y)>>(y)>>(y))&7) int f[2][maxst], n, m, a[maxn][maxm], ans; int slst[maxst], tots;...

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