프로그래머 진급 알고리즘 연습 (6)

머리말
이번 에는 네 문제 만 있 습 니 다. E 문 제 는 기괴 한 수학 문제 입 니 다. 이 경골 을 갉 아 먹 지 않 겠 습 니 다. A / B / C / D 를 분석 해 보 겠 습 니 다.

A 문 제 는 간단하게 규칙 문 제 를 찾 는 것 이다.

B 문 제 는 게임 의 입문 문제 이다.

C 문 제 는 간단 한 모 의 문제 로 문제 가 비교적 길다.

D 문 제 는 욕심 이 고 구조 라 고도 할 수 있다.

제목 의 대 의 를 보고 먼저 생각 하고 해석 을 본다.제목 의 부주의 가 분명 하지 않다 고 생각 하여 제목 링크 를 클릭 하여 원문 을 본다.
문집: 프로그래머 진급 알고리즘 연습 (一) 프로그래머 진급 알고리즘 연습 (二) 프로그래머 진급 알고리즘 연습 (三) 프로그래머 진급 알고리즘 연습 (四) 프로그래머 진급 알고리즘 연습 (五) 코드 주소
A
제목 링크 제목: n 을 입력 하고 문자열 을 출력 합 니 다.n = 1：I hate it n = 2：I hate that I love it n = 3：I hate that I love that I hate it
코드 구현:

    int n;
    cin >> n;
    
    string ret = "I hate ";
    for (int i = 0; i < n - 1; ++i) {
        if (i % 2 == 0) {
            ret += "that I love ";
        }
        else {
            ret += "that I hate ";
        }
    }
    ret += "it";
    cout << ret << endl;

법칙 을 찾다.문자열 을 세 부분 'I hate' +... + 'it' 로 나 누고 n 에 따라 중간 문자열 을 구축 합 니 다.
B
제목 링크 제목 대의: 하나의 디지털 게임 이 있 습 니 다. 한 무더기 의 정 수 를 제시 하고 돌아 가면 서 조작 하 며 조작 자가 질 수 없습니다.조작 은 하나의 정수 x 를 두 개의 정수 i, j 와 i + j = x 로 나 누 는 것 이다.현재 n 개의 정수 a [i] 가 있 습 니 다. 샤 오 밍 은 앞의 i 개 (i = 1 ~ n) 숫자 만 있 을 때 게임 의 승 률 상황 을 알 고 싶 습 니 다.
입력: 첫 번 째 줄 n (1   ≤   n   ≤   100   000) 두 번 째 줄 n 개 숫자, a1,   a2,  ..,   an (1   ≤   a [i]   ≤   1e 9),
출력: n 줄 데이터, i 출력 이 앞의 i 숫자 만 있 을 때 게임 의 승부 상황;선수 가 이기 면 1 을 출력 하고, 후수 가 이기 면 2 를 출력 한다.
Examples input 3 1 2 3 output 2 1 1
코드 구현:

    int n, t = 1; // 1       0      
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if (k != 1) {
            t = 1 -( t ^ (k % 2));
        }
        cout << t + 1 << endl;
    }

제목 해석: 선수 필승 이 0 이 고, 선수 필승 이 1 이 라 고 가정 하면 0 + 1 = 0 1 + 0 = 0 + 0 = 1 + 1 = 1 이상 또는 조작 부호 가 있 잖 아 요.구체 적 인 이해 사고방식 은 다음 과 같다. 1. 당신 이 하나의 수 x 를 분할 할 때 사실은 분할 필승 과 필 패 의 상태 이다.2. 필승 한 걸음 은 필 패 로 전환 할 수 있 고 한 걸음 은 필승 으로 전환 할 수 있다.그래서 실제로 기우 수 에 따라 필 패 나 필승 을 판단 할 수 있다.예 를 들 어 1 은 필 패, 2 는 필승, 3 은 필 패, 4 는 필승 이다.
C
제목 링크 제목 대의: 이것 은 핸드폰 시스템 로 컬 푸 시 시 시 뮬 레이 션 입 니 다.먼저 n, q, n 을 응용 수량 으로 입력 하고 q 를 조작 수량 으로 입력 합 니 다.(1   ≤   n,   q   ≤   300   000) 다음 q 행, 각 줄 에 두 개의 숫자 x, y 가 있다.

x = 1 일 때 id = y 의 응용 에 notify 가 생 긴 다 는 것 을 나타 낸다.

x = 2 는 모든 id = y 의 응용 을 읽 었 음 을 나타 낸다.

x = 3 은 앞의 y notify 를 읽 는 것 을 나타 낸다.

매번 입력 후 남 은 읽 지 않 은 수량 을 물 어보 세 요.
Examples input 3 4 1 3 1 1 1 2 2 3 output 1 2 3 2
코드 구현:

int n, m, ls = 1, k = 0, sum = 0;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        lld x, y;
        cin >> x >> y;
        if (x == 1) {
            a[++k] = y;
            ++num[y];
            ++sum;
        } else if (x == 2) {
            sum -= num[y];
            num[y] = 0;
            flag[y] = k;
        }
        else if (x == 3) {
            for (; ls <= y; ++ls) {
                if (ls > flag[a[ls]]) {
                    flag[a[ls]] = ls;
                    --num[a[ls]];
                    --sum;
                }
            }
        }
        cout << sum << endl;
    }

제목 해석: 문제 의 어 려 운 점 은 작업 2 가 모든 알림 을 업데이트 하고 작업 3 이 읽 기 전 y notify 의 무 게 를 제거 하 는 것 입 니 다.문 제 를 살 펴 보면 읽 지 않 은 수량 에 만 관심 을 가지 고 읽 지 않 은 수량 은 조작 1 만 생 길 수 있 는 것 으로 나 타 났 다.
조작 1 로 형 성 된 숫자 를 일련의 수열 로 보고 num [i] id 를 i 로 기록 하 는 응용 현재 읽 지 않 은 수량;조작 2 에 대해 서 는 num [y] 를 비우 고 flag [y] = k 의 로 고 를 추가 하면 y 가 k 번 째 이전에 모두 읽 었 음 을 나타 낸다.동작 3 에 대해 서 는 개수 가 y 보다 클 때 까지 오른쪽 으로 숫자 를 옮 겨 다 녀 야 합 니 다.
PS: 문제 의 조작 3 을 잘 보지 못 해서 최신 Y 개 로 오인 되 었 고 실제 적 으로 최초 로 Y 개가 생 겼 기 때문에 난이도 차이 가 많 습 니 다.
D
제목 링크 제목 대의: n 개의 의자 가 한 줄 로 서 있 고 (왼쪽 에서 오른쪽 번호 1 부터 n 까지) 개미 인 Scott 는 s 번 의자 에 서 있 습 니 다.개미 인간 은 어떤 의자 에서 다른 어떤 의자 로 뛰 어 내 릴 수 있다. 지금 은 모든 의 자 를 지나 가 려 고 한다. 결국 e 번 째 의자 에 멈 추고 싶다.(의자 마다 한 번 만 지나 간다) 개미 인간 은 커지 고 작 아진 다 는 것 은 잘 알려 져 있다.여기 서 개미 인간 은 의자 에서 만 변화 할 수 있 고 두 가지 상태 만 있다. 거인 과 소인 이다.개미 가 의자 왼쪽으로 뛰 어 들 때 는 소인 상태 일 수 밖 에 없다.개미 인간 이 의자 오른쪽으로 뛰 어 들 때 는 거인 상태 일 수 밖 에 없다.
의자 i 에서 의자 j 로 뛰 어 내 리 는 데 걸 리 는 시간 은 세 가지 로 나 뉜 다.

점프 시간, 소인 상태 에서 c [i], 자 이언 트 상태 에서 d [i];

띄 우기 시간, | x [i] - x [j] |;

착륙 시간, 소인 상태 에서 b [i], 자 이언 트 상태 에서 a [i];

Scott 에 게 의자 s 에서 의자 e 까지 의 가장 짧 은 시간 이 얼마 인지 물 었 다.
수학 언어: n 개 점, 점 마다 가중치 x [i], a [i], b [i], c [i], d [i].점 마다 다른 점 이 존재 합 니 다. 점 i 에서 점 j 변 까지 의 대 가 는 다음 과 같 습 니 다. | x [i]   -   x [j] |   +   c [i] +   b [j] section if j   | x [i]   x [j] |   x [j] |   +   d [i]   d []   +   a [j] second a [j] second section othe (j   > \8201i) 입 니 다. 점 s 에서 점 e 까지, e 를 구 합 니 다. 모든 점 의 최 단 경 로 를 기록 합 니 다.(점 마다 한 번 만 걷는다)
입력: 첫 번 째 줄 n, 『 8201 』 s and e (2 『 82001 』, ≤ 『 8201 』 n 『 8201 』, ≤ 『 5000, 『 8201 』 1 『 8201 』, ≤ 『 8201 』 s, 『 82001 』 s, 『 8201 』 e 『 82001 』 n, 『 82001 』 n, 『 8201 』 s 『 ≠하 하 다 』 e) 두 번 째 줄 x1, 『 8201 』 x2, 『 8201 』 x2, 『 8201 』...., 『 8201 』 xn (1 『 82001 』 ≤ ≤ 비 비 오 』 x x x x 1 』, 『 8201 』 x x 1 』 x x 1 』, 『 8201 』 x 1 』 x 1, 『 8201 』 x 1 』 x 1 』, 『 8201 』 x x 1 』 x 1 』, 『 8201 』 x x 1 』, 『 8201 』 셋째 줄 a1, 『 82001 』 a2, 『 82001 』..., 『 82001 』 an (1 『 82001 』 ≤   a1, 『 8201 』 a2, 『 82001 』..., 『 82001 』 an 『 ≤ 『 8201 』 1e9) 제4 행 b1, 『 8201 』 b2, 『 82001 』..., 『 82001 』 a2, 『 82001 』 a2, 『 82001 』, 『 82001 』 bn (1 『 82001 』 ≤ 『 8201 』 b1, 『 8201 』 b1, 『 8201 』 b2, 『 82001 』 b2, 『 82001 』 b2, 『 82001 』 b2, 『 b2, 『 82001 』 b2, 『 82001 』........., 『 82001 』 bnbnbn(1 』 ≤ ≤ 『   ≤   1e9) 제5 행 c1,   c2,  ..,   cn(1   ≤   c1,   c2,  ...,   cn   ≤   1e 9) 제6 행 d1,   d2,  ..,   dn (1   ≤   d1,   d2,  ..,   dn   ≤   19)
Example input 7 4 3 8 11 12 16 17 18 20 17 16 20 2 20 5 13 17 8 8 16 12 15 13 12 4 16 4 15 7 6 8 14 2 11 17 12 8 output 139
샘플 설명: 경로: 4 - > 2 - > 1 - > 6 - > 5 - > 7 - > 3 시간: 17   +   24   +   23   +   20   +   33   +   22   =   139.
코드 구현:

    lld ans = cost(src, dest);
    
    NEXT[src] = dest;
    for (lld i = 1; i <= n; ++i) {
        if (i == src || i == dest) {
            continue;
        }
        lld MAX = inf, key = 0;
        for (lld j = src; j != dest; j = NEXT[j]) {
            if (cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]) < MAX) {
                MAX = cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]);
                key = j;
            }
        }
        ans = ans + MAX;
        NEXT[i] = NEXT[key];
        NEXT[key] = i;
    }
    
    
    cout << ans << endl;

제목 해석: 점 마다 가 야 하고 점 마다 한 번 만 걸 을 수 있 습 니 다. 그러면 점 의 경로 전개 최종 경 로 는 s 에서 t 까지 의 직선 입 니 다. 귀납법: n = 2 일 때 직접 s 에서 t 까지 의 경로 가 가장 좋 습 니 다. n = 3 일 때 매 거 진 삽입 할 수 있 는 위 치 는 가장 좋 은 해 를 얻 을 수 있 습 니 다. n = k 일 때 n = k - 1 로 형 성 된 s 에서 t 체인 에 매 거 진 삽입 할 수 있 습 니 다.가장 좋 은 위 치 를 얻다.
삽 입 된 위치 가 i 라 고 가정 하면 n = k - 1 의 체인 은 몇 단락 으로 분 해 됩 니 다. s 에서 i, NEXT [i] 에서 t, i 에서 k, k 에서 NEXT [i] 입 니 다. 그 중에서 s 에서 i, NEXT [i] 에서 t 까지 의 거 리 는 변 하지 않 습 니 다. 그러면 cost (i, k) + cost (k, NEXT [i) - cost (i, NEXT [i]) 가 가장 좋 은 시간 에 i 가 삽 입 된 것 입 니 다.
증명 의 관건: n = k 가 삽 입 될 때 점 k 는 s 에서 i, NEXT [i] 에서 t 까지 의 경로 에 영향 을 주지 않 습 니 다.
실제 결함 이 존재 한 다 는 것 을 증명 하 는 것 은 아직 완벽 하 게 증명 되 지 않 았 는데, 이 방법 은 실로 욕심 이다.