最长上升子序列 & 几何题解

Hello_World

最长上升子序列

裸题

题目链接

OpenJudge 2757: 最长上升子序列

题意

对于一个序列，求出其最长递增子序列的长度，序列最长为 1000，可以用 $n^2$ 和 $n\log n$ 解法。

$n^2$ 解法

用一个数组 dp 来存放从第一个位置到当前位置的最长上升子序列的长度，于是就有递推公式：

$$dp_i=\max(dp_j|j\in[0,i))+1$$
最后从头到尾扫一遍，输出 $\max(dp_i|i\in[0,n))$。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define LL long long
const int maxn = 1005;
int num[maxn], dp[maxn];
int n, ans;
int main() {
    while(scanf("%d", &n) != EOF) {
        // 初始化
        ans = 0;
        memset(dp, 0, sizeof(dp));
        // 输入原序列
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            // 获得dp 数组
            for(int j = 0; j < i; ++j) {
                if(num[i] > num[j]) {
                    dp[i] = max(dp[i], dp[j]);
                }
            }
            ++dp[i];
            // 查找最大值
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

$n\log n$ 解法

用一个数组 dp 来将第 $i$ 个数字 $num_i$ 存放在下标为以 $num_i$ 结尾的最长上升子序列的长度的位置的最小数字，比如对于序列 $\left\{1,5,6,4,3,8,7,6\right\}$，用 $<a,b>$ 来表示数字 $a$ 在以 $a$ 为结尾的最长上升子序列的长度为 $b$，于是有：$\left\{<1,1>,<5,2>,<6_1,3>,<4,2>,<3,2>,<8,4>,<7,4>,<6_2,3>\right\}$，对于相同的 $b$ 的值，取最小的 $a$，放置在 $dp_b$ 上，这样 dp 数组的大小就是最长上升子序列的长度，对于该例子，dp 数组为 $\left\{1,3,6,7\right\}$。

现在需要解决的问题是如何得到这个 dp 数组，算法步骤如下：
1. 初始化 dp 数组为空;
2. 从 $0$ 到 $n-1$ 扫描原序列，对于序列的每一个元素 $num_i$，从 dp 数组中查找第一个大于等于 $num_i$ 的数字 $dp_j$;
3. 如果不存在 $dp_j$，则在 dp 数组的末尾添加 $num_i$;
4. 如果存在，则将 $dp_j$ 替换为 $num_i$;
对于如上序列 $\left\{1,5,6,4,3,8,7,6\right\}$，其算法过程如下：

步骤	num 数组	dp 数组
1	1	1
2	1 5	1 5
3	1 5 6	1 5 6
4	1 5 6 4	1 4 6
5	1 5 6 4 3	1 3 6
6	1 5 6 4 3 8	1 3 6 8
7	1 5 6 4 3 8 7	1 3 6 7
8	1 5 6 4 3 8 7 6	1 3 6 7

从以上步骤可以明显地看出，dp 数组始终有序，于是查找 dp 数组中第一个大于等于 $num_i$ 的值可以用二分查找，其时间复杂度为 $n_1\log n_2$，其中 $n_1$ 为原序列的长度，$n_2$ 为 dp 数组的最大长度，${n_2}_{max}=n_1$。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define LL long long
const int maxn = 1005;
int num[maxn], dp[maxn];
int n, cnt;
int *iter;
int main() {
    while(scanf("%d", &n) != EOF) {
        // 初始化
        cnt = 0;
        memset(dp, 0, sizeof(dp));
        // 输入原序列
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            // 更新dp 数组
            iter = lower_bound(dp, dp + cnt, num[i]);
            *iter = num[i];
            if(iter == dp + cnt) {
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

变体

题目链接

Codeforces 4D: Mysterious Present

题意

将一张卡片放到一张信封中，将一个信封放到更大的信封中，每个信封都有对应的长和宽的值，卡片能放到信封里的条件是卡片的长和宽严格小于信封的长和宽，小信封能放到大信封里的条件是小信封的长和宽严格小于大信封的长和宽，给出卡片的大小，以及所有信封的大小，问将卡片放入信封中，最多能套几层信封，并按信封大小的顺序，输出信封的序号。

最长上升子序列解法

先将信封按照长为主关键字、宽为次关键字从小到大排序，从卡片能放入的最小信封开始，$n^2$ 查找最长上升子序列，并记下能被第 $i$ 个信封装下的，层数最多的小一号的信封的序号。接着用一个栈或者递归输出信封序号。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define LL long long
const int maxn = 5005;
struct Node {
    int w, h, pos, layer, pre;
};
Node node[maxn];
int n, w, h, cnt, Maxindex;
stack<int> S;
bool operator<(const Node &a, const Node &b) {
    if(a.w == b.w) return a.h < b.h;
    return a.w < b.w;
}
int main() {
    while(scanf("%d%d%d", &n, &w, &h) != EOF) {
        // 初始化
        cnt = 0;
        Maxindex = 0;
        memset(node, 0, sizeof(node));
        // 读入数据并筛选掉不能装下卡片的信封
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &node[cnt].w, &node[cnt].h);
            if(node[cnt].w > w && node[cnt].h > h) {
                node[cnt++].pos = i;
            }
        }
        sort(node, node + cnt);
        for(int i = 0; i < cnt; ++i) {
            // 初始化
            node[i].pre = -1;
            node[i].layer = 1;
            // 获得dp 数组
            for(int j = 0; j < i; ++j) {
                if(node[j].w < node[i].w && 
                   node[j].h < node[i].h && 
                   node[j].layer + 1 > node[i].layer) {
                    node[i].pre = j;
                    node[i].layer = node[j].layer + 1;
                }
            }
            // 记录最大层数信封下标
            if(node[Maxindex].layer < node[i].layer) {
                Maxindex = i;
            }
        }
        if(cnt != 0) {
            // 获取各信封下标
            while(Maxindex != -1) {
                S.push(Maxindex);
                Maxindex = node[Maxindex].pre;
            }
            // 输出信封序号
            printf("%d\n", S.size());
            while(!S.empty()) {
                printf("%d ", node[S.top()].pos);
                S.pop();
            }
            printf("\n");
        } else {
            printf("0\n");
        }
    }
    return 0;
}

拓扑排序解法

先将给出的信封按照长、宽的主、次关键字排序，然后 $n^2$ 预处理出一张图：如果信封 $i$ 能够装入信封 $j$，那么就在图上添加一条从 $i$ 指向 $j$ 的边，这样形成一个有向无环图，接着进行拓扑排序，排序过程中，每有一个点出队，就查找该点的上一节点的最大信封层数，拓扑排序过程如下：
1. 初始化一个空队列，计算每个节点的入度
2. 将所有入度为 $0$ 的节点加入队列
3. 不断从队列中弹出元素，直到队列为空，每弹出一个元素，就进行以下操作：
① 查找该节点指向的所有点，将它们的入度减一；
② 入度减一后，如果某个点的入度为 $0$，则将该节点入队；
③ 查找指向该节点的所有节点的最大信封层数；
④ 该节点的信封层数即最大信封层数加一；
⑤ 如果该节点的最大信封层数大于全局最大信封层数，记录该下标

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cfloat>
#include <climits>
using namespace std;
#define LL long long
const int maxn = 5005;
struct Node {
    int w, h, pos, pre, layer;
};
Node node[maxn];
int tmp;
bool G[maxn][maxn];
stack<int> S;
queue<int> Q;
int n, w, h, cnt, Maxindex;
int deg[maxn];
int x;
bool operator<(const Node &a, const Node &b) {
    if(a.w == b.w) return a.h < b.h;
    return a.w < b.w;
}
int main() {
    while(scanf("%d%d%d", &n, &w, &h) != EOF) {
        // 初始化
        cnt = 0;
        Maxindex = 0;
        memset(node, 0, sizeof(node));
        memset(G, 0, sizeof(G));
        for(int i = 0; i < n; ++i) {
            node[i].pre = -1;
            node[i].layer = 1;
        }
        // 读入数据
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &node[cnt].w, &node[cnt].h);
            if(node[cnt].w > w && node[cnt].h > h) {
                node[cnt++].pos = i;
            }
        }
        sort(node, node + cnt);
        // 构图如果小信封i 能放入大信封j内容内，则i 有一条指向j 的边
        for(int i = 0; i < cnt; ++i) {
            for(int j = 0; j < i; ++j) {
                if(node[j].w < node[i].w &&
                    node[j].h < node[i].h) {
                    G[j][i] = true;
                    ++deg[i];
                }
            }
        }
        // 初始化队列
        for(int i = 0; i < cnt; ++i) {
            if(deg[i] == 0) {
                Q.push(i);
            }
        }
        // 拓扑排序
        while(!Q.empty()) {
            tmp = Q.front();
            Q.pop();
            // 从图中“删去”点 tmp，“删除”节点tmp 指向的所有点的边
            for(int i = 0; i < cnt; ++i) {
                if(G[tmp][i]) {
                    --deg[i];
                    if(deg[i] == 0) {
                        Q.push(i);
                    }
                }
            }
            // 从图中查找指向点tmp 的所有的点中
            // 能包含层数最多的小一号信封层数
            for(int i = 0; i < cnt; ++i) {
                if(G[i][tmp] && node[tmp].layer < node[i].layer + 1) {
                    node[tmp].layer = node[i].layer + 1;
                    node[tmp].pre = i;
                }
            }
            // 查找全局最大层数的信封下标
            if(node[Maxindex].layer < node[tmp].layer) {
                Maxindex = tmp;
            }
        }
        if(cnt == 0) {
            printf("0\n");
        } else {
            // 获取各信封下标
            while(Maxindex != -1) {
                S.push(Maxindex);
                Maxindex = node[Maxindex].pre;
            }
            // 输出信封序号
            printf("%d\n", S.size());
            while(!S.empty()) {
                printf("%d ", node[S.top()].pos);
                S.pop();
            }
            printf("\n");
        }
    }
    return 0;
}

几何

题目链接

Codeforces 1C: Ancient Berland Circus

题意

给三个顶点的坐标，求包含这三个顶点的面积最小的正多边形面积

题解

先做三角形的外接圆，求三个圆心角的最大公约数，这个最大公约数就是所求正多边形外接圆的内角，将内角对应三角形的面积乘上多边形的边数，就是所求多边形的面积，本题数据精度取 $10^{-3}$ 可以过，取 $10^{-5}$ 反而过不了。

公式推导：
设三角形外接圆圆心为 $(x,y)$，则：

$$(x-x_1)^2+(y-y_1)^2=(x-x_2)^2+(y-y_2)^2\\ (x-x_1)^2+(y-y_1)^2=(x-x_3)^2+(y-y_3)^2$$
化简得：
$$\begin{cases} 2x(x_1-x_2)+2y(y_1-y_2)=x_1^2-x_2^2+y_1^2-y_2^2\\ 2x(x_1-x_3)+2y(y_1-y_3)=x_1^2-x_3^2+y_1^2-y_3^2 \end{cases}$$
令：
$$\begin{cases} a_{x1}=2(x_1-x_2)\\ a_{y1}=2(y_1-y_2)\\ a_{x2}=2(x_1-x_3)\\ a_{y2}=2(y_1-y_3)\\ b_1=x_1^2-x_2^2+y_1^2-y_2^2\\ b_2=x_1^2-x_3^2+y_1^2-y_3^2 \end{cases}$$
则：
$$D=\left| \begin{matrix} a_{x1}&a_{y1}\\ a_{x2}&a_{y2} \end{matrix} \right|\quad D_1=\left| \begin{matrix} b_1&a_{y1}\\ b_2&a_{y2} \end{matrix} \right|\quad D_2=\left| \begin{matrix} a_{x1}&b_1\\ a_{x2}&b_2 \end{matrix} \right|$$
解得：
$$x=\frac{D_1}{D}\quad y=\frac{D_2}{D}\quad r=\sqrt{(x_1-x)^2+(y_1-y)^2}$$
对于每个点的坐标，求出对应的倾斜角（注意程序中 $arctan$ 函数在 $\left[0,2\pi\right)$ 中的返回值）：
$$deg_i=\arctan(\frac{y_i-y}{x_i-x})$$
对倾斜角排序后求出三边夹角 $\theta$，求出三个圆心角的最大公约数 $\theta_{gcd}$，有：
$$S=\frac{2\pi}{\theta_{gcd}}\times\frac{r^2\times\sin\theta_{gcd}}{2}$$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cfloat>
#include <climits>
using namespace std;
#define LL long long
const double PI = acos(-1);
const double eps = 1e-3;
// 在精度为eps 时，判断duoble 型数据是否为0
bool zero(double x) {
    return fabs(x) < eps;
}
// 计算double 型数值的gcd
double gcd(double x, double y) {
    if(zero(y)) {
        return x;
    } else {
        return gcd(y, fmod(x, y));
    }
}
// 计算倾斜角
double Get_deg(double x, double y) {
    if(zero(x)) {
        if(y > eps)
            return PI / 2;
        else
            return 1.5 * PI;
    }
    if(x < 0) {
        return atan(y / x) + PI;
    } else if(x > 0 && y < 0) {
        return atan(y / x) + 2 * PI;
    }
    return atan(y / x);
}
int main() {
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);
    double ax1 = 2 * (x1 - x2);
    double ay1 = 2 * (y1 - y2);
    double b1 = x1 * x1 - x2 * x2 + y1 * y1 - y2 * y2;
    double ax2 = 2 * (x1 - x3);
    double ay2 = 2 * (y1 - y3);
    double b2 = x1 * x1 - x3 * x3 + y1 * y1 - y3 * y3;
    double D = ax1 * ay2 - ay1 * ax2;
    double D1 = b1 * ay2 - ay1 * b2;
    double D2 = ax1 * b2 - b1 * ax2;
    double x = D1 / D;
    double y = D2 / D;
    double r = sqrt((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y));
    double deg[3];
    deg[0] = Get_deg(x1 - x, y1 - y);
    deg[1] = Get_deg(x2 - x, y2 - y);
    deg[2] = Get_deg(x3 - x, y3 - y);
    sort(deg, deg + 3);
    double Deg1 =  2 * PI - deg[2] + deg[0];
    double Deg2 = deg[1] - deg[0];
    double Deg3 = deg[2] - deg[1];
    double g = gcd(Deg1, Deg2);
    g = gcd(g, Deg3);
    printf("%.8lf\n", r * r * sin(g) * PI / g);
    return 0;
}