ABC275C. Counting Squares题解

发表于 更新于

题目传送门

题意：给你一个 9×99\times 9 的矩阵，格子非黑即白，问有多少个不同的正方形，满足四个顶点都为黑色。

很容易想到直接枚举四个顶点的位置，判断、去重，但这个做法显然过于麻烦，难以实现。

于是我们可以想到如何更简洁地确定正方形位置，并尽量省掉去重的步骤。我的做法是枚举左上的顶点，再枚举右下方的某个顶点，统计得到的线段往右平移画出的正方形。实现上，我们用 (i1,j1),(i2,j2)(i_1,j_1),(i_2,j_2) 来表示前两个节点，则可以用数学方式推出后两个节点的坐标。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define rep(x,s,t) for(int x=s;x<t;x++)
signed main() {
    string s[9];
    for(int i=0;i<9;i++)
        cin>>s[i];
    int ans=0;
    rep(i1,0,9) rep(j1,0,9)
    rep(i2,i1+1,9) rep(j2,j1,9) {//只统计右下方的节点，达到去重的效果
        if(i1==i2&&j1==j2) continue;
        if(s[i1][j1]=='.'||s[i2][j2]=='.') continue;
        int i3=i2+(j1-j2),j3=j2+(i2-i1);
        int i4=i1+(j1-j2),j4=j1+(i2-i1);
        if(i3<0||i3>=9) continue;
        if(i4<0||i4>=9) continue;
        if(s[i3][j3]=='#'&&s[i4][j4]=='#') ans++;
    }
    cout<<ans<<endl;
    return 0;
}

这个做法的数学式子仍然不是显然的，可以考虑优化这一过程。我们发现这个做法主要的麻烦之处在于通过前两个点的坐标来计算后两个点较为麻烦，于是可以考虑用一个点加一个向量来变相的描述这两个点。这样的好处在于，我们可以直接得到坐标的变化量，从而更容易地计算后两个点的坐标。

By Nachia

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;

int main(){
    vector<string> A(9);
    rep(i,9) cin >> A[i];
    auto IsIn = [&](int x, int y) -> bool { return 0 <= x && x <= 8 && 0 <= y && y <= 8 && A[y][x] == '#'; };
    int ans = 0;
    rep(sx,9) rep(sy,9){
        for(int dx=0; dx<9; dx++) for(int dy=1; dy<9; dy++){
            if(IsIn(sx,sy) && IsIn(sx+dx, sy+dy) && IsIn(sx+dy, sy-dx) && IsIn(sx+dx+dy, sy+dy-dx)) ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

还有一种表示方法，考虑这个正方形的外接的、横平竖直的正方形。我们枚举这个外接正方形的左上角顶点及边长，同时枚举原正方形顶点在此大正方形边上的位置。这样表示四个顶点将会容易许多。

另外，此方法不需要去重，因为每个 (i,j,r,ri)(i,j,r,r_i) 都唯一确定一个正方形。

By ogino

1
2
3
4
5
6
7
8
9
10
11
Ss = []
for i in range(9):
  Ss.append(input())
ans = 0
for r in range(1,9):
  for i in range(9-r):
    for j in range(9-r):
      for ri in range(r):
        if Ss[i+ri][j] + Ss[i][j+r-ri] + Ss[i+r][j+ri] + Ss[i+r-ri][j+r] == "####":
          ans += 1
print(ans)

向量有关笔记：

  • 定义：一个有方向和大小（直观上一般用长度表示）的量被称为向量，只有大小的量被称为标量。
  • 向量加法：将两个向量首尾相连，从第一个向量的首指向第二个向量的尾的向量为加法的结果。
  • 向量数乘：一个向量与一个标量相乘，若标量为正，方向不变，大小乘该标量；若为 00 则得到零向量；若为负则方向相反，大小乘该标量的绝对值。
  • 线性相关性：两个向量的方向相同或相反时称这两个向量线性相关（或平行），否则线性无关。将一个向量分解成两个线性无关的向量分别数乘后相加的形式，分解方式唯一。
  • 直角坐标系下的表示：定义 i,j\mathbf{i,j} 分别表示方向为 x,yx,y 轴正方向的单位向量，则每个向量 a=ai+bj\mathbf{a}=a\mathbf{i}+b\mathbf{j}，定义该向量在直角坐标系下表示为 (ab)\begin{pmatrix}a\\b\end{pmatrix}。
  • 向量加法：在直角坐标系表示下，有 (ab)+(cd)=(a+cb+d)\begin{pmatrix}a\\b\end{pmatrix}+\begin{pmatrix}c\\d\end{pmatrix}=\begin{pmatrix}a+c\\b+d\end{pmatrix}。
  • 向量数乘：在直角坐标系表示下，有 k×(ab)=(kakb)k\times\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}ka\\kb\end{pmatrix}
  • 向量模长：一个标量，表示该向量的大小，写作 ∣a∣|\mathbf{a}|。
  • 向量点积：一个标量，定义为 a⋅b=∣a∣∣b∣cos⁡θ\mathbf{a}\cdot\mathbf{b}=|\mathbf{a}||\mathbf{b}|\cos\theta，其中 θ\theta 为两向量的夹角。几何意义为 b\mathbf{b} 在 a\mathbf{a} 方向上的投影模长乘 a\mathbf{a} 的模长；反之亦然。在直角坐标系表示下，有 (ab)⋅(cd)=ac+bd\begin{pmatrix}a\\b\end{pmatrix}\cdot\begin{pmatrix}c\\d\end{pmatrix}=ac+bd
  • 高维向量：同理推广，加法为对应项相加，数乘为每项分别相乘，点积为对应项相乘后相加。