[ZJ][一年後修裝版][C++] b113. 6. 線性系統求解＠Morris' Blog

2012-09-20 22:12:12| 人氣986| 回應1 | 上一篇 | 下一篇

[ZJ][一年後修裝版][C++] b113. 6. 線性系統求解

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

輸入說明：

輸出說明：

本題因為結果為無限組任一輸出不太好確定是否為正確，

所以若結果為無限組的話，輸出N即可。

測資改為多筆測資，

讀完第一個值n後，

後面的方程式請讀到EOF做結束。

(MAPLEWING 2011/01/19修正)

範例輸入：

[Input 1] <-純粹標明是第幾筆的測資，在測資的輸入裡面並沒有。3			2 8 4 22 5 1 54 10 -1 1[Input 2]31 2 3 08 10 12 67 8 9 6[Input 3]3			1 2 3 04 5 6 37 8 9 0[Input 4]13 10

範例輸出：

[Output 1] <-純粹標明是第幾筆的測資，您不用輸出這個東西。1x1 = 11x2 = -4x3 = 3[Output 2]N[Output 3]0[Output 4]1x1 = 10/3

提示：

出處：

93全國資訊學科能力決賽

#include <cstdio>
#include <iostream>
using namespace std;
class Frac {
    public:
        long long a, b;
        Frac() {
            a = 0, b = 1;
        }
        Frac(int x, int y) {
            a = x, b = y;
            reduce();
        }
        Frac operator+(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) + y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
        }
        Frac operator-(const Frac &y) {
            long long ta, tb;
            tb = this->b/gcd(this->b, y.b)*y.b;
            ta = this->a*(tb/this->b) - y.a*(tb/y.b);
            Frac z(ta, tb);
            return z;
        }
        Frac operator*(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.b;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.a;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
        }
        Frac operator/(const Frac &y) {
            long long tx, ty, tz, tw, g;
            tx = this->a, ty = y.a;
            g = gcd(tx, ty), tx /= g, ty /= g;
            tz = this->b, tw = y.b;
            g = gcd(tz, tw), tz /= g, tw /= g;
            Frac z(tx*tw, ty*tz);
            return z;
        }
    private:
        static long long gcd(long long x, long long y) {
            if(!y) return x;
            if(x < 0)   x *= -1;
            if(y < 0)   y *= -1;
            long long t;
            while(x%y)
                t = x, x = y, y = t%y;
            return y;
        }
        void reduce() {
            long long g = gcd(a, b);
            a /= g, b /= g;
            if(b < 0)   a *= -1, b *= -1;
        }
};
ostream& operator<<(ostream& out, const Frac&x) {
    out << x.a;
    if(x.b != 1)
        out << '/' << x.b;
    return out;
}
int main() {
    int n, m, i, j, k;
    scanf("%d", &n);
        m = n;
        Frac matrix[m][n+1];
        for(i = 0; i < m; i++) {
            for(j = 0; j <= n; j++) {
                scanf("%lld", &matrix[i][j].a);
            }
        }
        Frac tmp, one(1,1);
        int sol = 0;
        for(i = 0; i < m; i++) {
            int ch = i;
            for(j = i; j < m; j++)
                if(matrix[j][i].a) {
                    ch = j;
                    break;
                }
            if(i != ch)
                for(j = i; j <= n; j++)
                    tmp = matrix[i][j], matrix[i][j] = matrix[ch][j], matrix[ch][j] = tmp;
            if(matrix[i][i].a == 0) {
                sol = 1;continue;
            }
            tmp = one/matrix[i][i];
            for(j = i; j <= n; j++)
                matrix[i][j] = matrix[i][j]*tmp;
            for(j = 0; j < m; j++) {
                if(i == j) continue;
                tmp = matrix[j][i]/matrix[i][i];
                for(k = i; k <= n; k++) {
                    matrix[j][k] = matrix[j][k] - tmp*matrix[i][k];
                }
            }
        }
        if(!sol) {
            puts("1");
            for(i = 0; i < m; i++) {
                printf("x%d = ", i+1);
                cout << matrix[i][m] << endl;
            }
        }
        for(i = 0; i < m; i++) {
            for(j = 0; j < m; j++) {
                if(matrix[i][j].a)
                    break;
            }
            if(j == m) {
                if(matrix[i][j].a == 0)
                    sol = 2;
                else
                    sol = 3;
                break;
            }
        }
        if(sol == 2)
            puts("N");
        else if(sol == 3)
            puts("0");
    return 0;
}

我要檢舉

#b113#6. 線性系統求解

台長： Morris

您可能對以下文章有興趣

b067. 6. 下棋問題

[NOIP][dp背包] 2006 2.金明的预算方案

[ZJ][BIT] a484. 美麗風景遞增之路

[ZJ] d372. 4. 合法執行路徑問題

人氣(986) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][樹形dp] a265. 紅黑樹
此分類上一篇:[ZJ][sort] a480. 導彈攔截系統

回應(1)