80pts求调 12和13测试点WA
查看原帖
80pts求调 12和13测试点WA
226839
Jorylee楼主2021/3/31 21:14

辅助图 1-1-1

#include<bits/stdc++.h>
using namespace std;
int n,bord[1010][1010];
int b_l[2010]/*蓝色线*/,b_r[2010]/*红色线*/;
int ans = 0;/*最终答案*/ 
//无效的返回值 
const pair<int,int> none = make_pair(-1,-1);
pair<int,int> P;/*全局临时变量*/
//计算任意红线和蓝线交点的坐标 
pair<int,int> point(int l/*蓝色线编号*/,int r/*红色线编号*/) {
	pair<int,int> res;
	if(((l-r+n-1)%2!=0)||((l+r-n+1)%2!=0)||/*判断点的坐标是否在格点上,是否在格子内,不符合要求返回none*/
	        (l-r+n-1)/2<0||(l-r+n-1)/2>(n-1)||(l+r-n+1)/2<0||(l+r-n+1)/2>(n-1)) return none;
	else return make_pair((l-r+n-1)/2,(l+r-n+1)/2);//返回一个包含交点坐标的pair 
}
//返回任意红线和蓝线的交点点的数值 
int cut(int l,int r) {
	P = point(l,r);//计算交点坐标 
	if(P!=none) return bord[P.second][P.first];//判断交点是否有效 
	else return 0;//无效既没有交点,返回0 
}
int main() {
	//freopen("pacman.in","r",stdin);
	//freopen("pacman.out","w",stdout);
	scanf("%d",&n);
	for(int y=0; y<n; y++) {
		for(int x=0; x<n; x++) {
			cin>>bord[y][x];
			b_l[x+y]+=bord[y][x];
			b_r[(n-1-x)+y]+=bord[y][x];
		}
	}
	//从题意可得,任意选取一条蓝色线都能得到一个与众不同的矩形 
	for(int al=0; al<n; al++) {//枚举第一个矩形(a)的蓝色线 
		for(int bl=0; bl<n; bl++) {//枚举第二个矩形(b)的蓝色线 
			if(al==bl) continue;//不能选同一个 
			int now = 0;//当前ans 
			int al_2 = 2*(n-1)-al;//a矩形的另一个蓝色线 
			int ar = (n-1)-al;//a矩形的红色线 
			int ar_2 = 2*(n-1)-ar;//a矩形的另一个红色线 
			//计算矩形上所有点的和,也就是四条线的和 
			now+=b_l[al];
			if(al_2!=al) now+=b_l[al_2];//判断是不是对角线 

			now+=b_r[ar];
			if(ar_2!=ar) now+=b_r[ar_2];//判断是不是对角线 

			//去除矩形内4条线的重复点,既交点 
			if(al_2==al) {//判断是不是对角线 
				if(ar_2==ar) {//判断是不是对角线 
					now-=cut(al,ar);
				} else {
					now-=cut(al,ar);
					now-=cut(al,ar_2);
				}
			} else {
				if(ar_2==ar) {//判断是不是对角线 
					now-=cut(al,ar);
					now-=cut(al_2,ar);
				} else {
					now-=cut(al,ar);
					now-=cut(al,ar_2);
					now-=cut(al_2,ar);
					now-=cut(al_2,ar_2);
				}
			}


			int bl_2 = 2*(n-1)-bl;//b矩形的另一个蓝色线 
			int br = (n-1)-bl;//b矩形的红色线 
			int br_2 = 2*(n-1)-br;//b矩形的另一个红色线 
			
			//计算矩形上所有点的和,也就是四条线的和 	
			now+=b_l[bl];
			if(bl_2!=bl) now+=b_l[bl_2];

			now+=b_r[br];
			if(br_2!=br) now+=b_r[br_2];
			
			//去除矩形内4条线的重复点,既交点 
			if(bl_2==bl) {//判断是不是对角线 
				if(br_2==br) {//判断是不是对角线 
					now-=cut(bl,br);
				} else {
					now-=cut(bl,br);
					now-=cut(bl,br_2);
				}
			} else {
				if(br_2==br) {//判断是不是对角线 
					now-=cut(bl,br);
					now-=cut(bl_2,br);
				} else {
					now-=cut(bl,br);
					now-=cut(bl,br_2);
					now-=cut(bl_2,br);
					now-=cut(bl_2,br_2);
				}
			}
			
			//去除两个矩形之间的重复点,计算所有两个矩形之间的蓝线和红线的交点的值并减去 
			if(al==al_2){//判断是不是对角线 
				if(br==br_2){//判断是不是对角线 
					now-=cut(al,br);
				}else{
					now-=cut(al,br);
					now-=cut(al,br_2);
				}
			}else{
				if(br==br_2){//判断是不是对角线 
					now-=cut(al,br);
					now-=cut(al_2,br);
				}else{
					now-=cut(al,br);
					now-=cut(al_2,br_2);
					now-=cut(al,br);
					now-=cut(al_2,br_2);
				}
			}
			
			if(ar==ar_2){//判断是不是对角线 
				if(bl==bl_2){//判断是不是对角线 
					now-=cut(bl,ar);
				}else{
					now-=cut(bl,ar);
					now-=cut(bl_2,ar);
				}
			}else{
				if(bl==bl_2){//判断是不是对角线 
					now-=cut(bl,ar);
					now-=cut(bl,ar_2);
				}else{//判断是不是对角线 
					now-=cut(bl,ar);
					now-=cut(bl_2,ar_2);
					now-=cut(bl,ar);
					now-=cut(bl_2,ar_2);
				}
			}
			//更新答案 
			ans = max(ans,now);
		}
	}
	//输出答案 
	printf("%d",ans);
	return 0;
}
2021/3/31 21:14
加载中...