网站开发 0755,留下自己的wordpress,建盏公司最新消息,实体店做网站有用吗1.【模板】单源最短路径#xff08;弱化版#xff09; 2.【模板】单源最短路径#xff08;标准版#xff09; 3.无线通讯网 4.子串简写 5.整数删除 6.拆地毯
【模板】单源最短路径#xff08;标准版#xff09;https://www.luogu.com.cn/problem/P4779 题目描述 给定一个…1.【模板】单源最短路径弱化版 2.【模板】单源最短路径标准版 3.无线通讯网 4.子串简写 5.整数删除 6.拆地毯
【模板】单源最短路径标准版https://www.luogu.com.cn/problem/P4779 题目描述 给定一个 n 个点m 条有向边的带非负权图请你计算从 s 出发到每个点的距离。 数据保证你能从 s 出发到任意点。 输入格式 第一行为三个正整数 ,,n,m,s。 第二行起 m 行每行三个非负整数 ,,ui,vi,wi表示从 ui 到 vi 有一条权值为 wi 的有向边。 输出格式 输出一行 n 个空格分隔的非负整数表示 s 到每个点的距离。 输入输出样例 输入 #1复制 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出 #1复制 0 2 4 3 说明/提示 样例解释请参考 数据随机的模板题。 1≤≤1051≤n≤105 1≤≤2×1051≤m≤2×105 1s1 1≤,≤1≤ui,vi≤n 0≤≤1090≤wi≤109, 0≤∑≤1090≤∑wi≤109。 【模板】单源最短路径标准版https://www.luogu.com.cn/problem/P3371 题目描述 如题给出一个有向图请输出从某一点出发到所有点的最短路径长度。 输入格式 第一行包含三个整数 ,,n,m,s分别表示点的个数、有向边的个数、出发点的编号。 接下来 m 行每行包含三个整数 ,,u,v,w表示一条 →u→v 的长度为 w 的边。 输出格式 输出一行 n 个整数第 i 个表示 s 到第 i 个点的最短路径若不能到达则输出 231−1231−1。 输入输出样例 输入 #1复制 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出 #1复制 0 2 4 3 说明/提示 【数据范围】 对于 20%20% 的数据1≤≤51≤n≤51≤≤151≤m≤15 对于 40%40% 的数据1≤≤1001≤n≤1001≤≤1041≤m≤104 对于 70%70% 的数据1≤≤10001≤n≤10001≤≤1051≤m≤105 对于 100%100% 的数据1≤≤1041≤n≤1041≤≤5×1051≤m≤5×1051≤,≤1≤u,v≤n≥0w≥0∑231∑w231保证数据随机。 Update 2022/07/29两个点之间可能有多条边敬请注意。 对于真正 100%100% 的数据请移步 P4779。请注意该题与本题数据范围略有不同。 样例说明 图片1到3和1到4的文字位置调换 思路dijkstra
#include bits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N2e55;struct edge{int from;int to;int w;edge(int a,int b,int c){froma;tob;wc;}
};
vectoredgee[N];
struct node{int id;int n_dis;node(int a ,int b){ida;n_disb;}bool operator (const node a)const{return n_disa.n_dis;}
}; int n,m,s,dis[N];
bool done[N];
priority_queuenodeq;void dijkstra(int s){for (int i1;in;i){dis[i]INF;done[i]false;}dis[s]0;q.push(node(s,dis[s]));while (!q.empty()){node pq.top(); q.pop();if (done[p.id]) continue;done[p.id]true;for (int i0;ie[p.id].size();i){edge ye[p.id][i];if (done[y.to]) continue;if (dis[y.to] p.n_disy.w){dis[y.to]p.n_disy.w;q.push(node(y.to,dis[y.to]));}}}
}signed main(){cinnms;for (int i0;im;i){int u,v,w;cinuvw;e[u].push_back(edge(u,v,w));}dijkstra(s);for (int i1;in;i){coutdis[i] ;}
}
无线通讯网https://www.luogu.com.cn/problem/P1991 题目描述 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络 每个边防哨所都要配备无线电收发器有一些哨所还可以增配卫星电话。 任意两个配备了一条卫星电话线路的哨所两边都有卫星电话均可以通话无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D这是受收发器的功率限制。收发器的功率越高通话距离 D 会更远但同时价格也会更贵。 收发器需要统一购买和安装所以全部哨所只能选择安装一种型号的收发器。换句话说每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D使得每一对哨所之间至少有一条通话路径直接的或者间接的。 输入格式 第一行22 个整数 S 和 PS 表示可安装的卫星电话的哨所数P 表示边防哨所的数量。 接下里 P 行每行两个整数 xy 描述一个哨所的平面坐标 (,)(x,y)以 km 为单位。 输出格式 第一行11 个实数 D表示无线电收发器的最小传输距离精确到小数点后两位。 输入输出样例 输入 #1复制 2 4 0 100 0 300 0 600 150 750 输出 #1复制 212.13 说明/提示 数据范围及约定 对于 20%20% 的数据21P2S1 对于另外 20%20% 的数据42P4S2 对于 100%100% 的数据保证1≤≤1001≤S≤100≤500SP≤5000≤,≤100000≤x,y≤10000。 思路Kruskal
#include bits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N505;int f[N],s,p;
double dis;
double a[N][2];
struct edge{int from;int to;double w;
};
edge e[N*N];
int find(int x){if (f[x]x) return x;else{f[x]find(f[x]);return f[x];}
}bool cmp(const edge a , const edge b){return a.wb.w;
}void unionn(int x,int y){f[find(x)]find(y);
}signed main(){cinsp;for (int i1;ip;i) f[i]i;for (int i1;ip;i){cina[i][0]a[i][1];}int bian0;for (int i1;ip;i){for (int ji1;jp;j){bian;e[bian].fromi;e[bian].toj;e[bian].wsqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));}}sort(e1,e1bian,cmp);int cnt0;for (int i1;ibian;i){if (find(e[i].from) ! find(e[i].to)){unionn(e[i].from,e[i].to);cnt;dismax(e[i].w,dis);}if (cntp-s) break;}printf(%.2lf,dis);
}
拆地毯https://www.luogu.com.cn/problem/P2121 题目描述 会场上有 n 个关键区域不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示其中 u 和 v 为地毯连接的两个关键区域编号w 为这条地毯的美丽度。 由于颁奖典礼已经结束铺过的地毯不得不拆除。为了贯彻勤俭节约的原则组织者被要求只能保留至多 K 条地毯且保留的地毯构成的图中任意可互相到达的两点间只能有一种方式互相到达。换言之组织者要求新图中不能有环。现在组织者求助你想请你帮忙算出这至多 K 条地毯的美丽度之和最大为多少。 输入格式 第一行包含三个正整数 n、m、K。 接下来 m 行中每行包含三个正整数 u、v、w。 输出格式 只包含一个正整数表示这 K 条地毯的美丽度之和的最大值。 输入输出样例 输入 #1复制 5 4 3 1 2 10 1 3 9 2 3 7 4 5 3 输出 #1复制 22 说明/提示 选择第 1、2、4 条地毯美丽度之和为 10 9 3 22。 若选择第 1、2、3 条地毯虽然美丽度之和可以达到 10 9 7 26但这将导致关键区域 1、2、3 构成一个环这是题目中不允许的。 1n,m,k100000 思路最大生成树
#include bits/stdc.h
using namespace std;
#define int long longconst int N 1e55;struct edge{int from;int to;int w;
};edge e[N];
int f[N],n,m,k,cnt,sum;int find(int x){if (f[x]x) return x;else{f[x]find(f[x]);return f[x];}
}void unionn(int i,int j){f[find(i)]find(j);
}bool cmp(const edge a,const edge b){return a.wb.w;
}signed main(){cinnmk;for (int i1;in;i) f[i]i;for (int i1;im;i){int u,v,w;cinuvw;e[i].fromu;e[i].tov;e[i].ww;}sort(e1,e1m,cmp);for (int i1;im;i){if (find(e[i].from)!find(e[i].to)){unionn(e[i].from,e[i].to);sume[i].w;cnt;}if (cntk) break;}coutsum;
}
子串简写https://www.dotcpp.com/oj/problem3154.html 题目描述 程序猿圈子里正在流行一种很新的简写方法对于一个字符串只保留首尾字符将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18nKubernetes 注意连字符不是字符串的一部分简写成 K8s, Lanqiao 简写成 L5o 等。 在本题中我们规定长度大于等于 K 的字符串都可以采用这种简写方法长度小于 K 的字符串不配使用这种简写。 给定一个字符串 S 和两个字符 c1 和 c2请你计算 S 有多少个以 c1 开头c2 结尾的子串可以采用这种简写 输入格式 第一行包含一个整数 K。 第二行包含一个字符串 S 和两个字符 c1 和 c2。 输出格式 一个整数代表答案。 样例输入 复制 4 abababdb a b 样例输出 复制 6 提示 符合条件的子串如下所示中括号内是该子串 [abab]abdb [ababab]db [abababdb] ab[abab]db ab[ababdb] abab[abdb] 对于 20% 的数据2 ≤ K ≤ |S | ≤ 10000。 对于 100% 的数据2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都是小写字母。 |S | 代表字符串 S 的长度。 思路数据的大小到了10的五次所以用双重循环肯定会TLE所以选择优化一下用一重循环把前面的可以形成的用计数器记录然后想后遍历如果遇到计数器加一如果遍历到c2那么就加到总数上
#include bits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fstring s;
char c1,c2;
int k;signed main(){cink;cins;cinc1c2;int cnt0,n0;for (int i0;is.size();i){if (i-k10 s[i-k1]c1) n;if (s[i]c2) cntn;}coutcnt;
}
整数删除https://www.dotcpp.com/oj/problem3155.html 题目描述 给定一个长度为 N 的整数数列A1, A2, . . . , AN。你要重复以下操作 K 次 每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列。 输入格式 第一行包含两个整数 N 和 K。 第二行包含 N 个整数A1, A2, A3, . . . , AN。 输出格式 输出 N − K 个整数中间用一个空格隔开代表 K 次操作后的序列。 样例输入 复制 5 3 1 4 2 8 7 样例输出 复制 17 7 提示 数列变化如下中括号里的数是当次操作中被选择的数 [1] 4 2 8 7 5 [2] 8 7 [7] 10 7 17 7 对于 20% 的数据1 ≤ K N ≤ 10000。 对于 100% 的数据1 ≤ K N ≤ 5 × 1050 ≤ Ai ≤ 108。 思路双向链表加上堆优化
#include bits/stdc.h
using namespace std;
#define lowbit(x) x(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3fconst int N5e55;int v[N], l[N], r[N];struct node1{int id;int w;node1(int a,int b){ida;wb;}bool operator (const node1 a)const{if (wa.w) return id a.id; else return wa.w;}
};priority_queuenode1q; //存节点的值和下标
int n,k;void sc(int x){r[l[x]] r[x], l[r[x]] l[x];v[l[x]] v[x], v[r[x]] v[x];
}signed main(){cinnk;r[0] 1, l[n 1] n;for (int i1;in;i){cin v[i], l[i] i - 1, r[i] i 1, q.push(node1(i, v[i]));}while (k--){node1 pq.top(); q.pop(); if (p.w!v[p.id]){q.push(node1(p.id,v[p.id]));k;}else{sc(p.id);}}int head r[0];while (head ! n 1) {cout v[head] ;head r[head];}
}
