平面设计欣赏网站推荐,网站推广是做什,为什么不建议学网络工程,机房网络组建方案目录
1、网络分析#xff08;第十一届蓝桥杯省赛第一场C A组/B组#xff09;
2、奶酪#xff08;NOIP2017提高组#xff09;
3、合并集合#xff08;模板#xff09;
4、连通块中点的数量#xff08;模板#xff09;
5、格子游戏#xff08;《信息学奥赛一本通》…目录
1、网络分析第十一届蓝桥杯省赛第一场C A组/B组
2、奶酪NOIP2017提高组
3、合并集合模板
4、连通块中点的数量模板
5、格子游戏《信息学奥赛一本通》 1、网络分析第十一届蓝桥杯省赛第一场C A组/B组
小明正在做一个网络实验。
他设置了 n 台电脑称为节点用于收发和存储数据。
初始时所有节点都是独立的不存在任何连接。
小明可以通过网线将两个节点连接起来连接后两个节点就可以互相通信了。
两个节点如果存在网线连接称为相邻。
小明有时会测试当时的网络他会在某个节点发送一条信息信息会发送到每个相邻的节点之后这些节点又会转发到自己相邻的节点直到所有直接或间接相邻的节点都收到了信息。
所有发送和接收的节点都会将信息存储下来。
一条信息只存储一次。
给出小明连接和测试的过程请计算出每个节点存储信息的大小。
输入格式
输入的第一行包含两个整数 n,m分别表示节点数量和操作数量。
节点从 1 至 n 编号。
接下来 m 行每行三个整数表示一个操作。
如果操作为 1 a b表示将节点 a 和节点 b 通过网线连接起来。当 a b 时表示连接了一个自环对网络没有实质影响。如果操作为 2 p t表示在节点 p 上发送一条大小为 t 的信息。
输出格式
输出一行包含 n 个整数相邻整数之间用一个空格分割依次表示进行完上述操作后节点 1 至节点 n 上存储信息的大小。
数据范围
1≤n≤10000 1≤m≤1e5 1≤t≤100
输入样例1
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1输出样例1
13 13 5 3
思路
连接的时候创建一个新的根节点作为祖先通过创建新节点可以实现在之后的dfs中不会将之前的信息加到后连接的计算机上
依次执行输入的指令传达的信息都加到根节点上
dfs把发送的信息全部累加到根节点上
遍历输出根节点的信息如果对于节点ip[i]i则说明这是个根节点不然说明这个根节点已经其点的子节点了
代码
#includebits/stdc.husing namespace std;const int N2e410,MN1;int p[N];int h[M],e[M],ne[M],idx;int add(int a,int b)
{e[idx]b;//值存到e里idx是e的编号 ne[idx]h[a];//d的编号的下一个指向h【a】指向的编号 h[a]idx;//h【a】指向b的编号
}int f[N];//存储信息 int n,m;int find(int x)
{if(x!p[x])p[x]find(p[x]);return p[x];
}void merge(int a,int b,int root)
{afind(a);bfind(b);if(a!b){p[a]p[b]root;add(root,a);add(root,b);root;}
}void dfs(int son,int father)
{f[son]f[father];for(int ih[son];i!-1;ine[i]){int je[i];dfs(j,son);}
}int main()
{memset(h,-1,sizeof h);cinnm;for(int i1;in*2;i){p[i]i;}int rootn1; while(m--){int t,a,b;cint;cinab;//coutyes;//coutmendl;if(t1){merge(a,b,root);}else{afind(a);f[a]b;}//coutmendl;}//coutyes1;for(int in1;iroot;i)if(p[i]i)dfs(i,0);//把每个根节点的值传递到每个计算机上for(int i1;in;i)coutf[i] ;return 0;
}
/*4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 113 13 5 3*/ 2、奶酪NOIP2017提高组
现有一块大奶酪它的高度为 h它的长度和宽度我们可以认为是无限大的奶酪中间有许多半径相同的球形空洞。
我们可以在这块奶酪中建立空间坐标系在坐标系中奶酪的下表面为 z0奶酪的上表面为 zh。
现在奶酪的下表面有一只小老鼠 Jerry它知道奶酪中所有空洞的球心所在的坐标。
如果两个空洞相切或是相交则 Jerry 可以从其中一个空洞跑到另一个空洞特别地如果一个空洞与下表面相切或是相交Jerry 则可以从奶酪下表面跑进空洞如果一个空洞与上表面相切或是相交Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道在不破坏奶酪的情况下能否利用已有的空洞跑到奶酪的上表面去?
空间内两点 P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下 输入格式
每个输入文件包含多组数据。
输入文件的第一行包含一个正整数 T代表该输入文件中所含的数据组数。
接下来是 T组数据每组数据的格式如下
第一行包含三个正整数 nh和 r两个数之间以一个空格分开分别代表奶酪中空洞的数量奶酪的高度和空洞的半径。
接下来的 n 行每行包含三个整数 x、y、z两个数之间以一个空格分开表示空洞球心坐标为 (x,y,z)。
输出格式
输出文件包含 T 行分别对应 T 组数据的答案如果在第 i 组数据中Jerry 能从下表面跑到上表面则输出 Yes如果不能则输出 No。
数据范围
1≤n≤1000 1≤h,r≤1e9 T≤20 坐标的绝对值不超过1e9
输入样例
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4输出样例
Yes
No
Yes
思路
多源dfs推荐
或者并查集
代码
多源bfs
#include bits/stdc.h
using namespace std;
int t, n, h, r, f[1010];
double x[1010], y[1010], z[1010];inline double dist(double X1, double X2, double Y1, double Y2, double Z1, double Z2) {return sqrt((X1 - X2) * (X1 - X2) (Y1 - Y2) * (Y1 - Y2) (Z1 - Z2) * (Z1 - Z2));
}int main() {scanf(%d, t);while (t--) {scanf(%d%d%d, n, h, r);for (int i 1; i n; i) scanf(%lf%lf%lf, x[i], y[i], z[i]), f[i] 0;queueint q; bool ok 0;for (int i 1; i n; i) if (z[i] r) q.push(i), f[i] 1;while (q.size()) {int p q.front(); q.pop();if (ok) break;if (z[p] r h) {ok 1; puts(Yes); break;}for (int i 1; i n; i) {if (f[i]) continue;if (dist(x[p], x[i], y[p], y[i], z[p], z[i]) 2 * r) {q.push(i), f[i] 1;if (z[i] r h) {ok 1; puts(Yes); break;}}}}if (!ok) puts(No);}return 0;
}并查集
#include bits/stdc.h
using namespace std;
int t, n, h, r;
int t1, s1[1010], t2, s2[1010], fa[1010];
pairlong long, pairlong long, long long a[1010];int get(int x) {if (fa[x] ! x) fa[x] get(fa[x]);return fa[x];
}
double dist(double X1, double X2, double Y1, double Y2, double Z1, double Z2) {return sqrt(pow(X1 - X2, 2) pow(Y1 - Y2, 2) pow(Z1 - Z2, 2));
}int main() {scanf(%d, t);while (t--) {scanf(%d%d%d, n, h, r); t1 0, t2 0;for (int i 1; i n; i) fa[i] i;for (int i 1; i n; i) {scanf(%lld%lld%lld, a[i].second.first, a[i].second.second, a[i].first);if (a[i].first r h) s1[t1] i;if (a[i].first - r 0) s2[t2] i;}if (t1 0 || t2 0) {puts(No); continue;}for (int i 1; i n; i)for (int j i 1; j n; j) {if (get(i) get(j)) continue;double d dist(a[i].second.first, a[j].second.first, a[i].second.second, a[j].second.second, a[i].first, a[j].first);if (d 2 * r) fa[get(i)] get(j);}int b 0;for (int i 1; i t1; i) {if (b) break;for (int j 1; j t2; j)if (get(s1[i]) get(s2[j])) {puts(Yes); b 1; break;}}if (!b) puts(No);}return 0;
}
3、合并集合模板
一共有 n 个数编号是 1∼n最开始每个数各自在一个集合中。
现在要进行 m 个操作操作共有两种
M a b将编号为 a和 b的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作Q a b询问编号为 a 和 b 的两个数是否在同一个集合中
输入格式
第一行输入整数 n 和 m。
接下来 m 行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b都要输出一个结果如果 a 和 b 在同一集合内则输出 Yes否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1e5
输入样例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例
Yes
No
Yes
思路
写好find函数和merge函数
代码
#includebits/stdc.husing namespace std;const int N1e55;int n,m;int p[N];int find(int x)
{if(x!p[x])p[x]find(p[x]);return p[x];
}void merge(int a,int b)
{p[find(a)]find(b);//a的祖先添加到b的祖先下面
}int main()
{cinnm;for(int i1;in;i)p[i]i;while(m--){char op;int a,b;cinop;cinab;if(opM){merge(a,b);}else{if(find(a)find(b))coutYesendl;else coutNoendl; }}//Yes Noreturn 0;
}
4、连通块中点的数量模板
给定一个包含 n 个点编号为 1∼n的无向图初始时图中没有边。
现在要进行 m 个操作操作共有三种
C a b在点 a 和点 b之间连一条边a 和 b 可能相等Q1 a b询问点 a 和点 b是否在同一个连通块中a 和 b 可能相等Q2 a询问点 a 所在连通块中点的数量
输入格式
第一行输入整数 n 和 m。
接下来 m 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b如果 a和 b 在同一个连通块中则输出 Yes否则输出 No。
对于每个询问指令 Q2 a输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1e5
输入样例
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例
Yes
2
3思路
cnt数组统计连通块中点的数量注意数量全放在祖先节点合并函数merge中进行累加
代码
#includebits/stdc.husing namespace std;const int N1e510;int n,m;int p[N];
int cnt[N];int find(int x)
{if(x!p[x])p[x]find(p[x]);return p[x];
}void merge(int a,int b)
{cnt[find(b)]cnt[find(a)];p[find(a)]find(b);
}int main()
{cinnm;for(int i1;in;i){p[i]i;cnt[i]1;}while(m--){char op[5];cinop;if(op[0]C){int a,b;cinab;if(find(a)find(b))continue;merge(a,b);}else if(op[1]1){int a,b;cinab;if(find(a)find(b))coutYesendl;else coutNoendl;}else{int t;cint;coutcnt[find(t)]endl;}}return 0;
}
5、格子游戏《信息学奥赛一本通》
Alice和Bob玩了一个古老的游戏首先画一个 n×n的点阵下图 n3 。
接着他们两个轮流在相邻的点之间画上红边和蓝边 直到围成一个封闭的圈面积不必为 1为止“封圈”的那个人就是赢家。因为棋盘实在是太大了他们的游戏实在是太长了
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序帮助他们计算他们是否结束了游戏
输入格式
输入数据第一行为两个整数 n 和 m。n表示点阵的大小m 表示一共画了 m 条线。
以后 m 行每行首先有两个数字 (x,y)代表了画线的起点坐标接着用空格隔开一个字符假如字符是 D则是向下连一条边如果是 R 就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行在第几步的时候结束。
假如 m 步之后也没有结束则输出一行“draw”。
数据范围
1≤n≤200 1≤m≤24000
输入样例
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D输出样例
4
思路
注意审题轮流在相邻的点之间画上红边和蓝边表示不存在有孤立的线的情况
可以把每个点进行转换变成一个独特的数然后我们就可以把每个点存起来如果新的两个点转化后发现有共同祖先那就表示封圈了
代码
#includebits/stdc.husing namespace std;const int N4e49;//因为二维转化为一维了所以一维空间必须开N的平方级 200*200
int p[N];int find(int x)
{if(x!p[x])p[x]find(p[x]);return p[x];
}void merge(int a,int b)
{p[find(a)]find(b);
}int main()
{int n,m;cinnm;for(int i1;in*n;i)p[i]i;int cnt1;for(int i1;im;i){int a,b;char c;cinabc;int p(a-1)*nb;//p表示原来的坐标 int q;//q表示另一端向下或者向右 if(cD)qa*nb;else q(a-1)*nb1;//coutfind(p) find(q)endl;if(find(p)find(q)){couti;return 0;}merge(p,q);}coutdraw;return 0;
}
