比赛 |
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;
}