3346. 皇后问题

SmallY
n = int(input())
row = [0]*(n+1)
col = [0]*(n+1)
slash1 = [0]*(2*n)
slash2 = [0]*(2*n)
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    col[y] += 1
    slash1[x-y+(n-1)] += 1
    slash2[x+y-(n-1)] += 1
res = 0
for i in range(1, n+1):
    res += (row[i]*(row[i]-1))//2
    res += (col[i]*(col[i]-1))//2
for i in range(1, 2*n):
    res += (slash1[i]*(slash1[i]-1))//2
    res += (slash2[i]*(slash2[i]-1))//2
print(res)
成耀大佬

用模拟的话复杂度O(n^2),但是把每一行、列、斜线的棋子个数存下来用组合数公式遍历相加复杂度就是O(n)了。

Rainco

注意数据类型用long long不要用int

10175102262 LarsPendragon

别忘了还有副对角线[捂脸]

CoolCarrot

组合数直接用公式求,求的过程中记得保证乘数是long long类型,否则结果会溢出

LzQuarter

一个方向对角线有2n - 1条,需要构建好坐标到对角线的映射

你当前正在回复 博客/题目
存在问题!