【CodeForces 621B】Wet Shark and Bishops

제목.
제목
1000 * 1000 칸 에 n ≤ 200 * 8201 점 의 좌 표를 드 립 니 다. 한 대각선 에 얼마나 많은 쌍 이 있 는 지 구 합 니 다.
분석 하 다.
점 마다 공 대각선 이 몇 개 있 는 점 을 구하 면 시간 이 초과 된다.
 
대각선 이 모두 주 대각선 1999 개 + 부 대각선 1999 개 라 는 것 을 감안 하면 우 리 는 모든 대각선 에 몇 개의 점 이 있 는 지 구 할 수 있다.
같은 주 대각선 에 있 는 요 소 는 a [i] 개가 있 고 C (a [i], 2) 대 점 이 있 습 니 다.
같은 대각선 에 있 는 요 소 는 b [i] 개 이 고 C (b [i], 2) 대 점 이 있 습 니 다.
 
x 와 y 를 읽 은 후,
x + y 는 같은 대각선 에 있 습 니 다. x + y 범 위 는 (2, 2000) 입 니 다.
x - y 같은 것 은 같은 대각선 이 고 x - y 범 위 는 (- 999, 999) 이 며 1001 을 더 하면 (2, 2000) 이다.
x + y = = 2 와 2000 의 대각선 은 하나의 원소 만 있 고 x - y + 1000 = = 2 와 2000 의 원소 만 있 기 때문에 x + y = = 2 에서 1998, x - y + 1001 = = 2 에서 1998 의 대각선 만 구하 면 된다.
이렇게 하면 매번 a [i] 와 b [i] 의 대각선 에 몇 개의 점 이 있 는 지 계산 할 수 있다. i = 2 부터 1998 까지
시간 초과 코드
#include <stdio.h>
#define N 200005
long long n,x[N],y[N],ans;
int main()
{
    scanf("%I64d",&n);
    for(int i=1;i<=n;i++)scanf("%I64d%I64d",&x[i],&y[i]);
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
        if(x[i]+y[i]==x[j]+y[j])ans++;
        if(x[i]-y[i]==x[j]-y[j])ans++;
    }
    printf("%I64d",ans);
    return 0;
}

AC 코드
#include <stdio.h>
#define N 2005
long long n,x,y,a[N],b[N],ans;
int main()
{
    scanf("%I64d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%I64d%I64d",&x,&y);
        a[x-y+1001]++;
        b[x+y]++;
    }
    for(int i=2; i<=1998; i++)ans+=a[i]*(a[i]-1)/2+b[i]*(b[i]-1)/2;
    printf("%I64d",ans);
    return 0;
}
Ajax(http://www.w3school.com.cn/ajax/ajax_xmlhttprequest.asp)
LruCache의 기본 사용 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage