博客

由于前半个学期有各种各样的课，没有多少时间刷多少题。这周做了两道基础题目，不过还是得到了不少wa……

第一题是UVa的401 palindrome

这道题不仅要判断回文串，还要判断题目里面自己定义的自己跟自己成镜像关系。所谓镜像关系就是像A，如果把A反过来看，还是A。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

char firstmstring[]={'A','E','H','I','J','L','M','O','S','T','U','V','W','X','Y','Z','1','2','3','5','8'};
char secondmstring[]={'A','3','H','I','L','J','M','O','2','T','U','V','W','X','Y','5','1','S','E','Z','8',};

int ispalindrom(char *A,int n){
	int isp=1;
	for(int i=0;i<=n/2+1;++i){
		if(A[i]!=A[n-i]){isp=0;break;}
	}
	return isp;
}

int ismstring(char *A,int n){
	int ism=1;
	for(int i=0;i<=n/2+1;++i){
		int t;
		int have=0;
		for(t=0;t<=20;++t){
			if(A[i]==firstmstring[t]){have=1;break;}
		}
		if(!have)return 0;
		if(A[n-i]!=secondmstring[t]){ism=0;break;}
	}
	return ism;
}

int main(){
	char A[25];
	while(scanf("%s",A)!=EOF){
		int a,b;
		a=ispalindrom(A,strlen(A)-1);
		b=ismstring(A,strlen(A)-1);
		if(!a&&!b){cout<<A<<" -- is not a palindrome."<<endl<<endl;continue;}
		if(a&&!b){cout<<A<<" -- is a regular palindrome."<<endl<<endl;continue;}
		if(!a&&b){cout<<A<<" -- is a mirrored string."<<endl<<endl;continue;}
		if(a&&b){cout<<A<<" -- is a mirrored palindrome."<<endl<<endl;continue;}
	}
	return 0;
}

这段代码的问题是在判断ismstring中会出问题。比如只输入一个A，这个函数就错了。原因是循环终止的条件不对。应当改成n/2。

另外，这个算法的效率也是很低的。

这周训练的第二题是大数据运算

424 integer inquiry

每个数据最大可以到100位，数据最多可以有100个连加。所以必定不能用基本数据类型

对于输入，直接用整形的话不好中断（怎么让程序知道按下回车以后输入一个数就结束了），所以输入用的字符型。C++中字符之中可以进行加减运算，是ASCII码的加减。

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int main(){
	char a[10000];
	int s[10000];
	memset(s,0,sizeof(s));
	int tot=0;
	while(scanf("%s",a)){
		int l=strlen(a);
		if((l-1)==0&&a[0]=='0')break;
		int j=0;
		int add=0;
		l-=1;
		while(l>=0){
			s[j]=add+s[j]+(a[l]-'0');
			add=0;
			if(s[j]>=10){
				add+=(s[j])/10;
				s[j]%=10;
			}
			l--;
			j++;
		}
		s[j]+=add;        //第一遍提交时为s[j]=add;
		tot=tot>j?tot:j;  //第一遍提交时为tot=j;
	}
	int st;
	for(st=tot;;st--){
		if(s[st])break;
	}
	for(;st>=0;st--){
		cout<<s[st];
	}
	cout<<endl;
	return 0;
}

第一遍提交的时候忽略了对最高位的特殊处理。导致了答案错误，比如输入999和99,会输出198,。

另外发现了一个问题，在Cfree中可以使用如tot>?=j这种运算符，表示tot等于tot与j中较大的一个，但是在uva中提交的时候就出现了编译错误。