头像

scc




离线:8天前


活动打卡代码 AcWing 843. n-皇后问题

scc
2个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 10;

char res[N][N];

bool col[N], row[N], pie[2 * N], na[2 * N];

int n;

void dfs(int y, int x, int s) {
    if(s == n) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j)
                cout << res[i][j];
            cout << endl;
        }

        cout << endl;
        return;
    }

    if(x == n) x = 0, ++y;

    if(y >= n) return;

    // 不放
    dfs(y, x + 1, s);

    // 放
    if(!col[x] && !row[y] && !pie[y - x + n] && !na[y + x]) {
        res[y][x] = 'Q';
        col[x] = row[y] = pie[y - x + n] = na[y + x] = true;
        dfs(y, x + 1, s + 1);
        col[x] = row[y] = pie[y - x + n] = na[y + x] = false;
        res[y][x] = '.';
    }
}

int main() {
    cin >> n;

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            res[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 841. 字符串哈希

scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

char str[N];

int p[N], h[N];

int get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    cin >> n >> m;

    cin >> str + 1;

    p[0] = 1;
    for(int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }

    int l1, r1, l2, r2;
    while(m--) {
        cin >> l1 >> r1 >> l2 >> r2;

        if(get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 842. 排列数字

scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 10;

int path[N], n;

bool st[N];

void bfs(int u) {
    if(u == n) {
        for(int i = 0; i < n; ++i) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 1; i <= n; ++i) {
        if(!st[i]) {
            path[u] = i;
            st[i] = true;
            bfs(u + 1);
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;
    bfs(0);

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 840. 模拟散列表

scc
3个月前
//这里填你的代码^^
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

int find(int x) {
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x) {
        ++k;
        if(k == N) k = 0;
    }

    return k;
}

int main() {
    int n;
    cin >> n;

    string op;
    int x;

    memset(h, 0x3f, sizeof h);

    while(n--) {
        cin >> op >> x;

        if(op == "I") {
            h[find(x)] = x;
        } else {
            if(h[find(x)] == null) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 839. 模拟堆

scc
3个月前
//这里填你的代码^^
#include <iostream>
#include <string>
using namespace std;

const int N = 100010;

// ph: idx -> k, hp: k -> idx
int arr[N], ph[N], hp[N], idx;

void heap_swap(int x, int y) {
    swap(hp[ph[x]], hp[ph[y]]);
    swap(ph[x], ph[y]);
    swap(arr[x], arr[y]);
}

void down(int x) {
    int i = x;
    while(x <= idx) {
        if(2 * x <= idx && arr[2 * x] < arr[i]) i = 2 * x;
        if(2 * x + 1 <= idx && arr[2 * x + 1] < arr[i]) i = 2 * x + 1;
        if(i == x) break;
        heap_swap(i, x);
        x = i;
    }
}

void up(int x) {
    while(x / 2 > 0) {
        if(arr[x / 2] > arr[x]) heap_swap(x / 2, x);
        else break;
        x /= 2;
    }
}

int main() {
    int n, m = 0;
    cin >> n;

    string op;
    int x, k;

    while(n--) {
        cin >> op;
        if(op == "I") {
            cin >> x;
            ++idx, ++m;
            arr[idx] = x;
            ph[idx] = m;
            hp[m] = idx;
            up(idx);
        } else if(op == "PM") {
            cout << arr[1] << endl;
        } else if(op == "DM") {
            heap_swap(1, idx);
            --idx;
            down(1);
        } else if(op == "D") {
            cin >> k;
            k = hp[k];
            heap_swap(k, idx);
            --idx;
            up(k);
            down(k);
        } else {
            cin >> k >> x;
            k = hp[k];
            arr[k] = x;
            up(k);
            down(k);
        }
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 100010;

int s[N], cnt[N];

int find(int x) {
    if(s[x] != x) s[x] = find(s[x]);
    return s[x];
}

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; ++i) {
        s[i] = i;
        cnt[i] = 1;
    }

    string op;
    int a, b;

    while(m--) {
        cin >> op;
        if(op == "C") {
            cin >> a >> b;

            int xRoot = find(a);
            int yRoot = find(b);

            if(xRoot != yRoot) {
                s[yRoot] = xRoot;
                cnt[xRoot] += cnt[yRoot];
            }
        } else if(op == "Q1") {
            cin >> a >> b;

            if(find(a) == find(b)) {
                cout << "Yes" << endl;
            } else
                cout << "No" << endl;
        } else {
            cin >> a;

            cout << cnt[find(a)] << endl;
        }
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 143. 最大异或对

scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 100010, M = 3000010;

int son[M][2], idx;

int a[N];

void insert(int x) {
    int st = 0;
    for(int i = 30; ~i; --i) {
        if(!son[st][x >> i & 1]) son[st][x >> i & 1] = ++idx;
        st = son[st][x >> i & 1];
    }
}

int query(int x) {
    int res = 0, st = 0;
    for(int i = 30; ~i; --i) {
        int tmp = x >> i & 1;
        if(son[st][!tmp]) {
            res += (1 << i);
            st = son[st][!tmp];
        } else
            st = son[st][tmp];
    }

    return res;
}

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        insert(a[i]);
    }

    int res = 0;
    for(int i = 0; i < n; ++i) {
        res = max(res, query(a[i]));
    }

    cout << res << endl;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 831. KMP字符串

scc
3个月前
//这里填你的代码^^
#include <iostream>
#include <string>

const int N = 100010;
int next[N];

void getNext(std::string &p) {
    if(p.size() == 1) {
        next[0] = -1;
        return;
    }

    next[0] = -1;
    next[1] = 0;

    int i = 2, cn = 0;
    while(i <= p.size()) {
        if(p[cn] == p[i-1]) {
            next[i++] = ++cn; 
        } else if(cn > 0) {
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
}

int main() {
    int n;
    std::string p;
    std::cin >> n >> p;

    int m;
    std::string s;
    std::cin >> m >> s;

    getNext(p);

    int idx1 = 0, idx2 = 0;
    while(idx1 < m) {
        if(idx2 == n) {
            std::cout << (idx1 - idx2) << " ";
            idx2 = next[idx2];
        }

        if(s[idx1] == p[idx2]) {
            ++idx1;
            ++idx2;
        } else if(next[idx2] == -1) {
            ++idx1;
        } else {
            idx2 = next[idx2];
        }
    }

    if(idx2 == n) std::cout << (idx1 - idx2);
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 838. 堆排序

scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 100010;
int h[N], num;

void down(int i) {
    int t = i;
    if(2 * i <= num && h[2 * i] < h[t]) t = 2 * i;
    if(2 * i + 1 <= num && h[2 * i + 1] < h[t]) t = 2 * i + 1;
    if(i != t) {
        swap(h[i], h[t]);
        down(t);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
        ++num;
    }

    for(int i = num / 2; i > 0; --i) {
        down(i);
    }

    while(m--) {
        cout << h[1] << " ";
        h[1] = h[num];
        --num;
        down(1);
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 836. 合并集合

scc
3个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N = 100010;

int s[N];
int find(int num) {
    if(s[num] != num) s[num] = find(s[num]);
    return s[num];
}

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; ++i) s[i] = i;

    string op;
    int a, b;

    while(m--) {
        cin >> op >> a >> b;
        if(op == "M") s[find(a)] = find(b);
        else {
            if(find(a) == find(b)) cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~