头像

忘打周赛

假号&开朗的网友&封禁&Py&光与暗&光之国家族,无条件互粉$\Huge{小小声:有同玩}$$\Huge{phigros的盆友}$$\Huge{互粉呗~}$




在线 


最近来访(2285)
用户头像
DDF
用户头像
我是xdy
用户头像
孤芳自赏
用户头像
太雪菜
用户头像
yiziyi
用户头像
SunnyYuan
用户头像
冰凝
用户头像
冰之韵
用户头像
Cold_heartless
用户头像
卡一哦
用户头像
no_one
用户头像
lsz_
用户头像
猫公主喵喵
用户头像
tomousw
用户头像
2010
用户头像
清风qwq
用户头像
wv290123
用户头像
Acwing_kws
用户头像
tiaotiao2011
用户头像
獨孤求敗

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

#include <bits/stdc++.h>
using namespace std;
int bcj[100002], n, m, a, b;
char op;
int find(int x) {
    if (bcj[x] == x) return x;
    return (bcj[x] = find(bcj[x]));
}
void merge(int x, int y) {
    bcj[find(x)] = find(y);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) bcj[i] = i;
    for (int i = 1; i <= m; i ++ ) {
        cin >> op >> a >> b;
        if (op == 'M') { if (find(a) != find(b)) merge(a, b); }
        else cout << (find(a) == find(b) ? "Yes" : "No") << endl;
    }
}


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

#include <bits/stdc++.h>
using namespace std;
int n, a[100002], trie[3000002][2], idx, ans;
void insert(int x) {
    int p = 0;
    for (int i = 30; ~ i; i -- ) {
        int &s = trie[p][x >> i & 1];
        if (! s) s = ++ idx;
        p = s;
    }
}
int find(int x) {
    int ans = 0, p = 0;
    for (int i = 30; ~ i; i -- ) {
        int s = x >> i & 1;
        if (trie[p][! s]) ans += 1 << i, p = trie[p][! s];
        else p = trie[p][s];
    }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        insert(a[i]);
    }
    for (int i = 1; i <= n; i ++ ) ans = max(ans, find(a[i]));
    cout << ans;
}


新鲜事 原文

深夜学习trie树的我



#include <bits/stdc++.h>
using namespace std;
int bcj[100002], cnt[100002], n, m;
int find(int u) {
    if (bcj[u] == u) return u;
    return bcj[u] = find(bcj[u]);
}
int main() {
    cin >> n >> m;
    string t;
    int x, y;
    for (int i = 1; i <= n; i ++ ) bcj[i] = i, cnt[i] = 1;
    for (int i = 1; i <= m; i ++ ) {
        cin >> t;
        if (t[0] == 'C') {
            cin >> x >> y;
            if (find(x) != find(y)) cnt[find(x)] += cnt[find(y)], bcj[find(y)] = bcj[find(x)];
        }
        else if(t[0] == 'Q') {
            if(t[1] == '1') {
                cin >> x >> y;
                if(find(x) == find(y)) cout << "Yes"<< endl;
                else cout  << "No" << endl;
            }
            else cin >> x, cout << cnt[find(x)] << endl;
        }
    }

}


活动打卡代码 AcWing 154. 滑动窗口

#include <bits/stdc++.h>
using namespace std;
int q[1000002], a[1000002], n, k, t, h = 1;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) {
        if (h <= t && q[h] <= i - k) h ++;
        while (h <= t && a[q[t]] >= a[i]) t --;
        q[++ t] = i;
        if (i >= k) printf("%d ", a[q[h]]);
    }
    cout << endl;
    t = 0, h = 1;
    for (int i = 1; i <= n; i ++ ) {
        if (h <= t && q[h] <= i - k) h ++;
        while (h <= t && a[q[t]] <= a[i]) t --;
        q[++ t] = i;
        if (i >= k) printf("%d ", a[q[h]]);
    }
}


活动打卡代码 AcWing 829. 模拟队列

为啥弹幕区有人说难

#include <bits/stdc++.h>
using namespace std;
int q[100002], h, t = 1, m;
string op;
int main() {
    cin >> m;
    while (m -- ) {
        cin >> op;
        if(op == "push") cin >> q[++ h];
        else if (op == "pop") t ++;
        else if (op == "empty") cout << (t > h ? "YES" : "NO") << endl;
        else cout << q[t] << endl;
    }
}


活动打卡代码 AcWing 3302. 表达式求值

#include <bits/stdc++.h>
using namespace std;
stack <int> num;
stack <char> op;
void calc() {
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    if (c == '+') num.push(a + b);
    else if (c == '-') num.push(a - b);
    else if (c == '*') num.push(a * b);
    else if (c == '/') num.push(a / b);
    else num.push(pow(a, b));//我偷偷加个幂没人介意吧。。。

}
int main() {
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ ) {
        auto c = str[i];
        if (isdigit(c)) {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j])) x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')') {
            while (op.top() != '(') calc();
            op.pop();
        }
        else {
            while (op.size() && pr[op.top()] >= pr[c]) calc();
            op.push(c);
        }
    }
    while (op.size()) calc();
    cout << num.top();
}


活动打卡代码 AcWing 827. 双链表

比上次就多了,调了亿个多小时

#include <bits/stdc++.h>
using namespace std;
int m, e[100002], l[100002], r[100002], idx;
void insert(int a, int x) {
    e[idx] = x, l[idx] = a, r[idx] = r[a], l[r[a]] = idx, r[a] = idx ++;
}
void remove(int a) {
    r[l[a]] = r[a], l[r[a]] = l[a];
}
int k, x;
string op;
int main() {
    cin >> m;
    r[0] = 1, l[1] = 0, idx = 2;
    while (m -- ) {
        cin >> op;
        if (op == "L") cin >> x, insert(0, x);
        else if (op == "R") cin >> x, insert(l[1], x);
        else if (op == "D") cin >> k, remove(k + 1);
        else if (op == "IL") cin >> k >> x, insert(l[k + 1], x);
        else cin >> k >> x, insert(k + 1, x);
    }
    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
}


活动打卡代码 AcWing 826. 单链表

调了亿小时,就那么亿小时

#include <bits/stdc++.h>
using namespace std;
int head, e[100002], ne[100002], idx;
void init() {
    head = -1;
    idx = 0;
}
void add_to_head(int x) {
    e[idx] = x, ne[idx] = head, head = idx ++;
}
void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}
void remove(int k) {
    ne[k] = ne[ne[k]];
}
int m, k, x;
char op;
int main() {
    cin >> m;
    init();
    while (m -- ) {
        cin >> op;
        if (op == 'H') cin >> x, add_to_head(x);
        else if(op == 'D') {
            cin >> k;
            if (! k) head = ne[head];
            remove(k - 1);
        }
        else cin >> k >> x, add(k - 1, x);
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
}



原题

我的10pts wa+tle die码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100002, M = 500002;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll h[N], e[M], ne[M], w[M], idx, state[N], dist[N], ene[N], n, m, ans;
void add(ll a, ll b, ll c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = ++ idx;
}
void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[n] = 0;
    for (int i = h[n]; i != -1; i = ne[i]) dist[i] = w[i];
    for (int i = 1; i <= n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) if (!state[j] && (t == -1 || dist[j] < dist[t])) t = j;
        state[t] = 1;
        for (int j = h[t]; j != -1; j = ne[j]) {
            int i = e[j];
            if (dist[i] == INF) dist[i] = w[j];
            else dist[i] = min(dist[i], dist[t] + w[j]);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) h[i] = -1, scanf("%lld", &ene[i]);
    while (m -- ) {
        ll a, b, w;
        scanf("%lld%lld%lld", &a, &b, &w);
        add(a, b, w);        
        add(b, a, w);
    }
    dijkstra();
    for (int i = 1; i <= n; i ++ ) if (dist[i] <= dist[1]) ans += ene[i];
    cout << ans;
}