头像

nickxiao

szpt




离线:7分钟前


最近来访(41)
用户头像
AK自动机
用户头像
s.y.
用户头像
大半球
用户头像
Cold_heartless
用户头像
花季护航
用户头像
一万小时定律
用户头像
凉蝉
用户头像
我呼吸了
用户头像
宇宇不爱喝奶茶
用户头像
卖当劳的小男孩
用户头像
TwinkleM
用户头像
flexible
用户头像
阿华
用户头像
-lazy
用户头像
lya
用户头像
huang
用户头像
jaylenwanghitsz
用户头像
三太子敖丙
用户头像
新生代奥特曼
用户头像
codehorse

活动打卡代码 AcWing 340. 通信线路

nickxiao
4小时前

二分 目标求出一个 l ,使得从 1n 的路径中,边权比 val[l] 大的边小于等于 k 个。
dist[i] 定义的是从1到i的路径最少的边权比 val[l] 大的个数。
随着 val[l] 增加,将有 dist[i] 呈现递减趋势,所以我们如果求的 (dist[n] <= k) 结果为 0 说明 dist[n] > k 我们为了使它变小,应该总体值变大,也就是 l = mid + 1,否则就是总体值变小r = mid.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <deque>
#include <algorithm>
#define rep(a,b,c) for (int a = b ; a < c ; ++a)
using namespace std;
const int maxn = 2e4 + 10;
int tot,h[maxn],nxt[maxn],w[maxn],to[maxn],dist[maxn],last[maxn],n,m,k;
bool vis[maxn];
typedef pair<int,int> pii;
deque<int>q;
inline bool check(int val){
    memset(dist,0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    dist[1] = 0;
    q.push_back(1);
    while (q.size()){
        int t = q.front();
        q.pop_front();
        if (vis[t]) continue ;
        vis[t] = 1;
        for (int v,a = h[t],wei ; a ; a = nxt[a]){
            v = to[a],wei = w[a] > val;
            dist[v] = min(dist[v],dist[t] + wei);
            if (!vis[v])
                if (wei)
                    q.push_back(v);
                else
                    q.push_front(v);
        }
    }
    return dist[n] <= k;
}
inline void add(int u,int v,int val){
    to[++tot] = v,nxt[tot] = h[u],w[tot] = val,h[u] = tot;
}
vector<int>val;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    int a,b,c;
    val.push_back(0);
    rep(i,1,m + 1){
        cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
        val.push_back(c);
    }
    val.push_back(1e6 + 10);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    int mid,l = 0, r = int(val.size()) - 1;
    while (l < r){
        mid = l + r >> 1;
        if (check(val[mid])) r = mid ;
        else l = mid + 1;
    }
    cout << (l + 1 == val.size() ? -1 : val[l]);
    return 0;
}


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

nickxiao
6小时前
#include <iostream>
#include <queue>
#include <cstring>
#define rep(a,b,c) for (int a = b ; a < c ; ++a)
using namespace std;
const int maxn = 2e5 + 10;
int tot,h[maxn >> 2],nxt[maxn],w[maxn],to[maxn],dist[7][maxn >> 2];
int p[10],res = 0x3f3f3f3f;
bool vis[maxn >> 2];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>>q;
inline void add(int u,int v,int val){
    to[++tot] = v,nxt[tot] = h[u],w[tot] = val,h[u] = tot;
}
inline void dfs(int last,int k,int sum){
    if (k == 5){
        res = min(res,sum);
        return ;
    }
    rep(j,2,7)
        if (!vis[j])
            vis[j] = 1,dfs(j,k + 1,sum + dist[last][p[j]]),vis[j] = 0;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    p[1] = 1;
    rep(i,2,7)
        cin >> p[i];
    int st,a,b,c;
    rep(i,1,m + 1){
        cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }
    memset(dist,0x3f,sizeof dist);
    rep(i,1,7){
        st = p[i];
        dist[i][p[i]] = 0;
        q.push({dist[i][p[i]],p[i]});
        while (q.size()){
            auto t = q.top();
            q.pop();
            if (vis[t.second]) continue ;
            vis[t.second] = 1;
            for (int v,a = h[t.second] ; a ; a = nxt[a]){
                v = to[a];
                dist[i][v] = min(dist[i][v],dist[i][t.second] + w[a]);
                if (!vis[v]) q.push({dist[i][v],v});
            }
        }
        memset(vis,0,sizeof vis);
    }
    rep(i,2,7)
        vis[i] = 1,dfs(i,1,dist[1][p[i]]),vis[i] = 0;
    cout << res ;
    return 0;
}


活动打卡代码 AcWing 903. 昂贵的聘礼

nickxiao
6小时前

枚举合法区间

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 10;
int tot,cl[maxn],h[maxn],nxt[maxn],to[maxn],w[maxn],dist[105];
bool vis[maxn];
inline void add(int u,int v,int ww){
    to[++tot] = v,w[tot] = ww,nxt[tot] = h[u],h[u] = tot;
}
typedef pair<int,int> pii ;
int main(){
    int n,m,st;
    cin >> m >> n;
    st = n + 1;
    for (int i = 1,a,b,t ; i <= n ; ++i){
        cin >> dist[i] >> cl[i] >> t;
        while (t--) cin >> a >> b,add(a,i,b);
        add(st,i,dist[i]);
    }
    vector<int>v;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({dist[st],st});
    int res = dist[1];
    for (int l = cl[1] - m,r ; l <= cl[1] ; ++l){
        r = l + m;
        memset(dist,0x3f,sizeof dist);
        memset(vis,0,sizeof vis);
        dist[st] = 0;
        q.push({dist[st],st});
        while (q.size()){
            auto t = q.top();
            q.pop();
            if (vis[t.second]) continue ;
            vis[t.second] = 1;
            for (int a = h[t.second],v ; a ; a = nxt[a]){
                v = to[a];
                if (cl[v] < l || cl[v] > r || vis[v]) continue ;
                dist[v] = min(dist[v],dist[t.second] + w[a]);
                q.push({dist[v],v});
            }
        }
        res = min(res,dist[1]);
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 920. 最优乘车

nickxiao
19小时前

注意 :
1. 只有单向边;
2. 答案是最少交换次数,用我这种方法需要 - 1 ;
3. 这里求最少交换次数的话,不用vis,因为当 原方案 >= 新方案 的时候就可能有一种截然不同的路径,注意有 ‘=’,走的上一步和下一步可能相同,但是上上一步或者之前的某一步不一定是一样的 ;

#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iomanip>
#define rep(a,b,c) for (int a = b; a < c ; ++a)
using namespace std;
const int maxn = 505,maxm = 5e4 + 10;
int h[maxn],to[maxm],nxt[maxm],w[maxm],from[maxn],tot,n,m;
int dist[maxn],v[maxn];
char c;bool f;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
inline void add(int u,int v,int val){
    to[++tot] = v,nxt[tot] = h[u],h[u] = tot,w[tot] = val ;
}
inline bool R(int &a){
    c = getchar();a = f = 0;
    while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar();}
    while (c >= '0' && c <= '9') { a = ( a << 3) + ( a << 1 ) + (c & 15) ;c = getchar();}
    if (f) a = -a;
    return c != '\n' && c != EOF;
}
int main(){
    int n,m,l;
    R(m),R(n);
    rep(i,1,m + 1){
        l = 0;
        while (R(v[++l]));
        rep(j,1,l)
            add(v[j],v[j + 1],i) ;
    }
    memset(dist,0x3f,sizeof dist);
    priority_queue<piii,vector<piii>,greater<piii>>q;
    dist[1] = 0;
    q.push({dist[1],{1,0}});
    while (q.size()){
        auto t = q.top();
        q.pop();
        for (int v,a = h[t.second.first],val; a ; a = nxt[a]){
            v = to[a];
            val = dist[t.second.first] + (from[t.second.first] != w[a]);
            if (dist[v] >= val)
                dist[v] = val,from[v] = w[a],q.push({dist[v],{v,from[v]}});
        }
    }
    if (dist[n] == 0x3f3f3f3f)
        cout << "NO" << '\n';
    else 
        cout << dist[n] - 1;
    return 0 ;
}


活动打卡代码 AcWing 1126. 最小花费

nickxiao
20小时前
#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <cstring>
#include <iomanip>
#define rep(a,b,c) for (int a = b; a < c ; ++a)
using namespace std;
const int maxn = 2050,maxm = 2e5 + 10;
int h[maxn],to[maxm],nxt[maxm],tot,n,m,vis[maxn];
double w[maxm];
typedef pair<double,int>pdi;
double dist[maxn];
inline void add(int u,int v,double val){
    to[++tot] = v,nxt[tot] = h[u],h[u] = tot,w[tot] = val * 1.0;
}
int main(){
    int n,m,st,ed;
    ios::sync_with_stdio(false);
    cin >> n >> m;
    int a,b;
    double c;
    rep(i,1,m + 1){
        cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }
    cin >> st >> ed;
    for (int i = 1 ; i <= n ; ++i)
        dist[i] = 0.0;
    priority_queue<pdi>q ;
    dist[st] = 1.0;
    q.push({dist[st],st});
    while (q.size()){
        auto t = q.top();
        q.pop();
        if (vis[t.second]) continue;
        vis[t.second] = 1;
        for (int v,a = h[t.second] ; a ; a = nxt[a]){
            v = to[a];
            dist[v] = max(dist[v],dist[t.second] * (1.0 - w[a] / 100.0));
            if (!vis[v])
                q.push({dist[v],v});
        }
    }
    double res = 100.0 / dist[ed] ;
    cout << fixed << setprecision(8) << res << '\n';
    return 0 ;
}



nickxiao
21小时前


活动打卡代码 AcWing 1127. 香甜的黄油

nickxiao
21小时前

floyd 过 8 / 12

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1010;
int dist[maxn][maxn],a[maxn];
bool vis[maxn];
vector<int>v,mi;
int main(){
    ios::sync_with_stdio(false);
    int n,m,t,p;
    cin >> n >> p >> m;
    for (int i = 1; i <= n ; ++i){
        cin >> t;
        if (++a[t] == 1)
            v.push_back(t);
    }
    memset(dist,0x3f,sizeof dist);
    int u,to,d;
    for (int i = 1; i <= m ; ++i){
        cin >> u >> to >> d,dist[u][to] = min(dist[u][to],d),dist[to][u] = min(dist[to][u],d);
        if (!vis[u]) mi.push_back(u);
        if (!vis[to]) mi.push_back(to);
        vis[u] = vis[to] = 1;
    }
    for (auto mid : mi)
        for (auto to : mi)
            if (to == mid) continue ;
            else for (auto u : mi)
                if (u == mid || to == u) continue ;
                else dist[u][to] = min(dist[u][to],dist[u][mid] + dist[mid][to]);
    int res = 0x3f3f3f3f;
    for (auto u : mi){
        int sum = 0;
        for (auto to : v)
            if (u == to) continue ;
            else if (dist[u][to] == 0x3f3f3f3f || sum >= res ) {
                sum = 0x7f7f7f7f;
                break;
            }else  
                sum += dist[u][to] * a[to];
        res = min(res,sum);
    }  
    cout << res ;
    return 0;
}

dijk ac

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxm = 805,maxn = 3000;
int h[maxm],to[maxn],nxt[maxn],w[maxn],dist[maxm][maxm],a[maxm],tot;
bool vis[maxn];
typedef pair<int,int> pii;
vector<int>v,g;
priority_queue<pii,vector<pii>,greater<pii>>q;
inline void add(int u,int v,int val){
    to[++tot] = v,nxt[tot] = h[u],w[tot] = val,h[u] = tot;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m,t,p;
    cin >> n >> p >> m;
    memset(dist,0x3f,sizeof dist);
    for (int i = 1; i <= n ; ++i){
        cin >> t;
        if (++a[t] == 1)
            v.push_back(t);
    }
    for (int i = 1,u,To,d; i <= m ; ++i){
        cin >> u >> To >> d,add(u,To,d),add(To,u,d);
        if (!vis[u]) g.push_back(u);
        if (!vis[To]) g.push_back(To);
        vis[u] = vis[To] = 1;
    }
    int sum,res = 0x3f3f3f3f;
    pii top;
    for (auto u : g){
        sum = 0;
        memset(vis,0,sizeof vis);
        while (q.size()) q.pop();
        dist[u][u] = 0;
        q.push({dist[u][u],u});
        while (q.size()){
            top = q.top();
            q.pop();
            if (vis[top.second])
                continue ;
            vis[top.second] = 1;
            sum += dist[u][top.second] * a[top.second];
            if (sum >= res)
                break;
            for (int b = h[top.second],v ; b ; b = nxt[b]){
                v = to[b];
                dist[u][v] = min(dist[u][v],dist[u][top.second] + w[b]);
                if (!vis[v])
                    q.push({dist[u][v],v});
            }
        }
        for (auto t : v)
            if (!vis[t]){
                sum = 0x7f7f7f7f;
                break;
            }
        res = min(sum,res);
    }
    cout << res ;
    return 0;
}


活动打卡代码 AcWing 1128. 信使

nickxiao
23小时前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2e5 + 10;
int tot,h[maxn],to[maxn],nxt[maxn],w[maxn],dist[maxn];
inline void add(int u,int v,int val){
    w[++tot] = val,to[tot] = v,nxt[tot] = h[u],h[u] = tot; 
}
bool vis[maxn];
int main(){
    int n,m,st,ed;
    cin >> n >> m ;
    int u,v,val;
    for (int i = 1 ; i <= m ; ++i)
        cin >> u >> v >> val,add(u,v,val),add(v,u,val);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> >q;
    memset(dist,0x3f,sizeof dist);
    st = 1;
    dist[st] = 0;
    q.push({dist[st],st});
    while (q.size()){
        auto t = q.top();
        q.pop();
        if (vis[t.second])
            continue ;
        vis[t.second] = 1;
        for (int a = h[t.second] ; a ; a = nxt[a]){
            int v = to[a];
            dist[v] = min(dist[v],dist[t.second] + w[a]);
            if (!vis[v])
                q.push({dist[v],v});
        }
    }
    int res = 0;
    for (int i = 1 ; i <= n ; ++i)
        res = max(res,dist[i]);
    cout << (res == 0x3f3f3f3f ? -1 : res);
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

nickxiao
23小时前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2e5 + 10;
int tot,h[maxn],to[maxn],nxt[maxn],w[maxn],dist[maxn];
inline void add(int u,int v,int val){
    w[++tot] = val,to[tot] = v,nxt[tot] = h[u],h[u] = tot; 
}
bool vis[maxn];
int main(){
    int n,m,st,ed;
    cin >> n >> m >> st >> ed;
    int u,v,val;
    for (int i = 1 ; i <= m ; ++i)
        cin >> u >> v >> val,add(u,v,val),add(v,u,val);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> >q;
    memset(dist,0x3f,sizeof dist);
    dist[st] = 0;
    q.push({dist[st],st});
    while (q.size()){
        auto t = q.top();
        q.pop();
        if (vis[t.second])
            continue ;
        vis[t.second] = 1;
        for (int a = h[t.second] ; a ; a = nxt[a]){
            int v = to[a];
            dist[v] = min(dist[v],dist[t.second] + w[a]);
            if (!vis[v])
                q.push({dist[v],v});
        }
    }
    cout << dist[ed];
    return 0;
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
int tar;
int v[maxn],p[maxn];
inline void init(){
    for (int i = 2 ; i < maxn ; ++i){
        if (!v[i])
            p[++p[0]] = i;
        for (int j = 1 ; j <= p[0] && p[j] * i < maxn ; ++j){
            v[p[j] * i] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}
inline void solve(){
    int res = 1;
    while (res <= p[0])
        if (!v[tar - p[res]])
            break;
        else 
            ++res;
    if (res != p[0])
        cout << tar << " = " << p[res] << " + " << tar - p[res] << '\n'; 
    else 
        cout << "Goldbach's conjecture is wrong.\n";
}
int main(){
    init();
    while (cin >> tar,tar) solve();
    return 0;
}