大学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;
}