<div class="post_brief"><p> 老久之前就看到过的题，不过不会做。今天晚上也是花了差不多俩小时才调过，虽然大概一个半小时都在纠结二分怎么写的问题。我没救了。</p>   考虑经典的中位数二分，是把≤x的数字取-1，>x的数取1，然后算最大子串看是否大于-1或1中的某一个，具体要看题目要求偶数是取上整还是下整什么的。   然后这题就把所有东西排序之后拿可持久化线段树把这个序列搞出来，然后照着之前的思路二分就好了。线段树用来维护最大和最小前缀和。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct dat { int sm, s; }; struct seg { int l, r; dat v[2]; seg *ls, *rs; }; #define _l (long long int) typedef pair <int, int> vpr; typedef dat(*dat_mf)(const dat&, const dat&); const int maxn = 20009; const int maxnd = maxn * 19; const dat null_str = {0, 0}; const dat neg_str0 = {-1, -1}; const dat neg_str1 = {-1, -1}; const dat pos_str0 = {1, 1}; const dat pos_str1 = {1, 1};...

<div class="post_brief"><p> ioi的数据结构题，果然还是比较BT的。</p>   做法是对颜色分开，大的颜色预处理，小的颜色直接暴力。   然后一个小错又坑了好久。我真的没救了。 #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int buf_len = 4000; const size_t buf_size = buf_len * sizeof(char); char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, buf_size, 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>   刚开始的时候比较naive，把相交的情况想简单了，打算直接上数学，然后悲剧地发现还有其它的不好算交点的情况，于是就去写simpson了。   simpson就是一个估计用的，s = (4 * f(mid) + f(l) + f(r))*(r-l)/6。至于为啥是对的就不知道了。反正比较能用。然后每次直接去扫一遍所有能交的地方，取max就行了，比挨个算交点方便许多。   然后第一次写，代码也比较乱。 #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 509; const double pi = asin(1) * 2; const double eps = 1e-6; #define x1 x1 #define x2 x2 #define y1 y1 #define y2 y2 int n; double tht, x[maxn], h[maxn], r[maxn]; double crd[maxn]; double x1[maxn], x2[maxn], y1[maxn], y2[maxn]; bool c[maxn];...

<div class="post_brief"><p> 听说是水水的splay，果然是。</p>   乍一看要用lct，然后因为度数只有2，所以肯定是一条链。然后就直接用splay来维护。然后因为少写了句splay(v)导致多调了至少一节课的时间。我没救了。 #include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; #define upmax(a,b) { if (a < b) a = b; } struct splay_node { int vl, vm, rv; splay_node *pt, *ls, *rs; inline void update() { vm = vl; if (ls) upmax(vm, ls-> vm); if (rs) upmax(vm, rs-> vm); } inline void fix() { if (rv) { swap(ls, rs); if (ls) ls-> rv ^= 1; if (rs) rs-> rv ^= 1; rv = 0; } } };...

<div class="post_brief"><p> 立杰出的题，orz。</p>   一个时间比较微妙的状压DP。用一个二进制状态表示0~k中哪些数已经可以被表示出来了，然后大于k的数直接乘，因为对状态不产生影响。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define pow2(x) (1<<(x)) #define _l (long long int) const int maxn = 21; const int maxb = pow2(maxn) + 9; const int mod = 1e9 + 7; int n, k, l, f[2][maxb], zu, va; #define incm(a,b) { a += b; if (a >= mod) a %= mod; } int sov() { int prv(0), cur(1); memset(f, 0, sizeof(f)); va = max(0, l - k) + 1; zu = pow2(k + 1) - 1; f[cur][1] = 1; for (int ti = 0; ti < n; ++ ti) { swap(cur, prv); for (int i = zu; i; – i) f[cur][i] = 0; for (int i = zu; i; – i) if (f[prv][i]) { for (int j = 1; j <= k; ++ j) { int zn((i | (i << j)) & zu); incm(f[cur][zn], f[prv][i]); } incm(f[cur][i], _l f[prv][i] * va % mod); } } int ans(0); for (int i = zu, e = pow2(k); i >= e; – i) incm(ans, f[cur][i]); return ans; }...

<div class="post_brief"><p> 灭绝树的模板题么。之前不知道这题，差点当原创题出出去了。</p>   好像有不少人不知道这东西的样子？orz zhx。   灭绝树只有一句口诀：一个东西的父亲是所有入边的另一端的点的LCA。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; const int maxn = 70009; const int maxl = 19; const int maxe = 2000009; int n, ind[maxn], oud[maxn], tpo[maxn], ath[maxn][maxl], sz[maxn], d[maxn]; edge *ha[maxn], *hr[maxn], *ht[maxn]; inline void addEdge(edge** head, int u, int v) { edge* ep = new edge; ep-> t = v; ep-> next = head[u]; head[u] = ep; }...

<div class="post_brief"><p> 原来在win下也有敲回车的bug。开心。</p>   这题坑啊。暴力还是很好想的，如果个数超过几十个的话就肯定有解了。比较坑的是两边之和大于第三边，边权231-1然后加起来就超过int的范围了。连WA若干次再见。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct edge { int t; edge *next; }; const int maxn = 100009; const int maxc = 88; int n, m, v[maxn], d[maxn], fa[maxn], c[maxc]; edge *head[maxn], elst[maxn << 1], *ep(elst); void bfs() { static int q[maxn]; int hd(0), tl(1); q[0] = 1; memset(d, 0, sizeof(d)); d[1] = 1; while (hd < tl) { int p(q[hd ++]); for (edge* e = head[p]; e; e = e-> next) if (!...

<div class="post_brief"><p> 记得这是高一的时候ty同学和我说的东西了。然后现在才解决，可以打败上帝造题的七分钟，荣登解决时间最长的题目了。</p>   其实也就是一个高斯消元，用电势来列方程。不过高斯消元写得不熟，平时有空都写ds的题去了。以后不能再这样了。   用自己的代码高亮脚本了，虽然还不完善不过还是很开心的。   #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; const int maxn = 109; const double inf = 1e100; const double eps = 1e-8; double x[maxn], a[maxn][maxn], b[maxn][maxn]; int n, m, perm[maxn]; int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif srand(19970911); while (scanf("%d%d", &amp;n, &amp;m) != EOF) { for (int i = 1; i &lt;= n; ++ i) perm[i] = i; if (n &gt; 2) random_shuffle(perm + 2, perm + n); for (int i = 1; i &lt;= n; ++ i) for (int j = 1; j &lt;= n; ++ j) if (i == j) a[i][j] = 0; else a[i][j] = inf; while (m --) { int u, v; double p; scanf("%d%d%lf", &amp;u, &amp;v, &amp;p); u = perm[u]; v = perm[v]; if (u == v) continue; a[u][v] = 1....

<div class="post_brief"><p> 决心写一道usaco之外的题，于是就挑中了这道。</p>   为啥这编辑器有BUG，每次按回车要向下跳？   发现可以预处理DP。f_i表示第i个数被砍完需要最少多少刀。对于每一个i，设p_i是它的质因子里最大的一个在给定集合里的，那么它可以转移到(i+1,i+p_i)这个范围。然后f_i显然不减，所以用单调队列之类的玩意。   然后卡着时间限制过了。不知道前面那些秒跑的人是怎么搞的。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10000009; const int maxm = 100009; int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm]; void pre(int n) { sort(p, p + m); memset(k, 0, sizeof(k)); for (int i = 0; i < m; ++ i) if (!i || p[i] != p[i - 1]) for (int j = 0; j <= n; j += p[i]) k[j] = p[i];...

<div class="post_brief"><p> 又搬blog。发现这里可以自定义css之后就果断了。</p>   写道水题试试。set的应用。然后还写丑WA了两次，我没救了。   代码高亮是坏了吗？不要吓我。   决定直接用oj7的代码版了，没有高亮就算了。 #include <cstdio> #include <algorithm> #include <set> using namespace std; typedef multiset <int> rb_tree; typedef rb_tree :: iterator rb_node; typedef pair <int, int> cow; const int maxn = 50009; int n, d, x[maxn], a[maxn], r[maxn]; cow c[maxn]; rb_tree t; int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif scanf("%d%d", &amp;n, &amp;d); for (int i = 1; i &lt;= n; ++ i) { scanf("%d%d", x + i, a + i); c[i] = cow(x[i], a[i]); r[i] = 0; } sort(c + 1, c + n + 1); for (int i = 1; i &lt;= n; ++ i) { x[i] = c[i]....