admin 管理员组文章数量: 887006
洛谷P2179 骑行川藏
什么毒瘤...
解：n = 1的，发现就是一个二次函数，解出来一个v的取值范围，选最大的即可。
n = 2的，猜测可以三分。于是先二分给第一段路多少能量，然后用上面的方法求第二段路的最短时间。注意剩余能量不足跑完第二段路的时候，返回INF。
正解是啥拉格朗日乘子法，完全搞不倒...
1 /**
2 * There is no end though there is a start in space. ---Infinity.
3 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
4 * Only the person who was wisdom can read the most foolish one from the history.
5 * The fish that lives in the sea doesn't know the world in the land.
6 * It also ruins and goes if they have wisdom.
7 * It is funnier that man exceeds the speed of light than fish start living in the land.
8 * It can be said that this is an final ultimatum from the god to the people who can fight.
9 *
10 * Steins;Gate
11 */
12
13 #include <bits/stdc++.h>
14
15 const int N = 10010;
16
17 double k[N], s[N], vv[N], E;
18 int n;
19
20 namespace n1 {
21 inline void solve() {
22 double v = vv[1] + sqrt(E / s[1] / k[1]);
23 printf("%.10f\n", s[1] / v);
24 return;
25 }
26 }
27
28 namespace n2 {
29
30 inline double cal(double v) {
31 double ans = s[1] / v;
32 double delta = k[1] * s[1] * (vv[1] - v) * (vv[1] - v);
33 //printf("E - delta = %.10f \n", E - delta);
34 double v2 = vv[2] + sqrt((E - delta) / s[2] / k[2]);
35 if(v2 < 0) return 1e14;
36 //printf("v2 %.10f = %.10f + sqrt(%.10f / %.10f / %.10f) \n", v2, vv[2], E - delta, s[2], k[2]);
37 //printf(" = %.10f + %.10f \n", vv[2], sqrt((E - delta) / s[2] / k[2]));
38 //printf("cal %.10f -> %.10f + %.10f / %.10f \n", v, ans, s[2], v2);
39 return ans + s[2] / v2;
40 }
41
42 inline void solve() {
43
44 double l = 0, r = vv[1] + sqrt(E / s[1] / k[1]);
45 for(int i = 1; i <= 100; i++) {
46 double mid = (l + r) / 2;
47 //printf("l = %.10f r = %.10f \n", l, r);
48 double ml = mid - (r - l) / 6, mr = mid + (r - l) / 6;
49 double vl = cal(ml), vr = cal(mr);
50 if(vl > vr) {
51 l = ml;
52 }
53 else {
54 r = mr;
55 }
56 }
57 printf("%.10f\n", cal(r));
58 return;
59 }
60 }
61
62 int main() {
63 scanf("%d%lf", &n, &E);
64 for(int i = 1; i <= n; i++) {
65 scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
66 }
67
68 if(n == 1) {
69 n1::solve();
70 return 0;
71 }
72
73 if(n == 2) {
74 n2::solve();
75 return 0;
76 }
77
78 return 0;
79 } 40分代码 学习了一波模拟退火，突然发现这道题可能比较适合乱搞？于是开始疯狂调参最后成功在LOJ和洛谷上A掉了...
考虑如何随机化得出解。我们随机每条路的能量分配即可。
风速为负的每条路有一个能量下限。在此基础上我们把多出来的能量作为自由能量来进行分配。
初始解就是把自由能量均分...之后我们每次随机出两条路a和b，把a的若干能量给b。这里我给的能量是min(a的能量，T * c) * Rand(0, 1)
这里的c是一个参数。于是我们做到了让调整量随着温度的降低而变小。
然后瞎调一波，从0分优化到了100分......中间有很多脑洞大开改参数的过程...
最好玩的是LOJ的AC代码在洛谷上95分，洛谷的AC代码在LOJ上90分...
1 // luogu-judger-enable-o2
2 #include <bits/stdc++.h>
3
4 const int N = 10010, INF = 0x3f3f3f3f;
5
6 double k[N], s[N], vv[N], E;
7 int n;
8
9 namespace n1 {
10 inline void solve() {
11 double v = vv[1] + sqrt(E / s[1] / k[1]);
12 printf("%.10f\n", s[1] / v);
13 return;
14 }
15 }
16
17 namespace n2 {
18
19 inline double cal(double v) {
20 double ans = s[1] / v;
21 double delta = k[1] * s[1] * (vv[1] - v) * (vv[1] - v);
22 double v2 = vv[2] + sqrt((E - delta) / s[2] / k[2]);
23 if(v2 < 0) return 1e14;
24 return ans + s[2] / v2;
25 }
26
27 inline void solve() {
28
29 double l = 0, r = vv[1] + sqrt(E / s[1] / k[1]);
30 for(int i = 1; i <= 100; i++) {
31 double mid = (l + r) / 2;
32 //printf("l = %.10f r = %.10f \n", l, r);
33 double ml = mid - (r - l) / 6, mr = mid + (r - l) / 6;
34 double vl = cal(ml), vr = cal(mr);
35 if(vl > vr) {
36 l = ml;
37 }
38 else {
39 r = mr;
40 }
41 }
42 printf("%.10f\n", cal(r));
43 return;
44 }
45 }
46
47 namespace Fire {
48 const double eps = 1e-13;
49 double T = 1, dT = 0.999992;
50 double nowE[N], temp[N], lm[N];
51 int test[N];
52
53 inline int rd(int l, int r) {
54 return rand() % (r - l + 1) + l;
55 }
56
57 inline double Rand() {
58 return 1.0 * rand() / RAND_MAX;
59 }
60
61 inline double calv(int i, double e) {
62 return vv[i] + sqrt(e / k[i] / s[i]);
63 }
64
65 inline double calt(int i, double e) {
66 return s[i] / (vv[i] + sqrt(e / k[i] / s[i]));
67 }
68
69 inline double init() {
70 for(int i = 1; i <= n; i++) {
71 if(vv[i] < -eps) {
72 lm[i] = k[i] * s[i] * vv[i] * vv[i];
73 E -= lm[i];
74 }
75 }
76 double dt = E / n, ans = 0;
77 for(int i = 1; i <= n; i++) {
78 nowE[i] = dt;
79 ans += calt(i, lm[i] + nowE[i]);
80 }
81 return ans;
82 }
83
84 inline void solve() {
85 double ans, fin = 1e14;
86 srand(69);
87 for(int A = 1; A <= 1; A++) {
88 ans = init();
89 fin = std::min(ans, fin);
90 while(T > eps) {
91 /// Random a new solution
92 int a = rd(1, n), b = rd(1, n);
93 while(a == b) {
94 a = rd(1, n), b = rd(1, n);
95 }
96 double deltaE = std::min((long double)nowE[a], (long double)T * 1e8) * Rand();
97 temp[a] = nowE[a] - deltaE;
98 temp[b] = nowE[b] + deltaE;
99
100 double New = ans - calt(a, lm[a] + nowE[a]) - calt(b, lm[b] + nowE[b])
101 + calt(a, lm[a] + temp[a]) + calt(b, lm[b] + temp[b]);
102
103 fin = std::min(fin, New);
104 if(New < ans || Rand() < exp((ans - New) / T)) {
105 ans = New;
106 nowE[a] = temp[a];
107 nowE[b] = temp[b];
108 }
109 T = T * dT;
110 }
111 }
112 printf("%.10f\n", fin);
113 return;
114 }
115 }
116
117 int main() {
118 scanf("%d%lf", &n, &E);
119 for(int i = 1; i <= n; i++) {
120 scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
121 }
122
123 if(n == 1) {
124 n1::solve();
125 return 0;
126 }
127
128 if(n == 2) {
129 n2::solve();
130 return 0;
131 }
132
133 Fire::solve();
134 return 0;
135 } 洛谷AC代码 1 #include <bits/stdc++.h>
2
3 const int N = 10010, INF = 0x3f3f3f3f;
4
5 double k[N], s[N], vv[N], E;
6 int n;
7
8 namespace n1 {
9 inline void solve() {
10 double v = vv[1] + sqrt(E / s[1] / k[1]);
11 printf("%.10f\n", s[1] / v);
12 return;
13 }
14 }
15
16 namespace n2 {
17
18 inline double cal(double v) {
19 double ans = s[1] / v;
20 double delta = k[1] * s[1] * (vv[1] - v) * (vv[1] - v);
21 double v2 = vv[2] + sqrt((E - delta) / s[2] / k[2]);
22 if(v2 < 0) return 1e14;
23 return ans + s[2] / v2;
24 }
25
26 inline void solve() {
27
28 double l = 0, r = vv[1] + sqrt(E / s[1] / k[1]);
29 for(int i = 1; i <= 100; i++) {
30 double mid = (l + r) / 2;
31 //printf("l = %.10f r = %.10f \n", l, r);
32 double ml = mid - (r - l) / 6, mr = mid + (r - l) / 6;
33 double vl = cal(ml), vr = cal(mr);
34 if(vl > vr) {
35 l = ml;
36 }
37 else {
38 r = mr;
39 }
40 }
41 printf("%.10f\n", cal(r));
42 return;
43 }
44 }
45
46 namespace Fire {
47 const double eps = 1e-13;
48 double T = 1000, dT = 0.99999;
49 double nowE[N], temp[N], lm[N];
50 int test[N];
51
52 inline int rd(int l, int r) {
53 return rand() % (r - l + 1) + l;
54 }
55
56 inline double Rand() {
57 return 1.0 * rand() / RAND_MAX;
58 }
59
60 inline double calv(int i, double e) {
61 return vv[i] + sqrt(e / k[i] / s[i]);
62 }
63
64 inline double calt(int i, double e) {
65 return s[i] / (vv[i] + sqrt(e / k[i] / s[i]));
66 }
67
68 inline double init() {
69 for(int i = 1; i <= n; i++) {
70 if(vv[i] < -eps) {
71 lm[i] = k[i] * s[i] * vv[i] * vv[i];
72 E -= lm[i];
73 }
74 }
75 double dt = E / n, ans = 0;
76 for(int i = 1; i <= n; i++) {
77 nowE[i] = dt;
78 ans += calt(i, lm[i] + nowE[i]);
79 }
80 return ans;
81 }
82
83 inline void solve() {
84 double ans, fin = 1e14;
85 srand(2332);
86 for(int A = 1; A <= 1; A++) {
87 ans = init();
88 fin = std::min(ans, fin);
89 while(T > eps) {
90 /// Random a new solution
91 int a = rd(1, n), b = rd(1, n);
92 while(a == b) {
93 a = rd(1, n), b = rd(1, n);
94 }
95 double deltaE = std::min((long double)nowE[a], (long double)T * 1e11) * Rand();
96 temp[a] = nowE[a] - deltaE;
97 temp[b] = nowE[b] + deltaE;
98
99 double New = ans - calt(a, lm[a] + nowE[a]) - calt(b, lm[b] + nowE[b])
100 + calt(a, lm[a] + temp[a]) + calt(b, lm[b] + temp[b]);
101
102 fin = std::min(fin, New);
103 if(New < ans || Rand() < exp((ans - New) / T)) {
104 ans = New;
105 nowE[a] = temp[a];
106 nowE[b] = temp[b];
107 }
108 T = T * dT;
109 }
110 }
111 printf("%.8f\n", fin);
112 return;
113 }
114 }
115
116 int main() {
117 scanf("%d%lf", &n, &E);
118 for(int i = 1; i <= n; i++) {
119 scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);
120 }
121
122 if(n == 1) {
123 n1::solve();
124 return 0;
125 }
126
127 if(n == 2) {
128 n2::solve();
129 return 0;
130 }
131
132 Fire::solve();
133 return 0;
134 } LOJAC代码 调参心得：△T越接近1，就越慢，同时效果越好。初始温度太大可能会超时...
转载于:.html
本文标签： 洛谷P2179 骑行川藏
版权声明：本文标题：洛谷P2179 骑行川藏 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732360522h1535083.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论