补昨天的题。 比较好想的计算几何。就看每个点在不在另一个颜色的点形成的上凸壳下面，下凸壳上面。这个用二分可以做到单次log。用单调应该也能O(n)。 但是写起来非常坑，要用long long，还有各种等号啥的。 写win32 app来显示点的代码比交上去的代码还长。开心。      #include <cstdio> #include <algorithm>   usingnamespacestd;   typedeflonglongqw;   #define _l (qw)   structpoint {     intx, y;     point (intx0 = 0, inty0 = 0) {         x = x0, y = y0;     }     inlinevoidread() {         scanf("%d%d", &x, &y);     } }; structvect {     intx, y;     vect(intx0 = 0, inty0 = 0) {         x = x0, y = y0;     }     vect(constpoint& a, constpoint& b) {...

因为运动会，好像时间又变少了。 早上本来想补觉来着，打开电脑就睡不着了。 上午先补题吧。 然后今天就去刷图论好了。最小生成树啊最短路啊还有各种神奇的东西都去写一写。 美好的一天。

本来以为是上回那道数正方形的原题的。结果发现不要求边与座标轴平行，于是我就naive了。然后数据结构变身计算几何一堆东西吼吼。 矩形的对角线相等且互相平分（来自初二数学书）。把所有点对的中点找出来，把所有相等且平分的放一起用单调性，有点像旋转卡(qia3)壳(qiao4)的做法。jason_yu说暴力枚举都能过，而且他跑得比我快！ 计算几何也写得比较naive。调了半天啊。 毕竟我弱嘛。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) const double eps = 1e-8; const int maxn = 1509; #define sqr(x) ((x)*(x)) #define dist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y)) #define nextele(_x_) ((_x_+1==r)?(l):(_x_+1)) struct point { qw x, y; point(qw x0 = 0, qw y0 = 0) { x = x0, y = y0; } inline point operator =(const point& a) {...

找到一道水题真是一件令人开心的事情。 最小生成树。完了。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define sqr(x) ((x)*(x)) struct edge { int a, b, v; edge(int a0 = 0, int b0 = 0, int v0 = 0) { a = a0, b = b0, v = v0; } }; const int maxn = 1009; int n, m, a[maxn], t, x[maxn], y[maxn], r[maxn]; edge e[maxn * maxn]; inline bool cmpE(const edge& a, const edge& b) { return a. v < b....

好端端的上午被体检腰斩了。 早上先花两节课继续复习数学吧。 然后去写图论。 下午爬梯子和bzoj。还有高一小朋友的图论基础（虽然多半听不到两分钟就受不了了）。 然后晚上还要考试好开心。

大概也不是很难。毕竟只有做水题的份。 就把原来的土地按x排个序，把能合并的合并，变成一个x单增y单减的序列。 然后就是dp。f[i] = min(f[j] + y[j+1]*x[i])，可以单调的斜率优化。 符号比较郁闷还搞错了好几次。 所以说我太弱了啊怎么办啊。 #include <cstdio> #include <algorithm> using namespace std; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define _f (exf) struct field { int x, y; }; inline bool cmpField(const field& a, const field& b) { return (a. x < b. x) || (a. x == b. x && a. y < b. y); }...

感觉几百年没有刷bzoj了？虽然昨天才写了题，下午也还交了题的。 还是挺水的一道矩阵题。看到数列想得到矩阵，不知道没看到数列能不能想到矩阵。 关键是求和比较不好想。其实新加一行把和记下来就行了。重点就是构造对吧。 然后矩阵快速幂啥的还好。主要是要记得快速乘。（想起了zhx的babysit） #include <iostream> #ifndef ONLINE_JUDGE #include <fstream> #define cin _cin_ std :: ifstream cin("in.txt"); #endif #include <algorithm> using namespace std; typedef long long qw; const int maxn = 19; qw n, b[maxn], c[maxn], x, y, mod; qw modMul(qw a, qw b) { qw s = 0; for (; b; b >>= 1, a = (a << 1) % mod) if (b & 1) s = (s + a) % mod; return s; } class matrix {...

突然感到noip已经很近了。 恐怕只剩下一周自己刷题了。 现在还没补完的专题？数学和图论。 今天先搞点数学题吧。 上午下午都用来刷cv好了。 晚上么，bzoj。

题意是严格次小生成树。 想了一下发现应该是一条不在最小生成树上的边构成的环上替换一条边就行了。感觉好想noi那道lct，哈。其实不用那么复杂的。 就用倍增就可以了。不过我还是比较倾向于用链剖。感觉链剖空间小而且写起来倍爽。不像倍增写挂了不只一次了。 要注意的是不仅要找最大值还要找严格次大值，因为要找严格次小。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct edge_g { int a, b, v, mk; }; struct edge_t { int t, v; edge_t *next; }; struct dat { int a, b; dat(int v0 = -1) { a = v0, b = -1; } dat(int a0, int b0) { a = a0, b = b0;...

居然继续沦落到写CV的题解的地步了。 这又是一道坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑题。 思路很简单。就是记a的列前缀和和b的行前缀和，每次询问的时候O(n)的扫一遍乘积累和。 但是，极限数据本地要跑3.2s。虽然我笔记本是慢，但是也不能这样玩我啊。交了好久都在tle。 最后想到一个常数优化的办法。因为每次是把一行或者一列的数都访问一遍，所以用一个指针把数组的那一行记下来。这样寻址会快一些。事实证明快了不只一些。 坑，哈哈。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 2001; int a[maxn][maxn], b[maxn][maxn], n, m; int main() { readInt(n);...