热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

洛谷P4035[JSOI2008]球形空间生成器(高斯消元法/模拟退火算法)

本文介绍了洛谷P4035[JSOI2008]球形空间生成器问题的解决方案,主要使用了高斯消元法和模拟退火算法。通过这两种方法,可以高效地求解多维空间中的球心位置。文章提供了详细的算法模板和实现代码,适用于ACM竞赛和其他相关应用场景。数据范围限制在10以内,确保了算法的高效性和准确性。

整理的算法模板合集: ACM模板


点我看算法全家桶系列!!!

实际上是一个全新的精炼模板整合计划




在这里插入图片描述
数据范围只开到了10,而且是经典的力学结构,所以我们可以用模拟退火,可以做一下 nnn 维的正交分解hhh,经典物理题。

然后实际上本题就是一个高斯消元模板题
在这里插入图片描述
apple pencil用习惯了,普通的笔写起来,字丑见谅

我用的是普通的高斯消元模板,因为听说高斯 - 约旦消元法有可能会被卡掉,所以学了,但是一直不敢用QWQ

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef int itn;
typedef pair<int, int>PII;
const int N &#61; 2007, mod &#61; 1e9 &#43; 7, INF &#61; 2.1e9;
const double eps &#61; 1e-8;int n, m;
double b[N][N];//增广矩阵
double a[N][N];int guass(double a[][N])
{int c;//当前最左边的一列int r;//当前最上面的一行for(c &#61; 1, r &#61; 1; c <&#61; n; &#43;&#43; c){int t &#61; r;for(int i &#61; r &#43; 1; i <&#61; n; &#43;&#43; i){if(fabs(a[i][c]) > fabs(a[t][c]))t &#61; i;}if(fabs(a[t][c]) < eps)//等于0就下一个continue;//换到第一行&#xff08;最上面的一行&#xff09;for(int i &#61; c; i <&#61; n &#43; 1; &#43;&#43; i)swap(a[t][i], a[r][i]);//把该行第一个数变成 1&#xff08;该行每一列都/&#61;第c列的值&#xff09;for(int i &#61; n &#43; 1; i >&#61; c; -- i)a[r][i] /&#61; a[r][c];//中间所有列&#xff08;所有项&#xff09;全部消掉for(int i &#61; r &#43; 1; i <&#61; n; &#43;&#43; i)if(fabs(a[i][c]) > eps)for(int j &#61; n &#43; 1; j >&#61; c; -- j)a[i][j] -&#61; a[r][j] * a[i][c];r &#43;&#43; ;}if(r <&#61; n){for(int i &#61; r; i <&#61; n; &#43;&#43; i)if(fabs(a[i][n &#43; 1]) > eps)//非零&#xff0c;无解return 2;return 1;//无穷多组解}//回代//行最简形矩阵for(int i &#61; n; i >&#61; 1; -- i)for(int j &#61; i &#43; 1; j <&#61; n &#43; 1; &#43;&#43; j)a[i][n &#43; 1] -&#61; a[j][n &#43; 1] * a[i][j]; return 0;
}int main()
{scanf("%d", &n);for(int i &#61; 1; i <&#61; n &#43; 1; &#43;&#43; i)for(int j &#61; 1; j <&#61; n; &#43;&#43; j)scanf("%lf", &a[i][j]);for(int i &#61; 1; i <&#61; n; &#43;&#43; i)for(int j &#61; 1; j <&#61; n; &#43;&#43; j){b[i][j] &#61; 2 * (a[i][j] - a[i &#43; 1][j]);b[i][n &#43; 1] &#43;&#61; a[i][j] * a[i][j] - a[i &#43; 1][j] * a[i &#43; 1][j];}guass(b);for(int i &#61; 1; i < n; &#43;&#43; i)printf("%.3f ", b[i][n &#43; 1]);printf("%.3f\n", b[n][n &#43; 1]);return 0;
}

推荐阅读
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文探讨了如何通过最小生成树(MST)来计算严格次小生成树。在处理过程中,需特别注意所有边权重相等的情况,以避免错误。我们首先构建最小生成树,然后枚举每条非树边,检查其是否能形成更优的次小生成树。 ... [详细]
  • 本文详细介绍了Java中org.neo4j.helpers.collection.Iterators.single()方法的功能、使用场景及代码示例,帮助开发者更好地理解和应用该方法。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • C++构造函数与初始化列表详解
    本文深入探讨了C++中构造函数的初始化列表,包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明,详细解释了初始化列表在对象创建时的重要性。 ... [详细]
author-avatar
今生绝恋2702934494
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有