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

<div class="post_brief"><p> 久了不写manacher又手生了只好抄红书了。</p>   后面的过程就是对每个位置i找一个最远的位置j满足j在i为中心的回文子串的一半以内且j最小。然后直接拿个set就能搞定。   #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; const int maxn = 500009; char a[maxn]; int d[maxn << 1], n; void manacher() { d[0] = 1; for (int i = 1, j = 0; i < (n << 1) - 1; ++ i) { int p(i >> 1), q(i - p), r(((j + 1) >> 1) + d[j] - 1); if (r < q) d[i] = 0; else d[i] = min(r - q + 1, d[(j << 1) - i]); while (p - d[i] >= 0 && q + d[i] < n && a[p - d[i]] == a[q + d[i]]) ++ d[i]; if (q + d[i] - 1 > r) j = i; } }...

<div class="post_brief"><p> 多少年前的坑了。</p>   用mac写的第一篇题解呢。   环套树DP。先把树上的情况处理了，然后枚举取不取环上的第一个。   要注意会有重边的情况，比较恶心。   #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4000; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; }...

<div class="post_brief"><p> 数据水。填坑。语文阅读题，看到都不想做。</p>   就一树形dp。f[i][j][k]表示第i个物品，上供j个，花k块钱的代价。背包转移是O(m2)的，因为是一棵树所以转移次数是O(n)的，但是还要考虑j最大为100。一个技巧是合并完所有的东西之后再考虑把上供的烧掉。虽然这样的复杂度还是有点高。   毕竟我还是太弱啊，居然又花了一个上午。（虽然睡到十点）   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, v; edge *next; }; const int maxm = 2009; const int maxn = 53; const int maxa = 103; int n, m, f[maxn][maxa][maxm], ans[maxm], vl[maxn], vmax[maxn]; bool lf[maxn], ir[maxn]; edge elst[maxn], *ep(elst), *head[maxn]; inline void addEdge(int u, int v, int w) { ep-> t = v; ep-> v = w; ep-> next = head[u]; head[u] = ep ++; }...

<div class="post_brief"><p> 插头DP的基础题。想插头DP都是将军没走的时候给我讲的了，距今有大半年了吧。mhy已经写了无数道了，我才开始写。唉，还是效率太低。</p>   插头DP的意思是把已经处理的部分的轮廓线上对后面状态有影响的东西状压下来，然后挨着处理每个格子的状态（比如方向，或者这里的地板怎么铺之类的）。   具体到这道题来说，考虑一个相邻格子之前的边，那么它可能没有连接两个相同的磁砖，有可能连接了两个还没有拐过弯的磁砖，有可能连接了两个已经拐过弯的磁砖，一共是3种情况，所以用一个三进制数把它压下来。然后直接一路转移过去就行了。要注意的是每行都处理完了之后要把最边上的那一条从右移动到左，所以还需要把所有的状态都改一下。   今天效率比较低，心不在焉，然后在最后一个转移的地方wa了大半天。插头DP的调试也比较麻烦。所以我还是naive。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 13; const int maxa = 109; const int maxs = 200009; const int mod = 20110520; bool mp[maxa][maxa]; int n, m, a[maxn], b[maxn], f[2][maxs]; #define fc f[cur] #define fp f[prv] #define doNothing ; inline void mInc(int& a, int b) { a += b; if (a >= mod) a %= mod; }...

<div class="post_brief"><p> 什么鬼。</p>   很好想的dp。f[i][j]表示深度不超过i且大小为j的二叉树的个数。转移是f[i][j] = ∑(f[i - 1][k] * f[i - 1][j - k - 1])。   然后直接暴力是O(n3)的。在spoj上能过在bzoj上不能过。在bzoj上得用记忆化搜索来减掉一些无用的东西。虽然我觉得很烦。   然后试图用fft，发现fft比暴力还慢。然后试图用fnt，然后发现fnt好像不能对1e9+7这种质数用。因为1e9+6只有来一个2。真悲伤。我还是太弱啊。   #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 609; const int mod = 1000000007; #define _l (long long int) int f[maxn][maxn]; int getf(int i, int j) { if (i == 0) return j <= 1; else if (j == 0) return 1; else if (f[i][j] == -1) { f[i][j] = 0; for (int k = 0; k < j; ++ k) f[i][j] = (f[i][j] + _l getf(i - 1, k) * getf(i - 1, j - k - 1)) % mod; } return f[i][j]; }...

<div class="post_brief"><p> 今天wc讲的题。主要其实是用拟阵来证明贪心的正确性。就构造一下就好了。不选的集合构成一个拟阵的基，如果基不能异或出0就是线性无关的。然后按照拟阵的贪心方法挨个加。</p>   策略是从大到小排个序能不选就不选，用异或消元来判断一下就好了。许久没有写了，还好没有搞忘。   代码还是比较短的，开心ing。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 109; int n, a[maxn], b[maxn], c[maxn], t; dint s; bool hasZero() { for (int i = 0; i < t; ++ i) b[i] = c[i]; for (int i = 31, j = 0; i >= 0 && j < t; – i) { for (int k = j; k < n; ++ k) if ((b[k] >> i) & 1) { swap(b[k], b[j]); break; } if ((b[j] >> i) & 1) { for (int k = j + 1; k < n; ++ k) if ((b[k] >> i) & 1) { b[k] ^= b[j]; if (!...

<div class="post_brief"><p> 有离线镜像还是能省不少流量。开心。不过流量还是用得飞快啊。</p>   这就是个cdq重构的题。学习了前几天xyz大爷讲的扔线段树的做法，省了不少代码。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { int v, c; node *next; }; struct seg { int l, r; node *head; seg *ls, *rs; }; const int maxa = 209; const int maxn = 40009; const int maxm = 10009; const int maxnd = maxn * 23; const int mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};...

<div class="post_brief"><p> bc的题。今天bc又挂了。这题没有写完，然后b题fst了。伤心啊。</p>   其实思路比较简单。直接链剖dfs序上把所有区间找出来swap就好了。不过代码实现起来还是比较麻烦的，很容易绕晕。加上smt久了没写手生了，于是就调了一晚上。唉，我还是太年轻了。   #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; struct node { int v, s, sz, w, rv; node ls, rs; inline void update() { sz = 1; s = v; if (ls) { sz += ls-> sz; s += ls-> s; } if (rs) { sz += rs-> sz; s += rs-> s; } } inline void fix() { if (rv) { swap(ls, rs); if (ls) ls-> rv ^= 1; if (rs) rs-> rv ^= 1; rv = 0; } } }; typedef pair <node, node> npr;...

<div class="post_brief"><p> 看mhy写了好几天了啊。然后研究了一下，居然过得比他早。</p>   首先敌人一定可以炸连续的一段。然后就是要看炸掉任意连续一段之后还有没有剩下的公共部分，既半平面交。   然后我yy出了一个半平面交的做法。找出一条基准直线，按方向顺时针方向排序。然后按照正常半平面交的方法根据栈顶两个元素和当前直线的位置关系判断是否需要退栈。然后当找到一条与基准直线的角度大于等于π的直线（直线是有向的，也可以说是成负角）且它把栈里退到只剩基准直线一条的时候，这些半平面没有交。否则这些半平面有交。   至于证明嘛，我也不会（挠头），毕竟是感受出来的。然后感觉这次代码写得比较漂亮，开心。   #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; inline double sqr(double x) { return x * x; } struct point { double x, y; inline point() {} inline point(double x0, double y0) { x = x0, y = y0; } inline void read() { scanf("%lf%lf", &x, &y); } }; struct vect { double x, y; inline vect() {} inline vect(double x0, double y0) { x = x0, y = y0; } inline vect(point a, point b) { x = b....