티스토리 뷰
https://codeforces.com/contest/1632
Dashboard - Codeforces Round #769 (Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. ABC
https://codeforces.com/contest/1632/problem/A
Problem - A - Codeforces
codeforces.com
문제
0 과 1로만 이루어진 문자열이 있다. 주어진 문자열을 원하는대로 재정렬하여 길이가 2이상인 팰린드롬이 없게 만들 수 있는지 출력하는 문제
풀이
0이든 1이든 같은 문자가 2개이상 있으면 정답은 NO 이외에는 YES이다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string s;
cin >> s;
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0')cnt0++;
else cnt1++;
}
if (cnt0 > 1 || cnt1 > 1)cout << "NO\n";
else cout << "YES\n";
}
}
B. Roof Construction
https://codeforces.com/contest/1632/problem/B
Problem - B - Codeforces
codeforces.com
문제
0 부터 n-1까지의 수가 있다. 모두 xor 시켰을때 최소 값이 나오도록 수를 임의의 순서로 정렬하여 출력하는 문제
풀이
모두 xor 시켰을때 결국 n-1보다 같거나 작은 2의 제곱수가 최소 값이 된다. 그렇게 정렬하려면 {n-1 , ... , 최대 2의제곱수 , 0, ... , 나머지 자유롭게 } 순으로 정렬하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
bool check[200001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
if (n == 2)cout << "0 1\n";
else if (n == 3)cout << "2 0 1\n";
else {
int cnt = 0, start = 1;
while (start <= (n-1))start *= 2;
start /= 2;
for (int i = n - 1; i >= start; i--)cout << i << ' ';
cout << 0 << ' ';
for (int i = start - 1; i > 0; i--)cout << i << ' ';
cout << '\n';
}
}
}
C. Strange Test
https://codeforces.com/contest/1632/problem/C
Problem - C - Codeforces
codeforces.com
문제
두 수 a,b가 주어졌을때 아래 연산을 통해 a를 b로 만들 수 있는 최소 연산의 수를 출력하는 문제
1. a+=1
2. b+=1
3. a|=b
풀이
a부터 b까지 모든 a를 더해가면서 , a를 b bit에 맞게 더한 후 or시킨 값과 , b를 a bit에 맞게 더한 후 or 시킨 값의 최소를 저장해 출력한다.
코드
#include <bits/stdc++.h>
using namespace std;
int d[23];
const int MAX = 3000000;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
d[0] = 1;
for (int i = 1; i < 23; i++)d[i] = d[i - 1] * 2;
int T;
cin >> T;
while (T--) {
int a, b;
cin >> a >> b;
int ans = MAX,sum=0;
while (true) {
if (a == b)break;
if ((a + 1) == b) {
ans = min(ans, sum + 1);
break;
}
bool flag = true;
for (int i = 19; i >= 0; i--) {
if ( (a & d[i]) && (b & d[i])==0) {
flag = false;
break;
}
}
if (flag) {
ans = min(ans, sum + 1);
}
ans = min(ans, sum + b - a);
int t1=MAX, t2 = MAX;
int tempB = b,tempA=a;
//b에 더해준다
for (int i = 19; i >= 0; i--) {
if ((tempB & d[i]) && (tempA & d[i]) == 0) {
tempB -= d[i];
}
else if ((tempA & d[i]) && (tempB & d[i])) {
tempA -= d[i];
tempB -= d[i];
}
else if ((tempA & d[i]) && (tempB & d[i])==0) {
t2 = tempA - tempB;
break;
}
}
//a에 더해준다
tempA = a; tempB = b;
for (int i = 19; i >= 0; i--) {
if ((a & d[i]) && (b & d[i])) {
tempA -= d[i];
tempB -= d[i];
}
else if ((a & d[i]) == 0 && (b & d[i])) {
t1 = d[i] - tempA;
break;
}
}
if (a + t1 == b) ans = min(ans, sum + t1);
else ans = min(ans, sum + t1 + 1);
ans = min(ans, sum + t2 + 1);
a++;
sum++;
}
cout << ans << '\n';
}
}
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.
'Algorithm > 코드포스' 카테고리의 다른 글
Codeforces Global Round 19 1663 -> 1589 (0) | 2022.02.14 |
---|---|
Codeforces Round #770 (Div. 2) 1654 -> 1663 (1) | 2022.02.07 |
Codeforces Round #768 (Div. 2) 1689 -> 1678 (0) | 2022.01.28 |
Codeforces Round #767 (Div. 2) 1673 -> 1689 (0) | 2022.01.23 |
Codeforces Round #766 (Div. 2) 1652 -> 1673 (0) | 2022.01.16 |