[BZOJ 2300] [HAOI 2011] 防线修建

题意:只有删点与查询操作,动态地维护一个上凸包的周长。

首先可以把题目离线化,倒转时间轴,则可以把题目转换成动态加点并维护凸包周长。

维护的实现可以采用平衡树(set)来做:在树上找到当前点的前驱与后继点(按 xy 坐标排序),然后判断是否符合凸包条件,若不满足则不断删去前驱后继并更新周长。

Note:

  1. 计算初始答案前就应当构建出一个凸包(可以用后面的方法做)。
  2. 这题 cin / cout 非常慢,全改成 scanf / printf 后快了 1s+

Reference:

https://erjiaqing.github.io/2014/04/14/bzoj2300/

代码如下:

继续阅读[BZOJ 2300] [HAOI 2011] 防线修建

BZOJ【2300】防线修建

描述

在第一象限中给出m个点,其中一共有3个点一定要保护,求最小凸包周长。

在这题中,河道相等于一条防线,于是题目就简化成了求最小上凸包。再看看数据,每次减掉一个要保护的点。我们可以从后往前看,先把没有被询问到的点做一次凸包,接着就可以把删除的点看做是加上去的点。比如把2 3 1 4点依次删除询问,可以看做刚开始一个点都没有,接着把4 1 3 2点依次加入。

所以我们只要先存心每次询问,从后往前做动态凸包即可。

至于动态凸包,由于有三个点一定要保护,于是对于每个新加入的点,找出与其相邻的点, 用叉积判断其是否最优,若不是,就可以将其两边的点删除,继续判断。

在这里,找于加入的点相邻的点可以用平衡树来维护,每次需要O(logn)的时间查找。

可以用自带的set来实现。

关于set,可以看这http://blog.csdn.net/sunshinewave/article/details/8068326

继续阅读BZOJ【2300】防线修建

[BZOJ 3624] [APIO 2008] 免费道路

并查集。

题意:求把 N 个点用 N-1 条边连成一棵树,且其中恰有 K 条边为 0 边的一种方案。

第一反应:先连 0 边再连 1 边。

但可能会有这么一种情况:所有的 1 边都连上之后仍然整个图仍然是不联通的。这意味着有一些 0 边是必选的。但如果像上面那样直接做的话可能选不到这些边,从而得不出答案。

于是可以这样做:

先把所有 1 边端点合并,然后接着枚举 0 边,若两顶点不在同一集合中,则把这条边端点所在集合合并,并加入答案中。

接着把并查集重置成只有答案集合中的边的情况,加入能加的 0 边直到答案中的 0 边数量达到 K。最后加入 1 边。

这题还要判断方案是否存在,判断方法为 1. 选取的 0 边边数恰为 K。 2. 选取的总边数为 N-1

代码如下(BZOJ 有点诡异,endl 交上去会 RTE,而 '\n' 就没问题):

继续阅读[BZOJ 3624] [APIO 2008] 免费道路

BZOJ1913 [APIO2010] 信号覆盖 signaling

BZOJ1913

题意:

给出平面上n个点,在这N个点中选3点构成一个圆,求圆上或圆内总点数的期望值。n 1500,保证无特殊情况。

题解:

显然一共有种情况,暴力枚举不可取。

考虑任取四个点构成一个四边形,可能有凸四边形和凹四边形两种情况。显然在一个四边形上任取三个点,有4种情况,每种情况都至少有3个点在圆上(即构成圆的3点),因此可以在计算时忽略这3个点,在输出时+3即可。由几何知识可得,在一个凸四边形上任取三个点,剩余的那个点在圆内可能有2种情况,而对于一个凹四边形可能有1种情况,那么要求的就变成了统计两种四边形的数目。

因为一共有个四边形,所以我们可以统计凸四边形的个数。首先枚举一个点,以这个点为原点,将其余点以极角序排序,然后使用类似旋转卡壳的思想,枚举另外两个点,保持这两个点的极角差<π,统计两点之间的点数即可。

时间复杂度为

BZOJ【3675】序列分割

【描述】

一串数列,每次将其分成两段,并求每次乘积的和的最大值。

对于一个最终分成a/bc/d的序列,我们可以发现无论怎么分,最后得到的答案都是一样的:

1.a/bcd

a/bc/d

ans = a * (b + c + d) + (b + c) * d = ab + ac + cd + bd + cd

2.abc/d

a/bc/d

ans = (a + b + c) * d + a * (b + c) = ab + ac +cd + bd + cd。

所以相当于分割的顺序没有什么用,答案都是每i段乘于前 i - 1段的和。

于是我们可以得到一个动态方程:

f[i][j]=max{f[i1][k]+sum[k]×(sum[j]sum[k])}

表示把前j个数分成i段的最大值,其中j > k。

设1 < a < b < j。

若b的方案比a优,则

f[i-1][b] + sum[b]*(sum[j]-sum[b]) > f[i-1][a] + sum[a]*(sum[j]-sum[a])

f[i-1][b]-f[i-1][a]> sum[a]*sum[j]-sum[a]^2 -sum[b]*sum[j]+sum[b]^2

f[i-1][b]-f[i-1][a]+sum[a]^2-sum[b]^2>(sum[a]-sum[b])*sum[j]

 

f[i-1][b]-f[i-1][a]+sum[a]^2-sum[b]^2

_______________________________________ > sum[j]

sum[a]-sum[b]

 

f[i-1][a]-f[i-1][b]-sum[a]^2+sum[b]^2

_______________________________________ < sum[j]

sum[a]-sum[b]

又sum[j]是一个常数

于是这题就可以用斜率优化来O(1)求出f[i][j]。

 

[BZOJ 1996] [HNOI 2010] 合唱队

区间动态规划。

三维状态:f[i][j][k=0/1] 表示排出理想队形第 i~j 位,且最后排上去的一个当 k=0 时是 i,当 k=1 时为 j。

因为新的数只能加在当前已有区间的左右端点,故 f[i][j][k] 区间只能由 f[i+1][j][t] 与 f[i][j-1][t] 转移得到。具体来说,有如下转移:


1
2
3
4
f[i-1][j][0] += f[i][j][0] (a[i-1] < a[i])
f[i][j+1][1] += f[i][j][0] (a[j+1] > a[i])
f[i-1][j][0] += f[i][j][1] (a[i-1] < a[j])
f[i][j+1][1] += f[i][j][1] (a[j+1] > a[j])

初始化时把 f[i][i][0] 与 f[i][i][1] 其中一个设为 1,另一个设为 0。如果都设为 1,则会导致单个数有两种放置方式。

代码如下:

继续阅读[BZOJ 1996] [HNOI 2010] 合唱队

[BZOJ 4031] [HEOI 2015] 小Z的房间

Kirchhoff's theorem or Kirchhoff's matrix tree theorem

  1. G的度数矩阵DG是一个n*n的矩阵,并且满足:当i≠j时,Di,j=0;当i=j时,Di,j等于Vi的度数。
  2. G的邻接矩阵AG也是一个n*n的矩阵,并且满足:如果ViVj之间有边直接相连,则Ai,j=1,否则为0。

定义G的 Kirchhoff 矩阵CGCG=DGAG

Matrix-Tree 定理:G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 CG任何一个n-1阶主子式(去掉第行第i列的新矩阵)的行列式的绝对值。

运用高斯消元计算行列式绝对值。高斯消元过程中除法运用辗转相消实现。

Reference:

https://www.cnblogs.com/wuyuhan/p/5238652.html

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/u010182633/article/details/45225179

代码如下:

继续阅读[BZOJ 4031] [HEOI 2015] 小Z的房间

BZOJ【1857】传送带

描述

在平面上给出两条线段AB,CD,再给出在线段、平面的速度,求出从A走到D最短的时间。

从题意上看,我们很(ping)容(zhi)易(jue)得出答案是单峰的,也就是对于AB上的点E,在从A到B的过程中,答案是先变小,再变大。于是就用三分来求峰值。

单峰证明:对于AB上的点E,到CD上的点F。当EF⊥CD时,E到CD的距离最短,而时间也最短。 否则的话E到CD的距离一定大于EF。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<climits>

using namespace std;

struct node
{
    double x, y;
}A, B, C, D, T;

double p, r, q;
double ans = INT_MAX;

double dir(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

node tri(node a, node b, int t)
{
    T.x = a.x + (b.x - a.x) * t *1.0 / 3;
    T.y = a.y + (b.y - a.y) * t *1.0 / 3;
    return T;
}

double ANS(node a, node b)
{
    return dir(a, A) / p + dir(b, D) / q + dir(a, b) / r;
}

double Ans(node t)
{
    node c = C, d = D, x, y;
    double time_x, time_y, times = INT_MAX;
    do
    {
       x = tri(c, d, 1);
       time_x = ANS(t, x);
       y = tri(c, d, 2);
       time_y = ANS(t, y);
       times = min(times, min(time_x, time_y));
       if (time_x > time_y) c = x;
       else d = y;
    }while (dir(c, d) >= 0.0000001);
    return times;
}

int main(void)
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
   
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
    cin >> p >> q >> r;
    node x, y;
    double time_x, time_y;
    do
    {
       x = tri(A, B, 1);
       time_x = Ans(x);
       y = tri(A, B, 2);
       time_y = Ans(y);
       ans = min(ans, min(time_x, time_y));
       if (time_x > time_y) A = x;
       else B = y;
    }while (dir(A, B) >= 0.0000001);
    printf("%.2f", ans);
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}