ZOJ 3647 (격 점 의 삼각형 수)
1641 단어 조합 수학
제목 링크:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3647
제목: 격 점 네트워크 에서 삼각형 을 세 는 것 이다.
생각: 생각 은 먼저 C (3, n * m) 를 만 들 고 세 점 의 공선 상황 을 모두 줄 이 는 것 이다.
관건 은 세 개의 공선 을 찾 는 경우 가장 일반적인 사고방식 은 매 거 진 사각형 (즉, 매 거 진 세 개의 점 중 두 개의 점) 이다. 그리고 대각선 에 몇 개의 점 (매 거 진 세 번 째 점) 이 있 는 지 찾 아서 이 작은 사각형 이 전체 큰 사각형 에서 가장 많이 몇 번 나 타 났 는 지 다시 판단 하 는 것 이다.
code:
#include
#include
#include
#include
#define clr(x, y) memset(x, y, sizeof x)
using namespace std;
typedef long long LL;
const int maxn = 1005;
int n, m;
int gcd(int a, int b)
{
int mid;
while(b != 0)
{
mid = a;
a = b;
b = mid % b;
}
return a;
}
LL cal(int _n)
{
if (_n < 3) return 0;
return (LL)_n * (_n - 1) * (_n - 2) / 6;
}
int main()
{
while(scanf("%d%d", &n, &m) == 2)
{
LL ans = cal((n + 1) * (m + 1)) - cal(n + 1) * (m + 1) - cal(m + 1) * (n + 1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
ans -= (LL)(gcd(i, j) - 1) * (n - i + 1) * (m - j + 1) * 2;
}
}
printf("%lld
", ans);
}
return 0;
}
그리고 또 하나의 아 이 디 어 는 dp 입 니 다.
dp [n] [m] 는 n * m 의 사각형 안의 삼각형 의 개 수 를 나타 내 고 용 반 정리 로 dp [n - 1] [m] dp [n] [m - 1] dp [n - 1] [m - 1] [m - 1] 과 의 관 계 를 찾 습 니 다. 구체 적 인 것 은 아직 쓰 지 않 았 습 니 다. 시간 을 찾 아 보충 하 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 손(조합수학+용척dp)컨베이어 문의 뜻 약술: (0,0)(0,0)(0,0)(0,0)(0,0)(e x,e y)(ex,ey)(ex,ey)(ex,ey)(0,0)(0,0)(0,0)(x,0)(x+ax+ax, y+ax, y+y)(x+ax+ax+ax...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.