bzoj 3107 2 진 a + b 구조

일상 orzPo 할아버지 때 봤 어 요.재 미 있 겠 다.
       예 를 들 면 정말 알 기 쉬 운 것 같 아 요.아래 의 a, b, c 는 모두 원제 에서 a, b, c 의 자릿수 를 나타 낸다. 또한 a < b 를 사용 해도 무방 하 다.그리고 경계 라 니 요?
       1. c < a < b, 구조의 예 는 다음 과 같다 (a = 4, b = 7, c = 2).
0001111111
0110000011
1000000010
       f (a, b, c) 는 c < a < b 시의 최소 자릿수 를 만족 시 킵 니 다.c = 1 일 때 a + b + 1 비트, 즉 f (a, b, 1) = a + b + c 가 필요 합 니 다.그렇지 않 으 면 마지막 에 (1, 1) 이 아니라면 자릿수 는 f (a - 1, b, c - 1) + 1 또는 f (a, b - 1, c - 1) + 1 이다.그렇지 않 으 면 자릿수 는 f (a - 1, b - 1, c - 1) + 1 이다.그러면 수학 귀납법 (광범 위 하 게 말 할 수 밖 에 없다) 에 따 르 면 f (a - 1, b - 1, c - 1) 가 가장 작 기 때문에 마지막 은 (1, 1) 일 수 밖 에 없다.
       2. a < c < b, 구조의 예 는 다음 과 같다 (a = 4, b = 7, c = 5).
00011110
01111111
10011101
       분명히 자릿수 는 반드시 > b 이 고, 그러면 자릿수 는 b + 1 이 가장 좋 을 것 이 므 로, 두 번 째 수의 b 개 1 을 마지막 에 둘 수 밖 에 없다.첫 번 째 수의 마지막 이 k 위 (낮은 것 에서 높 은 것 까지) 라 고 가정 하면 먼저 k 위 를 넣 으 면 100... 0010000 (k = 5 를 가정) 이 되 고 그 다음 에 넣 은 수 는 분명히 k ~ k + a - 2 위 가 되 어야 답 을 최소 화 할 수 있다.그러면 지금 c 의 제한 을 만족 시 키 는 것 을 고려 해 보 니 세 번 째 숫자 는 이 렇 습 니 다. 10...............................................................
       3. b < c < b + c, 구조의 예 는 다음 과 같다 (a = 4, b = 7, c = 8).
011100001
011111110
111101111
       같은 분명 한 자릿수 > c (a + b = c 를 제외 하고) 는 자릿수 가 c + 1 이 어야 합 니 다. 따라서 우 리 는 0 이 가능 한 한 빨리 나타 나 도록 해 야 합 니 다.두 번 째 수 를 기준 으로 첫 번 째 수의 시작 1 의 개 수 는 a + b - c 라 는 것 을 알 게 되 었 습 니 다. 그러면 우 리 는 시작 a + b - c 를 모두 1 로 하면 됩 니 다.
       4. 상황 을 이해 하지 못 한다...이것 괜찮아요?
AC 코드 는 다음 과 같 습 니 다.

#include<cstdio>
#include<iostream>
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<<(a+b-c))|((1<<c)-2);
	else if (c<=b) ans=((1<<b)|((1<<c)-1))^(1<<(c-a));
	else if (c<=a+b) ans=((1<<(c+1))-1)^(1<<(c+c-a-b));
	else{
		puts("-1"); return 0;
	}
	printf("%d
",(calc(ans)<=len)?ans:-1);
	return 0;
}

by lych
2016.4.7
이렇게 하면 0 을