题意只是要顾及临边，即每次加入到集合的那个数本身，排个序就好了
Description
国防部（DND）要用无线网络连接北部几个哨所。两种不同的通信技术被用于建立网络：每一个哨所有一个无线电收发器，一些哨所将有一个卫星频道。
任何两个有卫星信道的哨所可以通过卫星进行通信，而不管他们的位置。同时，当两个哨所之间的距离不超过D时可以通过无线电通讯，D取决于对收发器的功率。功率越大，D也越大，但成本更高。出于采购和维修的方便，所有哨所的收发器必须是相同的；那就是说，D值对每一个哨所相同。
你的任务是确定收发器的D的最小值。每对哨所间至少要有一条通信线路（直接或间接）。
Input
输入的第一行是测试数据的数量N。
每组测试数据的第一行包含卫星频道的数量S（1 < = S < = 100）和哨所的数量P（S < P < = 500）。接下来的P行，给出以公里为单位的每个哨所的坐标(x,y)( 坐标为0到10000之间的整数)。
Output
对于每组测试数据，输出一行，输出收发器的D的最小值。精确到小数点后两位。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int flag1=0;
int n,s,p;
double sum;
double arr_list[504][504];
double d[503];
struct Edge
{
int point;
double lowcost;
int flag;
};
Edge edge[505];
bool cmp(double a,double b)
{
return a>b;
}
struct Point
{
double x,y;
}point[502];
void prim(int p)
{
int i,j,k=1;
double min,sum2=0;
j=1;
for(i=1;i<=p;i++)
{
if(i!=j)
{
edge[i].point=j;
edge[i].lowcost=arr_list[j][i];
edge[i].flag=0;
}
}
edge[j].lowcost=0;
edge[j].flag=1;
int l=0;
for(i=1;i<p;i++)
{
min=65535000;
for(j=2;j<=p;j++)
{
if(edge[j].flag==0&&edge[j].lowcost<min)
{
k=j;
min=edge[j].lowcost;
}
}
d[l++]=arr_list[k][edge[k].point];
//sum2+=min;
edge[k].flag=1;
for(j=2;j<=p;j++)
{
if(edge[j].flag==0&&arr_list[k][j]<edge[j].lowcost)
{
edge[j].point=k;
edge[j].lowcost=arr_list[k][j];
}
}
}
}
int main()
{
// freopen("cin.txt","r",stdin);
cin>>n;
while(n--)
{
cin>>s>>p;
for(int i=1;i<=p;i++)
{
cin>>point[i].x>>point[i].y;
arr_list[i][i]=65535000;
}
for(int i=1;i<p;i++)
{
for(int j=i+1;j<=p;j++)
{
arr_list[i][j]=sqrt(pow((point[i].x-point[j].x),2)+pow((point[i].y-point[j].y),2));
arr_list[j][i]=arr_list[i][j];
//cout<<arr_list[i][j]<<endl;
}
}
prim(p);
sort(d,d+p-1,cmp);
cout.setf(ios::fixed);//保留两位小数
cout.precision(2);
cout<<d[s-1]<<endl;
}
return 0;
} 这个题貌似是12年杭州亚洲赛的题==，题意是求一个最小生成树，但是要求有两个已知点必须直接连着==
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=60*60;
struct point
{
int x,y;
double dis;
point(){}
point(int _x,int _y,double _d):x(_x),y(_y),dis(_d){}
bool operator <(const struct point &tmp)const{
return this->dis<tmp.dis;
}
}p[maxn];
point pp[100];
int par[60];
void init(){
for(int i=0;i<60;i++) par[i]=i;
}
int find_par(int x){
if(x!=par[x]) return par[x]=find_par(par[x]);
return par[x];
}
bool Union(int x,int y){
x=find_par(x);
y=find_par(y);
if(x!=y){
par[y]=x;
return true;
}
return false;
}
double calu(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
// freopen("cin.txt","r",stdin);
int n,p1,q1;
while(~scanf("%d",&n)&&n)
{
init();
scanf("%d%d",&p1,&q1);
int cnt=0;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&pp[i].x,&pp[i].y);
for(int j=1;j<i;j++)
{
double d=calu(pp[i],pp[j]);
p[cnt++]=point(i,j,d);
}
}
double ans=0;
Union(p1,q1);
ans+=calu(pp[p1],pp[q1]);
sort(p,p+cnt);
for(int i=0;i<cnt;i++)
{
if(Union(p[i].x,p[i].y))
ans+=p[i].dis;
}
printf("%.2lf\n",ans);
}
}
C - 仅剩
HDU - 5747很容易想到前面的数字小，后面的数字大，求快速幂有技巧
#include <cstdio>
#include <algorithm>
using namespace std;
int pow(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans *= a;
a *= a;
b = b / 2;
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
m = min(m, 30);
int ans = 0;
for (int i = m; i >= 0; --i) {
int k = pow(2, i);
ans += n / k;
n = n % k;
if(!n) break;
}
printf("%dn", ans);
}
return 0;
}给你n个数，问是否有连续子序列的和是m的倍数。很蛋疼啊一开始往线段树上想去了结果没做出来。
这题的做法就是求前缀数组和，什么意思呢，假设x到y这个区间的子序列的和是m的倍数，这里假设和为km，再假设从n[0]到n[x]的和为sum[x],那么n[0]到n[y]就是sum[y]，我们知道模运算计算的是余数，因为x到y的和为m的倍数，所以sum[x]对m取模的结果和sum[y]对m取模的结果一致。也就是说如果那个余数出现了两次或者以上那么就一定存在子序列和为m的倍数，然后我们设置一个数组vis用来统计余数出现的次数，这个余数当然是小于m的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 100010
int T, n, m, i, j, k;
int ch1[inf], t, vis[inf];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(vis, 0, sizeof(vis));
int sum = 0;
int temp = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &ch1[i]);
sum += ch1[i];
t = sum % m;
vis[t]++;
}
for (i = 0; i < n; i++)
{
if (vis[i] >= 2||vis[0]==1)
{
temp = 1;
break;
}
}
if (temp)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
} #include <stdio.h>
using namespace std;
int main()
{
int w,i,j,n,m;
long long t,sum;
scanf("%d",&w);
while (w--)
{
sum=0;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%lld",&t);
sum+=t;
}
for (i=1;i<=m;i++)
{
scanf("%lld",&t);
if (t>sum)
printf("1");
else
printf("0");
}
printf("\n");
}
return 0;
}
京公网安备 11010502036488号