2018-2-6测试(COCI2014/2015 Contest#5)

时间:2022-02-06 03:35:15

T1:FUNGHI(1s,32M,50pts)得分:50

题意:给你8个数组成一个环,要你求出其中连续的4个数,让它们的和最大

题解:暴力求出每一连续4个数之和,比较一下就好

标签:模拟

C++ Code:

#include<cstdio>
using namespace std;
int s[10],ans,maxn;
int main(){
	freopen("FUNGHI.in","r",stdin);
	freopen("FUNGHI.out","w",stdout);
	for (int i=0;i<8;i++)scanf("%d",&s[i]);
	for (int i=0;i<8;i++){
		ans=0;
		for (int j=0;j<4;j++)ans+=s[(i+j)%8];
		if (ans>maxn)maxn=ans;
	}
	printf("%d\n",maxn);
	return 0;
}

 

T2:ZMIJA(1s,32M,80pts)得分:80

题意:给你一个n*m的矩阵,有一条蛇在左下角(用“Z”表示),有一些苹果(用“J”表示)和空格(用“.”表示)。有两个操作,A:让蛇向它面朝的方向走一步(不可以走出矩阵),B:让蛇向上走一步,并且转向180°(左变右,右变左)。现在它面向右,让你求出最小操作几次使得蛇吃完所有的苹果。

题解:分析每一行,如果((n-i+1)&1)(在从下到上的奇数行,即面向右),为了吃完这一行所有苹果,到这一行时必须到这一行最左边的苹果的左边(或相同);如果是偶数行,就必须到这一行最右边的苹果的右边(或相同)。满足这就可以保证吃完苹果。为了操作数最少,如果可以的话就刚好到达最左或右的苹果(即在吃完苹果的前提下不多走路)。注意,如果上面几行是空行,就不必上去,不然操作数会多

标签:模拟,贪心

C++ Code:

#include<cstdio>
using namespace std;
int n,m,ans,tmp,x=1,tmp6;
char ch[1010];
bool s[1010][1010],pd,yes=1;
int main(){
	freopen("ZMIJA.in","r",stdin);
	freopen("ZMIJA.out","w",stdout); 
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%s",ch);
		pd=1;
		for (int j=1;j<=m;j++){
			s[i][j]=ch[j-1]=='J';
			if (s[i][j])pd=0;
		}
		if (pd&&yes)tmp6++;
			else yes=0;
	}
	for (int i=n;i;i--){
		if ((n-i+1)&1){
			tmp=x;
			for (int j=x+1;j<=m;j++)if (s[i][j])tmp=j;
			ans+=tmp-x;
			x=tmp;
		}else{
			tmp=x;
			for (int j=x-1;j;j--)if (s[i][j])tmp=j;
			ans+=x-tmp;
			x=tmp;
		}
		if (i==1)break;
		if ((n-i)&1){
			for (int j=1;j<x;j++)if (s[i-1][j]){
				ans+=x-j;
				x=j;
				break;
			}
		}else{
			for (int j=m;j>x;j--)if (s[i-1][j]){
				ans+=j-x;
				x=j;
				break;
			}
		}
		ans++;
	}
	if (yes){
		puts("0");
		return 0;
	}
	printf("%d\n",ans-tmp6);
	return 0;
}

 

T3:TRAKTOR(2s,32M,100pts)得分:100

题意:平面上有n个整点,问最小的i满足前i个点中已经出现k点共线(这里的线只可以平行与坐标轴或者成45°),无解输出-1

题解:维护4个数组,分别记录这一行、这一列、左上到右下的对角线、左下到右上的对角线,每读进一个蘑菇的坐标就维护一下这些数组,看最早什么时候值大于等于k

标签:模拟,数论

C++ Code:

#include<cstdio>
using namespace std;
int n,k;
int h[100010],l[100010],x[200020],y[200020];
int main(){
	freopen("TRAKTOR.in","r",stdin);
	freopen("TRAKTOR.out","w",stdout);
	scanf("%d%d",&n,&k);
	if (n<1){
		puts("-1");
		return 0;
	}
	if (k==0){
		puts("0");
		return 0;
	}
	for (int i=1;i<=n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		h[a]++;
		l[b]++;
		if ((h[a]>=k)||(l[b]>=k)){
			printf("%d\n",i);
			return 0;
		}
		x[a+b]++;
		y[a-b+100010]++;
		if ((x[a+b]>=k)||(y[a-b+100010]>=k)){
			printf("%d\n",i);
			return 0;
		}
	}
	puts("-1"); 
	return 0;
}

  

T4:ZGODAN(1s,32M,120pts)得分:120

题意:给你一个数N(N≤10^1000),询问离它最近的美丽数(美丽数定义:这个数中,任意两个相邻的数字奇偶性不同),如果有两个美丽数距离N一样,先输出小的,再输出大的

题解:发现找到第一个奇偶性不同的数,然后把它+1或-1。如果+1,后面的数为0101……或1010……(根据奇偶性决定);如果-1,后面的数为8989……或9898……(根据奇偶性决定)。然后判断一下这两个和原数差的大小即可。注意,如果+1或-1后不在0~9内就不用判断,因为这样会改变前一个数的奇偶性,差一定比另一个数大

标签:数论,高精度

C++ Code:

#include<cstdio>
#include<cstring>
using namespace std;
char s[1010];
bool pd=0,bb=1,cc=1;
int a[1010],b[1010],c[1010],d[1010],e[1010],len;
void jian(int *a,int *b,int *c){
	int tmp=0;
	for (int i=len-1;i;i--){
		c[i]=a[i]-b[i]-tmp;
		if (c[i]<0)c[i]+=10,tmp=1;
			else tmp=0;
	}
}
int bj(int *a,int *b){
	for (int i=0;i<len;i++)if (a[i]!=b[i])if (a[i]<b[i])return 0;else return 1;
	return -1;
}
void work(){
	jian(a,b,d);
	jian(c,a,e);
	int tmp=bj(d,e);
//			for (int i=0;i<len;i++)printf("%d",b[i]);
//			putchar(' ');
//			for (int i=0;i<len;i++)printf("%d",c[i]);
//			putchar('\n');
	if (tmp==1){
		for (int i=0;i<len;i++)printf("%d",c[i]);
		putchar('\n');
	}else{
		if (tmp==0){
			for (int i=0;i<len;i++)printf("%d",b[i]);
			putchar('\n');
		}else{
			for (int i=0;i<len;i++)printf("%d",b[i]);
			putchar(' ');
			for (int i=0;i<len;i++)printf("%d",c[i]);
			putchar('\n');
		}
	}
	
	return;
}
int main(){
	freopen("ZGODAN.in","r",stdin);
	freopen("ZGODAN.out","w",stdout);
	scanf("%s",s);len=strlen(s);
	for (int i=0;i<len;i++)a[i]=s[i]^48;
	b[0]=c[0]=a[0];
	for (int i=1;i<len;i++){
		if (pd){
			if (bb){
				if (b[i-1]&1)b[i]=8;
					else b[i]=9;
			}
			if (cc){
				if (c[i-1]&1)c[i]=0;
					else c[i]=1;
			}
		}
		if (!pd){
			b[i]=c[i]=a[i];
			if ((a[i]&1)==(a[i-1]&1)){
				pd=1;
				b[i]=a[i]-1;
				c[i]=a[i]+1;
				if (b[i]==-1)bb=0;
				if (c[i]==10)cc=0;
			}
		}
	}
	if (!bb){
		for (int i=0;i<len;i++)printf("%d",c[i]);
		putchar('\n');
		return 0;
	}
	if (!cc){
		for (int i=0;i<len;i++)printf("%d",b[i]);
		putchar('\n');
		return 0;
	}
	work();
	return 0;
}

  

T5:JABUKE(2s,128M,140pts)得分81

题意:给你一个n*m的矩阵,其中有苹果树(用“x”表示)和空地(用“.”表示),有G(1<=G<=10^5)年,每年会掉一个苹果,要你求出每年距该苹果最近的一棵苹果树的距离的平方,每个苹果第二年都会变成苹果树

题解:用p[i][j]存第j列到第i行中最近的苹果树的距离,每发现一棵苹果数就维护一下p数组(就维护这一行的p)。针对每个询问,枚举每一行,看离询问的那一列最近的距离(因为更远的苹果树到该点距离一定比现在的远),更新答案。

标签:数论,贪心

C++ Code:

原:

#include<cstdio>
using namespace std;
int n,m,num,T,minn,ans;
char ch[600];
int s[250100][2];
int main(){
	freopen("JABUKE.in","r",stdin);
	freopen("JABUKE.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%s",ch);
		for (int j=1;j<=m;j++)if (ch[j-1]=='x')s[++num][0]=i,s[num][1]=j;
	}
	scanf("%d",&T);
	while (T--){
		int a,b;
		scanf("%d%d",&a,&b);
		s[++num][0]=a;s[num][1]=b;
		minn=2147483647;
		for (int i=1;i<num;i++){
			ans=0;
			int x=s[i][0]-s[num][0],y=s[i][1]-s[num][1];
			ans=x*x+y*y;
			if (ans<minn)minn=ans;
		}
		printf("%d\n",minn);
	}
	return 0;
}

正确:

#include<cstdio>
using namespace std;
int n,m,num,T,minn,ans,x,y;
char ch[600];
int s[250100][2],p[510][510];
inline int abs(int a){return a>0?a:-a;}
int main(){
	freopen("JABUKE.in","r",stdin);
	freopen("JABUKE.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%s",ch);
		for (int j=1;j<=m;j++)p[i][j]=600;
		for (int j=1;j<=m;j++){
			if (ch[j-1]=='x'){
				x=i,y=j;
				for (int l=1;l<=m;l++){
					int a=abs(y-l);
					if (p[x][l]>a)p[x][l]=a;
				}
			}
		}
	}
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&x,&y);
		minn=2147483647;
		for (int i=1;i<=n;i++){
			int a=p[i][y],b=i-x;
			ans=a*a+b*b;
			if (ans<minn)minn=ans;
			if (!minn)break;
		}
		for (int i=1;i<=m;i++){
			int a=abs(y-i);
			if (p[x][i]>a)p[x][i]=a;
		}
		printf("%d\n",minn);
	}
	return 0;
}

 

T6:DIVLJAK(4s,768M,160pts)得分:50

题意:给你多个模式串,要求支持动态增加询问串和询问某个模式串是多少询问串的子串

题解:

标签:

C++ Code:

原:

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,s[100010];
string p[100010],tmp;
int main(){
	ios::sync_with_stdio(false);
	freopen("DIVLJAK.in","r",stdin);
	freopen("DIVLJAK.out","w",stdout);
	cin >> n;
	for (int i=1;i<=n;i++)cin >> p[i];
	cin >> m;
	while (m--){
		int op,o;
		cin >> op;
		if (op==1){
			cin >> tmp;
			for (int i=1;i<=n;i++)if (tmp.find(p[i])!=-1)s[i]++;
//			printf("Debug:%d\n",tmp.find(p[1]));
		}else{
			cin >> o;
			cout << s[o] << endl;
		}
	}
	return 0;
}

正确:

 略