【记录】洛谷 P4049 [JSOI2007] 合金

最近会以写记录为主，主要是我做这题的感想，而不是题解。

没啥参考价值，大家可以不看。

zP4049 [JSOI2007] 合金 – 洛谷 (luogu.com.cn)

不知道为什么，第一眼看到我的想法是高斯消元。

俩矩阵消下元，取两个矩阵剩余行的更小值。

直接开干错误代码：

#include
using namespace std;

const int N = 510;
const double eps = 1e-25;
double aa[N][4], bb[N][4];

int gauss(double a[][4], int n) { 
    int r = 1;
    for (int j = 1; j  eps) {
                double ra = a[r][j] / a[i][j];
                for (int k = 1; k  eps) {
			r++;
		}
    }
    
    int sum = 0;
    for (int i = 1; i > n >> m;
    for (int i = 1; i > aa[i][1] >> aa[i][2] >> aa[i][3];
    }
    for (int i = 1; i > bb[i][1] >> bb[i][2] >> bb[i][3];
    }
    
    int ans = min(gauss(aa, n), gauss(bb, m));
    cout 

一交上去 23 分。

哪里错了呢？首先没判无解。

然后这个算法并不正确，对于多个原材料混合成一个合金的方案没有判断。

在这个基础上改肯定是不可能了，考虑换算法。

然后我就直接看了题解。

真的很神奇，因为一行加起来固定值为 1，所以可以只用考虑前两个。

因为前两个满足要求那第三个肯定满足要求。

现在我们有了这样的式子：

a 和 b 是系数，x 和 y 和 k 是二元组。

这非常像向量的运算，考虑到前置条件，可以发现：

k 点一定在向量 x 和 y 张成的三角形中。

（这么理解：当 a 和 b 都等于 0.5 时，k 点在 x 和 y 张成的平行四边形的对角线交点上。

    那么再连一条起点到交点的向量，保持 a 和 b 不变，新的 k 就在新的对角线交点上。

    继续这么二分下去，发现 k 一直都在一条线段上，

    而这条线段正好是向量 x 和 y 组成的三角形的第三条边。

    更极限的想，当 a = 1 时 k 就正好等于 x，所以 k 点一定在向量 x 和 y 张成的三角形中）

那么原来材料的二元组就可以 n 方枚举出很多向量，再枚举要制成合金的点，

看看所有点在不在当前向量的左边，如果是就 x 和 y 连边。

最后连成一个多边形，而且所有点都在这个多边形的里面。

最后 floyd 求最小环，搞定。

代码：

#include
using namespace std;
 
const int N = 510;
const double eps = 1e-20;
 
struct point {
    double x, y;
} a[N], b[N];
 
point operator+(point a, point b) {
    return {a.x + b.x, a.y + b.y};
}
 
point operator-(point a, point b) {
    return {a.x - b.x, a.y - b.y};
}
 
double operator*(point a, point b) {
    return a.x * b.y - b.x * a.y;
}
 
bool check(point a, point b, point t) {
    point p = b - a, q = t - a;
    if (p * q > eps) {
        return 1;
    }
    else if (p * q > n >> m;
     
    for (int i = 1; i > a[i].x >> a[i].y >> t;
        a[i].x *= 1000; a[i].y *= 1000;
    }
     
    for (int i = 1; i > b[i].x >> b[i].y >> t;
        b[i].x *= 1000; b[i].y *= 1000;
    }
     
    memset(f, 0x3f, sizeof(f));
     
    for (int i = 1; i  n) {
        cout 

举一反三的想一下，如果给的不是三元组而是 k 元组，该怎么办？

首先流程还是一样的，看一个 k – 1 元组在不在 k – 1 维向量张成的一坨东西的里面。

这里可以用到行列式，将 k – 2 个向量和当前的 k – 1 元组联立为方阵，求行列式。

这个行列式就是 k – 1 个向量张成东西的面积或者体积或者什么积。

如果大于 0，在左边，反之右边。

然后循环判断在不在每一条边界线上。

floyd 就很恶心了， 的。

（感觉真这么写可以上黑嘛？）

文章来源于互联网:【记录】洛谷 P4049 [JSOI2007] 合金

相关推荐: 健身俱乐部|基于SpingBoot+vue的健身俱乐部网站(源码+数据库+文档)

健身俱乐部网站 基于SpingBoot+vue的健身俱乐部网站 一、前言 二、系统设计 三、系统功能设计  系统功能实现 后台模块实现 管理员模块实现 教练实现 用户模块实现 四、数据库设计  五、核心代码  六、论文参考 七、最新计算机毕设选题推荐 八、源码…