题解 P2643 【机房中出了一只大触！】

· · 题解

这道题嘛，肯定不用从化学的角度思考（神马乱凑啊，奇偶分析啦，化合价分析啦等等都可能过不去）。

如果你看到一个不会配平的方程式，如果你不想思考，你的第一反应一定是：待定系数法。

“待定系数法”什么意思？就是把它们都设出来，再解方程，那么你一定会想到——高斯消元。

举个例子（样例）:

我们设一下系数：

根据元素守恒，我们就得到了一个线性方程组：

显然，它有4个未知数，却只有3个方程，这是无法解的。

但你要发现，化学方程式的特点，如果去掉最大公因数为1和整数的条件，如果把每种物质的系数乘上（除以）同一个数后，它依旧是配平的，所以我们可以假设一个值为1，根据个人习惯，我假设x_4=1。

那么方程变成了：

解之，得

因此，原来的方程式为

我们只需要取分母的最小公倍数 L (本例中为9)，就得到正确的方程式：

所以，本题的基本思路就是一开始写一大堆字符串处理，然后开始高斯消元。

未知数的个数 n 等于物质的种类数，方程的个数 l 为元素的个数，数据一定会保证 l \geq n - 1 ，因为我们总是可以假设一个数为1。

如果 l > n - 1 ，如果我们加上绝对值优化的话，数据一定会保证最后 l - (n - 1) 行为全0，所以只需处理前 n-1 个数即可。

长(chou)的要死的代码：

(分数类和高斯消元)

typedef long long ll;

struct frac{
    ll x, y;
    frac (ll x0 = 0, ll y0 = 1): x(x0), y(y0) {
        if(!y0) y0 = 1;
        Canonicity();
    }
    void Canonicity(){
        if(y < 0){
            x = -x;
            y = -y;
        }
        ll d = gcd(abs(x), y);
        x /= d;
        y /= d;
    }
    frac operator + (const frac &b) const {return frac(x * b.y + y * b.x, y * b.y);}
    frac operator - (const frac &b) const {return frac(x * b.y - y * b.x, y * b.y);}
    frac operator * (const frac &b) const {return frac(x * b.x, y * b.y);}
    frac operator / (const frac &b) const {return frac(x * b.y, y * b.x);}
    bool operator < (const frac &b) const {return x * b.y < y * b.x;}
    bool operator > (const frac &b) const {return b < *this;}
    bool operator == (const frac &b) const {return x * b.y == y * b.x;}
    bool operator != (const frac &b) const {return !(*this == b);}
    void print(){
        if(y == 1) printf("%lld", x);
        else printf("%lld/%lld", x, y);
    }
};

inline frac frabs(frac z){
    if(z.x < 0) z.x = -z.x;
    return z;
}

template <typename T>
struct LnEqn{
    int r, c;
    T **m, *b;
    LnEqn (){m = NULL; b = NULL;}
    void resize(int r0, int c0){
        r = r0; c = c0; m = new T *[r];
        for(int i = 0; i < r; i++){
            m[i] = new T[c];
            memset(m[i], 0, c * sizeof(T));
        }
        b = new T[r];
        memset(b, 0, r * sizeof(T));
    }
    ~LnEqn (){
        if(m != NULL){for(int i = 0; i < r; i++) delete [] (m[i]); delete [] (m);}
        if(b != NULL) delete [] (b);
    }
    bool solve(){
        int i, j, k, maxi;
        T coe;
        for(k = 0; k < c; k++){
            maxi = k;
            for(i = k + 1; i < r; i++)
                if(frabs(m[i][k]) > frabs(m[maxi][k]))
                    maxi = i;
            if(frabs(m[maxi][k]) == frac(0)) return false;
            if(maxi != k){
                swap(m[maxi], m[k]);
                swap(b[maxi], b[k]);
            }
            coe = m[k][k];
            for(j = 0; j < c; j++)
                m[k][j] = m[k][j] / coe;
            b[k] = b[k] / coe;
            for(i = 0; i < r; i++){
                if((i == k ? ++i : i) >= r) break;
                coe = m[i][k];
                for(j = 0; j < c; j++)
                    m[i][j] = m[i][j] - coe * m[k][j];
                b[i] = b[i] - coe * b[k];
            }
        }
        return true;
    }
};

(字符串处理)

//nextint函数定义
int nextint(char *p, char **q){
    if(!isdigit(*p)){
        if(q != NULL) *q = p;
        return 1;
    }
    int b;
    for(b = *p - 48; isdigit(*++p); b = b * 10 + (*p - 48));
    if(q != NULL) *q = --p;
    return b;
}
//主字符串处理，适当的应用scanf技巧
for(n = 0; ; ++n){
        scanf("%[^ +=\n]", s[n]); // reading matter
        for(p = s[n]; *p; ++p){
            if(*p == '('){
                for(q = p; *q != ')'; ++q);
                Mul = nextint(++q, NULL);        
            }else if(*p == ')'){
                nextint(++p, &p);
                Mul = 1;
            }else if(*p >= 'A' && *p <= 'Z'){
                elem = *p - 65;
                if(p[1] >= 'a' && p[1] <= 'z'){
                    elem = elem * 26 + (p[1] - 65);
                    ++p;
                }
                mul = 1;
                if(isdigit(p[1]))
                    mul = nextint(++p, &p);
                eid = (~idx[elem] ? idx[elem] : idx[elem] = nid++);
                coe[eid][n] += Mul * mul;
                //printf("elem = %d, coe[%d][%d] = %d\n", elem, eid, n, coe[eid][n]);
            }
        }
        scanf("%[ +=\n]", s[N - 1]); // reading signs
        for(p = s[N - 1]; *p; ++p){
            if(*p == '=') eq = n + 1;
            if(*p <= '\n') break;
        }
        if(*p && *p <= '\n'){++n; break;}
    }