首先由均值不等式可以得到，min{a, b, c} <= 17，不妨假设最短的那条边为a。接下来考虑消除，答案肯定不会超过a，因为可以做若干次1*b*c的消除。

一开始看到这个结论我还是非常傻逼的以为，只要把需要消毒的每一片1*b*c都消毒即可，还傻傻问副队哪来的二分图……经过副队的教导才意识到这样不一定最优，比较科学的做法是：2^a枚举每层是否消掉，然后用a*1*c和a*b*1的片覆盖，也就是转成二维的最小棋盘覆盖。

所谓最小棋盘覆盖就是说，每次可以覆盖掉棋盘的一整行或一整列，问把所有标记点覆盖的最小次数。嗯，这个也不会做……Google了一下，看到搜索结果里面最小点覆盖和行列拆开这两个关键词才突然意识到，这不就是个水水的二分图匹配嘛。

考虑把所有行放在左边，所有列放在右边，然后如果(i, j)需要被覆盖，那么连边(Xi, Yj)。之后就是一个最小点覆盖的问题了（选择最少的点，使得每条边都至少有一个端点被选择），因为最小点覆盖=最大匹配，所以轻松做掉了。（这个时候突然很庆幸前不久刚学匈牙利，明显这种时候用匈牙利跑匹配比网络流省事多了=v=）

Orz福州一中lyk。

首先我们来看，对于每个询问，如果答案的分母是固定的话，那么变成了在树链上找两个点使得Yi+Qj最大，这个很简单吧，直接树链剖分然后线段树里面找两个最大的数。 好，其实，这个跟这题一点关系都没有。

但是我们可以二分答案`k`，那么问题变成了判定是否存在i, j使得
    (Yi+Qj)/(Xi+Pj) >= k
也就是
    k*Xi-Yi + k*Pj-Qj <= 0
因为加号左右基本是一样的，考虑左边，右边同理。不妨令
    B = k*Xi-Yi
也就是
    Yi = k*Xi - B
嗯，很像斜率优化，把(Xi, Yi)看成座标系上的点，那么实际上我们就是要在一堆点里面找到一个点使得截距-B最大

接下来就是维护凸壳了，我们只要先做树链剖分，顺便求出dfs序，然后按照dfs序建线段树。线段树节点[L, R]表示dfs序上[L, R]的点构成的上凸壳（其实这题要维护两个上凸壳，因为完全独立，所以也没什么好说的）。然后这题就解决了。

前言

前不久刚填完 sjtu 的夏令营报名表，怎么说呢，我个人一直对朴素的Word文档填表很反感。大概是上次因为帐户问题需要填 BudgetVM 的各种证明，这才发现国外比较通用的做法是使用可填式pdf或者word文档。 这类文档制作起来比较麻烦，但是对于填表人来说，个人感觉会方便许多 。

后来Google了一下如何制作可填式pdf，发现都要用Adobe Acrobat，印象中Adobe的东西都是很贵的，于是乎只好转向比较大众化的Word。因为目前大家Word版本都比较高，起码都2007了，所以本文就放弃doc格式，以Word 2010为例。

为什么需要FFT

我们都知道对于两个多项式f(x)和g(x)，朴素的方法计算它们的乘积h(x) = f(x) * g(x)需要O(n^2)的时间。这里隐含了一个条件：f(x)和g(x)都是系数形式表示的多项式，比如说： f(x) = a0x^0 + a1x^1 + a2x^2 + ... + an-1x^n-1 。

实际上多项式还有一种点值表示法，就是 f = {(p1, f(p1)), (p2, f(p2)), (p3, f(p3)), ..., (pn, f(pn))} ，也就是初中熟悉的待定系数法求多项式。这种看起来十分反人类的表示方法其实有一个非常大的好处：在两个多项式的采样点相同的时候，它们的四则运算都是O(n)的复杂度。比如说对于f = {(pi, f(pi))}和g = {(pi, g(pi))}，求h = f*g，那么很容易得到h = {(pi, f(pi)*g(pi))}，也就是x不变，y相乘。

于是，就有了一种比较曲折的计算f(x)*g(x)的方法：

1. 对f(x)和g(x)求值（系数形式转成点值形式 DFT）
2. 在f和g点值形式上进行乘法得到h
3. 对h插值，得到h(x)（点值形式转成系数形式 IDFT）

对于朴素方法，上面三步的复杂度分别为O(n^2), O(n), O(n^3)，然而巧妙的使用单位负根可以使复杂度变成O(nlogn), O(n), O(nlogn)，赶快去膜拜傅立叶大神吧！

什么时候需要多项式乘法呢？比如高精乘，比如卷积（h[i] = f[j]*g[i-j]）

Discrete Fourier Transform

DFT的作用就是把一个系数形式的多项式转换成点值形式。IDFT就是反过来。FFT和IFFT实际上就是用O(nlogn)的时间完成DFT和IDFT。

终于用了一整天的时间，把博客从Wordpress换到了Octopress。我是希望在本地能不装ruby但是服务器能自动更新，并且希望支持历史版本，在网上找了一整天也试了一整天，整理出下面代码备忘：

1
2
3
4
5
6

server$ cd ~
server$ mkdir oi.abcdabcd987.com.git
server$ cd oi.abcdabcd987.com.git
server$ git init --bare
server$ pwd
/home/quartergeek/oi.abcdabcd987.com.git

1
2
3
4
5
6
7
8
9
10
11

server$ cd /tmp
server$ git clone git://github.com/imathis/octopress.git octopress
server$ cd octopress
server$ bundle install
server$ rake install
server$ git add .
server$ git commit -m 'init octopress'
server$ git remote rename origin octopress
server$ git remote add origin /home/quartergeek/oi.abcdabcd987.com.git
server$ git config branch.master.remote origin
server$ git push origin master

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

server$ cd /home/quartergeek/oi.abcdabcd987.com.git
server$ echo <<EOF > hooks/post-receive
> #!/bin/bash -l
> GIT_REPO=/home/quartergeek/oi.abcdabcd987.com.git
> TMP_GIT_CLONE=/tmp/oi.abcdabcd987.com
> PUBLIC_WWW=/home/wwwroot/oi.abcdabcd987.com/octopress
> 
> git clone $GIT_REPO $TMP_GIT_CLONE
> cd $TMP_GIT_CLONE
> bundle install
> time rake generate
> cp -Rf public/* $PUBLIC_WWW
> rm -Rf $TMP_GIT_CLONE
> exit
> EOF
server$ chmod +x hooks/post-receive

1
2
3
4
5

laptop$ git clone ssh://quartergeek@209.141.57.185/home/quartergeek/oi.abcdabcd987.com.git
laptop$ cd oi.abcdabcd987.com
laptop$ vim _config.yml
laptop$ vim source/_posts/2013-05-18-deploy-octopress-git-on-vps.markdown
laptop$ git push

简介

LocalOrz是一个运行于Linux，类似于Cena的本地评测机。目前 LocalOrz 仍属于开发阶段，本来我也不想这么早把它放出来，但是考虑到接下来得认真准备NOI，可能没什么时间继续写，所以还是只能先放出来。好在核心的功能都是有的。

首先列出它现在支持的功能：

• 支持添加编译器和修改编译器选项
• 支持数据路径自动完成
• 支持自动添加其他数据
• 支持评测全部选手
• 支持评测某个选手的单题
• 支持多个输入文件的测试点（未经测试）
• 支持需要额外文件的题目（比如交互式。未经测试）
• 支持Special Judge
• 支持部分分

因为LocalOrz最初的设计目标就是代替Cena，所以Cena有的核心功能都有。当然还有很多Cena的其他功能来不及写，这个可能得等NOI忙完再说了（话说到时候我跟OI毛关系？）。我比较自豪的部分是做数据的部分，做数据很方便，鼠标点一点就能做完，像Cena一样。

这题很囧，去年被炫教抓到题目（虽然炫教抓到的是一维的），可惜我们学校的人恰好都没有去省队培训……唉……首先讲一下一维怎么做吧。

欧几里得说过gcd(a, b, c, d) = gcd(b-a, c-b, d-c, a)。嗯，所以我们就对数列进行差分，b[i] = a[i]-a[i-1]，这样我们在查询[L, R]的gcd的时候，只要查询gcd(a[L], gcd(b[L+1] ... b[R])即可，而修改的时候，只要修改a[L..R]和b[L], b[R+1]即可。这样做法就很明显了，用两个线段树分别维护a和b。实际上做的时候，维护a可以直接用树状数组维护前缀和sum：对区间[L, R]加c，等同于sum[L] += c, sum[R+1] -= c，查询i直接求sum[i]即可。

我们再来看一下二维的怎么做。。然后我们换一种维护的方法。因为题目要求一定会查询到守护者a[x, y]，所以我们以(x, y)为原点，建立直角座标系。二维的一样是得差分，对于第四象限的点：b[i, j] = a[i, j] - a[i-1, j] - a[i, j-1] + a[i-1, j-1]，其他三个象限类似。

• 原点的值：就是原点的值
• 座标轴上的值：用离原点比较远的那个点-和他相邻、离原点近的点
• 某个象限上的值：同理，用离原点远的点+离原点近的点-2个旁边的点。

查询的时候，很愉悦的在线段树里面查询[x1, y1]到[x2, y2]即可。

但是修改就很麻烦了，四个象限、座标轴、原点分别单点修改（有关象限的4个点，有关座标轴2个点，有关原点1个点）。

这题如果会拉格朗日乘数法的话，那就是裸题了。首先大概讲一下这题的意思。给定s[], k[], v'[], E，求一组v[]，满足E = sum{ k[i]*s[i]*(v[i]-v'[i])^2 }，并且使得t = sum{ s[i]/v[i] }最小。

很明显这个就是一个多元函数求最值的问题，拉格朗日乘数法就是解决这种问题的方法。

拉格朗日乘数法的核心是：对于多元函数f和约束方程g = 0，存在一个负数λ，使得∇f = λ ∇g，其中∇f为f的梯度向量，也就是对每个元取偏导构成的向量。所谓偏导，就是把某一个元看作是变量，其他的当作常量，求导数。然后，通过方程组∇f = λ ∇g以及g = 0就可以解出取最值的时候，所有变量的值了。

对于这题，可以得到：

-s1 / v1^2 = λ * 2 * k1 * s1 * (v1 - v'1)
-s2 / v2^2 = λ * 2 * k2 * s2 * (v2 - v'2)
...

sum{ ki * si * (vi - v'i) ^ 2 } = E

然后解这个方程组就可以解出vi和λ。但是解出来之后能干嘛呢？

发现其实有关gcd的题目还是挺多的，这里根据做题顺序写出8题。

[bzoj2818: Gcd] gcd(x,y)=质数, 1<=x,y<=n的对数

做这题的时候，懂得了一个非常重要的转化：求(x, y) = k, 1 <= x, y <= n的对数等于求(x, y) = 1, 1 <= x, y <= n/k的对数！所以，枚举每个质数p（线性筛素数的方法见：线性时间内筛素数和欧拉函数），然后求(x, y) = 1, 1 <= x, y <= n/p的个数。

那(x, y) = 1的个数如何求呢？其实就是求互质的数的个数。在[1, y]和y互质的数有phi(y)个，如果我们令x < y，那么答案就是sigma(phi(y))。因为x, y是等价的，所以答案*2，又因为(1, 1)只有一对，所以-1。最终答案为sigma(sigma(phi(n/prime[i])) * 2 - 1)。

这道题非常的有意思，它查询区间和，但是还不计重复。说实话，看到不计重复这种诡异的条件，往可持久化想了，然后完全就没了思路。Orz 网上各种题解。这题有一个比较仁慈的地方：没有修改操作！所以可以离线。

按照右端点排序询问。我们令s[i]为不重复的sum[i..x]，其中x在最外层循环中从1~n。x每前进一位，把s[last[x]+1]到s[x]全部加上a[x]，其中last[x]是x上一次出现的位置。现在，当x等于某一个询问的右端点r的时候，我们的询问[l, r]，相当于询问所有历史中（包括现在）出现的最大的s[k] (k <= r)。听到历史这个词，很容易想到可持久化数据结构，或者说二维数据结构（比如套一个时间维）。但是实际上，这题要求的历史，是从一开始的历史，而不是从某个时间点开始的，因此，还是可以直接使用线段树的。

线段树节点[L, R]记录四个东西：

max:     现在的s[L..R]中最大的一个
tag:     现在还有多少数没有下传给孩子
evermax: 历史到现在的s[L..R]中最大的一个
evertag: 从上一次清除tag到现在最大的tag

然后clear过程就是一个非常纠结的事情。

son.evertag = max(son.evertag, son.tag + p.evertag);
son.evermax = max(son.evermax, son.max + p.evertag);
son.tag += p.tag;
son.max += p.tag;
p.tag = p.evertag = 0;

后面三句很好理解就不说了。第一句是因为tag是一个累加变量，而距离上一次clear我们还有p.evertag没有下传给孩子，所以说孩子还有son.tag+p.evertag这么多没有给孩子的孩子- -|| 而第二句的话就同理了，参照第三句和第四句的关系以及第一句的意义。

代码