2018 CCPC 지 린 경기 지역 문제 풀이
100090 단어 데이터 구조 - 선분 트 리시합
#include1002. 더 월 드 출석 체크
#include1003. Justice
해법: 우선, 100000 보다 큰 ki 값 에 대해 우 리 는 관여 할 필요 가 없다. 만약 에 이 수의 총합 이 1 보다 크 면 반드시 해 가 있 을 것 이다. 우 리 는 먼저 이 수의 총합 이 1 보다 큰 지 판단 한다. 우 리 는 수조 vis 로 모든 수의 출현 횟수 를 통계 한 다음 에 큰 것 에서 작은 것 으로 x, vis [x] + = vis [x + 1] / 2 를 들 고 마지막 vis [0] 가 0 이 아니라면 조건 을 만족시킨다.두 번 째 단 계 는 우리 가 조합 합 니 다. 우 리 는 모든 값 이 20 보다 작은 ki 를 꺼 내 서 그들 을 모두 2 ^ (20 - ki) 로 만 든 다음 에 작은 매 거 진 숫자 에 이 르 러 이 숫자 들 이 2 ^ (19) 와 같 을 때 까지 이 숫자 들 을 1 로 표시 하고 나머지 는 모두 0 으로 표시 하면 됩 니 다.
#include1004. The Moon
해법: d [i] [j] 를 q 로 설정 하여 i 회 2%, j 회 1.5%, 즉 q = 0.02 + 0.02 * i + 0.015 * j 를 증가 시 켰 고 실패 할 확률 이 있 습 니 다. 우 리 는 다음 에 조작 에 성공 할 수 있 습 니 다. 그러면 ans + = d [i] * p * q * (i + j + 1), 다음 에 직접 몬스터 를 때 려 서 이기 지 못 했 을 수도 있 습 니 다. d [i] [j + 1] + d [i] * * (1 - p), 다음 에 도 몬스터 를 이 길 수 있 지만 당 첨 되 지 못 했 습 니 다. d [i + 1] [j]+ = d [i] [j] * p * (1 - q), 현재 q > 1 이 라면 계속 이동 하지 않 고 공헌 으로 계산 합 니 다. ans + = d [i] * (i + j) + d [i] / p.
#include
", ++kase, ans);
}
}
1006. The Hermit
제목: 각 점 i 에 대해 덮어 쓸 수 있 는 범 위 는 [i - ri + 1, i + ri - 1] 이 고 임의의 인접 점 i, i + 1, i + 1 의 덮어 쓸 수 있 는 왼쪽 경 계 는 반드시 i 가 덮어 쓰 는 왼쪽 경계 보다 크 며, 각 점 i 에 대해 서 는 합 법 적 인 k 의 수량 으로 정의 합 법 적 인 k: k < i, 그리고 k 는 i 의 덮어 쓰 는 범위 내 에 있 으 며, 점 j, k < j, 그리고 dist (k, j) 가 존재 합 니 다.> = dist (j, i), 그리고 i 와 k 는 모두 j 의 커버 범위 안에 있 습 니 다.각 점 의 가중치 가 다 르 거나 합 쳐 질 것 을 요구 하 다.
해법: 제목 의 뜻 이 매우 복잡 하 다. 제목 의 도둑 물 은 리 < 3 의 점 에 대해 분명히 가중치 가 0 이 고 리 > = 3 의 점 에 대해 우 리 는 제목 의 뜻 으로 리 - 1 이 덮 인 왼쪽 경 계 는 반드시 < = 리 가 덮 인 왼쪽 경 계 를 말한다. 즉, 나 는 j = i - 1 을 설정 하고 다른 i 왼쪽 이 덮 을 수 있 는 점 은 모두 합 법 적 인 k 점 으로 할 수 있다. 즉, i 의 가중치 가 리 - 2 이다.
#include
", ++kase, ans);
}
}
1008. Lovers
해법: 우 리 는 매번 조작 을 분리 하여 처리 합 니 다. tagR [o] 로 오른쪽 에 추 가 된 숫자 를 표시 합 니 다. R [o] 는 이 구간 오른쪽 에 숫자 를 추가 한 후의 총화 입 니 다. len [o] 는 이 구간 에 몇 번 을 추 가 했 습 니까? 우 리 는 표 시 를 보 냅 니 다. fa 노드 에 대한 정 보 는 o 노드 (o 노드 길이 가 n 이 라 고 가정 합 니 다) 에 전달 해 야 합 니 다. 먼저 R [o] * = 10 ^ len [fa], 그리고 R [o] + = ragR [fa] * n, 그리고 tagR [o]= tagR [o] * 10 ^ len [fa], ok, 오른쪽 가 수 는 간단 합 니 다. 이제 tagL [o] 와 L [o] 로 왼쪽 가 수 를 해결 합 니 다. tagL [o] 가 표시 하 는 숫자 는 tagR [o] 순서 가 반대 입 니 다. L [o] 는 이 구간 의 모든 숫자 왼쪽 의 절반 에 10 ^ len / 2 의 총 화 를 곱 하고 sum [o] 를 구간 '총화' 로 설정 합 니 다. 초기 값 sum [o] 을 구간 길이 로 한 번 씩 구간 을 업데이트 하면 이 구간 의 sum [o]* = 100, 하 전 태그: L [o] = L [o] * 10 ^ len [fa] (오른쪽 에 이렇게 많이 추가 되 었 기 때문에) + tagL [fa] * sum [o] * 10 ^ len [fa], tagL [o] = tagL [o] + tagL [fa] * 10 ^ len [o]) 을 마지막 으로 len [o] + = len [fa], sum [o] * = 10 ^ (len [fa] * 2) 을 업데이트 합 니 다.
#include
", ++kase);
scanf("%d%d", &n, &m);
build(1, 1, n);
while (m--) {
scanf("%s%d%d", s, &l, &r);
if (s[0] == 'w') {
scanf("%d", &x);
up(1, 1, n, l, r, x);
}
else
printf("%lld
", qu(1, 1, n, l, r));
}
}
}
1009. Strength
제목: 당신 은 m 개의 카드 를 가지 고 있 거나 공격 상태 에 있 거나 방어 상태 에 있 습 니 다. 나 는 n 개의 카드 를 가지 고 있 습 니 다. 카드 마다 한 번 만 사용 할 수 있 습 니 다. 나 는 카드 한 장 을 선택 하여 당신 의 공격 상태 카드 를 공격 하면 나의 카드 공 격 력 > = 당신 의 카드 공 격 력 이 있 으 면 당신 의 그 공격 당 한 카드 는 폐기 되 고 공 격 력 이 떨 어 지 는 혈 량 을 손실 할 것 입 니 다.만약 내 가 당신 의 방어 상 태 를 공격 하 는 카드 를 선택한다 면, 나의 카드 공 격 력 > = 당신 의 카드 공 격 력 이 있다 면, 당신 의 카드 는 폐기 되 지만, 당신 은 피 를 손실 하지 않 을 것 입 니 다. 만약 당신 이 카드 가 남지 않 았 다 면, 당신 이 손실 한 피 는 나의 남 은 카드 의 공 격 력 총화 가 될 것 입 니 다.가장 큰 피 해 를 주 십시오.
해법: 우 리 는 두 가지 전략 만 있 으 면 됩 니 다. 첫 번 째: 나의 모든 카드 는 당신 의 공격 상태 카드 를 공격 합 니 다. 두 번 째: 나 는 먼저 당신 의 방어 상태 카드 를 모두 공격 합 니 다. 만약 에 내 가 카드 가 남 으 면 모두 당신 의 공격 상태 카드 를 공격 합 니 다. 만약 에 남 으 면 모두 당신 을 공격 합 니 다.방어 상 태 를 공격 하 는 카드 의 욕심 전략 은 너무 간단 하 다. 우 리 는 공격 상태의 카드 를 어떻게 공격 하 는 지 에 대해 이야기 하 자. 우리 문 은 먼저 2 점 이나 더 블 포인터 로 내 가 상대방 의 카드 몇 개 를 이 길 수 있 는 지 를 구 한 다음 에 나 는 상대방 의 카드 와 정렬 을 한다. 만약 에 내 가 k 개의 카드 를 가장 많이 이 길 수 있다 고 가정 하면 우리 문 은 1 부터 매 거 i.나의 가장 큰 i 장의 카드 와 - 상대방 의 가장 작은 i 장의 카드 의 합 은 바로 상대방 이 단 추 를 한 혈 량 입 니 다. 우리 가 최대 치 를 취하 면 됩 니 다.
#include
", ++kase, ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[낙 곡] P2880 [USACO07JAN] 밸 런 스 라인업 Balanced Lineup (\# 트 리 배열)제목 배경 제목 설명: 어느 날, 존 은 일부 소 들 에 게 플 라 잉 경 기 를 시 키 기로 결정 했다. 그 는 대열 에 연 속 된 소 를 찾 아 경 기 를 하려 고 한다. 그러나 수준 차 이 를 피하 기 위해 소...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
