- A+B Problem
- 2016-10-31 11:56:32 @
###为了做这题我还特意去学习了单纯形.好难啊!听说别的神犇都推了好多数学结论,我打表看了一天愣是什么都没看出来...
测试数据 #0: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 580 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 576 KiB, score = 10
Accepted, time = 0 ms, mem = 580 KiB, score = 100
###代码:
#include <bits/stdc++.h>
const double eps = 1e-8;
double a[10][10];
int ans[10], n, m, A, B;
void pivot (int k, int x) {
ans[k] = x;
double t = -a[k][x]; a[k][x] = 0;
for (int i = 0; i <= n + m; ++ i)
a[k][i] /= t;
for (int i = 0; i <= m; a[i][x] = 0, ++ i)
for (int j = 0; j <= n + m; ++ j)
a[i][j] += a[i][x] * a[k][j];
a[k][x] = -1;
}
void simplex () {
int k, x;
while (1) {
k = x = 0;
for (int i = 1; i <= m; ++ i)
if (a[i][0] < -eps) { k = i; if (rand () & 1) break; }
if (!k) break;
for (int i = 1; !x && i <= n + m; ++ i)
if (eps < a[k][i]) x = i;
pivot (k, x);
}
double mx;
while (1) {
k = x = 0; mx = 1e9;
for (int i = 1; i <= n + m; ++ i)
if (eps < a[0][i]) { x = i; if (rand () & 1) break; }
if (!x) break;
for (int i = 1; i <= m; ++ i)
if (ans[i] != x && a[i][x] < -eps && a[i][0] / -a[i][x] < mx)
mx = a[i][0] / -a[i][x], k = i;
pivot (k, x);
}
printf ("%.0lf\n", a[0][0]);
}
int main () {
scanf ("%d %d", &A, &B), n = 2, m = 2;
a[0][1] = 1;
a[1][0] = A + B, a[1][1] = 1;
a[2][0] = -a[1][0], a[2][1] = 1;
for (int i = 1; i <= m; ++ i) ans[i] = n + i;
simplex ();
return 0;
}
4 条评论
-
xb010423 LV 7 @ 2017-01-19 09:05:28
呵呵呵......(看一群人在这胡扯)
-
2016-11-03 21:15:18@
单纯形是这题最简单的做法了,你还算运气好打了单纯形,不然一个月也难得A。
-
2016-11-03 21:10:33@
你看不出来也很正常,我尝试推导过这题的结论,根本推不动,听说这题难度绝非国王饮水记之流可比。
-
2016-11-03 21:10:30@
你看不出来也很正常,我尝试推导过这题的结论,根本推不动,听说这题难度绝非国王饮水记之流可比。
- 1
信息
- ID
- 1000
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 74397
- 已通过
- 28465
- 通过率
- 38%
- 被复制
- 222