自贡建设投资有限公司网站,国家企业网官网查询,怎么快速推广网站,搜索引擎广告是什么搜索
模拟退火
模拟退火一个很关键的是#xff0c;看看枚举到每一个方案是不是可能的。
3167. 星星还是树
在二维平面上有 n 个点#xff0c;第 i 个点的坐标为 ( x i , y i ) (x_i,y_i) (xi,yi)。请你找出一个点#xff0c;使得该点到这 n 个点的距离之和最小。这…搜索
模拟退火
模拟退火一个很关键的是看看枚举到每一个方案是不是可能的。
3167. 星星还是树
在二维平面上有 n 个点第 i 个点的坐标为 ( x i , y i ) (x_i,y_i) (xi,yi)。请你找出一个点使得该点到这 n 个点的距离之和最小。这个题如果是二维的话其实是一个凸函数我们可以用三分求解。
#includecstring
#includealgorithm
#includeiostream
#includecmath
#includectime#define x first
#define y secondusing namespace std;typedef pairdouble, double P;
const int maxn 110;
P q[maxn];
int N;
double ans 1e8;double rand(double l, double r) {//等概率得到区间的一个点return (double)rand() / RAND_MAX * (r - l) l;
}double get_dist(P a, P b) {double dx a.x - b.x;double dy a.y - b.y;return sqrt(dx * dx dy * dy);
}double calc(P p) {double res 0;for (int i 0; i N; i) {res get_dist(q[i], p);}ans min(ans, res);return res;
}void simulate_anneal() {P cur(rand(0, 10000), rand(0, 10000));//一开始可以把衰减系数定的大一些0.999边界条件定的小一些1e-6超时的话再调整for (double t 1e4; t 1e-4; t * 0.99) {P np(rand(cur.x - t, cur.x t), rand(cur.y - t, cur.y t));double dt calc(np) - calc(cur);//如果dt 0那么 if 里面的条件一定成立。//如果dt 0那么 if 里面的条件就是一个概率if (exp(-dt / t) rand(0, 1)) cur np;}
}int main() {scanf(%d, N);for (int i 0; i N; i) scanf(%lf%lf, q[i].x, q[i].y);for (int i 0; i 100; i) simulate_anneal();printf(%.f\n, ans);return 0;
}2680. 均分数据 已知 N N N 个正整数 A 1 、 A 2 、 … … 、 A n A_1、A_2、……、A_n A1、A2、……、An。今要将它们分成 M M M 组使得各组数据的数值和最平均即各组的均方差最小其实就是每组均值的方差。均方差公式如下 σ ∑ i 1 n ( x i − x ˉ ) 2 n , x ˉ ∑ i 1 n x i n \sigma \sqrt{\frac{\sum_{i1}^n(x_i - \bar{x})^2}{n}},\bar{x} \frac{\sum_{i1}^n x_i}{n} σn∑i1n(xi−xˉ)2 ,xˉn∑i1nxi 过程是这样的
每次模拟退火都先随机打乱一下序列每次都尝试交换序列中两个数的位置然后贪心地分组每次都把当前的数放到当前每组的数之和最小地组里面去然后看均方差是否变小用这个方式模拟退火。
#includeiostream
#includecstring
#includealgorithm
#includecmath
#includectimeusing namespace std;const int maxn 25, maxm 10;
int N, M;
int w[maxn], s[maxm];
double ans 1e8;double calc() {memset(s, 0, sizeof s);for (int i 0; i N; i) {int k 0;for (int j 0; j M; j) {if (s[j] s[k]) {k j;}}s[k] w[i];}double avg 0;for (int i 0; i M; i) avg (double)s[i] / M;double res 0;for (int i 0; i M; i) {res (s[i] - avg) * (s[i] - avg);}res sqrt(res / M);ans min(ans, res);return res;
}void simulate_anneal() {random_shuffle(w, w N);//最开始的t和答案的范围有关。for (double t 1e6; t 1e-6; t * 0.95) {int a rand() % N, b rand() % N;double x calc();swap(w[a], w[b]);double y calc();double delta y - x;if (exp(-delta / t) (double)rand() / RAND_MAX) {swap(w[a], w[b]);}}
}
int main() {scanf(%d%d, N, M);for (int i 0; i N; i) scanf(%d, w[i]);for (int i 0; i 100; i) simulate_anneal();printf(%.2f\n, ans);return 0;
}爬山法
爬山法必须是凸函数而且是单峰的。既然是凸函数为什么不用三分呢 在多年的 OI 生活中我意识到了人类是有极限的无论多么工于心计绞尽脑汁状态总是表示不出来的出题人的想法总是猜不透的边界总是写不对的——所以——我不三分了 JOJO 一维函数需要一个三分n 维函数需要 套用 n 个三分套用复杂度是指数级别的。——闫学灿 其实这个东西不咋考
207. 球形空间产生器
给一个 n 维空间的一个球给 n 1 个球上的点的坐标。求球心坐标。这个题是可以用高斯消元写的。不过这里展现爬山法的写法。
#includecstring
#includealgorithm
#includeiostream
#includecmath
using namespace std;const int maxn 15;
int N;
double d[maxn][maxn];
double ans[maxn]; //答案即球心坐标
double dist[maxn], delta[maxn]; //每个点到球心的距离每一维的偏移量。void calc(){double avg 0;for (int i 0; i N 1; i){dist[i] delta[i] 0;for (int j 0; j N; j)//求每个点到当前球心的距离dist[i] (d[i][j] - ans[j]) * (d[i][j] - ans[j]);dist[i] sqrt(dist[i]);//求所有点到球心距离的均值avg dist[i] / (N 1);}for (int i 0; i N 1; i)for (int j 0; j N; j)//这个似乎是求的梯度。delta[j] (dist[i] - avg) * (d[i][j] - ans[j]) / avg;
}int main(){scanf(%d, N);for (int i 0; i N; i) {for (int j 0; j N; j) {scanf(%lf, d[i][j]);//圆心先初始化为所有点的算术平均值ans[j] (d[i][j]) / (N 1);}}//爬山法对精度非常严格不然可能不收敛。for (double t 1e4; t 1e-6; t * 0.99997) {calc();for (int i 0; i N; i)ans[i] delta[i] * t;}for (int i 0; i N; i) printf(%.3lf , ans[i]);return 0;
}三分和二分
三分
把区间砍成三份设中间两个分界点分别为 x 1 m 1 , x 2 m 2 x_1 m_1, x_2 m_2 x1m1,x2m2. 从左到右三段区间记为 L 1 , L 2 , L 3 . L_1, L_2, L_3. L1,L2,L3. 这里我们假设 f ( x ) f(x) f(x) 是一个下凹的函数单峰函数如果是上凸的函数要学会转化。那么有两种情况
若 f ( m 1 ) f ( m 2 ) f(m1) f(m2) f(m1)f(m2)那么极值点一定不在 L 3 L_3 L3 这个区间可以舍掉 L 3 L_3 L3.若 f ( m 1 ) ≥ f ( m 2 ) f(m1) \ge f(m2) f(m1)≥f(m2)那么极值点一定不在 L 1 L_1 L1 这个区间可以舍掉 L 1 L_1 L1.
浮点数三分
注这个是有 f f f 极小值的情况。
const double eps 1e-8;
double f(m){//这里返回函数f(m)的值
}
double ternary_search(double l, double r){while(r - l eps){double m1 (l r) / 2;double m2 (m1 r) / 2;if(f(m1) f(m2)) r m2;else l m1;}return f(l);
}整数三分
注这个是 f f f 有极小值的情况。
double f(m){//这里返回函数f(m)的值
}
int ternary_search(int lb, int ub){while (ub - lb 1) {ll m1 (lb ub) / 2;ll m2 (m1 ub) / 2;ll f1 f(m1), f2 f(m2);if (f1 f2) lb m1;else ub m2;}return min(f(lb), f(ub));
}上面板子似乎有边界问题我改了改
ll ternary_search() {ll lb -2e17, ub 2e17;ll res min(f(lb), f(ub));while (ub lb) {ll m1 (lb ub) / 2;ll m2 (m1 ub) / 2;if (f(m1) f(m2)) lb m1 1;else ub m2 - 1;res min(res, min(f(m1), f(m2)));res min(res, min(f(lb), f(ub)));}return res;
}二分
整数二分新写法
bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid 1, r]时使用
int bsearch_1(int l, int r)
{while (l r){int mid l r 1;if (check(mid)) r mid; // check()判断mid是否满足性质else l mid 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
int bsearch_2(int l, int r)
{while (l r){int mid l r 1 1;if (check(mid)) l mid;else r mid - 1;}return l;
}
