icon

2018-11-15

USACO Big Barn

Problem link

一开始也没想出来,今天晚上去植物园散步的时候突然就想出来了,好像以前做过类似的题目。

主要思想:

  1. 可以通过2D前缀和在$O(1)$时间内得到一个矩形内#的数量
  2. 先确定正方形的左上角,然后我们就能对正方形的对角线长度进行2分搜索:upper_bound(..., 0)
  3. 遍历所有点,进行步骤2

复杂度: $O(n^2 \log n)$

复习一下upper_bound, 返回第一个大于val的指针,如果没有返回end

/*
ID: mwx36mw2
TASK: bigbrn
LANG: C++11
*/
// Author: Wenxing Mei
//   Date: 2018-11-07 11:55
#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

int g[1001][1001], n, t;

int sum(int x1, int y1, int x2, int y2) {
  if (x1 > x2) return 0;
  return g[x2][y2] + g[x1 - 1][y1 - 1] - g[x1 - 1][y2] - g[x2][y1 - 1];
}

int a[1001];
int check(int x, int y) {
  // int l = 0, r = min(n - x, n - y);
  // int re = 0;
  // while (l <= r) {
  //   int mid = (l + r) / 2;
  //   if (sum(x, y, x + mid, y + mid) == 0) {
  //     l = mid + 1; // upperbound
  //     re = l;
  //   } else {
  //     r = mid - 1;
  //   }
  // }

  // printf("%d %d %d %d\n", x, y, l, r);
  // return re;

  // todo: do it with upper_bound
  // search [1, min(n-x+1,n-y+1) + 1)
  int re = *upper_bound(a + 1, a + min(n - x + 1, n - y + 1) + 1, 0, [&](int lhs, int rhs) {
    return sum(x, y, x + lhs - 1, y + lhs - 1) < sum(x, y, x + rhs - 1, y + rhs - 1);
  });
  // printf("%d %d %d\n", x, y, re);
  return re - 1;
}

int main() {
#ifndef LOCAL
  freopen("bigbrn.in", "r", stdin);
  freopen("bigbrn.out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
#endif
  rep(i, 0, 1001) a[i] = i;

  memset(g, 0, sizeof g);
  cin >> n >> t;
  rep(i, 0, t) {
    int x, y;
    cin >> x >> y;
    g[x][y] = 1;
  }

  rep(i, 1, n + 1) rep(j, 1, n + 1) { g[i][j] += g[i][j - 1]; }
  rep(j, 1, n + 1) rep(i, 1, n + 1) { g[i][j] += g[i - 1][j]; }

  int ans = 0;
  rep(i, 1, n + 1) {
    rep(j, 1, n + 1) { ans = max(ans, check(i, j)); }
  }
  cout << ans << '\n';

  return 0;
}

/*
USER: wenxing mei [mwx36mw2]
TASK: bigbrn
LANG: C++11

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.007 secs, 6440 KB]
   Test 2: TEST OK [0.007 secs, 6624 KB]
   Test 3: TEST OK [0.007 secs, 6228 KB]
   Test 4: TEST OK [0.007 secs, 6408 KB]
   Test 5: TEST OK [0.007 secs, 6592 KB]
   Test 6: TEST OK [0.007 secs, 6608 KB]
   Test 7: TEST OK [0.011 secs, 6220 KB]
   Test 8: TEST OK [0.011 secs, 6440 KB]
   Test 9: TEST OK [0.021 secs, 6220 KB]
   Test 10: TEST OK [0.070 secs, 6232 KB]
   Test 11: TEST OK [0.112 secs, 6228 KB]
   Test 12: TEST OK [0.119 secs, 6412 KB]
   Test 13: TEST OK [0.112 secs, 6228 KB]
   Test 14: TEST OK [0.102 secs, 6572 KB]
   Test 15: TEST OK [0.105 secs, 6512 KB]

All tests OK.
Your program ('bigbrn') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!
*/
comments powered by Disqus

search See also