한 가지 수 x 를 nearly prime 라 고 정의 하고 x 는 x = p * q 라 고 표시 할 수 있 습 니 다. 그 중에서 1 은 n 에 게 4 개의 서로 다른 정수 의 합 을 표시 할 수 있 는 지 물 었 고 이 4 개의 수 중 적어도 3 개 는 nearly prime
입 니 다. 문제 풀이 의 사고 방향.
가장 작은 3 개 nearly prime 는 각각 6 = 23 10 = 25 14 = 2 * 7 이기 때문에 n 은 적어도 6 + 10 + 14 = 30 이상 이 어야 조건 에 부합 되 고 4 개 수 는 각각 6 - 10 14 n - 30
이다.
주의해 야 할 것 은 4 개의 서로 다른 정수 의 합 이기 때문에 다음 세 가지 상황 은 특수 처리 n - 30 = 6 \ quad n = 36 = 6 + 10 + 15 + 5 n - 30 = 10 \ \ quad n = 40 = 10 + 15 + 14 n - 30 = 14 \ quad n = 44 = 5 + 10 + 15 + 14
n 길이 의 정수 x 에 대해 우 리 는 k 를 정의 합 니 다. 이것 은 그들의 모든 수의 바 이 너 리 배열 입 니 다. 예 를 들 어 x = 729, k = 11101001 은 k 의 뒷 n 자 리 를 없 애고 새로운 숫자 r = 111101 을 형성 합 니 다. 현재 n 을 정 하고 가장 작은 x 를 계산 하여 형 성 된 r 를 최대 로 합 니 다.
문제 풀이 의 사고 방향.
k 의 뒷 n 자 리 를 빼 기 때문에 앞 에 있 는 것 이 클 수록 좋다 는 것 을 보증 해 야 한다. 즉, 모든 사람 이 9 이다.
8 = 1000, 9 = 1001, 7 = 111.
그래서 뒤 는 94848, n / 4 는 94888, n / 4 는 94884, n / 4 는 94884, n / 4 는 94888, 나머지 는 9 가 답
n 개의 결산 점 을 지정 한 나무 그림 은 각 노드 가 하나의 도 시 를 대표 한다. 현재 m 명 이 노드 1 에서 집 으로 돌아 가 야 한다. 집 이 결산 점 i 에 있 는 사람의 수 는 p [i] 이다. 집에 돌아 가 는 과정 에서 모든 사람 이 기분 이 좋 은 것 에서 기분 이 나 쁜 것 으로 바 뀔 수 있 지만 기분 이 나 쁜 것 에서 마음 이 좋 은 것 으로 바 뀌 어 서 는 안 된다. 현재 각 도시 i 는 지나 가 는 사람의 중심 이 좋 은 사람 수 - 기분 이 나 쁜 사람의 수 치 를 통계 한다.각 도시 통계 의 h [i] 가 정확 한 지 판단 하 다.
문제 풀이 의 사고 방향.
먼저 문 제 를 분석 해 보 자. 모든 사람 이 노드 1 에서 자신의 집 으로 돌아 가 는 것 이다. 그리고 반드시 앞의 길 은 기분 이 좋 은 것 이다 (앞의 길 은 0 일 수도 있다). 뒤의 길 은 기분 이 좋 지 않 고 우리 의 어 려 운 점 은 어디 에 있 습 니까?많은 사람 이 있 기 때문에 우 리 는 모든 사람 이 어느 노드 에서 기분 이 나 빠 지기 시 작 했 는 지 확정 할 수 없 지만 사실은 우 리 는 대체적으로 확정 할 수 있다
.
I. 잎 사 귀 노드 를 고려 해 한 잎 사 귀 노드 w 에 게 있어 서 w 에 도달 할 수 있 는 것 은 모두 집 이 w 에 있 는 것 이다. 이 사람들 이 도착 할 때 x 는 기분 이 좋 고, y 는 기분 이 나 쁘 면 {x + y = p [w] x - y = h [w] \ \ \ \ \ \ x - y = h [w] \ \ \ x - y = h [w] \ \ \ \ \ \ \ \ 엔 드 {cases} {x + y = p [w] x - y = p [w] x - y = h [w] 그래서 x = (p [w] + h [w]] + h [w]]) / 2, y = p [w] - w] - w] - p [w] - x] - x] - x + x x + x x (hw) 짝수 일 거 예요
II. 비 잎 노드 k 를 고려 하면 이 단 계 는 잎 노드 에서 위로 밀어 올 리 는 결점 k 의 최소 기분 이 좋 은 사람 은 모든 서브 노드 의 기분 이 좋 은 사람 을 더 한 것 이다. dp [k] [1] 결점 k 의 최대 기분 나 쁜 사람 은 모든 서브 노드 의 기분 나 쁜 사람 과 + p [k] 이 고 dp [k] [2] 로 기록 하 는 것 이다.개인 은 k 노드 에서 즐 거울 수도 있 고 즐 겁 지 않 을 수도 있 습 니 다. 모두 즐 겁 지 않 으 면 인원 이 가장 많 습 니 다. 그래서 + p [k] 를 거 쳐 야 합 니 다. 그러면 현재 이 점 을 지 나 는 k 의 총 인원 은 sumnow = dp [k] [1] + dp [k] [2] 입 니 다. 우 리 는 k 를 설정 한 사람 중 x 개인 이 기분 이 좋 고 y 개인 이 기분 이 나 쁘 면 {x + y = s u m n o w x - y = h [w] \ \ \ begin {cases} x + y = sumnow \ \ \ x - y = h [w] \ end {cases}{x + y = sumnowx − y = h [w] 그래서 x = (sumnow + h [w]) / 2, y = sumnow − x 는 (sumnow + hw) 짝수 일 것 이다. 왜냐하면 서브 노드 가 기분 이 좋 은 사람 은 이전 노드 에서 기분 이 좋 을 것 이다 (기분 이 좋 을 수 밖 에 없다 - > 기분 이 나 쁠 수 밖 에 없다). 그러나 일부 사람들 은 k 노드 에서 기분 이 좋 지만 서브 노드 에 달 려 가면 기분 이 나 빠 지기 때문에 여 기 는 x > = dp [k] [1] 를 만족 시 켜 야 한다.판단 이 끝 난 후에 k 점 의 기분 이 좋아 서 기분 이 나 쁜 사람 수가 계산 되 었 습 니 다. 그러면 dp [k] [1] = x, dp [k] [2] = y 를 계속 위로 밀 었 습 니 다
.
임의의 노드 w 에 대해 w 를 거 친 총 인원 을 만족 시 킵 니 다 > = abs (h [w])
