高斯消元
其实就是加减消元法(模拟忒麻烦) 其实我觉得 学算法最主要是对算法的理解,因为裸题在正式赛里真的很少会出….都需要你对算法进行一番改动，如果你是死搬硬背的那肯定一脸懵逼
解N元一次方程组
就和加减消元一毛一样,大概分以下几个步骤 用一个数组存下未知数的系数
1.枚举所有未知数,一个个消掉: 2.找一个系数非0的,作减数 3.算一下所有系数的最小公因数,然后把每个系数(其他项也要)乘到最小公因数 4.然后把所有式子都减去那个作减数的式子,并将那个式子标记一下,下次不能再做减数 (因为其实已经被化简掉了,如果再用来当减数那就和用一个式子化简出两个未知数带进去的后果一样)
5.到最后每一个式子肯定都被化简成了未知数=a的这种形式,求一遍答案就可以了.
如果未知数比较少,比如才三个的话就可以考虑手推公式,这样效率高而且代码短
例题
Description 现在有 a,b,c 三种物品，如果他们安 x:y:z 混合，就能产生一种神奇的物品 D 。 当然不一定只产生一份 D ，但 a,b,c 的最简比一定是 x:y:z 现在给你 3 种可供选择的物品 A,B,C : A,B,C 都是由 a,b,c Input 第一行三个整数，表示 d 的配比（ x,y,z ） 接下来三行，表示 A,B,C 的配比，每行三个整数（ <=10000 ） 。 Output 四个整数，分别表示在 A+B+C 最 小 的前提下 A,B,C ,D 的个数 目标答案 <=10000 Sample Input 3 4 5 1 2 3 3 7 1 2 1 2 Sample Output 8 1 5 7 Data Constraint Hint 50% 的数据保证答案中任意一个数 <=100 100% 的数据保证答案中任意一个数 <=10000
#include <cstdio> #include <iostream> #include <cstring> using namespace std; typedef long long ll; ll cpy[3][4],f[3][4]; //[第几条式子][第几个元] ll ans[4]; bool bz[4]; bool isInt; int gcd(ll a,ll b){ return (b==0)?a:gcd(b,a%b); } int abs(int x) { return (x>0)?x:-x; } int lcm(ll a,ll b) { return (a*b/gcd(a,b)); } void defact() { //这名字是我乱取的233 memset(bz,0,sizeof bz); ll f0,l,divi; for (int i=1; i<4; i++) { //第几个元 f0=0; while (f[f0][i]==0 || bz[f0]) f0=f0%3+1; //找第一个系数非0的 bz[f0]=true; l=f[f0][i]; for(int j=0; j<3; j++) if (f[j][i]) l=lcm(l,f[j][i]); //求所有系数的lcm for(int j=0; j<3; j++) { if (!f[j][i]) continue; divi = l/f[j][i]; for (int k=0; k<4; k++) { f[j][k]*=divi; //把整个式子全部乘上lcm/f[j][i] } } for (int j=0; j<3; j++) { if (j!=f0) { if (!f[j][i]) continue; //如果系数已经是0了那就不用管 for (int k=0;k<4; k++) { f[j][k]-=f[f0][k]; //消元 } } } } for(int i=0; i<3; i++) //找答案 for(int j=1; j<4; j++) { if (f[i][j]!=0) { if (f[i][0]%f[i][j]) isInt=false; ans[j]=f[i][0]/f[i][j]; break; } } } int main(){ for (int i=0; i<3; i++) { scanf("%d",&f[i][0]); } for (int i=0; i<3; i++) { scanf("%d %d %d",&f[0][i+1],&f[1][i+1],&f[2][i+1]); } memcpy(cpy,f,sizeof f); for (int d=1; d<=10000; d++) { memcpy(f,cpy,sizeof cpy); for (int i=0; i<3; i++) { f[i][0]=f[i][0]*d; } isInt=true; defact(); if (isInt && ans[1]>=0 && ans[2]>=0 && ans[3]>=0) { cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<" "<<d<<endl; return 0; } } cout<<"NONE"<<endl;} 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 源自于 JokerWYT的一篇挺好的文章。
