bzoj 3107: [cqoi 2013] 2 진 a + b 구조
1498 단어 bzoj
예 를 들 면 정말 알 기 쉬 운 것 같 아 요.아래 의 a, b, c 는 모두 원제 에서 a, b, c 의 자릿수 를 나타 낸다.
1.c
0001111111
0110000011
1000000010
f (a, b, c) 만족 c
2.a
00011110
01111111
10011101
분명히 자릿수 는 반드시 > b 이 고, 그러면 자릿수 는 b + 1 이 가장 좋 을 것 이 므 로, 두 번 째 수의 b 개 1 을 마지막 에 둘 수 밖 에 없다.첫 번 째 수의 마지막 이 k 위 (낮은 것 에서 높 은 것 까지) 라 고 가정 하면 먼저 k 위 를 넣 으 면 100... 0010000 (k = 5 를 가정) 이 되 고 그 다음 에 넣 은 수 는 분명히 k ~ k + a - 2 위 가 되 어야 답 을 최소 화 할 수 있다.그러면 지금 c 의 제한 을 만족 시 키 는 것 을 고려 해 보 니 세 번 째 숫자 는 이 렇 습 니 다. 10...............................................................
3.b
011100001
011111110
111101111
같은 분명 한 자릿수 > c (a + b = c 를 제외 하고) 는 자릿수 가 c + 1 이 어야 합 니 다. 따라서 우 리 는 0 이 가능 한 한 빨리 나타 나 도록 해 야 합 니 다.두 번 째 수 를 기준 으로 첫 번 째 수의 시작 1 의 개 수 는 a + b - c 라 는 것 을 알 게 되 었 습 니 다. 그러면 우 리 는 시작 a + b - c 를 모두 1 로 하면 됩 니 다.
4. 상황 을 이해 하지 못 한다...이것 괜찮아요?
AC 코드 는 다음 과 같 습 니 다.
#include
#include
using namespace std;
int calc(int x){
int t=0; for (; x; x>>=1) t++; return t;
}
int getit(int x){
int t=0; for (; x; x^=x&-x) t++; return t;
}
int main(){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
int len=max(max(calc(a),calc(b)),calc(c)),ans;
a=getit(a); b=getit(b); c=getit(c);
if (a>b) swap(a,b);
if (c<=a) ans=(1<
by lych
2016.4.7
이렇게 하면 0 을
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.