算法提高经典例题VIP免费

算法提高编号：ADV-1题目：两条直线关键字：排序类型：普通试题问题描述：给定平面上n个点。求两条直线，这两条直线互相垂直，而且它们与x轴的夹角为45度，并且n个点中离这两条直线的曼哈顿距离的最大值最小。两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和，一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。输入格式第一行包含一个数n。接下来n行，每行包含两个整数，表示n个点的坐标（横纵坐标的绝对值小于10^9）。输出格式输出一个值，表示最小的最大曼哈顿距离的值，保留一位小数。样例输入410012112样例输出1.0数据规模与约定对于30%的数据，n<=100。对于另外30%的数据，坐标范的绝对值小于100。对于100%的数据，n<=10^5。参考代码：该题暂时没有人完全正确，暂时没有该语言的参考程序。编号：ADV-2题目：矩阵翻转关键字：枚举贪心类型：普通试题问题描述：Ciel有一个N*N的矩阵，每个格子里都有一个整数。N是一个奇数，设X=(N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个X*X的子矩阵，并将这个子矩阵中的所有整数都乘以-1。现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。输入格式第一行为一个正整数N。接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1000。输出格式输出一个整数，表示操作后矩阵中所有数之和的最大值。样例输入3-1-11-11-11-1-1样例输出9数据规模与约定1<=N<=33，且N为奇数。参考代码：importjava.io.IOException;importjava.io.InputStream;publicclassMain{privatestaticclassMyScanner{privateInputStreamis=System.in;publicintnextInt(){try{inti;while((i=is.read())<45||i>57){}intmark=1,temp=0;if(i==45){mark=-1;i=is.read();}while(i>47&&i<58){temp=temp*10+i-48;i=is.read();}returntemp*mark;}catch(IOExceptione){e.printStackTrace();}return-1;}}privatestaticintx;privatestaticint[][]map,symbol;privatestaticint[][][][][]dp;privatestaticintcalculate(intj){intsum=0;for(inti=0;i0){sum+=dp[symbol[i][x]+1][symbol[x][j]+1][symbol[x][x]+1][i][j];continue;}inti2=x+i+1;intj2=x+j+1;inttemp=map[i][j];temp+=map[i][j2]*symbol[i][x];temp+=map[i2][j]*symbol[x][j];temp+=map[i2][j2]*symbol[i2][x]*symbol[x][j2];sum+=Math.abs(temp);dp[symbol[i][x]+1][symbol[x][j]+1][symbol[x][x]+1][i][j]=Math.abs(temp);}returnsum;}publicstaticvoidmain(String[]args){MyScannersc=newMyScanner();intn=sc.nextInt();map=newint[n][n];symbol=newint[n][n];dp=newint[3][3][3][n][n];for(inti=0;i=0;--count){intk=count;intcenter=(k&1)>0?1:-1;k>>=1;symbol[x][x]=center;intsum=map[x][x]*center;for(intj=0;j0?1:-1;symbol[j][x]=t;symbol[x+j+1][x]=t*center;sum+=map[j][x]*t;sum+=map[x+j+1][x]*t*center;k>>=1;}for(intj=0;j