比赛 2025暑期集训第6场 评测结果 AAAAAAAAAAAAAAA
题目名称 Equilateral Triangles 最终得分 100
用户昵称 OTTF 运行时间 1.518 s
代码语言 C++ 内存使用 5.97 MiB
提交时间 2025-07-12 11:45:10
显示代码纯文本

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

constexpr int N = 999;

int n;
char ch;
bool cow[N][N];
bool t[N][N];
int sum[N][N];
vector<pair<int, int>> nums;
int res;

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ch;
			if (ch == '*') {
				cow[i][j] = true;
			}
		}
	}

	for (int index = 1; index <= 4; index++) {
		nums.clear();
		for (int i = 1; i <= 2 * n; i++) {
			for (int j = 1; j <= 2 * n; j++) {
				if (cow[i][j]) {
					nums.emplace_back(i, j);
				}
			}
		}
		for (int i = 1; i <= 2 * n; i++) {
			for (int j = 1; j <= 2 * n; j++) {
				sum[i][j] = cow[i][j] + sum[i - 1][j + 1];
			}
		}

		for (int i = 0; i < nums.size(); i++) {
			auto [ix, iy] = nums[i];
			for (int j = 1; j <= n; j++) {
				int jx = ix - j;
				int jy = iy + j;
				if (jx < 1 || jy > n || !cow[jx][jy]) {
					continue;
				}
				res += sum[ix + j][iy + j] - sum[ix][iy + j + j];
			}
		}

		for (int i = 1; i <= 2 * n; i++) {
			for (int j = 1; j <= 2 * n; j++) {
				t[i][j] = cow[i][j];
			}
		}

		for (int i = 1; i <= 2 * n; i++) {
			for (int j = 1; j <= 2 * n; j++) {
				cow[i][j] = t[j][n - i + 1];
			}
		}
	}

	cout << res << endl;
	
	return 0;
}