大学ACM学习笔记

高斯消元###

该来的总会来的系列

int gauss()

{

    for(int i=1;i<=n;i++)//按照列来枚举，当前之前i-1列全消完了

	{

        int k=i;

        for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[k][i]))k=j;//找一个系数绝对值最大的放在当前行，方便消元

        if(fabs(del=a[k][i])<eps)return 0;

        for(int j=i;j<=n+1;j++)swap(&a[i][j],&a[k][j]);

        for(int j=i;j<=n+1;j++)a[i][j]/=del;//把第i行的同时除系数

        for(int j=1;j<=n;j++)

			if(j!=i)

			{

            	del=a[j][i];

            	for(int k=i;k<=n+1;k++)a[j][k]-=a[i][k]*del;

        	}

    }

    return 1;

}

在大学，背诵代码不是那么重要了，重要的还是积累，这个高斯消元就是标准的把一个n*n方阵消成上三角形，然后这个程序比较优秀的是一遍消下面一遍消上面，所以一下子就变成了对角线上全为1的矩阵了，十分方便。

求n个点曼哈顿距离极值###

先假设为三维的，就是求 $ max { |a_i-a_j| + |b_i-b_j| + |c_i-c_j| } $
我们有绝对值不等式得$ |a|+|b| \geq |a+b| $

$ |a_i-a_j| + |b_i-b_j| + |c_i-c_j| = (\pm a_i \pm b_i \pm c_i )-( \pm a_j \pm b_j \pm c_j ) $

其中必须保证符号一致

所以我们就2^3次枚举 $ a_i，b_i，c_i $ 这个三元组的符号，然后每一次计算出最大值和最小值就可以了，代码如下

int calc()

{

	int ans=0,Min,Max;

	int i,j,k;

	for(i=0;i<8;i++)

	{

		Min=oo,Max=-oo;

		for(j=0;j<n;j++)

		{

			double sum=0;

			for(k=0;k<3;k++)

			{

				int t=i&1<<k;

				if(t)sum+=p[j][k];

				else sum-=p[j][k];

			}

			Max=MAX(Max,sum);Min=MIN(Min,sum);

		}

		ans=MAX(ans,Max-Min);

	}

	return ans;

}

巴特西

大学ACM学习笔记

高斯消元###

求n个点曼哈顿距离极值###

最新文章

热门文章