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

第21题

拓扑排序是指将有向无 环图 G中的所有顶点排成一个线性序列，使得图中任意一对顶 点 u 和 v，若 ∈E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓扑序 列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为 ______。

第22题

某个国家的钱币面值有 1, 7, 7 ², 7 ³共计四种，如果要用现金付清 10015元的货物， 假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱 币。

第23题

#include <iostream>
using namespace std;
int a,b;
int work(int a,int b)
{
	if (a%b)
	return work(b,a%b);
	return b;
}
int main()
{
	cin >> a >> b;
	cout << work(a,b) << endl;
	return 0;
}

输入： 123 321 

输出： _________

第24题

#include <iostream>
using namespace std;
int main()
{
	int a[4],b[4];
	int i,j,tmp;
	for (i=0;i<4;i++)
	cin >> b[i];
	for (i=0;i<4;i++) 
	{
		a[i]=0;
		for (j=0;j<=i;j++)
		{
			a[i]+=b[j];
			b[a[i]%4]+=a[j];
		}
	}
	tmp=1;
	for (i=0;i<4;i++) 
	{
		a[i]%=10;
		b[i]%=10;
		tmp*=a[i]+b[i];
	}
	cout << tmp << endl;
	return 0;
}

输入： 2 3 5 7 

输出： _________

第25题

#include <iostream>
using namespace std;
const int maxn=50;
const int y=2009;
int main()
{
	int n,c[maxn][maxn],i,j,s=0;
	cin >> n; 
	c[0][0]=1;
	for(i=1;i<=n;i++)
	{
		c[i][0]=1;
		for(j=1;j<i;j++)
		c[i][j]=c[i-1][j-1]+c[i-1][j];
		c[i][i]=1;
	} 
	for(i=0;i<=n;i++)
	s=(s+c[n][i])%y;
	cout << s << endl;
	return 0;
}

输入： 17 

输出:_______

第26题

#include <iostream>
using namespace std;
int main()
{
	int n,m,i,j,p,k;
	int a[100],b[100];
	cin >> n >> m;
	a[0]=n;
	i=0;
	p=0;
	k=0;
	do
	{
		for (j=0;j<i;j++)
		if (a[i]==a[j])
		{
			p=1;
			k=j;
			break;
		}
		if (p)
		break;
		b[i]=a[i]/m;
		a[i+1]=a[i]%m*10;
		i++;
	}while (a[i]!=0);
	cout << b[0] << ".";
	for (j=1; j<k; j++)
	cout << b[j];
	if (p)
		cout << "(";
	for (j=k;j<i;j++)
	cout << b[j];
	if (p)
	cout << ")";
	cout << endl; 
	return 0;
}

输入： 5 13 

输出： _________

第27题

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

#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg,end;
int main()
{
	cin >> n;
	for (i=1;i<=n;i++)
	cin >> 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
		⑤ ;
	}
	cout << ans << " " << len << endl; 
	return 0;
}

第28题

( 寻找等差数列 ) 有一些长度相等的等差数列（数列中每个数都为 0~59 的整数），设 长度均为 L，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先， L 最大可能为多大？先读入一个数 n（1<=n<=60），再读入 n 个数，代表打乱后的数。输出等 差数列最大可能长度 L。

#include <iostream>
using namespace std;
int hash[60];
int n, x, ans, maxnum;
int work(int now) 
{
	int first, second, delta, i;
	int ok;
	while ( ① && !hash[now])
	++now;
	if (now > maxnum)
		return 1;
	first = now;
	for (second = first; second <= maxnum; second++)
	if (hash[second]) 
	{
		delta = ② ;
		if (first + delta * ③ > maxnum)
		break;
		if (delta == 0)
			ok = ( ④ );
		else{
		ok = 1;
		for (i = 0; i < ans; i++) 
		ok = ⑤ && (hash[first+delta*i]);
		} 
		if (ok)
		{
			for (i = 0; i < ans; i++)
			hash[first+delta*i]--;
			if (work(first))
			return 1;
			for (i = 0; i < ans; i++)
			hash[first+delta*i]++;
		}
	}
	return 0;
}
int main()
{ 
	int i;
	memset(hash, 0, sizeof(hash));
	cin >> n;
	maxnum = 0;
	for (i = 0; i < n; i++){
		cin >> x;
		hash[x]++;
		if (x > maxnum)
		maxnum = x;
	}
	for (ans = n; ans >= 1; ans--)
	if ( n%ans==0 && ⑥ ) {
		cout << ans << endl;
		break;
	}
	return 0;
}