team2012-D3-1D
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
=== 0019 ===
{{{
树上的倍增，维护某一段的最大值、最小值、祖先减后辈的最大值、后辈减祖先的最大值
设，要从b访问a，且lca(a,b) = c
分情况：
1. a-->c的最大值减去c-->b的最小值
2. a-->c的最大值减去c
3. c减去c-->b的最小值
4. 对于从a-->c的路径内：
2.1 某一段中的后辈减祖先的最大值
2.2 a-->x的最大值减去某一段（设为x-->y)的最小值
5. 对于从c-->b的路径内：
3.1 某一段中的祖先减后辈的最大值
3.2 某一段（设为x-->y）的最大值减去y-->b的最小值
}}}
{{{
int gao(int a, int bb) {
int c = lca(a, bb);
int la = dis[a] - dis[c], lb = dis[bb] - dis[c];
int ret = 0;
int maxa = 0, minb = 0x7FFFFFFF;
for (int i = maxf-1; i >= 0; --i) {
if ((la >> i) & 0x1) {
ret = max(ret, max(dmax[a][i], maxa - bmin[a][i]));
maxa = max(maxa, bmax[a][i]);
a = fa[a][i];
}
if ((lb >> i) & 0x1) {
ret = max(ret, max(umax[bb][i], bmax[bb][i] - minb));
minb = min(minb, bmin[bb][i]);
bb = fa[bb][i];
}
}
ret = max(ret, maxa-minb);
ret = max(ret, max(maxa-b[c], b[c]-minb));
return ret;
}
}}}
=== 0020 ===
{{{
f[i]:到第i关时，所能杀掉的最大boss数，以及在此条件下，耗费最少的potion数（为了方便pair比较，记为负数）
f[i] = max(跳过这个boss时：f[i-1],
要杀掉这个boss时：不妨设从第j+1关到第i关恰好能够攒到5个XX，并且杀掉第i关的boss最少耗费药水potion
此时的PII为（f[j].first+1,f[j].second-potion））
如何计算打boss最少耗费的药水：
如果P >= d[i]，那么一直模拟，hp不够的时候加一个potion
否则P < d[i]，那么贪心，被打完了就加一个potion，如果目前剩下的hp>剩下的回合数×d[i]，那么可以return了
}}}
=== 0021 ===
额。。。求凸包
{{{
int graham(int n, point * p, point * ch, bool comEdge = false){
if(n < 3){ for(int i = 0; i < n; i++) ch[i] = p[i]; return n; }
const double e1 = comEdge ? eps : -eps; int i, j, k;
sort(p, p + n); ch[0] = p[0]; ch[1] = p[1];
for(i = j = 2; i < n; ch[j++] = p[i++]) while(j > 1 && (ch[j - 2] - ch[j - 1]) * (p[i] - ch[j - 1]) > e1) j--;
ch[k = j++] = p[n - 2];
for(i = n - 3; i > 0; ch[j++] = p[i--]) while(j > k && (ch[j - 2] - ch[j - 1]) * (p[i] - ch[j - 1]) > e1) j--;
while (j > k && (ch[j - 2] - ch[j - 1]) * (ch[0] - ch[j - 1]) > e1) j--;
return j;
}
}}}
=== 0022 ===
{{{
蘑菇题
按照题目的意思递归模拟即可
注意：
1. a,b,c和e,f,g的条件是并列的，优先级递降，而不是搞完a再搞b
2. 那个goal difference竟然要算负数-__-，翻译不是净胜球嘛，为什么输了也算。。。直接p1-p2即可，不用和0作比较
}}}
=== 0023 ===
{{{
首先确定m个点
然后二分答案，贪心判断
如何确定m个点：
不妨设：n = k * m + r
那么就把n个点分成了k块，剩下r个点
然后我们发现，当k是偶数时，无论中间选择哪一个点作为仓库（？），两端到它的距离都不相等，这就造成了浪费
于是当k是偶数时，令 n = (k-1) * m + (m+r)
然后最前面的都是每块k个点，最后面的都是每块k+2个点，中间可能有一块有k+1个点
}}}
{{{
int k = n / m;
int r = n % m;
if ((k&0x1) == 0) k--,r+=m;
p[0] = (k-1)/2;
int t = m-(r+1)/2;
for (int i = 1; i < t; i++)
p[i] = p[i-1] + k;
if (t > 0) p[t] = p[t-1] + k + (1-(r%2));
for (int i = t+1; i < m; i++)
p[i] = p[i-1] + k + 2;
}}}
=== 0024 ===
{{{
先算出l[i],r[i]，表示向左、向右最远可以推倒到哪一个
然后进行dp
对于向右推的操作，可以用一个priority_queue来维护
对于向左推的操作，记录fl[i] = min(f[i],f[i-1],...,f[l[i]]) 并随时更新
}}}
{{{
// left
if (f[i] < 0 || f[i] > f[l[i]-1]+1) f[i] = f[l[i]-1]+1;
int z = i-1;
while (z >= l[i]) {
int fj = fl[z];
if (f[i] < 0 || f[i] > fj + 1) {
f[i] = fj + 1; fl[i] = fj;
if (fl[i] < 0 || fl[i] > fj) fl[i] = fj;
}
z = l[z] - 1;
}
if (fl[i] < 0 || fl[i] > f[i]) fl[i] = f[i];
}}}0019
{{{
树上的倍增，维护某一段的最大值、最小值、祖先减后辈的最大值、后辈减祖先的最大值
设，要从b访问a，且lca(a,b) = c
分情况：
1. a-->c的最大值减去c-->b的最小值
2. a-->c的最大值减去c
3. c减去c-->b的最小值
4. 对于从a-->c的路径内：
2.1 某一段中的后辈减祖先的最大值
2.2 a-->x的最大值减去某一段（设为x-->y)的最小值
5. 对于从c-->b的路径内：
3.1 某一段中的祖先减后辈的最大值
3.2 某一段（设为x-->y）的最大值减去y-->b的最小值
}}}
{{{
int gao(int a, int bb) {
int c = lca(a, bb);
int la = dis[a] - dis[c], lb = dis[bb] - dis[c];
int ret = 0;
int maxa = 0, minb = 0x7FFFFFFF;
for (int i = maxf-1; i >= 0; --i) {
if ((la >> i) & 0x1) {
ret = max(ret, max(dmax[a][i], maxa - bmin[a][i]));
maxa = max(maxa, bmax[a][i]);
a = fa[a][i];
}
if ((lb >> i) & 0x1) {
ret = max(ret, max(umax[bb][i], bmax[bb][i] - minb));
minb = min(minb, bmin[bb][i]);
bb = fa[bb][i];
}
}
ret = max(ret, maxa-minb);
ret = max(ret, max(maxa-b[c], b[c]-minb));
return ret;
}
}}}
0020
{{{
f[i]:到第i关时，所能杀掉的最大boss数，以及在此条件下，耗费最少的potion数（为了方便pair比较，记为负数）
f[i] = max(跳过这个boss时：f[i-1],
要杀掉这个boss时：不妨设从第j+1关到第i关恰好能够攒到5个XX，并且杀掉第i关的boss最少耗费药水potion
此时的PII为（f[j].first+1,f[j].second-potion））
如何计算打boss最少耗费的药水：
如果P >= d[i]，那么一直模拟，hp不够的时候加一个potion
否则P < d[i]，那么贪心，被打完了就加一个potion，如果目前剩下的hp>剩下的回合数×d[i]，那么可以return了
}}}
0021
额。。。求凸包
{{{
int graham(int n, point * p, point * ch, bool comEdge = false){
if(n < 3){ for(int i = 0; i < n; i++) ch[i] = p[i]; return n; }
const double e1 = comEdge ? eps : -eps; int i, j, k;
sort(p, p + n); ch[0] = p[0]; ch[1] = p[1];
for(i = j = 2; i < n; ch[j++] = p[i++]) while(j > 1 && (ch[j - 2] - ch[j - 1]) * (p[i] - ch[j - 1]) > e1) j--;
ch[k = j++] = p[n - 2];
for(i = n - 3; i > 0; ch[j++] = p[i--]) while(j > k && (ch[j - 2] - ch[j - 1]) * (p[i] - ch[j - 1]) > e1) j--;
while (j > k && (ch[j - 2] - ch[j - 1]) * (ch[0] - ch[j - 1]) > e1) j--;
return j;
}
}}}
0022
{{{
蘑菇题
按照题目的意思递归模拟即可
注意：
1. a,b,c和e,f,g的条件是并列的，优先级递降，而不是搞完a再搞b
2. 那个goal difference竟然要算负数-__-，翻译不是净胜球嘛，为什么输了也算。。。直接p1-p2即可，不用和0作比较
}}}
0023
{{{
首先确定m个点
然后二分答案，贪心判断
如何确定m个点：
不妨设：n = k * m + r
那么就把n个点分成了k块，剩下r个点
然后我们发现，当k是偶数时，无论中间选择哪一个点作为仓库（？），两端到它的距离都不相等，这就造成了浪费
于是当k是偶数时，令 n = (k-1) * m + (m+r)
然后最前面的都是每块k个点，最后面的都是每块k+2个点，中间可能有一块有k+1个点
}}}
int k = n / m;
int r = n % m;
if ((k&0x1) == 0) k--,r+=m;
p[0] = (k-1)/2;
int t = m-(r+1)/2;
for (int i = 1; i < t; i++)
p[i] = p[i-1] + k;
if (t > 0) p[t] = p[t-1] + k + (1-(r%2));
for (int i = t+1; i < m; i++)
p[i] = p[i-1] + k + 2;
0024
{{{
先算出l[i],r[i]，表示向左、向右最远可以推倒到哪一个
然后进行dp
对于向右推的操作，可以用一个priority_queue来维护
对于向左推的操作，记录fl[i] = min(f[i],f[i-1],...,f[l[i]]) 并随时更新
}}}
{{{
// left
if (f[i] < 0 || f[i] > f[l[i]-1]+1) f[i] = f[l[i]-1]+1;
int z = i-1;
while (z >= l[i]) {
int fj = fl[z];
if (f[i] < 0 || f[i] > fj + 1) {
f[i] = fj + 1; fl[i] = fj;
if (fl[i] < 0 || fl[i] > fj) fl[i] = fj;
}
z = l[z] - 1;
}
if (fl[i] < 0 || fl[i] > f[i]) fl[i] = f[i];
}}}