头像

jeffstart




离线:5小时前


最近来访(162)
用户头像
zzr0126
用户头像
LAG_流雲
用户头像
csai
用户头像
种花家的兔兔
用户头像
瞳星结
用户头像
ret.
用户头像
Bigfish
用户头像
yxc
用户头像
wt20
用户头像
鸟笼_5
用户头像
NULL_
用户头像
我去2001年
用户头像
陌上花开Charlie
用户头像
我超喜欢沈以诚
用户头像
MyloXyloto
用户头像
@_858
用户头像
一万小时定律
用户头像
合理的预期
用户头像
y总的忠实粉丝
用户头像
龙星尘

活动打卡代码 AcWing 175. 电路维修

jeffstart
11小时前
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 510;
char d[N][N];
int dist[N][N];
bool visited[N][N];
typedef pair<int, int> P;
int n, m;

int bfs() {
    memset(visited, false, sizeof(visited));
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;
    deque<P> que;
    que.push_back({0, 0});
    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
    char c[] = "\\/\\/";
    while (!que.empty()) {
        P t = que.front();
        que.pop_front();
        int x = t.first, y = t.second;
        if (visited[x][y]) {
            continue;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            int j = x + ix[i], k = y + iy[i];
            if (a >= 0 && a <= n && b >= 0 && b <= m) {
                int diff = 0;
                if (d[j][k] != c[i]) {
                    diff = 1;
                }
                if (dist[a][b] > dist[x][y] + diff) {
                    dist[a][b] = dist[x][y] + diff;
                    if (diff) {
                        que.push_back({a, b});
                    } else {
                        que.push_front({a, b});
                    }
                }
            }
        }
    }
    return dist[n][m];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++) {
                d[i][j] = s[j];
            }
        }
        int tot = bfs();
        if (tot != INF) {
            cout << tot << "\n";
        } else {
            cout << "NO SOLUTION\n";
        }
    }
    return 0;
}


活动打卡代码 AcWing 145. 超市

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
typedef pair<int, int> P;
P a[N];

int comp(P a, P b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> a[i].first >> a[i].second;
        }
        sort(a, a + n, comp);
        priority_queue<int, vector<int>, greater<int>> que;
        for (int i = 0; i < n; i++) {
            if (que.size() < a[i].second) {
                que.push(a[i].first);
            } else {
                if (que.top() < a[i].first) {
                    que.pop();
                    que.push(a[i].first);
                }
            }
        }
        int ans = 0;
        while (!que.empty()) {
            ans += que.top();
            que.pop();
        }
        cout << ans << "\n";
    }
    return 0;
}


活动打卡代码 AcWing 4285. 多少张桌子

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
vector<int> G[N];
bool visited[N];

void dfs(int u) {
    if (visited[u]) {
        return;
    }
    visited[u] = true;
    for (auto v : G[u]) {
        dfs(v);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(visited, false, sizeof(visited));
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            G[i].clear();
        }
        while (m--) {
            int a, b;
            cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                ans++;
                dfs(i);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}


活动打卡代码 AcWing 4267. 可疑人员

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 10;
int p[N];

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

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    while (cin >> n >> m && n) {
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        while (m--) {
            int num;
            cin >> num;
            int last = -1;
            while (num--) {
                int x;
                cin >> x;
                if (last != -1) {
                    p[find(last)] = find(x);
                }
                last = x;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (find(i) == find(0)) {
                ans++;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}


活动打卡代码 AcWing 4266. 无线网络

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
typedef pair<int, int> P;
P a[N];
int fa[N];
bool open[N];
const double eps = 1e-6;

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

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        fa[i] = i;
    }
    char op;
    while (cin >> op) {
        if (op == 'O') {
            int p;
            cin >> p;
            open[p] = true;
            for (int j = 1; j <= n; j++) {
                int dx = a[p].first - a[j].first;
                int dy = a[p].second - a[j].second;
                double dist = sqrt(1.0 * dx * dx + dy * dy);
                int fp = find(p), fj = find(j);
                if (dist - d < eps && open[j] && fp != fj) {
                    fa[find(p)] = find(j);
                }
            }
        } else {
            int p, q;
            cin >> p >> q;
            if (find(p) == find(q)) {
                cout << "SUCCESS\n";
            } else {
                cout << "FAIL\n";
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 4619. 减法操作

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    int tot1 = 0, tot2 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        if (a[i] % 2 == 1) {
            a[i + 1]--;
            if (a[i + 1] < 0) {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << (a[n - 1] & 1 ? "NO\n" : "YES\n");
    return 0;
}



#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int tree[N], a[N];
int n, m;

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += c;
    }
}

int sum(int x) {
    int ans = 0;
    for (int i = x; i >= 1; i -= lowbit(i)) {
        ans += tree[i];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        add(i, a[i] - a[i - 1]);
    }
    while (m--) {
        char op;
        cin >> op;
        if (op == 'Q') {
            int x;
            cin >> x;
            cout << sum(x) << "\n";
        } else {
            int l, r, c;
            cin >> l >> r >> c;
            add(l, c), add(r + 1, -c);
        }
    }
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 10;
int p[N], d[N], len[N];

int find(int x) {
    if (p[x] != x) {
        int k = find(p[x]);
        d[x] += d[p[x]];
        p[x] = k;
    }
    return p[x];
}

int main() {
    for (int i = 1; i <= 3e4 + 10; i++) {
        p[i] = i, len[i] = 1;
    }
    int t;
    cin >> t;
    while (t--) {
        char s;
        int x, y;
        cin >> s >> x >> y;
        if (s == 'M') {
            x = find(x), y = find(y);
            if (x != y) {
                d[x] = len[y], len[y] += len[x];
                p[x] = y;
            }
        } else {
            int fx = find(x), fy = find(y);
            if (fx != fy) {
                cout << -1 << "\n";
            } else {
                cout << max(0, abs(d[x] - d[y]) - 1) << "\n";
            }
        }
    }
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 168. 生日蛋糕

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int minv[N], mins[N], H[N], R[N];
int n, m;
int ans = INF;

void dfs(int u, int v, int s) {
    if (v + minv[u] > n) return;
    if (s + mins[u] >= ans) return;
    if (s + 2 * (n - v) / R[u + 1] >= ans) return;
    if (u == 0) {
        if (v == n) {
            ans = s;
        }
        return;
    }
    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--) {
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
            int t = 0;
            if (u == m) {
                t = r * r;
            }
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }
    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);
    if (ans == INF) {
        ans = 0;
    }
    cout << ans << "\n";
    return 0;
}