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

2024. 9. 7. 11:03· [Codeforces]
목차
  1. A. Sakurako's Exam
  2.  
  3.  
  4. B. Square or Not
  5. C. Longest Good Array
  6. D. Sakurako's Hobby
반응형

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;
}

 

반응형

'[Codeforces]' 카테고리의 다른 글

[Codeforces] Diagonals [C++]  (0) 2024.07.24
[Codeforces] Array Craft [C++]  (0) 2024.07.21
[Codeforeces] Submission Bait [C++]  (0) 2024.07.21
  1. A. Sakurako's Exam
  2.  
  3.  
  4. B. Square or Not
  5. C. Longest Good Array
  6. D. Sakurako's Hobby
'[Codeforces]' 카테고리의 다른 글
  • [Codeforces] Diagonals [C++]
  • [Codeforces] Array Craft [C++]
  • [Codeforeces] Submission Bait [C++]
경우42
경우42
개발 등 공부기록용 블로그입니다
경우42
경우없는 개발 블로그
경우42
전체
오늘
어제
  • 분류 전체보기 (225)
    • 후기 (1)
    • [Codeforces] (4)
    • [SW Expert Academy] (10)
    • [백준] (149)
      • C++ (144)
      • C# (4)
      • python (1)
    • [프로그래머스] (15)
      • lv.3 (8)
      • lv.2 (4)
      • lv.1 (3)
    • [CS(Computer Science)] (2)
      • 자료구조 (2)
    • 알고리즘 (32)
      • Tip (6)
      • 코드 (15)
      • SQL 문법 정리 (10)
    • 웹개발지식 (2)
    • 스프링 (2)
    • 딥러닝 (0)
    • [가톨릭대주변음식점] (2)
      • 런칭&모니터링 (0)
      • 개발 (0)
      • 트러블 슈팅 (2)
    • [만냠-밥약속매칭플랫폼] (1)
    • [일정정리 웹 개발] (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 10845번
  • lv.2
  • 두 포인터
  • 10989번
  • 4920번
  • 17352번
  • c#
  • C++
  • 133300번
  • 냠톨릭
  • 9012번
  • 14246번
  • 11365번
  • 2751번
  • 2003번
  • 프로그래머스
  • 플로이드-워셜
  • 코드 #다익스트라
  • 백준
  • 5585번

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
경우42
Codeforces Round 970 (Div. 3) A,B,C,D 풀이
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.