2025年7月25日训练日志
挖沟
#include #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> e[N];int d[N];bool vis[N];priority_queue<pair,vector<pair>,greater<pair>>q;void prim(int s){ for(int i=0;i w){ d[v] = w; q.push({d[v],v}); } } } cout<> n >> m; for(int i = 0; i > 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 #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>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,vector<pair>,greater<pair>>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>>n>>m){ for(int i=0;i<=N;i++) e[i].clear(); for(int i=1;i>v>>w>>h; e[v].push_back({w,h}); e[w].push_back({v,h}); } if(prim(1)) cout<<\"Yes\"<<endl; else cout<<\"No\"<>t; while(t--) solve(); return 0;}204. 计数质数 - 力扣（LeetCode）
线性筛模板
#define ll long long class Solution {public: int countPrimes(int n) { vectorisp(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& nums) { int n = nums.size(); vectorip(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_mapcnt; 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> findPrimePairs(int n) { vectorip(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>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; vectoris(N+1,1); //is[1] = 0; int res = r - l + 1; for(int i=2;i=l && i * i <= r){ res--; } for(int j = i*i;j<=N;j+=i){ is[j] = 0; } } } return res; }};
