Codeforces Round 970 (Div. 3) A,B,C,D 풀이

A. Sakurako's Exam

 

 

a b 가 주어지는데 a개수만큼 1이 주어지고 b의 개수만큼 2가 주어지는데

각 숫자 사이에 부호를 + , -를 배치해서 0을 만들수 있는지 출력하는문제

 

a와 b의 개수를 파악해서 각자 짝수냐 홀수냐 그리고 1의개수를 잘 따지면 된다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int a, b;
        cin >> a >> b;
 
        int remainB = 0;
        if (b % 2 != 0) {
            remainB = b % 2;
        }
 
        if (a  == remainB *2) {
            cout << "yes" << '\n';
        }
        else if (a % 2 != 0 || a == 0) {
            cout << "no" << '\n';
        }
        else {
            cout << "yes" << '\n';
        }
 
    }
 
    return 0;
}

 

 

B. Square or Not

 

 

 

정사각형의 테두리는 1이고 가운데는 0인 행렬로 만들 수 있는지 물어보는 문제

주어지는 입력이 한줄로 이뤄지기 때문에

 

이 한줄 입력을 정사각행렬에 맞춰서 인덱스 조회가 가능한지 물어보는 문제

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
 
 
int main() {
    
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
 
        bool flag = true;
 
        int root = sqrt(n);
        if (root * root != n) {
            flag = false;
        }
 
        for (int i = 0; i < root; i++) {
            if (s[i] != '1' || s[n - root + i] != '1') flag = false;
 
            if (s[i * root] != '1' || s[(i + 1) * root - 1] != '1') flag = false;
        }
 
        for (int i = 1; i < root - 1; i++) {
            for (int j = 1; j < root - 1; j++) {
                if (s[i * root + j] != '0') flag = false;
            }
        }
 
        if (flag) {
            cout << "yes" << '\n';
        }
        else {
            cout << "no" << '\n';
        }
    }
 
    return 0;
}

 

 

C. Longest Good Array

 

점점 증가하는 행렬을 만드는데 이전과 원소와의 차이도 증가하는 행렬을 만드는 문제

차이가 점점 증가하므로 등차수열을 활용하면 된다 

 

#include <iostream>
using namespace std;
 
 
long long sum_sequence(long long n) {
    return n * (n + 1) / 2;
}
 
int longest_array(int l, int r) {
    int diff = r - l;
 
 
    int left = 0, right = 10000000; 
    int max_n = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
        if (sum_sequence(mid) <= diff) {
            max_n = mid; 
            left = mid + 1;
        }
        else {
            right = mid - 1; 
        }
    }
 
    return max_n + 1; 
}
 
int main() {
    int t;
    cin >> t; 
 
    while (t--) {
        int l, r;
        cin >> l >> r; 
 
 
        if (l == r) {
            cout << 1 << endl;
        }
        else {
            cout << longest_array(l, r) << endl;
        }
    }
 
    return 0;
}

 

D. Sakurako's Hobby

 

 

각 배열을 흰색 혹은 블랙으로 이뤄져있고

 

각 배열의 인덱스 i 에서 배열의 원소가 3이라면 3의 인덱스를 참조하고 배열의 인덱스 3 의 p[3] 원소를 또참조해서 만나는 블랙의 원소들의 개수를 전부 카운팅 하는 문제

 

말그대로 구현문제이다.

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
 
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> p(n);
        vector<int> F(n, -1);
        vector<bool> visited(n, false);
 
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            p[i]--;
        }
 
        string s;
        cin >> s;
 
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
 
            vector<int> cycle;
            int x = i;
            while (!visited[x]) {
                visited[x] = true;
                cycle.push_back(x);
                x = p[x]; 
            }
 
 
            int black_count = 0;
            for (int idx : cycle) {
                if (s[idx] == '0') black_count++;
            }
 
            for (int idx : cycle) {
                F[idx] = black_count;
            }
        }
 
        for (int i = 0; i < n; i++) {
            cout << F[i] << " ";
        }
        cout << endl;
    }
 
    return 0;
}