头像

codecloud

同济大学软件学院




离线:8小时前


最近来访(78)
用户头像
MercedesKK
用户头像
长风_52
用户头像
lsz_
用户头像
R虎虎生威R
用户头像
Alkaid3529
用户头像
呐呐呐呐
用户头像
1954266
用户头像
skyoung
用户头像
yxc
用户头像
RexyZhang
用户头像
Wen111
用户头像
百森
用户头像
Immelon
用户头像
托马斯杨儿
用户头像
是这样的捏
用户头像
letsgo
用户头像
arch_hui
用户头像
月下涼風
用户头像
想ac的呼哧呼哧
用户头像
逆暖


class Solution {
public:
    vector<int> p;

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

    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        vector<vector<int>> g(n);

        for (auto& e: edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }

        vector<int> q(n);
        p.resize(n);
        for (int i = 0; i < n; i ++ ) p[i] = q[i] = i;
        sort(q.begin(), q.end(), [&](int a, int b) {
            return vals[a] < vals[b];
        });

        int res = 0;
        for (int i = 0; i < n; i ++ ) {
            int j = i + 1;
            while (j < n && vals[q[i]] == vals[q[j]]) j ++ ;

            for (int k = i; k < j; k ++ ) {
                int x = q[k];
                for (int y: g[x]) {
                    if (vals[x] >= vals[y])
                        p[find(x)] = find(y);
                }
            }

            unordered_map<int, int> hash;
            for (int k = i; k < j; k ++ )
                hash[find(q[k])] ++ ;
            for (auto& [k, v]: hash)
                res += v * (v + 1) / 2;
            i = j - 1;
        }

        return res;
    }
};



活动打卡代码 AcWing 4620. 旅行

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+10;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
int p[N];
LL ans;
LL f[N];
int n;
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int father){
    LL max1=0,max2=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==father)continue;
        dfs(j,u);
        if(f[j]-w[i]>=max1){

            max2=max1;
            max1=f[j]-w[i];
        }
        else if(f[j]-w[i]>max2){
            max2=f[j]-w[i];
        }
    }
    ans=max(ans,max1+max2+p[u]);
    f[u]=max1+p[u];
}
int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    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);
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}



class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>f(n),g(n);
        for(int i=0;i<n;i++){
            f[i]=1;
            if(i&&nums[i]<=nums[i-1])f[i]=f[i-1]+1;
        }
        for(int i=n-1;i>=0;i--){
            g[i]=1;
            if(i!=n-1&&nums[i]<=nums[i+1])g[i]=g[i+1]+1;
        }
        vector<int>res;
        for(int i=k;i<n-k;i++){
            if(f[i-1]>=k&&g[i+1]>=k)res.push_back(i);
        }
        return res;
    }
};



class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int val=0,res=0;
        for(auto i:nums)val=max(val,i);
        for(int i=0,cnt=0;i<nums.size();i++){
            if(nums[i]==val){
                cnt++;
                res=max(res,cnt);
            }
            else{
                cnt=0;
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 2418. 按身高排序

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        map<int,string>hash;
        for(int i=0;i<names.size();i++)hash[heights[i]]=names[i];
        vector<string>res;
        for(auto& h:hash)res.push_back(h.second);
        reverse(res.begin(),res.end());
        return res;
    }
};


新鲜事 原文

AcWing同济大学算法交流群开张啦!欢迎大家来玩~ QQ群号:608852866
图片


新鲜事 原文

PAT!未完待续,来日再见...


活动打卡代码 AcWing 1558. 加油站

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1020, INF = 0x3f3f3f3f;

int n, m, k, D;
int g[N][N];
int dist[N];
bool st[N];

int get(string s)
{
    if (s[0] == 'G') return n + stoi(s.substr(1));
    return stoi(s);
}

void dijkstra(int start, int &mind, int &sumd)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[start] = 0;
    for (int i = 0; i < n + m; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n + m; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n + m; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    for (int i = 1; i <= n; i ++ )
        if (dist[i] > D)
        {
            mind = -INF;
            return;
        }

    mind = INF, sumd = 0;
    for (int i = 1; i <= n; i ++ )
    {
        mind = min(mind, dist[i]);
        sumd += dist[i];
    }
}

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

    memset(g, 0x3f, sizeof g);
    while (k -- )
    {
        string a, b;
        int z;
        cin >> a >> b >> z;
        int x = get(a), y = get(b);

        g[x][y] = g[y][x] = min(g[x][y], z);
    }

    int res = -1, mind = 0, sumd = INF;
    for (int i = n + 1; i <= n + m; i ++ )
    {
        int d1, d2;
        dijkstra(i, d1, d2);

        if (d1 > mind) res = i, mind = d1, sumd = d2;
        else if (d1 == mind && d2 < sumd) res = i, sumd = d2;
    }

    if (res == -1) puts("No Solution");
    else printf("G%d\n%.1lf %.1lf\n", res - n, (double)mind, (double)sumd / n + 1e-8);

    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int C, n, S, m;
int c[N];
int g[N][N];
int dist[N];
bool st[N];

vector<int> path, ans;
int send = INF, bring = INF;

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 0; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;
        for (int j = 0; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

void dfs(int u, int s, int mins)
{
    if (u)
    {
        s -= (C + 1) / 2 - c[u];
        mins = min(mins, s);
    }

    if (u == S)
    {
        int sd = abs(min(mins, 0));
        int bg = s + sd;

        if (sd < send) ans = path, send = sd, bring = bg;
        else if (sd == send && bg < bring) ans = path, bring = bg;

        return;
    }

    for (int i = 1; i <= n; i ++ )
        if (dist[u] == g[u][i] + dist[i])
        {
            path.push_back(i);
            dfs(i, s, mins);
            path.pop_back();
        }
}

int main()
{
    cin >> C >> n >> S >> m;
    for (int i = 1; i <= n; i ++ ) cin >> c[i];

    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i ++ )
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = g[y][x] = min(g[x][y], z);
    }

    dijkstra();

    path.push_back(0);   
    dfs(0, 0, 0);

    cout << send << ' ' << 0;
    for (int i = 1; i < ans.size(); i ++ )
        cout << "->" << ans[i];
    cout << " " << bring << endl;

    return 0;
}



活动打卡代码 AcWing 1643. 旅行商问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], vers[310];
bool st[N];

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = c;
    }

    int k;
    cin >> k;

    int min_dist = INF, min_id;
    for (int T = 1; T <= k; T ++ )
    {
        int cnt;
        cin >> cnt;
        for (int i = 0; i < cnt; i ++ ) cin >> vers[i];

        int sum = 0;
        bool success = true;
        memset(st, 0, sizeof st);
        for (int i = 0; i + 1 < cnt; i ++ )
        {
            int a = vers[i], b = vers[i + 1];
            if (d[a][b] == INF)
            {
                sum = -1;
                success = false;
                break;
            }
            else sum += d[a][b];
            st[a] = true;
        }

        for (int i = 1; i <= n; i ++ )
            if (!st[i])
            {
                success = false;
                break;
            }

        if (vers[0] != vers[cnt - 1]) success = false;

        if (sum == -1) printf("Path %d: NA (Not a TS cycle)\n", T);
        else
        {
            if (!success) printf("Path %d: %d (Not a TS cycle)\n", T, sum);
            else
            {
                if (cnt == n + 1) printf("Path %d: %d (TS simple cycle)\n", T, sum);
                else printf("Path %d: %d (TS cycle)\n", T, sum);

                if (min_dist > sum)
                {
                    min_dist = sum;
                    min_id = T;
                }
            }
        }
    }

    printf("Shortest Dist(%d) = %d\n", min_id, min_dist);

    return 0;
}