头像

唯爱

暂无组织




离线:4小时前


最近来访(46)
用户头像
Jz_9
用户头像
小飞龙
用户头像
zyz529
用户头像
用户头像
lujunting
用户头像
FBIFBIFBIFBIFBIFBIFBIFBIFBIFBI
用户头像
--+
用户头像
游手好闲人上壬
用户头像
是贤鱼ya
用户头像
111yy66
用户头像
Zrosor_Acw
用户头像
SCP基金会
用户头像
轶只小giao
用户头像
Chi
用户头像
shaoyifan
用户头像
星星亮了
用户头像
LiyeeW
用户头像
stamina_zeng
用户头像
陶晰睿
用户头像
Colopen

新鲜事 原文

唯爱
1天前
孤独也许是一个人在某个时候的所思所想,放手拼搏吧,少年,你的未来一片光明!
图片


活动打卡代码 AcWing 1135. 新年好

唯爱
1天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;
const int N = 500010, M = 200010, INF = 0x3f3f3f3f;
vector<int> q, p;
bool snt[6], tt[N];
int n, m, e[M], ne[M], h[N], idx, w[N], d[6][N], res = INF;
unordered_map<int, int> mp;

void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

void spfa(int x, int k){
    memset(tt, 0, sizeof tt);
    d[k][x] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> qu;
    qu.push({0, x});
    while(qu.size()){
        auto value = qu.top();
        qu.pop();
        int val = value.second, dis = value.first;
        if (tt[val]) continue;
        tt[val] = true;
        for (int i = h[val]; i != -1; i = ne[i]){
            int t = e[i];
            if (d[k][t] > dis + w[i]){
                d[k][t] = dis + w[i];
                qu.push({d[k][t], t});
            }
        }
    }
}

void dfs(int sums, int pr, int num){
    if (num == 5) {
        res = min(res, sums);
        return;
    }
    for (int i = 0; i < 5; i ++){
        int k = p[i];
        if (!snt[i]){
            snt[i] = true;
            dfs(sums + d[pr][k], mp[k]+1, num + 1);
            snt[i] = false;
        }
    }
}

int main(){
    cin >> n >> m;
    memset(d, INF, sizeof d);
    memset(h, -1, sizeof h);
    for(int i = 0; i < 5; i ++) {
        int x;
        scanf("%d", &x);
        p.push_back(x);
        mp[x] = i;
    }

    for (int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    spfa(1, 0);
    for (int i = 0; i < 5; i ++) spfa(p[i], i+1);
    dfs(0, 0, 0);
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1072. 树的最长路径

唯爱
3天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 20010, M = 10010;
int n, e[N], ne[N], h[M], idx, w[N];
int ans;
bool snt[M];

void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dfs(int val, int d){
    bool falg = false;
    int d1 = 0, d2 = 0, maxV = 0;
    for (int i = h[val]; i != -1; i = ne[i]){
        int k = e[i];
        if (!snt[k]){
            snt[k] = true;
            falg = true;
            int t = dfs(k, d) + w[i];
            maxV = max(maxV, t);

            if (t >= d1) d2 = d1, d1 = t; 
            else if (t >= d2) d2 = t;
            snt[k] = false;
        }
    }

    ans = max(ans, d1 + d2);
    if (!falg) return d;
    return maxV;

}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n-1; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    snt[1] = true;
    dfs(1, 0);
    cout << ans;
    return 0;
}


新鲜事 原文

唯爱
3天前
图片


活动打卡代码 AcWing 1068. 环形石子合并

唯爱
3天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 410;
int f[N][N], sums[N], a[N], q[N][N];

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        sums[i] = a[i] + sums[i-1];
    };

    for (int i = n + 1; i <= 2 * n; i ++){
        sums[i] = sums[i - 1] + a[i-n];
    }

    for (int i = 2; i <= 2 * n; i ++){
        for (int l = 1; l <= 2 * n - i + 1; l ++){
            int r = l + i - 1;
            f[l][r] = 0x3f3f3f3f;
            q[l][r] = 0;
            for (int k = l; k < r; k ++){
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + sums[r]-sums[l-1]);
                q[l][r] = max(q[l][r], q[l][k] + q[k+1][r] + sums[r]-sums[l-1]);
            }
        }
    }
    int resMin = 0x3f3f3f3f, resMax = 0;
    for (int i = 1; i < 2 * n - n + 1; i ++){
        resMin = min(resMin, f[i][i + n - 1]);
        resMax = max(resMax, q[i][i + n - 1]);
    }
    cout << resMin << endl;
    cout << resMax;
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

唯爱
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;
typedef pair<int, int> PR;
const int N = 14010, INF = 0x3f3f3f3f, M = 2510;
int e[N], ne[N], h[N], idx, w[N], n, c, start, es, dist[M];

void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}

int dijstra(){
    priority_queue<PR, vector<PR>, greater<PR>> qu;
    memset(dist, INF, sizeof dist);
    qu.push({0, start});
    dist[start] = 0;
    while(qu.size()){
        auto x = qu.top();
        qu.pop();
        int val = x.second, dis = x.first;
        if (val == es) return dis;
        for (int i = h[val]; i != -1; i = ne[i]){
            int k = e[i];
            if (dis + w[i] < dist[k]){
                dist[k] = dis + w[i];
                qu.push({dis + w[i], k});
            }
        }
    }
    return dist[es];
}

int main(){
    cin >> n >> c >> start >> es;
    memset(h, -1, sizeof h);

    for (int i = 0; i < c; i ++){
        int rs, re, ci;
        scanf("%d%d%d", &rs, &re, &ci);
        add(rs, re, ci);
        add(re, rs, ci);
    }
    cout << dijstra();
    return 0;
}


新鲜事 原文

唯爱
4天前
图片


活动打卡代码 AcWing 1064. 小国王

唯爱
5天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 12, M = 110, K = 1 << 10;
typedef long long LL;
LL f[N][M][K], n, k;
vector<int> head[K];
vector<int> state;
int cnt[K];

bool check(int x){
    for (int i = 0; i <= x; i ++){
        if (1 << i & x && 1 << (i+1) & x) return false;
    }
    return true;
}

int counts(int x){
    int num = 0;
    while(x) {
        num ++;
        x = (x-1) & x;
    }
    return num;
}

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

    for (int i = 0; i < 1 << n; i ++){
        if (check(i)){
            state.push_back(i);
            cnt[i] = counts(i);
        }
    }
    int len = state.size();
    for (int i = 0; i < len; i ++){
        for (int j = 0; j < len; j ++){
            int a = state[i], b = state[j];
            if ((a & b) == 0 && check(a | b)) {
                head[i].push_back(j);
            }
        }
    }

    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i ++) {
        for (int j = 0; j <= k; j ++) {
            for (int a = 0; a < state.size(); a ++){
                for (int b: head[a]){
                    int c = cnt[state[a]];
                    if (j >= c){
                        f[i][j][a] = (LL)f[i][j][a] + f[i-1][j - c][b];
                    }
                }
            }

        }
    }

    cout << f[n+1][k][0];
    return 0;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

唯爱
6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010, M = 101, INF = 0x3f3f3f3f;
int dp[N][M][2];

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

    memset(dp, -INF, sizeof dp);
    for (int i = 0; i <= n; i ++) dp[i][0][0] = 0;


    for (int i = 1; i <= n; i ++){
        int x;
        scanf("%d", &x);
        for (int j = 1; j <= k; j ++){
            dp[i][j][0] = max(dp[i-1][j][1] + x, dp[i-1][j][0]);
            dp[i][j][1] = max(dp[i-1][j-1][0] - x, dp[i-1][j][1]);
        }    
    }

    int res = 0;
    for (int j = 0; j <= k; j ++){
        res = max(res, dp[n][j][0]);
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

唯爱
6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 100010;
int dp[N][2];

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

    for (int i = 0; i < t; i ++){
        int n;
        scanf("%d", &n);
        memset(dp, 0, sizeof dp);
        for (int j = 1; j <= n; j ++){
            int x;
            scanf("%d", &x);
            dp[j][0] = max(dp[j-1][0], dp[j-1][1]);
            dp[j][1] = dp[j-1][0] + x;
        }
        printf("%d\n", max(dp[n][0], dp[n][1]));
    }
    return 0;
}