题目链接：http://codeforces.com/contest/463/problem/C
题目意思：要在一个 n * n 大小的棋盘上放置两个bishop，bishop可以攻击的所有位置是包括经过bishop 位置的两条成90度的对角线所经过的所有坐标点。每个坐标点都有数字在上面，放置一个bishop后，可以获得能被放置的bishop攻击的所有坐标点的数字的和。但是有一个条件限制：同一个坐标点不能被两个bishop攻击，也就是四条对角线的交点不能是棋盘上的某个坐标点。求出在该条件限制下，两个bishop的放置位置以及能获得的最大和。
首先没有看到这个条件wa了很多次： place two bishops on the chessboard in such a way that there is no cell that is attacked by both of them。
好不容易看到之后，就各种TLE了，原来是读入问题！！！！涨姿势勒= =
可喜的是，原来自己最开始的做法是可取的，不过都是因为读入问题。
先介绍作者的灵活高效版：
先看一个图：
作者的做法有两个巧妙之处：
（1）求 bishop 能够攻击的所有坐标点的和，简而言之就是一个坐标点的两条对角线的和。
设两个数组d1[]，d2[]，用于保存两种方向下的对角线总和。（虚线部分标明了方向）。d1[]数组是通过d1[i+j] += board[i][j] 来算的，而 d2是这样：d2[i-j+n] += board[i][j]。
如果要求某个特定的坐标（i, j）的对角线和，那么就是d1[i+j] + d2[i-j+n] - board[i][j] ，之所以要减去board是因为每个坐标点的和都被重复算多了一次。
（2）判断攻击的方法
假设 bishop1 坐标为（i1, j1)，bishop2 为（i2, j2），如果( i1 + j1)，( i2 + j2) 同奇或同偶，那么就存在某一个坐标点同时被两个bishop 攻击！
所以要满足不存在某个坐标同时被两个bishop 攻击，就需要(i1 + j1) 和 （i2+j2) 处于一奇一偶的情况。那么奇数找一个最大值，偶数的话又找一个最大值，加起来就是两个bishop放置后能够获得的最大和了。
Time: 217ms Memory: 31400KB
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; typedef long long LL;
const int maxn = + ; LL board[maxn][maxn];
LL d1[maxn<<], d2[maxn<<];
pair<int, int> ans[];
LL tmp[]; inline LL read() // 这个读入是避免TLE的关键
{
int x = , f = ;
char ch = getchar();
while (ch >= '' && ch <= '')
{
x = *x + ch-'';
ch = getchar();
}
return (LL)(x * f);
} int main()
{
int n, x1, x2, y1, y2;
while (scanf("%d", &n) != EOF)
{
memset(d1, , sizeof(d1));
memset(d2, , sizeof(d2));
getchar(); // 不能省！n之后有个空格= =
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
board[i][j] = read();
d1[i+j] += board[i][j];
d2[i-j+n] += board[i][j];
}
}
tmp[] = tmp[] = -; // 0也可以，但是后面要>=，防止多次被替换还是-1好，省时一点吧
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
LL val = d1[i+j] + d2[i-j+n] - board[i][j];
if (val > tmp[(i+j)&])
{
tmp[(i+j)&] = val;
ans[(i+j)&].first = i;
ans[(i+j)&].second = j;
}
}
}
printf("%lld\n", tmp[] + tmp[]);
printf("%d %d %d %d\n", ans[].first, ans[].second, ans[].first, ans[].second);
}
return ;
}
接下来就是我的做法（大家可以忽略）
求对角线的和的时候，我是采取从第1行，第1列，最后1列出发来求得的，最后还是需要减去board[i][j]，代码量好大，因为太多重复 = =
至于判断攻击，除了利用abs函数（恰好对角线），还利用了之前做的一条 cf370A 的 Rook, Bishop and King的做法啦—— 判断Bishop 步数。
毕竟自己写的，留下纪念吧 = =
真是又长又耗时啊~~
Time: 1122ms Memory: 125504KB
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; typedef long long LL;
const int maxn = + ; struct node
{
LL s;
int x, y;
bool operator < (const node& a) const
{
return s < a.s;
}
}num[maxn*maxn]; LL board[maxn][maxn];
LL sum[maxn][maxn]; inline LL read() // 这个读入是避免TLE的关键
{
int x = , f = ;
char ch = getchar();
while (ch >= '' && ch <= '')
{
x = *x + ch-'';
ch = getchar();
}
return (LL)(x * f);
} int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
getchar();
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
board[i][j] = (LL)read();
}
memset(sum, , sizeof(sum));
// 第 1 行
int i = ;
for (int j = ; j <= n; j++)
{
LL ss = ;
int ti = i;
int tj = j; // 右下
while (ti <= n && tj <= n)
{
ss += board[ti][tj];
ti++;
tj++;
}
ti = i;
tj = j;
while (ti <= n && tj <= n)
{
sum[ti][tj] += ss;
ti++;
tj++;
}
ti = i;
tj = j; // 左下
ss = ;
while (ti <= n && tj >= )
{
ss += board[ti][tj];
ti++;
tj--;
}
ti = i;
tj = j;
while (ti <= n && tj >= )
{
sum[ti][tj] += ss;
ti++;
tj--;
}
}
// 第 1 列
int j = ;
for (int i = ; i <= n; i++)
{
LL ss = ;
int ti = i;
int tj = j;
while (ti <= n && tj <= n)
{
ss += board[ti][tj];
ti++;
tj++;
} ti = i;
tj = j;
while (ti <= n && tj <= n)
{
sum[ti][tj] += ss;
ti++;
tj++;
}
}
j = n;
for (int i = ; i <= n; i++)
{
LL ss = ;
int ti = i;
int tj = j;
while (ti <= n && tj >= )
{
ss += board[ti][tj];
ti++;
tj--;
}
ti = i;
tj = j;
while (ti <= n && tj >= )
{
sum[ti][tj] += ss;
ti++;
tj--;
}
}
int cnt = ;
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
num[cnt].x = i;
num[cnt].y = j;
num[cnt++].s = sum[i][j] - board[i][j];
}
}
int flag = ;
LL maxsum;
int x1, y1, x2, y2;
sort(num, num+cnt);
for (int i = cnt-; i >= && !flag; i--)
{
for (int j = i-; j >= && !flag; j--)
{
int t1 = num[i].x + num[i].y;
int t2 = abs(num[j].x - num[j].y);
if ((t1 + t2) % == )
continue;
if (abs(num[i].x-num[j].x) != abs(num[i].y - num[j].y))
{
flag = ;
x1 = num[i].x, x2 = num[j].x;
y1 = num[i].y, y2 = num[j].y;
maxsum = num[i].s + num[j].s;
break;
}
}
}
printf("%lld\n", maxsum);
printf("%d %d %d %d\n", x1, y1, x2, y2);
}
return ;
}