Category Archives: DefaultCategory

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;
}

POJ 2704(Pascal's Travels-裸dp)

Posted on by
Language:
Pascal's Travels
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4821   Accepted: 2139

Description

An n x n game board is populated with integers, one nonnegative integer per square. The goal is to travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any one square dictates how large a step away
from that location must be. If the step size would advance travel off the game board, then a step in that particular direction is forbidden. All steps must be either to the right or toward the bottom. Note that a 0 is a dead end which prevents any further
progress. 

Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed. 

Input

The input contains data for one to thirty boards, followed by a final line containing only the integer -1. The data for a board starts with a line containing a single positive integer n, 4 <= n <= 34, which is the number of rows in this board. This is followed
by n rows of data. Each row contains n single digits, 0-9, with no spaces between them.

Output

The output consists of one line for each board, containing a single integer, which is the number of paths from the upper left corner to the lower right corner. There will be fewer than 263 paths for any board. 

Sample Input

4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1

Sample Output

3
0
7

Hint

Brute force methods examining every path will likely exceed the allotted time limit. 64-bit integer values are available as long values in Java or long long values using the contest's C/C++ compilers.

Source

Mid-Central USA 2005

就是dp……

一开始忘打‘n’ wa了……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN (34+1)
int a[MAXN][MAXN],n;
long long f[MAXN][MAXN];
int main()
{
	while (scanf("%d",&n)&&n+1)
	{
		for (int i=1;i<=n;i++)
		{
			char s[MAXN];
			scanf("%s",s+1);
			for (int j=1;j<=n;j++) a[i][j]=s[j]-'0';
		}
		memset(f,0,sizeof(f));f[1][1]=1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (a[i][j])
				{
					if (i+a[i][j]<=n) f[i+a[i][j]][j]+=f[i][j];
					if (j+a[i][j]<=n) f[i][j+a[i][j]]+=f[i][j];
				}
		printf("%lldn",f[n][n]);
	}
	return 0;
}


CH 白色情人节1(②第一天-KM算法)

Posted on by

背景

下过雨的夏天傍晚 我都会期待
唱歌的蝉 嘿 把星星都吵醒 月光晒了很凉快
就是这样回忆起来 第一次告白
尴尬的我 看 爱装得很哲学的你其实很可爱
你说活在明天 活在期待 不如活得今天很自在
我说我懂了 会不会太快 未来 第一天要展开

描述

时间回溯到男女主认识的第一天——女主同学举办的联谊会，男主迟到了那天的联谊会，而男主到达现场时女主也刚好没有男伴，这就是他们的第一次相遇。
男主回想起来不禁一阵感慨(为啥这么好的妹子你们都不搭讪呢)，突然男主想到，如果当时已经配对的n对男女好感值之和不是最大，会不会自己就遇不上女主了呢？

输入格式

第一行两个正整数n和queen，表示已有n对男女可以配对和女主的编号queen。(男编号为X1~Xn，女编号为Y1~Yn+1)
接下来n*(n+1)行，每行三个正整数Xi，Yi，Zi，表示男Xi女Yi之间的好感度为Zi，保证每对(Xi,Yi)没有重复，即两人的关系至多一条。
不存在男与男、女与女之间的好感度！

输出格式

前n行输出联谊会上n对男女的配对情况(会多出来一名女生)，每行两个正整数Xi和Yi(空格隔开)，任意一种符合条件的方案均可。
第n+1行，对于你输出的方案，如果女主未配对，输出"YES"(不含引号)，表示女主会遇到男主，否则输出"NO"(不含引号)。

样例输入

2 3
1 1 15
1 2 20
1 3 17
2 1 22
2 2 14
2 3 14

样例输出

1 2
2 1
YES

数据范围与约定

对于100%的数据，1leq nleq 520,1leq Z_{i}leq 201314。

样例解释

如图，已经配对的关系有是男1号女2号和男2号女1号。

来源

*****关系~

km算法

就是二分图匹配时维护lx[i],ly[i]

满足

1.对于任意边lx[i]+ly[i]>=w[i,j]

2.如果存在一组匹配，其中任意边满足lx[i]+ly[i]=w[i,j]，它一定是最大匹配（如果随意调换一边，必然出现lx[i]+ly[j]+lx[i']+ly[j']=w[i,j]+w[i',j']≥w[i,j']+w[i',j]

于是每次找出slock，表示对所有找过的i,不为0的min(lx[i]+ly[j]-w[i,j])

把slock的值从左移至右，既不改变原图能走的边，又能使图得到扩充。

//一开始应该把lx[i]设成max(w[i,j],0),ly[i]设成0

每次扩充必须保证图中的边满足lx[i]+ly[i]=w[i,j]，否则用slock扩充


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
using namespace std;
#define INF (100000000)
#define MAXN (520+10)
#define MAXWi (201314)
int n,m,yi,slack;
int w[MAXN][MAXN],lx[MAXN],ly[MAXN],a[MAXN];//a=?->yi
bool vx[MAXN],vy[MAXN];
bool find(int x)
{
	vx[x]=1;
	for (int i=1;i<=m;i++)
		if (!vy[i])
		{
			int t=lx[x]+ly[i]-w[x][i];
			if (t==0)
			{
				vy[i]=1;
				if (a[i]==0||find(a[i])) {a[i]=x;return 1;}
			}else slack=min(slack,t);
		}
	return 0;
}
int main()
{
//	freopen("input","r",stdin);
	scanf("%d%d",&n,&yi);m=n+1;
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(a,0,sizeof(a));
	for (int i=1;i<=n*(n+1);i++)
	{
		int u,v,wei;scanf("%d%d%d",&u,&v,&wei);w[u][v]=wei;
		lx[u]=max(lx[u],wei);
	}
	for (int i=1;i<=n;i++)
	{
		memset(vx,0,sizeof vx);
		memset(vy,0,sizeof vy);
		slack=INF;
		while (!find(i))
		{
			for (int j=1;j<=n;j++) if (vx[j]) lx[j]-=slack;
			for (int j=1;j<=m;j++) if (vy[j]) ly[j]+=slack;
			memset(vx,0,sizeof vx);
			memset(vy,0,sizeof vy);
			slack=INF;
		//	find(i);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if (a[i]) printf("%d %dn",a[i],i);
	}
	if (a[yi]) printf("NOn");
	else printf("YESn");
	return 0;
}

CF 286C(Main Sequence-贪心括号匹配)

Posted on by
C. Main Sequence
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

As you know, Vova has recently become a new shaman in the city of Ultima Thule. So, he has received the shaman knowledge about the correct bracket sequences. The shamans of Ultima Thule have been using lots of different types of brackets since prehistoric times.
A bracket type is a positive integer. The shamans define a correct bracket sequence as follows:

  • An empty sequence is a correct bracket sequence.
  • If {a1, a2, ..., al} and {b1, b2, ..., bk} are
    correct bracket sequences, then sequence {a1, a2, ..., al, b1, b2, ..., bk} (their
    concatenation) also is a correct bracket sequence.
  • If {a1, a2, ..., al} —
    is a correct bracket sequence, then sequence  also is a correct bracket sequence, where v (v > 0) is
    an integer.

For example, sequences {1, 1,  - 1, 2,  - 2,  - 1} and {3,  - 3} are
correct bracket sequences, and {2,  - 3} is not.

Moreover, after Vova became a shaman, he learned the most important correct bracket sequence {x1, x2, ..., xn},
consisting of nintegers. As sequence x is the most
important, Vova decided to encrypt it just in case.

Encrypting consists of two sequences. The first sequence {p1, p2, ..., pn} contains
types of brackets, that is, pi = |xi| (1 ≤ i ≤ n).
The second sequence {q1, q2, ..., qt} contains t integers
— 这些地方必须取负数 {x1, x2, ..., xn}.

Unfortunately, Vova forgot the main sequence. But he was lucky enough to keep the encryption: sequences {p1, p2, ..., pn} and{q1, q2, ..., qt}.
Help Vova restore sequence x by the encryption. If there are multiple sequences that correspond to the encryption, restore any of them. If there are no
such sequences, you should tell so.

Input

The first line of the input contains integer n (1 ≤ n ≤ 106).
The second line contains n integers: p1, p2, ..., pn (1 ≤ pi ≤ 109).

The third line contains integer t (0 ≤ t ≤ n),
followed by t distinct integers q1, q2, ..., qt (1 ≤ qi ≤ n).

The numbers in each line are separated by spaces.

Output

Print a single string "NO" (without the quotes) if Vova is mistaken and a suitable sequence {x1, x2, ..., xn} doesn't
exist.

Otherwise, in the first line print "YES" (without the quotes) and in the second line print n integers x1, x2, ..., xn (|xi| = pi; xqj < 0).
If there are multiple sequences that correspond to the encrypting, you are allowed to print any of them.

Sample test(s)
input
2
1 1
0
output
YES
1 -1
input
4
1 1 1 1
1 3
output
YES
1 1 -1 -1
input
3
1 1 1
0
output
NO
input
4
1 2 2 1
2 3 4
output
YES
1 2 -2 -1

贪心，从后向前做，尽可能取左括号。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000000+10)
#define MAXP (1000000000+10)
int n,m,a[MAXN],ans[MAXN],tot;
bool b[MAXN];
int s[MAXN],size=0;
int main()
{
	memset(b,0,sizeof(b));
	scanf("%d",&n);tot=n+1;
	if (n%2) {printf("NOn");return 0;}
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int p;
		scanf("%d",&p);
		b[p]=1;
	}
	for (int i=n;i;i--)
	{
		if (size==0||s[size]!=a[i]||b[i])
		{
			s[++size]=a[i];ans[--tot]=-a[i];
		}
		else ans[--tot]=s[size--];
	}
	if (size) printf("NOn");
	else
	{
		printf("YESn");
		for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%dn",ans[n]);
	}

	return 0;
}

圈地(斜率排序+坐标系旋转)

Posted on by

Problem 2 圈地(land.cpp/c/pas)

【题目描述】

2维平面上有n个木桩，你有一次圈地的机会并得到圈到的土地，为了体现你的高风亮节，你要使你圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。

 

【输入格式】

第一行一个整数n，表示木桩个数。
　　接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。

【输出格式】

仅一行，表示最小圈得的土地面积，保留2位小数。

【样例输入】

样例1：
3

0 0

0 1

1 0

样例2：
4

0 0

0 1

0 2

1 1

【样例输出】

样例1：
0.50
样例2：
0.00
【数据范围】

    对于10%的数据，n<=100；
　对于30%的数据，n<=300；
　对于50%的数据，n<=500；
　对于100%的数据，n<=1000。

显然这题的多边形一定是三角形。

首先求出所有边，按k排序（必须先求出来，不能直接在排序的时候求）

然后考虑这些边，会发现正好是绕坐标系旋转一圈。

也就是说如果按照以这边为y轴从左至右排序，那么每转移一条边，只需要调换该边2个点的位置

这题没给范围，但是必须用long long

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN (1000+10)
#define INF (1000000000)
#define eps 1e-10
struct P
{
	int x,y;
	long long operator*(const P &b)
	{
		return (long long)x*b.y-(long long)b.x*y;
	}
	friend bool operator<(P a,P b){if (a.x^b.x)	return a.x<b.x;return a.y<b.y;}
}a[MAXN];
long long abs2(long long x){if (x>0) return x;return -x;}
int n,h[MAXN];
struct E
{
	int i,j;
	double k;
	E(){}
	E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}
	friend bool operator<(E a,E b){return a.k<b.k;	}
}e[MAXN*MAXN/2];
long long S2(P A,P B,P C)
{
	return abs2(A*B+B*C+C*A);
}
int size=0;
int main()
{
	freopen("land.in","r",stdin);
	freopen("land.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
	long long ans=(long long)1<<60;
	/*
	for (int i=1;i<=n-2;i++)
		for (int j=i+1;j<n;j++)
			for (int k=j+1;k<=n;k++)
				ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i]));
	*/

	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) h[i]=i;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++)
		{
			e[++size]=E(i,j);
		}

	sort(e+1,e+1+size);

	for (int i=1;i<=size&&ans;i++)
	{
		if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));
		if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));
		swap(a[h[e[i].i]],a[h[e[i].j]]);
		swap(h[e[i].i],h[e[i].j]);
	}

	printf("%.2lf",(double)ans/2);
	return 0;
}