CF #269 DIV2 A,B,C,D_html/css_WEB-ITnose

Elephant"，否则输出"

Bear"；

<pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <set>#include <map>#include <list>#include <queue>#include <stack>#include <deque>#include <vector>#include <bitset>#include <cmath>#include <utility>#define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;int main(){	int a[6],flag;	//re;wr;	while(~scanf("%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5]))	{		flag=0;		sort(a,a+6);		if(a[0]==a[1]&&a[2]==a[1]&&a[3]==a[2])			flag=1;		if(a[1]==a[2]&&a[2]==a[3]&&a[3]==a[4])			flag=2;		if(a[2]==a[3]&&a[3]==a[4]&&a[4]==a[5])			flag=3;		if(flag==0)		{			puts("Alien");			continue;		}		if(flag==1)		{			if(a[4]==a[5])			{				puts("Elephant");				continue;			}			else			{				puts("Bear");				continue;			}		}		else if(flag==2)		{			if(a[0]==a[5])			{				puts("Elephant");				continue;			}			else			{				puts("Bear");				continue;			}		}		else		{			if(a[0]==a[1])			{				puts("Elephant");				continue;			}			else			{				puts("Bear");				continue;			}		}	}	return 0;}

http://codeforces.com/contest/471/problem/B

解题思路：给你一个序列，问是否有三种不同的方法使它们按非减序排序，显然只有有2个相等的元素集合数大于等于2时或者有3个相等的元素的集合时才有解，有解的时候集合内排序一下，我写的很繁，导致后面的题目没写，整场就跪了

<pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <set>#include <map>#include <list>#include <queue>#include <stack>#include <deque>#include <vector>#include <bitset>#include <cmath>#include <utility>#define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;struct Mask{	int dif;	int id;	friend bool operator <(Mask a,Mask b)	{		if(a.dif!=b.dif)			return a.dif<b.dif;		else			return a.id<b.id;	}};int main(){	int n,m[2005],cnt,i,j;	bool flag;	Mask arr[2005];	//re;wr;	while(~scanf("%d",&n))	{		flag=false;		cnt=0;		memset(m,0,sizeof(m));		for(i=1;i<=n;i++)		{			scanf("%d",&arr[i].dif);			m[arr[i].dif]++;			arr[i].id=i;		}		for(i=0;i<=2000;i++)		{			if(m[i]>2)			{				flag=true;				break;			}			if(m[i]==2)				cnt++;		}		if(flag||cnt>=2)		{			puts("YES");			sort(arr+1,arr+1+n);			if(flag)			{				for(i=1;i<=n;i++)				{					if(m[arr[i].dif]>2)						break;				}				int a=arr[i].id;				int b=arr[i+1].id;				int c=arr[i+2].id;				//cout<<a<<b<<c<<endl;				for(j=1;j<=n;j++)				{					//cout<<j<<endl;					if(j<i||j>i+2)					{						printf("%d%c",arr[j].id,j==n?'\n':' ');					}					else if(i==n-2)					{						printf("%d %d %d\n",a,b,c);						j+=2;					}					else					{						printf("%d %d %d ",a,b,c);						j+=2;					}				}				for(j=1;j<=n;j++)				{					if(j<i||j>i+2)					{						printf("%d%c",arr[j].id,j==n?'\n':' ');					}					else if(i==n-2)					{						printf("%d %d %d\n",b,a,c);						j+=2;					}					else					{						printf("%d %d %d ",b,a,c);						j+=2;					}				}				for(j=1;j<=n;j++)				{					if(j<i||j>i+2)					{						printf("%d%c",arr[j].id,j==n?'\n':' ');					}					else if(i==n-2)					{						printf("%d %d %d\n",c,b,a);						j+=2;					}					else					{						printf("%d %d %d ",c,b,a);						j+=2;					}				}			}			else			{				int f1,f2;				for(i=1;i<=n;i++)					if(m[arr[i].dif]==2)					{						f1=i;						break;					}				for(i=i+2;i<=n;i++)					if(m[arr[i].dif]==2)					{						f2=i;						break;					}				int a=arr[f1].id;				int b=arr[f1+1].id;				int c=arr[f2].id;				int d=arr[f2+1].id;				//cout<<a<<b<<c<<d<<endl;				//cout<<f1<<f2<<endl;				for(i=1;i<=n;i++)				{					if((i<f1||i>f1+1)&&(i<f2||i>f2+1))						printf("%d%c",arr[i].id,i==n?'\n':' ');					else if(i>=f1&&i<=f1+1)					{						printf("%d %d ",a,b);						i+=1;					}					else if(i>=f2&&i<=f2+1)					{						if(f2==n-1)							printf("%d %d\n",c,d);						else							printf("%d %d ",c,d);						i+=1;					}				}				for(i=1;i<=n;i++)				{					if((i<f1||i>f1+1)&&(i<f2||i>f2+1))						printf("%d%c",arr[i].id,i==n?'\n':' ');					else if(i>=f1&&i<=f1+1)					{						printf("%d %d ",a,b);						i+=1;					}					else if(i>=f2&&i<=f2+1)					{						if(f2==n-1)							printf("%d %d\n",d,c);						else							printf("%d %d ",d,c);						i+=1;					}				}				for(i=1;i<=n;i++)				{					if((i<f1||i>f1+1)&&(i<f2||i>f2+1))						printf("%d%c",arr[i].id,i==n?'\n':' ');					else if(i>=f1&&i<=f1+1)					{						printf("%d %d ",b,a);						i+=1;					}					else if(i>=f2&&i<=f2+1)					{						if(f2==n-1)							printf("%d %d\n",c,d);						else							printf("%d %d ",c,d);						i+=1;					}				}			}		}		else		{			puts("NO");			continue;		}	}}

http://codeforces.com/contest/471/problem/C

<pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <set>#include <map>#include <list>#include <queue>#include <stack>#include <deque>#include <vector>#include <bitset>#include <cmath>#include <utility>#define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;LL cal(LL n){	return (3*n+1)*n/2;}LL calc(LL a,LL k,LL n){	return a+(n-1)*k;}int main(){	LL n,ans;	//re;wr;	while(~scanf("%I64d",&n))	{		ans=0;		LL l=0,r=(Maxm<<1),lv;		while(r>=l)		{			LL m=(l+r)>>1;			if(cal(m)<=n)			{				lv=m;				l=m+1;			}			else				r=m-1;		}		for(LL i=1;i<=lv;i++)		{			LL a=cal(i);			if((n-a)%3==0)				ans++;		}		printf("%d\n",ans);	}	return 0;}

<strong>http://codeforces.com/problemset/problem/471/D</strong>

<strong>解题思路：做出两个数列的相邻两项的差分数列，KMP判断短的差分数列在长的差分数列中出现几次即可，特判n=1和w=1的情况</strong>

<strong></strong><pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <set>#include <map>#include <list>#include <queue>#include <stack>#include <deque>#include <vector>#include <bitset>#include <cmath>#include <utility>#define Maxn 100005#define Maxm 1000005#define lowbit(x) x&(-x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define PI acos(-1.0)#define make_pair MP#define LL long long #define Inf (1LL<<62)#define inf 0x3f3f3f3f#define re freopen("in.txt","r",stdin)#define wr freopen("out.txt","w",stdout)using namespace std;int next[Maxn<<1];void get_next(int *arr,int len){	int j=0,k=-1;	next[0]=-1;	while(j<=len)	{		if(k==-1||arr[j]==arr[k])		{			j++;k++;			next[j]=k;		}		else			k=next[k];	}}int kmp(int *a,int *b,int l1,int l2){	get_next(a,l1);	get_next(b,l2);	int i=0,j=0,ans=0;	while(i<l1)	{		if(j==-1||a[i]==b[j])		{			i++;j++;		}		else			j=next[j];		if(j==l2)		{			j=next[j];			ans++;		}	}	return ans;}int a[Maxn<<1],b[Maxn<<1],ca[Maxn<<1],cb[Maxn<<1];int main(){	int m,n;	//re;wr;	while(~scanf("%d%d",&m,&n))	{		memset(a,0,sizeof(a));		memset(b,0,sizeof(b));		memset(ca,0,sizeof(ca));		memset(cb,0,sizeof(cb));		for(int i=0;i<m;i++)		{			scanf("%d",a+i);			if(i>=1)				ca[i-1]=a[i]-a[i-1];		}		for(int i=0;i<n;i++)		{			scanf("%d",b+i);			if(i>=1)				cb[i-1]=b[i]-b[i-1];		}		if(m==1||n==1)		{			printf("%d\n",max(m,n));			continue;		}		printf("%d\n",m>=n?kmp(ca,cb,m-1,n-1):kmp(cb,ca,n-1,m-1));	}	return 0;}