HDU 4961 (항 전 다 교 \ # 9 1002 문제) 보링 섬 (마구 잡 이)

제목: HDU 4961
보아하니 이 문제 의 테스트 데 이 터 는 무 작위 인 것 같다.그렇지 않 으 면 극한 데이터 가 나 오 면 정말 넘 을 수 없다.이 문 제 는 제 방법 은 해시 구조 체 를 만 들 고 두 변 수 를 기록 하 는 것 입 니 다. 각각 num 위치 이 고 그 다음 에 f, f = = 0 은 이 수가 나타 나 지 않 았 음 을 나타 내 고 f = 1 은 이 수가 나타 난 적 이 있 음 을 나타 냅 니 다.그리고 앞 과 뒤에서 한 번 씩 쓸 어 주세요.쓸 때마다 나타 나 는 수 를 표시 합 니 다.그리고 현재 의 수 에 대해 이 수의 배 수 를 매 거 하고 모두 매 거 하 며 위치 num 이 가장 큰 것 을 취한 다.그리고 찾 은 후에 하 쉬 구조 체 를 업데이트 합 니 다.앞 에 나타 난 적 이 있다 면 바로 바 꿔 라. 뒤의 수가 앞 보다 더 좋 기 때문이다.마지막 으로 두 번 스 캔 하면 두 배열 이 구 할 수 있 습 니 다.계산 하면 돼.
코드 는 다음 과 같 습 니 다:

#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
#define LL __int64
struct node
{
    LL num, f;
}_hash[110000];
LL a[110000], b[110000], c[110000];
int main()
{
    LL n, i, j, sum, max1, mmax;
    LL ans;
    while(scanf("%I64d",&n)!=EOF&&n)
    {
        max1=-1;
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&a[i]);
            if(max1<a[i])
                max1=a[i];
        }
        for(i=1;i<=max1;i++)
            _hash[i].f=0;
        for(i=1;i<=n;i++)
        {
            mmax=-1;
            for(j=a[i];j<=max1;j+=a[i])
            {
                if(_hash[j].f)
                {
                    if(mmax<_hash[j].num)
                    {
                        mmax=_hash[j].num;
                    }
                }
            }
            _hash[a[i]].f=1;
            _hash[a[i]].num=i;
            if(mmax==-1)
                b[i]=a[i];
            else
                b[i]=a[mmax];
        }
        for(i=1;i<=max1;i++)
            _hash[i].f=0;
        for(i=n;i>=1;i--)
        {
            mmax=1e7;;
            for(j=a[i];j<=max1;j+=a[i])
            {
                if(_hash[j].f)
                {
                    if(mmax>_hash[j].num)
                    {
                        mmax=_hash[j].num;
                    }
                }
            }
            _hash[a[i]].f=1;
            _hash[a[i]].num=i;
            if(mmax==1e7)
                c[i]=a[i];
            else
                c[i]=a[mmax];
        }
        ans=0;
        for(i=1;i<=n;i++)
        {
            ans+=b[i]*c[i];
            //printf("b==%d  c==%d
",b[i],c[i]);
        }
        printf("%I64d
",ans);
    }
    return 0;
}