진급훈련-기본 알고리즘

7236 단어
비트 연산, 추이와 귀속, 접두사와 차분, 이분, 순서, 배증, 욕심

비트 연산


시프트 컴퓨팅

  • 쾌속멱, 쾌속승(1e18), 상태압축, 쌍변환,lowbit.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 
    ll mul(ll a,ll b,ll p){
        ll ans=0;
        while(b){
            if(b&1) a=(ans+a)%p;
            a=a*2%p;
            b>>=1;
        }
        return ans;
    }


    • 차례로 미루고 귀속시키다

  • 추이: 이미 알고 있는'문제 경계'를 기점으로'원문제'를 정방향으로 추론
  • 귀속:'원문제'를 기점으로 상태 공간을 이미 알고 있는'문제 경계'로 축소하는 노선을 찾고 노선을 통해 역추적

    • 접두사 및 와차

  • 접두사와: s[i]= ∑(a[1]~a[i])
  • 차분: b[i]=a[i]-a[i-1].접두사와 차분은 상호 역연산으로 나뉘고 b의 접두사와 서열은 a로 원 서열의 구간 조작을 차분 서열의 단점 조작으로 바꿀 수 있다.

    • 이분

  • 정수 도메인:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //1
    while(l
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    //2
    while(l
        int mid=(l+r+1)>>1;
        if(check(mid)) r=mid-1;
        else l=mid;
    }

  • 실수 도메인:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while(l+1e-5
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    // ， ， 
    for(int i=0;i<100;i++){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }

  • 3점: 단봉함수라고 불리는 함수가 있는데 그들은 유일한 극대치점을 가지고 극대치 왼쪽에서 엄격하게 단점이 상승하고 오른쪽에서 엄격하게 단조롭게 떨어진다.또는 유일한 극소치점은 왼쪽은 엄격하게 단조롭게 내려가고 오른쪽은 엄격하게 단조롭게 올라간다.삼분법으로 극치를 구할 수 있다.
  • 함수역 [l,r]에서 두 개의 lmid와 rmid
    • 를 취한다
  • 만약에 f(lmid)
  • 같은 이치로 f(lmid)>f(rmid)라면 r=mid.만약 함수가 엄격하고 단조롭지 않다면 한식에 값이 같은 부분이 존재하면 정의역의 좌우 경계가 어떻게 축소되는지 판단할 수 없고 3분법은 더 이상 적용되지 않는다.

  • 2점 답안: 답안과 원문제가 단조로울 때 답안을 2점으로 나누고 매번 체크()를 한다.

    • 정렬

  • 이산화:sort+unique, 수치가 비교적 크지만 분산된 수를 유한 집합으로 비추어 통계에 편리하도록 한다.
  • 중위수: 우리는 1차원 서열에서 한 점을 찾아서 다른 점이 그것의 거리와 가장 짧은 시간에 중위수가 바로 답이 되도록 해야 한다.증명: 서열을 정렬하고 x번째 점을 선택하면 x는 왼쪽에 P점, 오른쪽에 Q점이 있습니다.만약 P < Q 라면 x를 오른쪽으로 한 단위 거리를 이동하면 거리의 합은 Q-p로 작아진다.같은 이치로 P>Q라면 x를 왼쪽으로 이동하지 않으면 거리와 거리가 작아지고 P=Q일 때가 가장 좋다.즉, ∑|s[i]-s[k]|, s[k]를 찾아서 식을 최소화하면 이 s[k]가 바로 s의 중위수이다.
  • 제k대수: 구간을 정하고 제k를 구한다.최소 O (nlgn) 를 정렬합니다.빠른 배열의 사상을 이용하여 매번 기준치를 선택한 후에 기준치보다 큰 수량 cnt를 통계해 낸다. 만약에 k<=cnt라면 왼쪽으로 찾아라. 그렇지 않으면 오른쪽에서 k-cnt를 찾아라. 시간의 복잡도는 O(n)
    • 이다.
  • 역순대: 병합 정렬을 이용하여 해답을 구한다.구간 [l, r]에서mid=(l+r)/2, i는 l에서mid, j는mid+1에서 r, a[i]>a[j]일 때 a[i~mid]는 반드시 a[j]보다 크다. 단독으로 보면 좌우 구간은 이미 순서가 정해져 있기 때문에sum+=mid-i+1이면 된다.

    • 갑절

  • 일반적인 선형 추이가 시간과 공간의 복잡도에 대한 요구를 충족시키지 못할 때 배로 증가하는 방식으로 추이 상태 공간이 2의 정수 차멱에 있는 값만 대표할 수 있다.다른 위치의 값이 필요할 때, 우리는 '임의의 정수로 몇 개의 2의 차멱항의 합을 나타낼 수 있다' 는 성질을 통해 이전에 구한 대표 값을 사용하여 원하는 값으로 조합할 수 있다.이 알고리즘은 우리가 점차적으로 추측하는 문제의 상태 공간이 2의 차멱에 대해 구분성을 가지도록 요구한다.
  • 이런 문제를 생각해 보자. N으로 긴 수열을 제시하고 매번 T를 주며 가장 큰 정수 k를 구하면 ∑(a[1]~a[k])<=T.
  • 일반적인 방법은 두 가지인데 첫 번째는 직접 O(n)로 쓸어버리는 것이다. 분명히 효율이 매우 느리다.두 번째는 O(n)가 접두사와 2점 k를 미리 처리하고 매번 O(lgn)를 물어보는 것이다.두 번째는 평균 상황에서 잘 보이지만 매번 주는 T가 작으면 k도 작을 것이다. 이때 2점은 그냥 지나가는 것보다 빠를 수도 있다.
  • 우리는 이러한 배증 알고리즘을 설계할 수 있다.
  • 령p=1,k=0,sum=0,예처리처 접두사와 S;
  • A 수조에서 k 이후 p 개수의 관계와 T와의 관계를 비교한다.만약sum+S[k+p]-S[k]<=T라면sum+=S[k+p]-S[k],k+=p,p*=2,즉 이 p개수의 합을 더해서 경계를 배로 늘린다.만약sum+S[k+p]-S[k]>T라면 p/=2.
  • 상소 절차를 반복하고 p의 값이 0인 것을 알면 k가 답이다

  • ST 알고리즘: RMQ 문제를 배수로 구하고 나무에 LCA를 배수로 구한다.

    • 탐욕스럽다

  • 욕심법은 문제의 전체적인 최우성을 국부적인 최우성으로 유도할 수 있고 증명해야 한다. 흔히 볼 수 있는 증명 방법은 다음과 같다.
  • 소요(인접 항목 교환): 임의의 국면에서 국부적 최우선 전략에 대한 미세한 변화가 전체적인 결과를 나쁘게 할 수 있음을 증명한다.서열을 욕심 전략으로 하는 증명에 자주 쓰인다.예제: 국왕놀이
  • 범위 축소: 국부적 최우선 전략 작용 범위의 확장이 전체적인 결과를 나쁘게 하지 않는다는 것을 증명한다.예제: 레이더 설비
  • 의사결정 포용성: 임의의 국면에서 국부적으로 가장 좋은 의사결정을 한 후에 문제 상태 공간에서의 가달 집합은 다른 의사결정을 한 후의 가달 집합을 포함한다.다시 말하면, 이 부분적인 최우선 전략이 제공할 가능성은 다른 모든 전략이 제공할 가능성을 포함한다.
  • 반증법.
  • 수학 귀납법.

    • 귀속을 어떻게 이해합니까
    LetCode 326 Power of Three(3의 멱)(반복, Log 함수)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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