CCF-CSP认证 2024年3月 4.化学方程式配平

题解：首先完成数据的读入，然后高斯消元求秩按题意解即可

#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;

using matrix = double[maxn][maxn];
using vect = array<double, maxn>;

const double eps = 1e-8;
int row[maxn], var[maxn];
int one_possible(matrix A, int n, int m, vect &ans)
{
    memset(row, -1, sizeof(row));
    int r = 0;
    for (int c = 0; c < m && r < n; ++c)
    {
        int x = r;
        for (int i = x + 1; i < n; ++i)
            if (fabs(A[i][c]) > fabs(A[x][c]))
                x = i;
        if (x != r)
            for (int j = 0; j <= m; ++j)
                swap(A[x][j], A[r][j]);
        if (fabs(A[r][c]) < eps)
            continue;
        for (int k = r + 1; k < n; ++k)
            for (int j = m; j >= c; --j)
                A[k][j] -= A[k][c] / A[r][c] * A[r][j];
        row[c] = r++;
    }
    for (int i = r; i < n; ++i)
        if (fabs(A[i][m]) > eps)
            return -1;
    for (int c = m - 1; c >= 0; --c)
    {
        int x = row[c];
        if (x < 0)
            ans[c] = 0;
        else
        {
            for (int i = x - 1; i >= 0; --i)
                A[i][m] -= A[i][c] / A[x][c] * A[x][m];
            ans[c] = A[x][m] / A[x][c];
        }
    }
    return r;
}
unordered_map<string,int> Yuansu;
int cnt=0;
void work_in(matrix &M,string s,int index)
{
    string yuansu="";
    double num=0;
    for(int i=0;i<s.size();)
    {
        while(isalpha(s[i]))
        {
            // cout<<s[i]<<endl;
            yuansu+=s[i];
            i++;
        }
        while(isdigit(s[i]))
        {
            num=num*10+(s[i]-'0');
            i++;
        }
        if(Yuansu.find(yuansu)==Yuansu.end())
        {
            Yuansu[yuansu]=cnt++;
        }
        // M[Yuansu[yuansu]][0]=1;
        M[Yuansu[yuansu]][index]=num;
        // cout<<yuansu<<": "<<Yuansu[yuansu]<<" :"<<num<<endl;
        num=0;
        yuansu="";
    }
    // print_M(M,cnt,m);
}
void print_M(matrix M,int n,int m)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            cout<<M[i][j]<<" ";
        }
        cout<<endl;
    }
}
void work()
{
    int q;
    cin>>q;
    
    while(q--)
    {
        matrix M={0};
        cnt=0;
        Yuansu.clear();
        int m;
        cin>>m;
        string s1;
        for(int j=0;j<m;j++)
        {
            cin>>s1;
            work_in(M,s1,j);
        }
        for(int j=0;j<cnt;j++)
        {
            M[j][m]=0;
        }
        // print_M(M,cnt,m);
        vect ans;
        int r=one_possible(M,cnt,m,ans);
        if(r==-1)
        {
            cout<<"N"<<endl;
            continue;
        }
        
        if(m-r>0)
        {
            cout<<"Y"<<endl;
        }
        else
        {
            cout<<"N"<<endl;
        }
        // cout<<"r,m:"<<r<<" "<<m<<endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    work();
    return 0;
}