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

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

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