HDU - 5875 Function(단일 스택)

제목 링크: 보기 클릭
제목 대의: 연속 수열을 제시하고 m개의 질문을 제시하며 주어진 함수에 따라 결과를 조회할 것을 요구한다
제목 분석: 첫눈에 보면 제목이 귀속 제목이라고 생각하지만 맹목적으로 귀속되면 TLE가 틀림없다. 그래서 우리는 이 제목이 도대체 무엇을 하려는지 분석해야 한다. 이 제목은 사실 폐구간[l,r]에 있다. 처음에 숫자가 a[l]이고 순서대로 a[l+1]에서 a[r]로 모델을 뽑는다. 즉, 연속으로 모델을 뽑는다. 반나절을 분석했지만 아무런 성질이 없지만 작은 기교를 발견했다. 바로 하나의 숫자로 모델을 뽑을 때만약에 모드가 이 수보다 크다면 이 수에 영향을 주지 않는다. 모드가 이 수보다 작을 때만 모드를 취하는 것이 의미가 있다. 그래서 우리는 연속 모드를 현재 결과보다 작은 수를 찾을 때마다 최적화해서 모드를 취할 수 있다. 이것은 점프 모드와 유사하다. 이렇게 하면 시간의 복잡도를 크게 낮출 수 있기 때문에 우리는 라인 트리로 구간 내의 최소값을 저장할 수 있다.이렇게 하면 조회할 때 왼쪽 구간을 우선적으로 조회할 수 있다. 이렇게 하면'첫 번째'와'현재 숫자보다 작다'는 두 가지 조건을 동시에 만족시킬 수 있다.하지만 내 라인 트리는 아직 요리야. 내가 머리를 묻고 한 시간 동안 그 조회 함수를 조정하지 못했어. 항상 약간의 버그가 있어. 생각해 보니 오른쪽의 첫 번째 작은 숫자를 찾아야 하는 것 같아. 그러면 단조로운 창고를 사용할 수 있겠어? 단조로운 창고의 주된 용도는 o의 시간 복잡도로 왼쪽이나 오른쪽의 첫 번째 숫자가 현재의 숫자보다 크거나 작은 위치를 저장하는 거야. 이런 가지치기가 생겼어.마지막으로 매번 모형을 뽑는 횟수는 라인 트리에 비해 증가하지만 폭력에 비해 훨씬 빠르다. 어쨌든 모형을 뽑는 것이기 때문이다.그리고 마지막으로 사실은 데이터가 그렇게 징그러운 것이 없다는 것을 설명한다. 단조로운 창고가 튀어나온 것은 라인 트리보다 빠르다. 단조로운 창고의 시간 복잡도는 n이기 때문이다. 그 후에 조회 시간의 복잡도는 1로 변한다. 이렇게 각 구간을 한 번씩 훑어보면 전체 시간의 복잡도는 n+m보다 약간 크다. 왜냐하면 매번 조회는 뛰어넘어야 하지만 여러 번 찾기 때문이다.그러나 라인 트리는 nlogn을 만들고 매번 조회도logn이며 최악의 조회도logn*logn이기 때문에 시간 복잡도는 nlogn+nlogn*logn이다. 눈을 들어 보면 일반적인 데이터는 단조로운 창고가 더 빠르지만 특수한 데이터는 끊길 수 있다.하지만 고맙게도 이 제목은 그런 징그러운 데이터를 내지 못했다.
코드를 바로 올렸어요. 단조로운 창고는 오랫동안 사용하지 않았어요. 인터넷에서 복사한 판자:

#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long LL;
 
const int inf=0x3f3f3f3f;
 
const int N=1e5+100;

int a[N];

int id[N];

int main()
{
//    freopen("input.txt","r",stdin)
    int w;
    cin>>w;
    while(w--)
    {
        int n,m;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        stacks;
        for(int i=n;i>=1;i--)
        {
            while(!s.empty()&&a[s.top()]>a[i])// 
            {
                s.pop();
            }
            if(s.empty())
                id[i]=-1;
            else
                id[i]=s.top();
            s.push(i);
        }
        scanf("%d",&m);
        while(m--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y)
            {
                printf("%d
",a[x]);
            }
            else
            {
                int ans=a[x];
                while(1)
                {
                    int pos=id[x];
                    if(pos==-1||pos>y)
                        break;
                    ans%=a[pos];
                    x=pos;
                }
                printf("%d
",ans);
            }
        }
    }
    
    
    
    return 0;
}

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

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

POJ2796 - Feel Good - 단조로운 대기열(dp사상)

His recent investigations are dedicated to studying how good or bad days influent people's memories about some period of...

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

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

HDU - 5875 Function(단일 스택)

좋은 웹페이지 즐겨찾기