HDU 3089 (쾌속 조세 프 링)

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=3089

제목: 모두 n 명 입 니 다.1 일부 터 k 명 씩 T 가 떨어진다.마지막 사람 한테 물 어 봐.초대형
문제 풀이 방향:
엄 청 난 n 을 제외 하고조세 프 링 의 누 드 문제 야.
조세 프 링 푸 시 공식, n 은 인원수 이 고 k 는 보폭 이다.
f(1)=0
f(n)=[f(n-1)+k]%i i∈[2,n]
f (n) 는 시작 위치 수정 을 거 쳐 시작 위 치 를 s, 즉 ans = [f (n) + s]% n 으로 설정 해 야 합 니 다.
기본 조세 프 링 최적화 는 k = 1 일 때 매번 전달 할 때마다 + 1 이 고 빠 른 속도 로 계산 할 수 있 습 니 다. f (n) = f (1) + n - 1

n 이 매우 클 때 이런 사고 에 따라 전달 과정 을 신속하게 간소화 할 수 있다.전달 후기 에 f (x) + k 는 긴 주기 내 에 < i, m 주기 가 있다 고 가정 합 니 다.
그러면 이 주기 가 합 쳐 진 결 과 는 f (x) + m * k 에 해당 합 니 다.빠르게 넘 어 갈 수 있 습 니 다.조건 제한: f (x) + m * k < i + (m - 1)
출시 가능:
m = 1 시 조건 제한: f (x) + k < i
m = 2 는, 조건 제한: f (x + 1) + k < i + 1 = f (x) + 2 * k < i + 1
m = m 시 조건 제한: f (x) + m * k < i + (m - 1)
화 간 은 m < (i - f (x) - 1)/(k - 1) 이 있 습 니 다. 정리 할 수 있다 면 (i - f (x) - 1)/(k - 1) - 1 입 니 다. 그렇지 않 으 면 (i - f (x) - 1)/(k - 1) 직접 정리 합 니 다.
이렇게 해서 i + = m, f (x) + = m * k 는 중간 과정 을 빠르게 뛰 어 넘 었 습 니 다.
i + m > n 은 빠 른 점프 가 경 계 를 넘 었 다 는 것 을 설명 합 니 다. 이 럴 때 f (n) = f (x) + (n - i - 1) * m 를 직접 계산 할 수 있 습 니 다.

#include "cstdio"

#define LL long long

LL solve(LL n,LL k,LL s=1)

{

    if(k==1) return (n-1+s)%n;

    LL ans=0;

    //ans=(ans+k)%i

    for(LL i=2;i<=n;)

    {

        if(ans+k<i) //    

        {

            LL leap;

            if((i-ans-1)%(k-1)==0) leap=(i-ans-1)/(k-1)-1;

            else leap=(i-ans-1)/(k-1);

            if(i+leap>n) return ((ans+(n+1-i)*k)+s)%n;

            i+=leap;

            ans+=leap*k;

        }

        else

        {

            ans=(ans+k)%i;

            i++;

        }

    }

    return (ans+s)%n;

}

int main()

{

    //freopen("in.txt","r",stdin);

    LL n,k;

    while(scanf("%I64d%I64d",&n,&k)!=EOF)

    {

        LL ans=solve(n,k);

        if(ans==0) printf("%I64d
",n);

        else printf("%I64d
",ans);

    }

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

기본 조세 프 링 최적화 는 k = 1 일 때 매번 전달 할 때마다 + 1 이 고 빠 른 속도 로 계산 할 수 있 습 니 다. n 이 매우 클 때 이런 사고 에 따라 전달 과정 을 신속하게 간소화 할 수 있다.전달 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 3089 (쾌속 조세 프 링)

좋은 웹페이지 즐겨찾기