맑은 신의 시뮬레이션 | 반복(중복 제외), 쿼리 + DFS

1019 | 천자백태

#include 
#include 

#define MOD 1000000007
using namespace std;
typedef long long LL;
LL type_cnt[1001] = {0};

LL dfs(int num) {
    if (num == 1 || num == 0) return type_cnt[num];
    for (int i = 0; i < num; ++i) {
        if (type_cnt[i] == 0) type_cnt[i] = dfs(i);
        if (type_cnt[num - i - 1] == 0) type_cnt[num - i - 1] = dfs(num - i - 1);
        type_cnt[num] = (type_cnt[num] + type_cnt[i] * type_cnt[num - i - 1] % MOD) % MOD;
    }
    return type_cnt[num];
}

int main() {
    int ign, n;
    scanf("%d%d", &ign, &n);
    type_cnt[0] = 1, type_cnt[1] = 1;
    printf("%lld
", dfs(n));
    return 0;
}

1023 | 누락수

#include 
#include 

using namespace std;
int vec[10000001];

int main() {
    int nn;
    long long temp;
    scanf("%d", &nn);
    for (int i = 1; i <= nn; ++i) {
        scanf("%lld", &temp);
        vec[i] = int(temp);
    }
    for (int i = 1; i <= nn; ++i) {
        while (vec[i] <= nn && vec[i] > 0 && vec[vec[i]] != vec[i])
            swap(vec[i], vec[vec[i]]);
    }
    for (int i = 1; i <= nn; ++i) {
        if (vec[i] != i) {
            printf("%d
", i);
            return 0;
        }
    }
    printf("%d
", nn + 1);
    return 0;
}

1024 | 우주 트리

#include 
#include 
#include 
#include 

using namespace std;
int nn, mm, uf[10001];
string path_val, tree_val;
char types[10001];
vector graph[10001];
bool visited[10001] = {false};

int _find(int a) {
    return uf[a] < 0 ? a : uf[a] = _find(uf[a]);
}

void _union(int a, int b) {
    a = _find(a);
    b = _find(b);
    if (a != b) {
        int ta = min(a, b), tb = max(a, b);
        uf[ta] += uf[tb];
        uf[tb] = ta;
    }
}

string str_plus(string &sa, string &sb) {
    int la = sa.length(), lb = sb.length();
    int extra = 0, temp;
    string res;
    int i = la - 1, j = lb - 1;
    for (; i >= 0 || j >= 0; i--, j--) {
        int a = i >= 0 ? sa[i] - '0' : 0, b = j >= 0 ? sb[j] - '0' : 0;
        temp = extra + a + b;
        extra = temp / 10;
        temp %= 10;
        res += char(temp + '0');
    }
    if (extra) res += char(extra + '0');
    while (res.back() == '0') res.pop_back();
    if (res.empty()) res = "0";
    reverse(res.begin(), res.end());
    return res;
}

void DFS(int curr) {
    if (graph[curr].empty()) {
        string temp;
        temp += types[curr];
        tree_val = str_plus(tree_val, temp);
        return;
    }
    if (graph[curr].size() == 1 && visited[graph[curr][0]]) { // leaf
        path_val += types[curr];
        tree_val = str_plus(tree_val, path_val);
        path_val.pop_back();
        return;
    }
    visited[curr] = true;
    path_val += types[curr];
    for (auto item:graph[curr]) {
        if (!visited[item])DFS(item);
    }
    visited[curr] = false;
    path_val.pop_back();
}

int main() {
    scanf("%d%d
", &nn, &mm);
    fill(uf, uf + nn, -1);
    int v1, v2;
    for (int i = 0; i < nn; ++i)
        scanf("%c ", &types[i]);
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d", &v1, &v2);
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
        _union(v1, v2);
    }
    vector roots;
    int cnt = 0;
    for (int i = 0; i < nn; ++i) {
        _find(i);
        if (uf[i] < 0) {
            roots.push_back(i);
            cnt++;
        }
    }
    printf("%d
", cnt);
    for (int i = 0; i < cnt; i++) {
        tree_val = "0";
        DFS(roots[i]);
        printf("%s", tree_val.data());
        printf(i + 1 == cnt ? "
" : " ");
        fill(visited, visited + nn, false);
    }
    return 0;
}