A:::::::::::::::::::通电（最小生成树，Prim，Kruskal）
题目描述
2015 年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为(x1,y1) 高度为 h1 的村庄与坐标为 (x2,y2) 高度为h2 的村庄之间连接的费用为
高度的计算方式与横纵坐标的计算方式不同。
由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。
输入描述
输入的第一行包含一个整数 n ，表示村庄的数量。
接下来 n 行，每个三个整数 x,y,h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。
其中，1≤n≤1000，0≤x,y,h≤10000。
输出描述
输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。
输入输出样例
示例
输入
4 1 1 3 9 9 7 8 8 6 4 5 4
输出
17.41
#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; int n; struct node{ int x,y,h; }; struct node1{ int qi,zhong; double juli; node1(int qiqi,int zhongzhong,double julijuli){ qi=qiqi; zhong=zhongzhong; juli=julijuli; } }; int fa[10005]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } bool panduan(int x,int y){ int tx=find(x); int ty=find(y); if(tx==ty) return false; fa[tx]=ty; return true; } node dian[1005]; vector<node1> f; bool cmp(node1 x,node1 y){ return x.juli<y.juli; } int main(){ cin>>n; for(int i=1;i<=n;i++){ int x,y,h; cin>>x>>y>>h; dian[i].x=x; dian[i].y=y; dian[i].h=h; } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ double s= sqrt((dian[i].x-dian[j].x)*(dian[i].x-dian[j].x)+(dian[i].y-dian[j].y)*(dian[i].y-dian[j].y))+(dian[i].h-dian[j].h)*(dian[i].h-dian[j].h); f.push_back(node1(i,j,s)); } } sort(f.begin(),f.end(),cmp); for(int i=1;i<=n;i++){ fa[i]=i; } double ans=0; int len=f.size(); for(int i=0;i<len;i++){ if(panduan(f[i].qi,f[i].zhong)){ ans+=f[i].juli; } } printf("%0.2f",ans); return 0; }
B:::::::::::::::::::正约数（唯一分解定理）
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
定义阶乘 n!=1×2×3×⋅⋅⋅×n。
请问 100! （100 的阶乘）有多少个正约数。
#include <iostream> using namespace std; int a[100]; long long ans=1; int main(){ for(int i=2;i<=100;i++){ int n=i; for(int j=2;j<=n;j++){ while(n%j==0 && n!=0){ a[j]++; n=n/j; } } } for(int i=1;i<=100;i++){ ans=(a[i]+1)*ans; } cout<<ans; return 0; }
C:::::::::::::::::::迷宫（BFS）
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000 000100 001001 110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中D<L<R<U。
01010101001011001001010110010110100100001000101010 00001000100000101010010000100000001001100110100101 01111011010010001000001101001011100011000000010000 01000000001010100011010000101000001010101011001011 00011111000000101000010010100010100000101100000000 11001000110101000010101100011010011010101011110111 00011011010101001001001010000001000101001110000000 10100000101000100110101010111110011000010000111010 00111000001010100001100010000001000101001100001001 11000110100001110010001001010101010101010001101000 00010000100100000101001010101110100010101010000101 11100100101001001000010000010101010100100100010100 00000010000000101011001111010001100000101010100011 10101010011100001000011000010110011110110100001000 10101010100001101010100101000010100000111011101001 10000000101100010000101100101101001011100000000100 10101001000000010100100001000100000100011110101001 00101001010101101001010100011010101101110000110101 11001010000100001100000010100101000001000111000010 00001000110000110101101000000100101001001000011101 10100101000101000000001110110010110101101010100001 00101000010000110101010000100010001001000100010101 10100001000110010001000010101001010101011111010010 00000100101000000110010100101001000001000000000010 11010000001001110111001001000011101001011011101000 00000110100010001000100000001000011101000000110011 10101000101000100010001111100010101001010000001000 10000010100101001010110000000100101010001011101000 00111100001000010000000110111000000001000000001011 10000001100111010111010001000110111010101101111000
#include <iostream> #include <queue> using namespace std; char s[4]={'D','L','R','U'}; int b[4][2]={{1,0},{0,-1},{0,1},{-1,0}}; struct node{ int x; int y; string a; int bushu; node(int xx,int yy,string aa,int aaa){ x=xx; y=yy; a=aa; bushu=aaa; } }; char a[35][55]; bool c[35][55]; queue<node> q; int guding; void bfs(int xxx,int yyy){ c[xxx][yyy]=1; q.push(node(xxx,yyy,"",0)); while(!q.empty()){ int xx=q.front().x; int yy=q.front().y; if(xx==29 && yy==49){ cout<<q.front().a<<endl; break; } for(int i=0;i<4;i++){ int tx=xx+b[i][0]; int ty=yy+b[i][1]; if(tx>=0 && tx<30 && ty>=0 && ty<50 && !c[tx][ty] && a[tx][ty]=='0'){ q.push(node(tx,ty,q.front().a+s[i],q.front().bushu++)); c[tx][ty]=1; } } q.pop(); } } int main(){ for(int i=0;i<30;i++){ for(int j=0;j<50;j++){ cin>>a[i][j]; } } bfs(0,0); //(0,0)开始， return 0; }
