Codeforces Round #804 (Div. 2) 1692 → 1696

https://codeforces.com/contest/1699

Dashboard - Codeforces Round #804 (Div. 2) - Codeforces

!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!

 

A. The Third Three Number Problem

https://codeforces.com/contest/1699/problem/A

Problem - A - Codeforces

문제

a ^ b + b ^ c + a ^ c = n이 되는 a,b,c 세수를 출력하는 문제

 

풀이

 

n이 짝수라면 0 , 0 , n/2로 하면되고 홀수로는 답을 만들 수 없다..

 

코드

 

    #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--) {
            long long n;
            cin >> n;
            if (n % 2) {
                cout << -1 << '\n';
            }
            else {
                cout << 0 << ' ' << 0 << ' ' << n / 2 << '\n';
            }
        }
     
    }

 

B. Almost Ternary Matrix

https://codeforces.com/contest/1699/problem/B

Problem - B - Codeforces

문제

 

n과 m이 주어진다.두 값은 짝수이고 n*m 이진 행렬에서 각 셀마다 인접한 셀중에 다른 값을 가진 셀이 정확히 2개가 되도록 그리드를 만들어서 출력하는 문제

 

풀이

 

1 0 0 1

0 1 1 0

0 1 1 0

1 0 0 1

구조를 반복해 만들어서 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int a[101][101];
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n, m;
            cin >> n >> m;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    a[i][j] = 0;
                }
            }
            a[1][1] = 1; a[1][2] = 0;
            a[2][1] = 0; a[2][2] = 1;
            int cnt = 1;
            for (int i = 3; i <= m; i += 2) {
                if (cnt % 2) {
                    //01
                    //10
                    a[1][i] = 0; a[1][i + 1] = 1;
                    a[2][i] = 1; a[2][i + 1] = 0;
                }
                else {
                    //10
                    //01
                    a[1][i] = 1; a[1][i + 1] = 0;
                    a[2][i] = 0; a[2][i + 1] = 1;
                }
                cnt++;
            }
            cnt = 1;
            for (int i = 3; i <= n; i+=2) {
                if (cnt % 2) {
                    for (int j = 1; j <= m; j++) {
                        a[i][j] = a[i - 1][j];
                        a[i + 1][j] = 1 - a[i][j];
                    }
                }
                else {
                    for (int j = 1; j <= m; j++) {
                        a[i][j] = a[i - 4][j];
                        a[i + 1][j] = 1 - a[i][j];
                    }
                }
                cnt++;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    cout << a[i][j] << ' ';
                }
                cout << '\n';
            }
        }
     
    }

C. The Third Problem

https://codeforces.com/contest/1699/problem/C

Problem - C - Codeforces

문제

 

n과  0..n-1로 이루어진 permutation이 주어진다. 두개의 permuation a와 b는 아래의 조건을 만족할때 닮았다고 한다.

조건 : 모든 [l,r] ( 1 <= l <= r <=n)에 대해서 MEX(a[l]..a[r])  = MEX(b[l]..b[r]) 이다.

a 배열이 주어졌을때 닮은 배열의 개수를 출력하는 문제

 

풀이

 

0부터 n-1까지 인덱스를 저장한 후 0..1 , 0..2 와 같은 구간을 찾아 준 뒤 각 구간에서 자유롭게 섞을 수있는 원소들의 개수를 구한후 순열을 곱해주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    const long long mod = 1000000007;
    long long fact[100001];
    long long mpow(long long a, long long x)
    {
        if (x == 0) return 1;
        long long res = mpow(a, x / 2);
        res = res * res % mod;
        if (x % 2) res = res * a % mod;
        return res % mod;
    }
     
    long long nCr(long long n, long long r)
    {
        long long res = fact[n];
        res *= mpow(fact[r], mod - 2); res %= mod;
        res *= mpow(fact[n - r], mod - 2);
        return res % mod;
    }
    int a[100001];
     
    int idx[100001];
    bool check[100010];
     
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        fact[0] = 1;
        for (long long i = 1; i < 100001; i++) {
            fact[i] = fact[i - 1] * i;
            fact[i] %= mod;
        }
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                idx[a[i]] = i;
                check[i] = false;
            }
            check[n] = false;
            int ml = idx[0], mr = idx[0];
            long long MEX = 1;
            int cnt = 1;
            int sum = 0;
            long long ans = 1;
            for (int i = 1; i < n; i++) {
                bool flag = true;
                if (ml > idx[i]) {
                    for (int j = ml - 1; j >= idx[i]; j--) {
                        check[a[j]] = true;
                    }
                    ml = idx[i];
                    flag = false;
                }
                if (mr < idx[i]) {
                    for (int j = mr + 1; j <= idx[i]; j++) {
                        check[a[j]] = true;
                    }
                    mr = idx[i];
                    flag = false;
                }
                if (flag)continue;
                cnt++;
                long long nowMEX = MEX;
                while (check[nowMEX])nowMEX++;
                int len = mr - ml + 1;
                int dif = nowMEX-(i+1);
                int rest = len - cnt - sum;
                for (long long j = rest - dif + 1; j <= rest; j++) {
                    ans *= j;
                    ans %= mod;
                }
                sum += dif;
                MEX = nowMEX;
            }
            cout << ans << '\n';
     
     
     
        }
     
    }

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.