Day11 备战CCF-CSP练习

Day 11

题目描述

题目很长，就不赘述了（主要是懒得写）

题目解析

Gauss 消元
题目的提示很明显，将元素守恒作为建立等式的基础。只要满足每一行元素守恒，即\(x_1 + x_2 + ··· + x_n = 0\)即可

元素个数为\(m\)，物质个数为\(n\)，增广矩阵的大下为\(m * (n + 1)\)，Gauss消元时间复杂度为\(O(m n^2)\) 数据量很小

要注意的是，这里有个特解，比如\(x_1 = x_2 = x_3 = ··· = x_n = 0\)一定是成立的，但是在题干描述中并不合法，所以在\(rankA = n\)时还是要求出具体的解，判断一下特解

C++代码

#include <bits/stdc++.h>using namespace std;
const int N = 110;
const double eps = 1e-10;int T;
int n;
map<string , int> mp;
int idx = 0;
double g[N][N];void process_str(int k , string x)
{int i = 0;while(i < x.size()){string s = "";while(i < x.size() && !isdigit(x[i])) s += x[i ++];int amount = 0;while(i < x.size() && isdigit(x[i])) amount = amount * 10 + x[i ++] - '0';if(!mp.count(s)) mp[s] = idx ++;g[mp[s]][k] = amount;}
}int gauss()
{int c, r;for (c = 0, r = 0; c < n; c ++ ){int t = r;for (int i = r; i < idx; i ++ )if (fabs(g[i][c]) > fabs(g[t][c]))t = i;if (fabs(g[t][c]) < eps) continue;for (int i = c; i <= n; i ++ ) swap(g[t][i], g[r][i]);for (int i = n; i >= c; i -- ) g[r][i] /= g[r][c];for (int i = r + 1; i < idx; i ++ )if (fabs(g[i][c]) > eps)for (int j = n; j >= c; j -- )g[i][j] -= g[r][j] * g[i][c];r ++ ;}if (r < n){for (int i = r; i < idx; i ++ )if (fabs(g[i][n]) > eps)return 0; // 无解return 1;}for (int i = idx - 1; i >= 0; i -- )for (int j = i + 1; j < n; j ++ )g[i][n] -= g[i][j] * g[j][n];bool f = true;for(int i = 0 ; i < idx ; i ++)f &= (g[i][n] < eps);if(f) return 0;return 1;
}void solve()
{memset(g , 0 , sizeof g);mp.clear();idx = 0;cin >> n;for(int i = 0 ; i < n ; i ++){string x;cin >> x;process_str(i , x);    }if(gauss()) cout << "Y\n";else cout << "N\n";
}int main()
{cin >> T;while(T --){solve();}return 0;
}