- 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
- 分类
- (无)
- 标签
- (无)
- 递交数
- 75087
- 已通过
- 28721
- 通过率
- 38%
- 被复制
- 261