注：本文是我原先在csdn内写的一篇博文，现转到这里，两篇博文尽量同时更新。
//#include<iostream->shuati>
//define 为什么刷 学长☞hzwer用的测评系统，最近火上了
//define 技术 渣渣
不刷题很不爽啊
那就爽一爽吧虽然过几天就不一定会刷了
【1000】a+b问题
......人家提交框都给答案了
【1001】舒适的路线
Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。
Z小镇附近共有
N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景点前往另一个景点的时候，都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。
第一行包含两个正整数，N和M。
接下来的M行每行包含三个正整数：x，y和v（1≤x,y≤N，0 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。
样例1
4 2
1 2 1
3 4 2
1 4
样例2
3 3
1 2 10
1 2 5
2 3 8
1 3
样例3
3 2
1 2 2
2 3 4
1 3
样例1
IMPOSSIBLE
样例2
5/4
样例3
2
N(1<N≤500)
M（0<M≤5000）
Vi在int范围内
题解：
1.并查集，记录起点和终点是不是连通了
2.如果连通了，计算比例值，并更新最优比例值
3.化简比例值
没啥好说的了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int x,y,v;
}a[5001]; int n,m,fa[501],s,t,ma=0xfffffff,mi=1;//0xfffffff原值约为268435455
double ljj,pjy; int ask(int x){return fa[x]==x ? x : fa[x]=ask(fa[x]);} bool cmp(node a,node b){return a.v<b.v;} int sift(int x,int y){return x%y==0 ? y : sift(y,x%y);} int main(){
int i,j,p,q;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
scanf("%d%d",&s,&t);
sort(a+1,a+1+m,cmp);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++) fa[j]=j;
for(j=i;j>0;j--)
{
p=ask(a[j].x);q=ask(a[j].y);
fa[q]=p;
if(ask(s)==ask(t))//看看两个景点是否连上了？连上了就开始算咯
{
ljj=ma*1.0/mi;
pjy=a[i].v*1.0/a[j].v;////由于前面已经对a数组中的v排序，因此数据已经按照车辆行驶速度从小到大排序，因为j<=i，因此a[i].v*1.0/a[j].v>=1
if(ljj>pjy){ma=a[i].v;mi=a[j].v;}//如果原比例值比先比例值大就更新比例
}
}
}
int syf=sift(ma,mi);//约分，求两数最大公倍数
ma/=syf;mi/=syf;
if(ma==0xfffffff) printf("IMPOSSIBLE\n");
else if(mi==1) printf("%d\n",ma);
else printf("%d/%d\n",ma,mi);
return 0;
}
【1002】搭桥
有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。
在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。
在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。
样例1
3 5
#...#
..#..
#...#
样例2
3 5
##...
.....
....#
样例3
3 5
#.###
#.#.#
###.#
样例4:
3 5
#.#..
.....
....#
样例1
5
4 4
样例2
2
0 0
样例3
1
0 0
样例4
3
1 1
见描述
我只有几句话想说。
1.此题变态
2.输入比较坑，注意输入
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&map[i][j]);
if(map[i][j]=='#') a[++cntn]=p(i,j);
}
}
也不知咋地，输入map[i][j]时占位符前面必须加一个空格（可能是吃空行吧，但如果前面是字符呢？），或者改成cin>>map[i][j]。之前因为这个scanf的占位符问题WA了不少次，反正我只想做这个动作：
3.解答如下
第一问等于细胞，第二问等于最小生成树。
当然我用的是并查集+最小生成树
之后跑一遍并查集数组即可，输出前给并查集数组排个序。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 51*51
using namespace std;
const int dx[8]={-1,0,1,1,1,0,-1,-1};
const int dy[8]={-1,-1,-1,0,1,1,1,0}; struct edge{
int l,r,w;
bool operator < (const edge an)const{
return w<an.w;
}
}e[maxn*100]; int cnt,n,m,a[maxn],tot,f[maxn],ans,sum,cntn;
bool vis[maxn];
char map[60][60]; int find(int x){return x==f[x] ? x : f[x]=find(f[x]);} int p(int i,int j){return (i-1)*m+j;} inline void add(int i,int j,int k,int l){
e[++cnt].l=p(i,j);
e[cnt].r=p(k,l);
e[cnt].w=l-j-1;
} inline void add2(int i,int j,int k,int l){
e[++cnt].l=p(i,j);
e[cnt].r=p(k,l);
e[cnt].w=k-i-1;
} int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&map[i][j]);
if(map[i][j]=='#') a[++cntn]=p(i,j);
}
}
for(int i=1;i<=cntn;i++) f[a[i]]=a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j] == '#')
for(int k=0;k<8;k++)//向八面扩展
if(map[i+dx[k]][j+dy[k]] == '#')
{
int f1=find(p(i,j)),f2=find(p(i+dx[k],j+dy[k]));
f[f2]=f1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j] == '#')
for(int k=j;k<=m;k++)
{
if(map[i][k]=='#') add(i,j,i,k);
if(map[i+1][k]=='#') add(i,j,i+1,k);
if(map[i-1][k]=='#') add(i,j,i-1,k);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(map[i][j]=='#')
for(int k=i;k<=n;k++)
{
if(map[k][j]=='#') add2(i,j,k,j);
if(map[k][j-1]=='#') add2(i,j,k,j-1);
if(map[k][j+1]=='#') add2(i,j,k,j+1);
}
for(int i=1;i<=cntn;i++)
if(!vis[find(a[i])]) tot++,vis[find(a[i])]=1;
sort(e+1,e+1+cnt);
for(int i=1;i<=cnt;i++)
{
int f1=find(e[i].l),f2=find(e[i].r);
if(f1==f2) continue;
if(e[i].w) ans++;
sum+=e[i].w;
f[f2]=f1;
}
printf("%d\n%d %d\n",tot,ans,sum);
return 0;
}
【1003】电话连线
一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
输入文件的第一行是n的值（n<=100）.
第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。
输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1.
第m+2行是连接这些电话线的总费用。
5
0 15 27 6 0
15 0 33 19 11
27 33 0 0 17
6 19 0 0 9
0 11 17 9 0
2
1 4
2 5
17
n<=100
【1007】级数求和
已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。
现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。
键盘输入 k
屏幕输出 n
1
2
#include<iostream>
using namespace std;
double k,go,m=1.0;
int n;
int main(){
cin>>k;
while(go<=k){
go+=1/m;
m+=1.0;
n++;
}
cout<<n;
return 0;
}