首页 > 代码库 > Codeforces 463C Gargari and Bishops

Codeforces 463C Gargari and Bishops

2024-07-20 09:17:26   219人阅读

首先要记得黑白染色原理，题目里要求矩阵里的两个点，两个点对应的对角线不能有重合点，其实就是黑白染色嘛，找坐标相加为奇数和坐标相加为偶数的点即可

然后就是题目要求的和值最大，暴力不行，所以预处理出来每个对角线的和值，发现其实每个对角线要么是 y=x+b或者y=-x+b,b是独一无二的，所以以b为特征点来记录每个对角线的和值，当然b可能为负，所以人为的+3*n使其为正（其实+n就可以为正，+3*n是因为还要跟x+y=b区分出来）。

注意处理细节，然后还是蛮简单的

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define LL __int64using namespace std;int n;int  mat[2010][2010];LL sum[4020*3];int main(){    while (scanf("%d",&n)!=EOF)    {        for (int i=1;i<=n;i++)            for(int j=1;j<=n;j++) scanf("%d",&mat[i][j]);        for (int i=1;i<=n;i++)            for (int j=1;j<=n;j++){            sum[i+j]+=(LL)mat[i][j];            sum[i-j+3*n]+=(LL)mat[i][j];        }        LL ans1=-1,ans2=-1;        int x1,y1,x2,y2;        for (int i=1;i<=n;i++){            for (int j=1;j<=n;j++){                LL ret=sum[i+j]+sum[i-j+3*n];                ret-=(LL)mat[i][j];                if ((i+j)&1){                    if (ans1<ret){                        ans1=ret;                        x1=i;                        y1=j;                    }                }                else{                    if (ans2<ret){                        ans2=ret;                        x2=i;                        y2=j;                    }                }            }        }        //cout<<sum[x1+y1]<<" "<<sum[x1-y1+3*n]<<endl;        //cout<<ans1<<" "<<ans2<<endl;        printf("%I64d\n",ans1+ans2);        printf("%d %d %d %d\n",x1,y1,x2,y2);    }    return 0;}

 

Codeforces 463C Gargari and Bishops


联系
我们