当前位置：首页 > news >正文

算法日常练习

news 来源：原创 2024/9/20 5:21:45

在这里插入图片描述

对于这个题，如何处理同一个方向的问题，且对于同一组的如果间隔太大如何实现离散化

#include<bits/stdc++.h>
using namespace std;#define int long long
typedef long long ll;
map<pair<int,int>,vector<pair<ll,ll>>> mp;  // 注意里面是用vector装着 
signed main(){int n;cin >> n;int ans = 0;int num = 0;for(int i=1;i<=n;i++){int a,b,c;cin >> a >> b >> c;int d= abs(__gcd(a,b));  // 请注意这个 gcd 是两个下划线// 且要取绝对值 mp[{a/d,b/d}].push_back({a*a+b*b,c});ans += c;}for(auto u:mp){vector<pair<ll,ll>> t = u.second;sort(t.begin(),t.end());int len = t.size();for(int i=0;i<len;i++){if(t[i].second!=1) num++;else if((i+1)==len || t[i+1].second!=1) num++;}}cout << ans << " " << num;return 0;
}

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;const int N = (int)1e3 + 5;
int e[N * N], ne[N * N], h[N], idx = 0;
int energy[N * N], va[N * N];
int vis[N];
int di[N];void add(int a, int b, int ener, int value) {e[++idx] = b;ne[idx] = h[a]; h[a] = idx;energy[idx] = ener, va[idx] = value;
}
int n, m;
int maxdistance = 0xfffffff;
int start;  // 设置为全局变量int dikj() {priority_queue<pair<int, int>> q;int ma = 0;//vis[start] = 1; // 记录一下for (int i = 0; i <= n; i++) vis[i] = 0,di[i] = 0xffffff;//vis[start] = 1;q.push({ 0,start });while (q.size()) {int dis = -q.top().first, node = q.top().second;q.pop();if (vis[node]) continue;vis[node] = 1;for (int i = h[node]; i != -1; i = ne[i]) {int to = e[i];//if (vis[to]) continue;//vis[to] = 1;int newdis = energy[i] + dis; // 这是新的距离if (newdis < di[to]) {di[to] = newdis;q.push({ -newdis, to });}/* ma = max(ma, newdis);*/}}for (int i = 1; i <= n; i++) {if (di[i] == 0xffffff) continue;ma = max(ma, di[i]);}return ma;
}
int pre[N];// 记录前缀
int ju[N];
void solve(int start) {for (int i = 1; i <= n; i++) {pre[i] = i, vis[i] = 0, di[i] = 0xffffff;}priority_queue<pair<int, int>> q;q.push({ 0,start });//vis[start] = 1;while (q.size()) {int dis = -q.top().first, node = q.top().second;q.pop();//if (vis[node]) continue;vis[node] = 1;for (int i = h[node]; i != -1; i = ne[i]) {int to = e[i];//if (vis[to]) continue;//vis[to] = 1;int t = dis + energy[i];if (t < di[to]) {di[to] = t; pre[to] = node;ju[to] = ju[node] + va[i];q.push({ -t,to });//cout << "1 to: " << to << " node " << node << endl;}else if (t == di[to]) {int u = ju[node] + va[i];if (u > ju[to]) {di[to] = t; pre[to] = node;ju[to] = ju[node] + va[i];//q.push({ -t,to });//cout << "2 to: " << to << " node " << node << endl;}}}}
}void print(int s, int t) {if (s == t) {printf("%d", s);return;}print(s, pre[t]);printf("->%d", t);}
int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i <= m; i++) {int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, c, d);add(b, a, c, d);}int kaishi;for (int i = 1; i <= n; i++) {start = i;int d = dikj();//cout << d << endl;if (d < maxdistance) {kaishi = start;maxdistance = d;}}cout << kaishi << endl;solve(kaishi);//int o = kaishi;int t;cin >> t;//for (int i = 1; i <= n; i++) {//    cout << pre[i] << endl;//}di[kaishi] = ju[kaishi] =0 ;for (int i = 1; i <= t; i++) {int a;cin >> a;print(kaishi,a);cout << endl;cout << di[a] << " " << ju[a] << endl;}
}

在这里插入图片描述

对于这个题我们需要从最后一天开始计算，因为我们的并查集是不能删除边的

#include<bits/stdc++.h>
using namespace std;const int N = (int)5e4 + 5;
vector<int> ed[N];
int fa[N];
int n, m, d;
int jud[N];
int ans[N];
int find(int x) {if (x == fa[x]) return x;return fa[x] = find(fa[x]);
}void uni(int x, int y) {x = find(x), y = find(y);if (x == y) return;fa[x] = y;
}void ini() {for (int i = 1; i <= n; i++) fa[i] = i;
}
map<int,vector<pair<int, int>>> bian;
vector<int> shan;
int main() {cin >> n >> m >> d;for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;ed[a].push_back(b);ed[b].push_back(a);}ini();int c, q;for (int i = 1; i <= d; i++) {cin >> c >> q;shan.push_back(c);jud[c] = 1;int x, y;for (int j = 1; j <= q; j++) {cin >> x >> y;bian[i].push_back({ x,y });//cout << "789" << endl;bian[1].push_back({ 0,0 });}}//cout << "len " << bian[0].size() << endl;for (int i = 1; i <= n; i++) {if (jud[i]) continue;for (auto u : ed[i]) {if (jud[u]) continue;uni(u, i);  // 合并}}//cout << "shan " << shan[0] << endl;for (int i = d; i >= 1; i--) {int now = shan[i-1];//cout << "123" << endl;vector<pair<int, int>> r = bian[i];for (auto u : r) {//cout << "u.first " << u.first << " u.second " << u.second << endl;if (find(u.first) != find(u.second)) ans[i]++;//cout << ans[i] << endl;}jud[now] = 0;for (int u : ed[now]) {if (jud[u]) continue;uni(u, now);}}for (int i = 1; i <= d; i++) cout << ans[i] << endl;return 0;
}