codeforces 463C. Gargari and Bishops 解题报告

题目链接：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 ;

 }

巴特西

codeforces 463C. Gargari and Bishops 解题报告

最新文章

热门文章