追分大作战Final·补♂课第110场

24 Dec 2017 5104字 18分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

Overview 小标题上的链接给出了可供参考的外部地址。这套题的前身是补 ♂ 课第 110 场冰淇淋强迫症标程，所有代码的 main 函数都只由 for 语句构成，其余部分也尽可能地用 for 语句缩短代码。实际写代码的时候不要模仿。

算术运算

出这道题的目的是让不会读文件末的同学学习一下应对多组数据的处理方法。

#include<stdio.h>
long long a,b;
int main()
{
	for(char c; scanf("%lld %c %lld",&a,&c,&b)!=EOF; printf("%lld\n",c=='+'?a+b:a-b));
}

扩展 1：scanf 函数返回值

成功赋值的接收参数的数量（可以为零，在首个接收用参数赋值前匹配失败的情况下），或者若输入在首个接收用参数赋值前发生失败，则为EOF。

扩展 2：EOF

int类型的负值整数常量表达式，通常为-1。因此喜欢压代码量的竞赛选手有时候会喜欢直接使用位取反运算符~，即像下面这样写：while(~scanf(\*...*\)) {}

扩展 3：%c 与%s

%c是非格式化读入，会把空格、换行等空白符也读进来。因此，假如不知道读进来的时候有多少个空格作为间隔符，scanf("%lld %c %lld",&a,&c,&b)通常用scanf("%lld%s%lld",&a,s,&b)代替，此时会跳过空白符，s[0]就是所要的可显字符，使得程序更具鲁棒性。

判断数字个数

输入有空格，要用 gets 整行读入。

#include<stdio.h>
int cnt[255]= {0};
int main()
{
	for(char s[1023]; gets(s)!=NULL;)
	{
		for(int i=0; s[i]; ++i)
			++cnt[s[i]];
		for(char i='0'; i<='9'; cnt[i++]=0)
			if(cnt[i])
				printf("%c:%d\n",i,cnt[i]);
	}
}

扩展：gets 函数

char *gets(char *s);//(C11 中移除)
char *gets_s(char *str,rsize_t n);//(C11 起)(可选)

成功时为str，失败时为NULL。（由于返回的是指针类型因此不返回EOF） gets()函数不进行边界检查，从而此函数对缓冲区溢出攻击极度脆弱。无法安全使用它（除非程序运行的环境限定能出现在stdin上的内容）。因此，此函数在C99的第三次勘误中被弃用，而在C11标准发布时被移除。推荐的替代品是fgets()和gets_s()，详见参考链接。

另外一种字符处理类型的题目的思路

把单个字符逐个getchar进来，遇到间隔符'\n'的时候开始实际处理。

#include<stdio.h>
int cnt[255]= {0};
int main()
{
	for(int ch; (ch=getchar())!=EOF; ++cnt[ch])
		if(ch=='\n')
			for(char i='0'; i<='9'; cnt[i++]=0)
				if(cnt[i])
					printf("%c:%d\n",i,cnt[i]);
}

扩展：getchar

定义于头文件<stdio.h>，成功时为获得的字符，失败时为EOF。等价于getc(stdin)。返回值类型是int，因为要区分读入的char值和int类型的EOF。

素数回文数的个数

判断素数和回文数的常见套路。

#include<stdio.h>
int isPrime(int n)
{
	for(int i=2; i*i<=n; ++i)
		if(n%i==0)
			return 0;
	return 1;
}
int isPalindromic(int n)
{
	int m=0;
	for(int t=n; t; t/=10)
		m=m*10+t%10;
	return m==n;
}
int main()
{
	for(int n,ans; scanf("%d",&n)!=EOF; printf("%d\n",ans))
		for(int i=11+(ans=0); i<=n; ++i)
			if(isPrime(i)&&isPalindromic(i))
				++ans;
}

另一种较优的解法

手动构造回文数，判断是否为素数。考虑有多次询问，可以先生成一张回文素数表，对于每次询问直接查表。此外，下述代码中表恰好是从小到大存储的，因此可以直接二分查找第一个比 n 小的数的下标作为答案，在程序的执行效率上会有更优的表现，请自己实现。

#include<stdio.h>
int len=0,a[127]= {0};
int isPrime(int n)
{
	for(int i=2; i*i<=n; ++i)
		if(n%i==0)
			return 0;
	return 1;
}
int main()
{
	for(int i=11; i<=99; i+=11)
		if(isPrime(i))
			a[len++]=i;
	for(int i=1; i<=9; ++i)
		for(int j=0; j<=90; j+=10)
			if(isPrime(i*101+j))
				a[len++]=i*101+j;
	for(int n,ans; scanf("%d",&n)!=EOF; printf("%d\n",ans))
		for(int i=ans=0; i!=len; ++i)
			if(n>=a[i])
				++ans;
}

扩号匹配

很推荐一做的题目，多个括号之间如何确定配对关系？从待匹配的地址出发，遇到右括号就将计数器加一，遇到左括号把计数器减一，当计数器的值为 0 的时候就是成功匹配了。很有益的思想。

#include<stdio.h>
char s[1023];
int pipei(int p)
{
	for(int cnt=1; cnt;)
	{
		if(s[--p]=='2')++cnt;
		else --cnt;
	}
	return p;
}
int main()
{
	for(int n; scanf("%d%s",&n,s)!=EOF; printf("\n"))
		for(int i=0; i!=n; ++i)
			if(s[i]=='2')
				printf("%d ",pipei(i)+1);
}

加减乘除

由于有多组数据，因此不可以直接读三个数据进来。先读进来前两个元素，然后再判断需不需要读第三个。

#include<stdio.h>
int a,b;
int main()
{
	for(char c; scanf("%d %c",&a,&c)!=EOF;)
	{
		if(c=='!')
		{
			for(int i=b=1; i<=a; b*=i++);
			printf("%d\n",b);
			continue;
		}
		scanf("%d",&b);
		if(!b&&(c=='/'||c=='%'))
			printf("error\n");
		else
			printf("%d\n",
				   c=='+'?a+b:
				   c=='-'?a-b:
				   c=='*'?a*b:
				   c=='/'?a/b:a%b);
	}
}

期末考试第二题——比较数字个数

由于NULL的值通常是 0，因此像下面这样直接省略也可以。

#include<stdio.h>
int main()
{
	for(char flag,s[2][128],cnt[256]; gets(s[0]),gets(s[1]); printf("%d\n",!flag))
	{
		for(int i=flag=0; i!=256; cnt[i++]=0);
		for(int i=0; s[1][i]; ++i)
			++cnt[s[1][i]];
		for(int i=0; s[0][i]; ++i)
			if('a'<=s[0][i]&&s[0][i]<='z')
				if(--cnt[s[0][i]]<0)
					flag=1;
	}
}

期末考试第三题——最大最小数之差

#include<stdio.h>
long long p,q,len,a[31];
int main()
{
	for(char s[31]; gets(s); printf("%lld\n",q-p))
	{
		for(int i=p=q=len=0; s[i]; ++i)
		{
			if('0'<=s[i]&&s[i]<='9')
				a[len++]=s[i]-'0';
			if('a'<=s[i]&&s[i]<='f')
				a[len++]=s[i]-'a'+10;
			if('A'<=s[i]&&s[i]<='F')
				a[len++]=s[i]-'A'+10;
			for(int j=0,t; j!=len; ++j)//使插入元素有序
				if(a[j]>a[len-1])
				{
					t=a[j];
					a[j]=a[len-1];
					a[len-1]=t;
				}
		}
		for(int i=0; i!=len; ++i)
			p=p*16+a[i];
		for(int i=len-1; i!=-1; --i)
			q=q*16+a[i];
	}
}

扩展：不定长的数据

虽然 C 语言有malloc和free机制，但是在在线测试中不够实用。在实战中，用一个大小足够大的数组和一个 siz 标记来代替是更实用的选择。

#define N 100009
int a[N],siz=0;
a[siz++]=1;//向a尾部加一个1
--siz;//去掉a尾部的元素
a[--siz];

停车场收费

灵活使用条件表达式。

#include<stdio.h>
int main()
{
	for(double t; scanf("%lf",&t)!=EOF; printf("%.2lf\n",t<3?5:t>20.5?40:2*t-1));
}

Inserting Something in Strings

#include<stdio.h>
int main()
{
	for(char pos,s[2][15]; scanf("%s%s",s[0],s[1])!=EOF; printf("\n"))
	{
		for(int i=pos=0; s[0][i]; ++i)
			if(s[0][pos]<s[0][i])
				pos=i;
		for(int i=0; s[0][i]; ++i)
			printf("%c%s",s[0][i],i==pos?s[1]:"");
	}
}

有未知数的表达式

递归求表达式的应用，熟悉栈结构也可以用之代替。理解运算符的结合顺序，递归展开时从低到高展开。思考题：如果表达式中有括号怎么处理？（可参考「括号匹配」这一题）

#include<stdio.h>
#include<string.h>
#include<math.h>
char s[31];
int work(int l,int r)
{
	for(int i=r; i>=l; --i)
	{
		if(s[i]=='+')
			return work(l,i-1)+work(i+1,r);
		if(s[i]=='-')
			return work(l,i-1)-work(i+1,r);
	}
	for(int i=l,b=0; i<=r; ++i)
	{
		if('0'>s[i]||s[i]>'9')
		{
			if(i==l)break;
			return b*work(i,r);
		}
		b=b*10+s[i]-'0';
		if(i==r)return b;
	}
	for(int i=r; i>=l; --i)
		if(s[i]=='^')
			return pow(work(l,i-1),work(i+1,r));
	return l>r?0:3;
}
int main()
{
	for(; scanf("%s",s)!=EOF; printf("%d\n",work(0,strlen(s)-1)));
}