发表于 | 评论数：

给你两个1e5的序列问两个序列所有的数合并后总共N^2个数中前N个数的大小
我们先对数组进行排序，得到两个有序的数组AB
之后我们再把A[1]+B[1].A[1]+B[2],…,A[1]+B[N]这样的得出N个有序数列每个数列有N项
接着我们开一个优先队列把这个矩阵中第一列放进去，然后每次拿出最小的后，把那一行后一列加入到优先队列中，最终NlogN解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define mk(a,b) make_pair(a,b)
priority_queue<pair<int,int> > q;
int a[100005],b[100005],p[100005];
int main()
{
	int n,cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[i]=1;
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) q.push(mk(-(a[i]+b[1]),i));
	while(q.size()&&cnt<n)
	{
		printf("%d ",-q.top().first);	
		int id=q.top().second;
		q.pop();
		q.push(mk(-(a[id]+b[++p[id]]),id));
		cnt++;
	}
}

发表于 | 评论数：

SPFA变负权跑最短路即可(dij不行) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,s,bk[400005],head[400005],cnt;
ll x,y,z,inf=INT_MAX,dis[400005];
struct edge
{
	ll to,w,nxt;
}e[4000005];
void add(ll x,ll y,ll z)
{
	e[++cnt].to=y;e[cnt].w=z;e[cnt].nxt=head[x];head[x]=cnt;
}
void spfa()
{
	for(int i=1;i<=n;i++)
	dis[i]=i==s?0:inf;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int jk=q.front();
		q.pop();
		bk[jk]=0;
		for(int i=head[jk];i;i=e[i].nxt)
		if(dis[e[i].to]>dis[jk]+e[i].w)
		{
			dis[e[i].to]=dis[jk]+e[i].w;
			if(!bk[e[i].to])
			q.push(e[i].to),bk[e[i].to]=1;
		}
	}
	printf("%lld",dis[n]==inf?-1:-dis[n]);
}
int main()
{
	scanf("%d%d",&n,&m);
	s=1;
	while(m--)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,-z);
	}
	spfa();
}

发表于 | 评论数：

题目大多数都是给你一张图让你求其中两点见所有通路上边权最小值最大或者最大值最小的值
首先我们分析直接暴力去做那是肯定不可以的，数据一多就会T如果给定一张图的话可以用堆优化的dij能保证NlogN复杂度
边权最小值最大
我们分析一下最初的dij+堆优化的思路就是从终点开始，小根堆维护当前最小的dis然后用它去递推下面的dis答到最优更新的目的。
也就是dis[当前点]=min(dis[当前点],dis[之前的点]+边权值)
这里我们也是那种递推的思想
f[当前点]=min(f[当前点],max(边权值,f[之前的点]))
这个递推式实际上有点最大连续子区间的感觉 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//poj 2253(1~2之间所有路径上边权值最大的最小值)
#include <cstdio>
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll cnt,bk[305],ree;
double f[305];
struct node
{
	double v;
	ll id;
	bool operator<(const node& a) const 
	{
		return v>a.v;
	}
};
pair<double,double> a[200005];
double dis(int x,int y)
{
	double x1=a[x].first,y1=a[x].second,x2=a[y].first,y2=a[y].second;
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
priority_queue<node> q;
int main()
{
	int n;
	while(~scanf("%d",&n)&&n)
	{
		for(int i=1;i<=n;i++)
		scanf("%lf%lf",&a[i].first,&a[i].second),bk[i]=0,f[i]=1<<30;
		f[1]=0;
		node re;
		re.v=0.0,re.id=1;
		q.push(re);
		while(q.size())
		{
			node jk=q.top();
			q.pop();
			if(bk[jk.id]) continue;
			bk[jk.id]=1;
			for(int i=1;i<=n;i++)
			if(i!=jk.id&&max(f[jk.id],dis(jk.id,i))<f[i])
			{
				f[i]=max(f[jk.id],dis(jk.id,i));
				re.v=f[i],re.id=i;
				q.push(re);
			}
		}
		printf("Scenario #%lld\nFrog Distance = %.3lf\n\n",++ree,f[2]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// poj 1797(1-n所有路径上边权值最小值最大注意要用大根堆)  
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int head[1000005],bk[1000005],cnt,n,m,f[1000005];
struct edge
{
	int to,w,nxt;
}e[1000005];
struct node
{
	int v,id;
	node(int x,int y):v(x),id(y){};
	bool operator<(const node& a) const
	{
		return v<a.v;
	}
};
void add(int x,int y,int z)
{
	e[++cnt].to=y;e[cnt].w=z;e[cnt].nxt=head[x];head[x]=cnt;
}
int dij()
{
	for(int i=1;i<=n;i++) f[i]=bk[i]=0;
	f[1]=1<<30;
	priority_queue<node> q;
	q.push(node(0,1));
	while(q.size())
	{
		node jk=q.top();
		q.pop();
		if(bk[jk.id]) continue;
		bk[jk.id]=1;
		for(int i=head[jk.id];i;i=e[i].nxt)
		if(min(f[jk.id],e[i].w)>f[e[i].to])
		{
			f[e[i].to]=min(f[jk.id],e[i].w);
			q.push(node(f[e[i].to],e[i].to));
		}
	}
	return f[n];
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		int x,y,z;
		scanf("%d%d",&n,&m);
		cnt=0;
		memset(head,0,sizeof(head));
		while(m--)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		printf("Scenario #%d:\n%d\n\n",k,dij());
	}
}

发表于 | 评论数：

线段相交并查集，注意线段相交模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
int f[100005],mk[100005],ans;
struct node
{
	long long x,y;
}a[100005];
struct line
{
	node a,b;
}l[100005];
int check(line xx,line yy)
{
	node a=xx.a,b=xx.b,c=yy.a,d=yy.b;
	if(!(min(a.x,b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x) && min(a.y,b.y)<=max(c.y,d.y)))
	return 0;
	double u,v,w,z;
    u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
    v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
    w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
    z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
    return(u*v<=0.00000001 && w*z<=0.00000001);
}
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
	int n,p=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
		scanf("%lld%lld",&a[p].x,&a[p].y);
		p++;
		scanf("%lld%lld",&a[p].x,&a[p].y);
		l[i]=(line){a[p-1],a[p]};
		p++;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j)
	{
		if(check(l[i],l[j]))
		f[find(i)]=find(j);
	}
	for(int i=1;i<=n;i++)
	if(!mk[find(i)])
	mk[find(i)]=1,ans++;
	printf("%d",ans);
}

发表于 | 评论数：

题目链接
这题我也是服了，我比赛的时候都没发现可以放在实数点上，以为圆心只能在x为整数的点上
算法上就是计算出当前点所能画出的圆心的最左边到最右边的区间之后就是那种线段相交包含的感觉了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,cnt=0;double m,x,y;
    while(~scanf("%d%lf",&n,&m))
    {
        if(n==0&&m==0)
        break;
        int f=0,ans=1;
        pair<double,double> p[10005];
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&x,&y);
            if(y>m)
            f=1;
            double z=sqrt(m*m-y*y);
            p[i].first=x-z;
            p[i].second=x+z;
        }
        printf("Case %d: ",++cnt);
        if(f) puts("-1");
        else
        {
            sort(p+1,p+1+n);
            double jk=p[1].second;
            for(int i=2;i<=n;i++)
            {
                if(jk>p[i].first) jk=min(jk,p[i].second);
                else jk=p[i].second,ans++;
            }      
            printf("%d\n",ans);
        }  
    }  
}
0%