NOIP第十五届全国青少年信息学奥林匹克联赛初赛试题[2009普及组]

第21题

小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有______ 种。

第22题

有如下的一段程序：

1. a=1;

2. b=a;

3. d=-a;

4. e=a+d;

5. c=2*d;

6. f=b+e-d;

7. g=a*f+c;

现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 _______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC 引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

第23题

#include<stdio.h>

int a,b;

int work(int a,int b){

	if (a%b)

	return work(b,a%b);

	return b;

}

int main()
{

	scanf("%d%d",&a,&b);

	printf("%d\n",work(a,b));

	return 0;

}

输入：20 12

输出：_____

第24题

#include <stdio.h>
int main()
{
	int a[3],b[3];
	int i,j,tmp;
	for (i=0;i<3;i++)
	scanf("%d",&b[i]);
	for (i=0;i<3;i++)
	{
		a[i]=0; 
		for (j=0;j<=i;j++)
		{
			a[i]+=b[j];
			b[a[i]%3]+=a[j];
		}
	}
	tmp=1;
	for (i=0;i<3;i++)
	{
		a[i]%=10;
		b[i]%=10;
		tmp*=a[i]+b[i];
	}
	printf("%d\n",tmp);
	return 0;
}

输入： 2 3 5 

输出： _______

第25题

#include<stdio.h>
const int c=2009;
int main()
{
	int n,p,s,i,j,t;
	scanf("%d%d",&n,&p);
	s=0;t=1;
	for(i=1;i<=n;i++)
	{
		t=t*p%c;
		for(j=1;j<=i;j++)
		s=(s+t)%c;
	}
	printf("%d\n",s);
	return 0;
}

输入： 11 2 

输出： ______

第26题

#include<stdio.h>
#include<string.h>
#define maxn 50
void getnext(char str[])
{
	int l=strlen(str),i,j,k,temp; 
	k=l-2;
	while(k>=0&&str[k]>str[k+1]) k--;
	i=k+1;
	while(i<l&&str[i]>str[k]) i++;
	temp=str[k];
	str[k]=str[i-1];
	str[i-1]=temp;
	for(i=l-1;i>k;i--)
	for(j=k+1;j<i;j++)
	if(str[j]>str[j+1])
	{
		temp=str[j];
		str[j]=str[j+1];
		str[j+1]=temp;
	}
	return ;
}
int main()
{
	char a[maxn];
	int n;
	scanf("%s %d",a,&n);
	while(n>0)
	{
		getnext(a);
		n--;
	}
	printf("%s\n",a);
	return 0;
}

输入： NOIP 3 

输出： ______

第27题

（最大连续子段和）给出一个数列（元素个数不多于 100），数列元素均为负整数、 正整数、 0。请找出数列中的一个连续子数列， 使得这个子数列中包含的所有元素之和最大， 在和最大的前提下还要求该子数列包含的元素个数最多， 并输出这个最大和以及该连续子数 列中元素的个数。例如数列为 4，-5，3，2， 4 时，输出 9 和 3；数列为 1 2 3 -5 0 7 8 时，输 出 16 和 7。

#include <stdio.h>
int a[101];
int n,i,ans,len,tmp,beg;
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) 
	scanf("%d",&a[i]);
	tmp=0;
	ans=0;
	len=0;
	beg= ① ;
	for (i=1;i<=n;i++)
	{
	if (tmp+a[i]>ans)
	{
		ans=tmp+a[i];
		len=i-beg;
	}
	else if ( ②&&i-beg>len)
		len=i-beg;
	if (tmp+a[i] ③ )
	{
		beg= ④ ;
		tmp=0;
	}
	else
		⑤ ;
	}
printf("%d %d\n",ans,len);
return 0;
}

第28题

(国王放置 ) 在 n*m 的棋盘上放置 k 个国王， 要求 k 个国王互相不攻击， 有多少种不同 的 放 置 方 法 。 假 设 国 王 放 置 在 第 (x,y) 格 ， 国 王 的 攻 击 的 区 域 是 :(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1) 。读入三个数 n,m,k，输出答案。题目 利用回溯法求解。棋盘行标号为 0~n-1，列标号为 0~m-1。

#include <stdio.h>
#include <string.h>
int n,m,k,ans;
int hash[5][5];
void work(int x,int y,int tot)
{
	int i,j;
	if (tot==k)
	{
		ans++;
		return;
	}
do
{
	while (hash[x][y])
	{
		y++; 
		if (y==m)
		{
			x++;
			y= ① ;
		}
		if (x==n)
		return;
	}
	for (i=x-1;i<=x+1;i++)
	if (i>=0&&i<n)
		for (j=y-1;j<=y+1;j++)
	if (j>=0&&j<m)
		② ;
	③ ;
	for (i=x-1;i<=x+1;i++)
	if (i>=0&&i<n)
	for (j=y-1;j<=y+1;j++)
	if (j>=0&&j<m)
		④ ;
	y++;
	if (y==m)
	{
		x++;
		y=0;
	}
	if (x==n)
	return;
}
while (1);
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	ans=0;
	memset(hash,0,sizeof(hash));
	⑤ ;
	printf("%d\n",ans);
	return 0;
}