POJ 2362(Square-搜索剪枝1-相对顺序)

Posted on by
Language:
Square
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 17066   Accepted: 5878

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Sample Output

yes
no
yes

Source

Waterloo local 2002.09.21

《搜索是怎样剪枝的-1》

1.只要找到3条边。

2.从大到小顺序找。

3.每次搜边时要确定边的相对顺序唯一（直接从TLE→秒）


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXM (20+10)
int tt,n,a[MAXM],cnt,len;
bool b[MAXM],flag;
bool dfs(int l,int x,int pre)
{
//	cout<<l<<' '<<x<<' '<<kth<<endl;
	if (x==len) {l++;x=0;pre=n-1;}
	if (l==4)
	{
		return 1;
	}
	for(int i=pre-1;i;i--)
		if (!b[i]&&x+a[i]<=len)
		{
			b[i]=1;
			if (dfs(l,x+a[i],i)) return 1;
			b[i]=0;
		//	if (!x) return 0;
		}
	return 0;
}
int main()
{
	scanf("%d",&tt);
	while (tt--)
	{
		cnt=0;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			cnt+=a[i];b[i]=0;
		}
		sort(a+1,a+1+n);
		if (n<4||cnt%4||a[n]>cnt/4)
		{
			printf("non");continue;
		}
		b[n]=1;len=cnt/4;
		if (dfs(1,a[n],n))
		{
			printf("yesn");
		}
		else printf("non");
	}
	return 0;
}


POJ 2553(The Bottom of a Graph-缩点求出度)

Posted on by
Language:
The Bottom of a Graph
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 7308   Accepted: 3003

Description

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges.
Then G=(V,E) is called a directed graph. 
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1).
Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1). 
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of
all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer
numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with
the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output

1 3
2

Source

Ulm Local 2003

Tarjen缩点统计出度。


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (5000+10)
#define MAXM (1000000+10)
int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot;
bool b[MAXN];
int edge[MAXM],next[MAXM],pre[MAXN],size;
int x[MAXM],y[MAXM],numk[MAXN];
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}
void tar(int u)
{
	dfs[u]=t[u]=++tim;b[u]=1;s[++tot]=u;
	for (int p=pre[u];p;p=next[p])
	{
		int &v=edge[p];
		if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]);
		else if (!h[v]) dfs[u]=min(dfs[u],t[v]);  //保证指向祖先
	}
	if (dfs[u]==t[u])
	{
		kind++;
		while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++;
		h[s[tot--]]=kind;numk[kind]++;

	}
}
int outdegree[MAXN];
int main()
{
	while (scanf("%d",&n)&&n)
	{
		scanf("%d",&m);
		tot=size=tim=kind=0;
		memset(h,0,sizeof(h));
		memset(t,0,sizeof(t));
		memset(dfs,0,sizeof(dfs));
		memset(s,0,sizeof(s));
		memset(pre,0,sizeof(pre));
		memset(b,0,sizeof(b));
		memset(numk,0,sizeof(numk));
		memset(outdegree,0,sizeof(outdegree));

		for (int i=1;i<=m;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
			addedge(x[i],y[i]);
		}
		for (int i=1;i<=n;i++) if (!b[i]) tar(i);
//		for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl;
		for (int i=1;i<=m;i++)
		{
			if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++;
		}
		/*
		int ans=0;
		for (int i=1;i<=kind;i++)
			if (!outdegree[i]) ans+=numk[i];
		cout<<ans<<endl;
		*/
		bool flag=0;
		for (int i=1;i<=n;i++)
			if (!outdegree[h[i]])
			{
				if (flag) printf(" ");else flag=1;printf("%d",i);
			}


	//	cout<<ans<<endl;
		cout<<endl;
	}
	return 0;
}

BZOJ 2732([HNOI2012]射箭-半平面交)

Posted on by

2732: [HNOI2012]射箭

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 186  Solved: 104
[Submit][Status][Discuss]

Description

沫沫最近在玩一个二维的射箭游戏，如下图 1 所示，这个游戏中的 x 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手，可以朝 0 至 90?中的任意角度（不包括 0度和 90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些 只有端点被射中的靶子。这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。在闯关模式中，第一关只有一个靶
子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭 双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出 现一个靶子，在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关，否则游戏 结束。沫沫花了很多时间在这个游戏上，却最多只能玩到第七关“七星连珠”，这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关

Input

输入文件第一行是一个正整数N，表示一共有N关。接下来有N行，第i+1行是用空格隔开的三个正整数xi，yi1，yi2(yi1<yi2 )，表示第i关出现的靶子的横坐标是xi，纵坐标的范围是从yi1到yi2 。 
 输入保证30%的数据满足N≤100，50%的数据满足N≤5000，100%的数据满足N≤100000且给 出的所有坐标不超过109 。 
 

Output

仅包含一个整数，表示最多的通关数。 

Sample Input

5


2 8 12

5 4 5

3 8 10

6 2 3

1 3 7

Sample Output

3

HINT

先把方程写出来，改一改。
然后在坐标系上做半平面交。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
#define MAXN (100000+10)
#define MAXCi (1000000000)
#define eps 1e-15
#define For(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n;
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
}p[MAXN*4];
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend double operator*(V a,V b){return a.x*b.y-a.y*b.x;}
	friend V operator*(double a,V b){return V(a*b.x,a*b.y);}
	friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
};
struct line
{
	P p;
	V v;
	double ang;
	int i;
	line(){}
	line(double _x,double _y,double _a,double _b,int _i):p(P(_x,_y)),v(V(_a,_b)),i(_i){ang=atan2(v.y,v.x);}
	bool onleft(P A)
	{
		return v*V(p,A)>=0;
	}
	bool operator<(const line& l) const
	{
		return ang<l.ang;
	}
	friend P getinter(line a,line b)
	{
		/*
		V u=V(a.p,b.p);
		double t=(a.v*u)/(b.v*a.v);
		return b.p+(t*b.v);
		double s1=V(a.p,b.p+b.v)*a.v;
		double s2=a.v*V(a.p,b.p);
		return b.p+(-s1/(s1+s2))*b.v;
//		V u=V(a.p,b.p);
		*/
		V u=V(b.p,a.p);
		double t=(b.v*u)/(a.v*b.v);
		return a.p+t*a.v;

	}
}que[MAXN*10],q[MAXN*4];
int size=0;
int half_intersection(line *l,int n)
{
	int first=1,last=0;
	for (int i=1;i<=size;i++)
	{
		if (l[i].i>n) continue;
		if (!last) {q[++last]=l[i];continue;}
		while (first<last&&!l[i].onleft(p[last-1])) last--;
		while (first<last&&!l[i].onleft(p[first])) first++;
		if (fabs(q[last].v*l[i].v)<=eps)
		{
			if (q[last].onleft(l[i].p)) q[last]=l[i];
		}
		else q[++last]=l[i];
		if (first<last) p[last-1]=getinter(q[last-1],q[last]);
	}
	bool flag=1;
	while (flag)
	{
		flag=0;
		while (first<last&&!q[first].onleft(p[last-1])) last--,flag=1;
		while (first<last&&!q[last].onleft(p[first])) first++,flag=1;
	}
	/*
	p[last]=getinter(q[last],q[first]);
	for (int i=first;i<=last;i++)
		printf("%lf %lfn",p[i].x,p[i].y);
	cout<<endl;
	*/
	return last-first>1;
}
void pri(line a,line b)
{
	P c=getinter(a,b);
	printf("%.lf %.lfn",c.x,c.y);
}
int main()
{
	freopen("archery.in","r",stdin);
	freopen("archery.out","w",stdout);
	cin>>n;
	que[1]=line(0,0,0,1,0);
	que[2]=line(-1,0,1,0,0);
	que[3]=line(0,MAXCi,-1,0,0);
	que[4]=line(-MAXCi,MAXCi,0,-1,0);size=4;
//	pri(que[3],que[4]);
//	size=0;
	for (int i=1;i<=n;i++)
	{
		double x,l,r;
		scanf("%lf%lf%lf",&x,&l,&r);
		que[++size]=line(0,l/x,1/x,-1,i);
		que[++size]=line(0,r/x,-1/x,1,i);
	}
	sort(que+1,que+1+size);
//	cout<<size<<endl;
//	for (int i=l;i<=r;i++) cout<<halsf_intersection(que,i)<<' ';
//	cout<<half_intersection(que,50001);
	int l=0,r=n,Mid=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (half_intersection(que,mid)) {Mid=mid;l=mid+1;}else r=mid-1;
	}
	cout<<Mid<<endl;
	return 0;
}

BZOJ 2241([SDOI2011]打地鼠-二分判断+贪心)

Posted on by

Description

打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。

游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了，所以你改装了锤子，增加了锤子与地面的接触面积，使其每次可以击打一片区域。如果我们把地面看做M*N的方阵，其每个元素都代表一个地鼠洞，那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点：每次挥舞锤子时，对于这R*C的区域中的所有地洞，锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中，每个地洞必须至少有1只地鼠，且如果某个地洞中地鼠的个数大于1，那么这个地洞只会有1只地鼠被打掉，因此每次挥舞锤子时，恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密，因此在游戏过程中你不能旋转锤子（即不能互换R和C）。

你可以任意更改锤子的规格（即你可以任意规定R和C的大小），但是改装锤子的工作只能在打地鼠前进行（即你不可以打掉一部分地鼠后，再改变锤子的规格）。你的任务是求出要想打掉所有的地鼠，至少需要挥舞锤子的次数。

Hint：由于你可以把锤子的大小设置为1*1，因此本题总是有解的。

Input

 第一行包含两个正整数M和N；

下面M行每行N个正整数描述地图，每个数字表示相应位置的地洞中地鼠的数量。

Output

输出一个整数，表示最少的挥舞次数。

Sample Input

3 3



1 2 1



2 4 2



1 2 1



Sample Output



4



【样例说明】



使用2*2的锤子，分别在左上、左下、右上、右下挥舞一次。



【数据规模和约定】





对于100%的数据，1<=M,N<=100，其他数据不小于0，不大于10^5

二分判断+贪心

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#define MAXN (100+10)
#define INF (1000000000)
#define For(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,m,a[MAXN][MAXN],a2[MAXN][MAXN];
int is_ok(int l,int r)
{
	memcpy(a2,a,sizeof(a));
	int sum=0;
	For(i,n-l+1) For(j,m-r+1)
		if(a2[i][j])
		{
			int delta=a2[i][j];sum+=delta;
			for (int k=i;k<=i+l-1;k++)
				for (int k2=j;k2<=j+r-1;k2++)
					if (a2[k][k2]<delta) return 0;
					else a2[k][k2]-=delta;
		}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	int cnt=0,ans=0;
	For(i,n) For(j,m) {scanf("%d",&a[i][j]);cnt+=a[i][j];}
	For(i,n) For(j,m)
	{
		if (i*j<ans) continue;
		if (!(cnt%(i*j))&&is_ok(i,j)*i*j==cnt)
		{
			ans=i*j;
		}
	}
	cout<<cnt/ans<<endl;
	return 0;
}

BZOJ 2705([SDOI2012]Longge的问题-欧拉函数φ(i))

Posted on by

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 375  Solved: 239
[Submit][Status][Discuss]

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据，0<N<=2^16。

对于100%的数据，0<N<=2^32。

 

欧拉函数：

枚举n的约数k，令s(k)为满足gcd(m,n)=k,(1<=m<=n)  m的个数，则ans=sigma(k*s(k)) (k为n的约数）

 因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)

 枚举n的约数即可，复杂度o(sqrt(n))

PS:刚刚ksy告诉我C++，直接读int比读char转int慢（——0）



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (2<<31)
long long ans=0,n;
long long phi(long long n)
{
	if (n==1) return 1;
//	cout<<n;
	long long ans=1;
	for (long long i=2;i*i<=n;i++)
		if (n%i==0)
		{
			int k=0;
			while (n%i==0) {k++,n/=i;}
			ans*=i-1;
			for (int j=2;j<=k;j++) ans*=i;
		}
	if (n>1) ans*=n-1;
//	cout<<' '<<ans<<endl;
	return ans;
}
int main()
{
	cin>>n;
	for (int i=1;i*i<=n;i++)
		if (n%i==0)
		{
			ans+=(long long)i*phi(n/i);
			if (i*i<n) ans+=(long long)n/i*phi(i);
		}
	cout<<ans<<endl;
	return 0;
}

CH 白色情人节2(⑤我心永恒-字符串序列个数统计)

Posted on by

背景

You're here, there's nothing I fear,
and I know that my heart will go on.
We'll stay forever this way.
You are safe in my heart.
And my heart will go on and on.

描述

男主想要用三句话表达对女主的爱，男主要对这三句话进行一番锤炼，现在要找出三句话中永恒不变的事物，需要做的，就是计算出三份序列的最长公共子序列长度、公共子序列个数，其中个数对第201314个质数(2769433)取模。字符之间的匹配不区分大小写(即"a"与"A"视为相等)

输入格式

共三行，一行一个字母序列。

输出格式

第一行，三份序列的最长公共子序列长度。
第二行，三份序列的公共子序列个数对第201314个质数(2769433)取模得到的答案。

样例输入

INeedYou
IMissYou
ILoveYou

样例输出

4
15

数据范围与约定

对于100%的数据，序列仅含大小写字母，序列长度均leq 100。

样例解释

最长公共子序列是IYou，长度为4，公共子序列分别是I Y o u IY Io Iu Yo Yu ou IYo IYu Iou You IYou，共4+6+4+1 = 15个

来源

本题有个无节操版本……

这题是统计公共子序列个数+去重

正解用了容斥原理,并且允许空串。

F[I][J][K]=2F[I-1][J-1][K-1]-F[I'-1][J'-1][K'-1] I',J',K'为I,J,K,之前出现a[i],b[j],c[k]的位置（没有就不用减）

 假设之前已经去重，那么F[I][J][K]只需与F[I'-1][J'-1][K'-1]去重。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define F (2769433)
#define MAXN (100+10)
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<=n;i++)
int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500];
char a[MAXN],b[MAXN],c[MAXN];
void make_pre(char *a,int n,int *pre)
{
	memset(s,128,sizeof(s));
	memset(pre,0,sizeof(pre));
	For(i,n)
	{
		a[i]=tolower(a[i]);
		pre[i]=s[a[i]];
		s[a[i]]=i;
	}
}
int main()
{
	memset(f,0,sizeof(f));
	scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' ';
	len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1;
	make_pre(a,len1,pre1);
	make_pre(b,len2,pre2);
	make_pre(c,len3,pre3);
	int cnt=0;
	For(i,len1)
		For(j,len2)
			For(k,len3)
				if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1;
				else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]);
	cnt=f[len1][len2][len3];
//	memset(f,0,sizeof(f));
	Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1;
	For(i,len1)
		For(j,len2)
			For(k,len3)
			{
				f[i][j][k]=0;
				if (a[i]==b[j]&&b[j]==c[k])
				{
					f[i][j][k]=(10*F+f[i-1][j-1][k-1]*2)%F;
					if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F;
				//	if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--;
				}
				else
				{
					f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F;
				}
			}

	printf("%dn%dn",cnt,(F+f[len1][len2][len3]-1)%F);
	return 0;
}


BZOJ 1185([HNOI2007]最小矩形覆盖-旋转卡壳+点集几何意义)

Posted on by

1185: [HNOI2007]最小矩形覆盖

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 258  Solved: 137

Description

 

l要事先改成r，注意把向量的2点设成同一点会出现奇妙的事情

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN (50000+10)
#define INF (1000000000)
#define eps 1e-6
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
	friend bool operator<(P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y;	}
	friend bool operator==(P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
	friend bool operator!=(P a,P b){return !(a==b);}

}a[MAXN],s[MAXN],ansp[5];
int size=0;
double ans=INF;
double dis2(P a,P b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend double operator*(V a,V b){return	a.x*b.y-a.y*b.x;}
	friend V operator*(double a,V b){return V(a*b.x,a*b.y);}
	friend double operator/(V a,V b){return	a.x*b.x+a.y*b.y;}
	friend P operator+(P a,V b){return P(a.x+b.x,a.y+b.y);}
	friend P operator-(P a,V b){return P(a.x-b.x,a.y-b.y);}
	friend V operator~(V a){return V(a.y,-a.x);}
	double dis2(){return x*x+y*y;	}
}c[MAXN];
int cmp(P A,P B)
{
	double tmp=V(a[1],A)*V(a[1],B);
	if (tmp>0) return 1;
	else if (fabs(tmp)<eps) return (-dis2(A,a[1])-dis2(B,a[1])>0);
	return 0;
}
int n;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	for (int i=2;i<=n;i++) if (a[i]<a[1]) swap(a[1],a[i]);
	sort(a+2,a+1+n,cmp);
	s[1]=a[1];size=1;
	for (int i=2;i<=n;)
		if (size<2||V(s[size-1],s[size])*V(s[size],a[i])>eps) s[++size]=a[i++];
		else size--;
	s[0]=s[size];

	int l=1,r=1,t=1;
	for (int i=0;i<size;i++)
	{
		while (V(s[i],s[i+1])*V(s[i],s[t+1])-V(s[i],s[i+1])*V(s[i],s[t])>-eps) t=(t+1)%size;
		while (V(s[i],s[i+1])/V(s[i],s[r+1])-V(s[i],s[i+1])/V(s[i],s[r])>-eps) r=(r+1)%size;
		if (i==0) l=r;
		while (V(s[i],s[i+1])/V(s[i],s[l+1])-V(s[i],s[i+1])/V(s[i],s[l])<eps) l=(l+1)%size;
		double Dis2=dis2(s[i],s[i+1]),wlxdis=V(s[i],s[i+1])/V(s[i],s[l]),wrxdis=V(s[i],s[i+1])/V(s[i],s[r]),hxdis=V(s[i],s[i+1])*V(s[i],s[t]);
		double tmp=hxdis*(wrxdis-wlxdis)/Dis2;
		if (tmp<0) tmp=-tmp;
		if (ans>tmp)
		{
			ans=tmp;
			ansp[0]=s[i]-(wlxdis/Dis2)*V(s[i+1],s[i]);
			ansp[1]=s[i]+(wrxdis/Dis2)*V(s[i],s[i+1]);
			ansp[2]=ansp[1]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
			ansp[3]=ansp[0]+(hxdis/Dis2)*(~V(s[i+1],s[i]));
		}
	}
	int p=0;
	for (int i=1;i<4;i++) if (ansp[i]<ansp[p]) p=i;//p=0;
	printf("%.5lfn",ans);
	for (int i=0;i<4;i++)
		printf("%.5lf %.5lfn",ansp[(p+i)%4].x,ansp[(p+i)%4].y);
	return 0;
}

BZOJ 1007(水平可见直线-斜率排序+栈贪心)

Posted on by

1007: [HNOI2008]水平可见直线

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1830  Solved: 656
[Submit][Status][Discuss]

Description

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

3

-1 0

1 0

0 0

Sample Output

1 2

按斜率排序，从小到大插入。
半平面交的特殊情况：
每次
都要保证x坐标<x,top>><top,top'> 否则top不可见（top为栈顶元素）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
	int k,b,i;
	friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;	}
	friend double intx(line a,line b)
	{
		return (double)(b.b-a.b)/(a.k-b.k);
	}
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
	while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
	s[++size]=x;
}
bool b[MAXN];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
	sort(a+1,a+1+n);
	push(1);
	for (int i=2;i<=n;i++)
		if (a[i].k>a[i-1].k) push(i);
//	for (int i=1;)
	memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
	for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
	return 0;
}




CH Adera 3(ZZB的数学作业-构造法初讲)

Posted on by

描述

把一个正整数M分成P个不超过K的正整数的和，满足分成的数不是N的倍数，并且P也不是N的倍数，求这样的P最小是多少？”

输入格式

一个测试点不超过10组数据，每行三个整数N、M、K代表一组数据，以EOF结尾。

输出格式

对于每组数据输出一行，一个整数，即最小的P。

样例输入

3 11 6
2 12 47

样例输出

4
-1

数据范围与约定

对于20%的数据，1<=N，M，K<=20。
对于60%的数据，1<=N，K<=10000。
对于另20%的数据，1<=K<=2。
对于100%的数据，1<=N，M，K<=10^9。

特判 

n=1 m%n肯定不行

n=2 m是偶数 奇数个奇数和≠偶数 不行

否则找最小的k

现在开始维护p，各种特判

由于最后多出来的一部分=k-1是不能合并 所以必须拆

最后维护p

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (1000000000)
int n,m,k;
int main()
{
	while (cin>>n>>m>>k)
	{
		if (n==1||n==2&&!(m%2))
		{
			puts("-1");continue;
		}
		while (!(k%n)) k--;
		if (k==1)
		{
			if (m%n) cout<<m<<endl;
			else puts("-1");
			continue;
		}
		int ans=(m-1)/k+1;
		if (ans==1&&!(m%n)) ans++;
		if (!((k-1)%n)&&m%k==k-1) ans++;
		if (!(ans%n)) ans++;
		cout<<ans<<endl;
	}
	return 0;
}

FZU 2100(排队-Treap维护队列最大值)

Posted on by
 Problem 2100 排队

Accept: 16    Submit: 160
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

一些人在排队买车票，假设每个人都有不同的买票紧急程度，如果某个人的紧急程度比排在他前一个的人的紧急程度更大，则这个人可以和前一个人调换位置，并且假设每个人都有一个耐心值，若某人的耐心值为x，则他最多可以向前调换x次，当然前提是他之前x个人的紧急程度都比他小，若遇到前面一个人紧急程度比他大的他将停止往前调换。现假设有N个人，按顺序一个个进入队列，并且每进去一个人立即按照紧急程度和其耐心值向前进行调换，调换停止后下一个人才进入队列。给出这N个人的紧急程度和耐心值，问最终的排队情况。

Input

第一行输入一个整数T，表示数据组数。接下来T组数据，对于每组数据，第一行输入一个整数n (1<=n<=10^5)，接下来第2到n+1行每行输入两个整数a[i],c[i] (1<=a[i]<=n,0<=c[i]<=n)，分别表示第i个人的紧急程度在n个人种排第几及其耐心值，a[i]越大表示紧急程度越大。

Output

对于每组数据，请输出一行n个数，以一个空格隔开，表示最终队列的排队情况，第i个数表示最终排在第i个位置的人是第几个进入队列的。

Sample Input

152 31 44 33 15 2

Sample Output

3 1 5 4 2

Source

FOJ有奖月赛-2012年11月

这题因为把转移中的maxv打成v而Wa了一天（一天啊！）
言归正传，这题是要维护平衡树子树最大值，Treap的rotate是参考刘汝佳的写法。
就是insert时要根据左右子树的s(size)和maxv比大小

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100000+10)
int t,n;
struct node
{
	int v,r,s,maxv,i;
	node *ch[2];
	node(int _v,int _i):s(1),r(rand()),v(_v),maxv(_v),i(_i){ch[0]=ch[1]=NULL;}
	bool operator<(const node &b){return r<b.r;}
	void maintain()
	{
		s=1;maxv=v;
		if (ch[0]!=NULL) {s+=ch[0]->s;maxv=max(maxv,ch[0]->maxv);}
		if (ch[1]!=NULL) {s+=ch[1]->s;maxv=max(maxv,ch[1]->maxv);}
	}
}*root=NULL;
void rotate(node *&o,int d)
{
	node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;
	o->maintain();k->maintain();o=k;
}
void del(node *&o)
{
	if (o==NULL) return;
	del(o->ch[0]);
	del(o->ch[1]);
	delete o;
	o=NULL;
}
bool flag=1;
void print(node *&o)
{
	if (o->ch[0]!=NULL) print(o->ch[0]);
	if (flag) printf(" ");else flag=1;
	printf("%d",o->i);
	if (o->ch[1]!=NULL) print(o->ch[1]);
}
void insert(node *&o,int x,int k,int i)
{
	if (o==NULL){o=new node(x,i);return;	}
	int d;
	if (o->ch[1]==NULL)
	{
		if (k&&o->v<x) d=0;else d=1;
	}
	else if (o->ch[1]->s>=k||o->ch[1]->maxv>x||o->v>x) d=1;
	else d=0;
	if (d==0)
	{
		if (o->ch[1]!=NULL) k-=o->ch[1]->s;
		k--;
	}
	insert(o->ch[d],x,k,i);o->maintain();
	if (o->ch[d]<o) rotate(o,d^1);o->maintain();
}
int main()
{
//	freopen("fzu2100.in","r",stdin);
//	freopen("fzu2100.out","w",stdout);
	scanf("%d",&t);
	while (t--)
	{
		del(root);root=NULL;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			insert(root,x,y,i);
		}
		flag=0;print(root);printf("n");
	}
	return 0;
}