2025年7月25日训练日志

挖沟

最小生成树模板

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define FAST ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;
using namespace std;

int n, m;
vector<pair<int, int>> e[N];
int d[N];
bool vis[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

void prim(int s){
    for(int i=0;i<=n;i++){
        d[i] = inf;
        vis[i] = false;
    }
    d[s] = 0;
    q.push({0,s});
    int ans = 0;
    while(!q.empty()){
        auto [dist,u] = q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        ans += dist;
        for(auto [v,w] : e[u]){
            if(d[v] > w){
                d[v] = w;
                q.push({d[v],v});
            }
        }
    }
    cout<<ans;
}

void solve() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        e[a].push_back({b, w});
        e[b].push_back({a, w});
    }
    prim(1);
}

signed main() {
    FAST
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

 道路建设

最小生成树模板，判断费用是否不大于c以及是否能构成最小生成树 

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define FAST ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int MOD = 1e9+7;
const int mod = 998244353;
using namespace std;

int c,n,m;
vector<pair<int,int>>e[N];
int d[N],vis[N];

bool prim(int s){
    int ans = 0,cnt = 0;
    for(int i=0;i<=n;i++){
        d[i] = inf;
        vis[i] = 0;
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    q.push({0,s});
    d[s] = 0;
    while(q.size()){
        auto [di,u] = q.top();q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        ans += di;
        cnt++;
        for(auto [v ,w] : e[u]){
            if(d[v] > w){
                d[v] = w;
                q.push({d[v],v});
            }
        }
    }
    return ans<=c&&cnt==m;
}

void solve(){
    while(cin>>c>>n>>m){
        for(int i=0;i<=N;i++)
            e[i].clear();
        for(int i=1;i<=n;i++){
            int v,w,h;
            cin>>v>>w>>h;
            e[v].push_back({w,h});
            e[w].push_back({v,h});
        }
        if(prim(1)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
}

signed main() {
    FAST
    int t = 1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

 204. 计数质数 - 力扣（LeetCode）

线性筛模板 

#define ll long long 
class Solution {
public:
    int countPrimes(int n) {
        vector<int>isp(n,1);
        int ans = 0;
        for(int i=2;i<n;i++){
            if(isp[i]){
                ans ++;
                if((ll) i * i < n){
                    for(int j = i * i;j<n;j+=i){
                        isp[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};

 3591. 检查元素频次是否为质数 - 力扣（LeetCode）

欧拉筛预处理，然后用unordered_map存次数来判断

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        int n = nums.size();
        vector<int>ip(n+1,1);
        ip[1] = 0;
        for(int i=2;i<n+1;i++){
            if(ip[i]){
                if((long long)i * i < n+1){
                    for(int j = i*i;j<n+1;j+=i){
                        ip[j] = 0;
                    }
                }
            }
        }
        unordered_map<int,int>cnt;
        for(int x : nums){
            cnt[x] ++;
        }
        for(auto& [_,cn] : cnt){
            if(ip[cn]){
                return true;
            }
        }
        return false;
    }
};

 2761. 和等于目标值的质数对 - 力扣（LeetCode）

 线性筛预处理然后从2开始枚举到n/2就可以

class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        vector<int>ip(n+1,1);
        ip[1] = 0;
        for(int i=2;i<n+1;i++){
            if(ip[i]){
                if((long long)i * i < n+1){
                    for(int j = i*i;j<n+1;j+=i){
                        ip[j] = 0;
                    }
                }
            }
        }
        vector<vector<int>>ans;
        for(int i=2;i<=n/2;i++){
            if(ip[i] && ip[n-i]){
                ans.push_back({i,n-i});
            }
        }
        return ans;
    }
};

 3233. 统计不是特殊数字的数字数量 - 力扣（LeetCode）

  很容易发现如果某个数是质数的平方数的话，那他就是特殊数，因此我们判断质数的时候就可以顺带减掉质数的平方数。

由上述可知我们判断质数的范围N只需要到sqrt(r)！！！

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int N = sqrt(r)+1;
        vector<int>is(N+1,1);
        //is[1] = 0;
        int res = r - l + 1;
        for(int i=2;i<=N;i++){
            if(is[i]){
                if(i * i >=l && i * i <= r){
                    res--;
                }
                for(int j = i*i;j<=N;j+=i){
                    is[j] = 0;
                }
            }
        }
        return res;
    }
};