
Codeforces Round #735 (Div. 2)-C. Mikasa
falconlee236
·2021. 12. 19. 15:39
문제 설명
두 정수
음이 아닌 정수를 원소로 가진 수열의
Input
첫번째 줄에는 테스트 케이스의 수
각 테스트 케이스의 첫번째 줄에는 두 정수
Output
각 테스트케이스마다 문제의 답을 출력한다.
Example
input
5
3 5
4 6
3 2
69 696
123456 654321
output
4
3
0
640
530866
문제 접근
사용한 알고리즘: 비트마스크, 그리디 알고리즘, 수학
걸린 시간 : 00:11
이전 virtual contest에서 알았던 개념인 MEX를 그리디 알고리즘과 응용해서 나온 문제이다. 이 문제가 좋았던 점은 실제 MEX를 구하는 방법을 알려주는 것과 같은 의도를 가지고 출제했다는 것이었다. 두 정수
여기서
이면 이다.
3번 성질을 이 문제에서 사용할 것이다. 그렇다고 해서 1번과 2번을 이해하지 못하면 안된다. 왜냐하면 1번과 2번 성질을 이용해서 나온 성질이 3번이기 때문이다.
그렇다면 이
의 한 비트가 0이고, 의 한 비트가 0일때, 이 경우는 두 비트가 같아야 0이 나오기 때문에 무조건 k의 값이 0이 될수밖에 없다. 의 한 비트가 1이고, 의 한 비트가 1일때, 이 경우는 두 비트가 달라야 1이 나오기 때문에 무조건 k의 값이 0이 될수밖에 없다. 의 한 비트가 1이고, 의 한 비트가 0일때, 이 경우는 일단 두 비트가 같아야 0이 나오는데, 우리는 값을 보다 크게 만들어야 하는게 목적이다. 그렇다면 이 대응되는 비트를 0으로 만든다면 의 값이 1이 나오게 되고, 이 값은 대응대는 비트가 0인 보다 반드시 크다. 그리고 최소 값을 만들어야 하기 때문에 뒤의 비트들을 모두 0으로 만들면 최소 값을 만들 수 있다. 즉 이 경우에 바로 뒤를 0으로 만들고 break를 하면 된다. 의 한 비트가 0이고, 의 한 비트가 1일때, 이경우는 일단 두 비트가 달라야 1이 나오는데, 가 0이면 가 보다 반드시 작기 때문에 이 경우의 비트는 반드시 1이 되어야 한다.
정답 코드
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--){
int n, m; cin >> n >> m;
int p = m + 1;
int ans = 0;
for(int i = 30; i >= 0; i--){
bool a = n & (1 << i);
bool b = p & (1 << i);
if(!a && b) ans |= (1 << i);
if(a && !b) break;
}
cout << ans << "\n";
}
return 0;
}
'알고리즘 > codeforces' 카테고리의 다른 글
Codeforces Round #734 (Div. 3)-B1. Wonderful Coloring - 1 (0) | 2021.12.20 |
---|---|
Codeforces Round #734 (Div. 3)-A. Polycarp and Coins (0) | 2021.12.20 |
Codeforces Round #735 (Div. 2)-B. Cobb (0) | 2021.12.19 |
Codeforces Round #735 (Div. 2)-A. Cherry (0) | 2021.12.19 |
Codeforces Round #738 (Div. 2)-D1. Mocha and Diana (Easy Version) (0) | 2021.12.19 |