USACO20Feb Equilateral Triangles 【构造】【前缀和】

挺有趣的这题

虽然结论都是一样的，但是有两种思路看待这个问题：在曼哈顿距离下，和在切比雪夫距离下

（图片来自luogu）

我是从曼哈顿距离下看待这个问题的

若这三点构成一个曼哈顿等边三角形，我们其实可是虚构一个点O出来

图中A到C和B到C的换了路线，但是距离没有边，因为BC=AC且他们公用OC，BO=OA，那么我们就可以通过找等边三角形的方式先确定两个点

考虑第三个点C，我们发现一个45度的斜线上的所有点均满足要求，所以统计45度的前缀和即可

图中只是曼哈顿三角形的一个形式，还需要通过旋转整个图来匹配所有的形式

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define gi get_int()
const int MAXN = 600;
int get_int()
{
  int x = 0, y = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != ‘-‘)
    ch = getchar();
  if (ch == ‘-‘)
    y = -1, ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - ‘0‘, ch = getchar();
  return x * y;
}

class Node
{
public:
  int x, y;
} num[MAXN * MAXN + 10];

int map[MAXN][MAXN], count[MAXN][MAXN], tmp[MAXN][MAXN], sum[MAXN][MAXN], n, cnt, ans;

void getAns()
{
  memset(sum, 0, sizeof(sum));
  for (int i = 0; i < n * 2; i++)
    for (int j = 0; j < n * 2; j++) {
      if (i == 0)
        sum[i][j] = map[i][j];
      else
        sum[i][j] = sum[i - 1][j + 1] + map[i][j];
    }
  for (int i = 0; i < cnt; i++) {
    for (int j = 1; j <= n; j++) {
      int nowX = num[i].x - j, nowY = num[i].y + j;
      if (nowX < 0 || nowY >= n) break;
      if (map[nowX][nowY] == 0) continue;
      ans += sum[num[i].x + j][num[i].y + j] - sum[num[i].x][num[i].y + 2 * j];
    }
  }
}

void prep()
{
  cnt = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (map[i][j] == 0) continue;
      num[cnt].x = i;
      num[cnt++].y = j;
    }
}

void flip()
{
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      tmp[i][j] = map[i][j];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      map[j][i] = tmp[n - i - 1][j];
    }
  prep();
}

int main()
{
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);

  n = gi;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      char ch;
      std::cin >> ch;
      if (ch == ‘*‘)
        map[i][j] = 1;
    }
  for (int i = 0; i < 4; i++) {
    flip();
    getAns();
  }
  std::cout << ans;

  return 0;
}

USACO20Feb Equilateral Triangles 【构造】【前缀和】

原文：https://www.cnblogs.com/enisP/p/14790501.html