알고리즘 노트 연습 9.2 두 갈래 나무의 반복 문제 B: 두 갈래 나무
8232 단어 알고리즘 노트
알고리즘 노트 연습 문제 모음집
링크
제목
제목 설명
위에서 보듯이 정수 1, 2, 3.......로 특수한 두 갈래 나무를 이루었다.우리는 이미 이 두 갈래 나무의 마지막 결점이 n이라는 것을 안다.현재의 문제는 결점 m가 있는 자수에 모두 몇 개의 결점이 포함되어 있느냐는 것이다.
예를 들어 n=12, m=3 그러면 위 그림의 결점 13, 14, 15 및 뒤의 결점은 모두 존재하지 않는다. 결점 m가 있는 자수에 포함된 결점은 3, 6, 7, 12이기 때문에 결점 m가 있는 자수에는 모두 4개의 결점이 있다.
입력 입력 데이터는 여러 줄을 포함하고 각 줄은 두 개의 정수 m, n(1<=m<=n<=100000000)을 포함하는 테스트 데이터를 제공한다.마지막 테스트 데이터에는 두 개의 0이 포함되어 있으며, 입력의 끝을 표시하며, 이 데이터는 처리할 필요가 없다.
출력은 모든 테스트 데이터에 대해 한 줄을 출력합니다. 이 줄은 하나의 정수를 포함하고 결점 m가 있는 하위 트리에 포함된 결점의 수를 제시합니다.
샘플 입력3 7
142 6574
2 754
0 0
샘플 출력3
63
498
생각
만약에 한 결점의 번호가 kkk라고 가정하면 분명히 그의 왼쪽 아이 결점 번호는 2k2k이고 오른쪽 아이 결점 번호는 2k+12k+12k+1이다.
그러면 무한히 아래로 뻗은 만 두 갈래 나무 안에서 임의로 결점 번호r를 취하고 이 노드를 루트 노드로 하는 서브트리를 설정한다. nn층(루트 노드는 0 0층) 노드 번호의 범위는 폐구간 [l e ft, r i g h t] [left,\right] [left,right], l e ft left의 값은 r *= 2 nn번 교체된 후r여야 한다.r i g h t right right의 값은 r = r * 2 + 1 nnn회 교체된 후r여야 한다.
이상의 결론과 만 두 갈래 나무 결점 수량의 계산 공식에 따라 본 문제의 답안을 신속하게 얻을 수 있고 마지막 층은 특수 처리가 필요하며 구체적으로 아래 코드를 실현해야 한다.
이 방법을 사용하기 전에 폭력적 귀속 버전을 썼는데, 시간이 초과되었고, 아래에 첨부되었다.
코드
AC 코드
#include
", count());
return 0;
}
반복 누적 (시간 초과)
#include
", count(m));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 스크립트 일기의 검증 두 갈래 검색 트리
두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다.
두 갈래 검색 트리에는 다음과 같은 정의가 있습니다.
예 1:
두 갈래 나무[2,1,3],true로 돌아갑니다.
예 2:
두 갈래 나무[1,2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
제목 설명
위에서 보듯이 정수 1, 2, 3.......로 특수한 두 갈래 나무를 이루었다.우리는 이미 이 두 갈래 나무의 마지막 결점이 n이라는 것을 안다.현재의 문제는 결점 m가 있는 자수에 모두 몇 개의 결점이 포함되어 있느냐는 것이다.
예를 들어 n=12, m=3 그러면 위 그림의 결점 13, 14, 15 및 뒤의 결점은 모두 존재하지 않는다. 결점 m가 있는 자수에 포함된 결점은 3, 6, 7, 12이기 때문에 결점 m가 있는 자수에는 모두 4개의 결점이 있다.
입력 입력 데이터는 여러 줄을 포함하고 각 줄은 두 개의 정수 m, n(1<=m<=n<=100000000)을 포함하는 테스트 데이터를 제공한다.마지막 테스트 데이터에는 두 개의 0이 포함되어 있으며, 입력의 끝을 표시하며, 이 데이터는 처리할 필요가 없다.
출력은 모든 테스트 데이터에 대해 한 줄을 출력합니다. 이 줄은 하나의 정수를 포함하고 결점 m가 있는 하위 트리에 포함된 결점의 수를 제시합니다.
샘플 입력
3 7
142 6574
2 754
0 0
샘플 출력
3
63
498
생각
만약에 한 결점의 번호가 kkk라고 가정하면 분명히 그의 왼쪽 아이 결점 번호는 2k2k이고 오른쪽 아이 결점 번호는 2k+12k+12k+1이다.
그러면 무한히 아래로 뻗은 만 두 갈래 나무 안에서 임의로 결점 번호r를 취하고 이 노드를 루트 노드로 하는 서브트리를 설정한다. nn층(루트 노드는 0 0층) 노드 번호의 범위는 폐구간 [l e ft, r i g h t] [left,\right] [left,right], l e ft left의 값은 r *= 2 nn번 교체된 후r여야 한다.r i g h t right right의 값은 r = r * 2 + 1 nnn회 교체된 후r여야 한다.
이상의 결론과 만 두 갈래 나무 결점 수량의 계산 공식에 따라 본 문제의 답안을 신속하게 얻을 수 있고 마지막 층은 특수 처리가 필요하며 구체적으로 아래 코드를 실현해야 한다.
이 방법을 사용하기 전에 폭력적 귀속 버전을 썼는데, 시간이 초과되었고, 아래에 첨부되었다.
코드
AC 코드
#include
", count());
return 0;
}
반복 누적 (시간 초과)
#include
", count(m));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 스크립트 일기의 검증 두 갈래 검색 트리
두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다.
두 갈래 검색 트리에는 다음과 같은 정의가 있습니다.
예 1:
두 갈래 나무[2,1,3],true로 돌아갑니다.
예 2:
두 갈래 나무[1,2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
AC 코드
#include
", count());
return 0;
}
반복 누적 (시간 초과)
#include
", count(m));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 스크립트 일기의 검증 두 갈래 검색 트리두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다. 두 갈래 검색 트리에는 다음과 같은 정의가 있습니다. 예 1: 두 갈래 나무[2,1,3],true로 돌아갑니다. 예 2: 두 갈래 나무[1,2...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
