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

第21题

LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编 码词典， 如果在编码的过程中遇到一个新的词条， 则该词条及一个新的编码会被追加到词典 中，并用于后继信息的编码。 举例说明，考虑一个待编码的信息串：“ xyx yy yy xyx ”。初始词典只有 3 个条目， 第一个为 x,编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串“ xyx”的 编码为 1-2-1 （其中 -为编码分隔符），加上后面的一个空格就是 1-2-1-3 。但由于有了一个 空格，我们就知道前面的“ xyx”是一个单词，而由于该单词没有在词典中，我们就可以自 适应的把这个词条添加到词典里，编码为 4，然后按照新的词典对后继信息进行编码，以此 类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4 。 我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础 词典就可以完成对该序列的完全恢复。 解码过程是编码过程的逆操作。 现在已知初始词典的 3 个条目如上述，接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6 ，则解码 后的信息串是” ______________________________________________________________ ”。

第22题

无向图 G 有 7 个顶点，若不存在奇数条边构成的简单回路，则它至多有 __________ 条 边。

第23题

记 T 为一队列初始为空现有 n 个总和不超过 32 的正整数依次入队如果无论这些数具 体为何值都能找到一种出队的方式使得存在某个时刻队列 T 中的数之和恰好为 9 那么 n 的最小值是 ________________。

第24题

#include <stdio.h>
#define SIZE 10
int main() 
{
	int data[SIZE], i, j, cnt, n, m;// 定义 // 
	scanf("%d %d\n", &n, &m);// 输入 n 和 m，此处我们输入的是 5 和 2//
	for(i = 1; i <= n; i++)
		scanf("%d", &data[i]);// 再次输入 i 个数 data[1] =96 data[2]=-8 data[3]=0 data[4]=16 data[5]=87//
	for(i = 1; i <= n; i++) 
	{ //n=5//
		cnt = 0;
		for(j = 1; j<= n; j++)//n=5 ，data[1] =96 data[2]=-8 data[3]=0 data[4]= 16
		data[5]=87//
		if ((data[i] < data[j]) || (data[j] == data[i] && j< i))// 如果说 data[i]<data[j] ，或者说{data[j] 等于 data[i] ，同时 j 小于 i
		cnt++;//cnt 的数目加 1// 
		if(cnt == m)// 如果说 cnt 等于 m 等于 2，因为 cnt=2 ，即整个程序运行了两遍，也运行两遍，换句话说，只有恰好运行两遍的数字才能满足题意。假设， data[1]=96 ，与
		data[2]=-8 data[3]=0 data[4]= 16 data[5]=87 //比较大小时， 显然为最大， 不能比其他的数小，不满足条件 data[i] < data[j] ，同样， data[2]=-8 ，比它大的数有 3 个也不满足题意，
		data[3]=0 //比它大的数有 4 个，不合题意 data[4]= 16 ，比它大的数恰恰只有两个，满足题意，为所输出 //
		printf("%d\n", data[i]);// 输出 data[i]//
	}
	getch(); //（此语句在 windows 2000 以上系统用 winTC 编译 C 时需要加入，用以暂停查看屏幕）
	return 0;
}

输入： 5 2 

 96 -8 0 16 87 

输出： ______

第25题

#include <stdio.h>
#define SIZE 100
int main()
{
	int na, nb, a[SIZE], b[SIZE], i, j, k;// 定义 //
	scanf("%d\n", &na);// 输入 5,即 na=5//
	for (i = 1; i <= na; i++)
		scanf("%d", &a[i]);// 输入数字， a[1]=1. a[2]=3 a[3]=5 a[4]=7 a[5]=9//
	scanf("%d\n", &nb);// 输入数字 4//
	for (i = 1; i <= nb; i++)
		scanf("%d", &b[i]);// 同理，输入数字 b[1] =2 b[2] =6 b[3] =10 b[4] =14//
	i=1;
	j=1;
	while ((i <= na) && (j <= nb)) 
	{// 当 i 小于等于 na 时，并且 j 小于等于 nb 时候 //
		if (a[i] <= b[j]) 
		{// 如果说 a[i]大于 b[j]//
			printf("%d ", a[i]);// 输出 a[i]//
			i++;//i 增加 1//
		}
		else {
		printf("%d ", b[j]);// 否则输出 b[j]//
		j++;
		}
	}
	if (i <= na)// 如果 i 小于等于 na//
	for (k = i; k<= na; k++)// 循环 //
	printf("%d ", a[k]); //按照上面的循环条件输出数字 //
	if (j <= nb)
	for (k = j; k<= nb; k++)// 同理 //
	printf ("%d ", b[k]); 
	getch();
	return 0;
}

输入： 5

 1 3 5 7 9 

4 

2 6 10 14 

输出：______

第26题

#include<iostream>
using namespace std;
const int NUM=5;
int r(int n)
{
	 int i;
	 if(n<=NUM)
	 return 0;
	 for(i=1;i<=NUM;i++)
	 if( r(n-i)<0)
	 return i;
	 return -1;
}
int main()
{
	 int n; 
	 cin>>n;
	 cout<<r(n)<<endl;
	 return 0;
}

输入： 16 

输出： ______________ 

第27题

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r[SIZE];
bool map[SIZE][SIZE],found;
bool successful()
{
 int i;
 for(i=1;i<=n;i++)
 if(!map[r[i]][r[i%n+1]])
 return false;
 return true;
}
void swap(int *a,int *b)
{
 int t;
 t=*a;
 *a=*b;
 *b=t;
}
void perm(int left,int right)
{
 int i;
 if(found)
 return ;
 if(left>right)
 { 
 if(successful())
 {
 for(i=1;i<=n;i++)
 cout<<r[i]<<' ';
 found=true;
 }
 return ; 
 }
 for(i=left;i<=right;i++)
 {
 swap(r+left,r+i);
 perm(left+1,right);
 swap(r+left,r+i);
 }
}
int main()
{
 int x,y,i;
 cin>>n>>m;
 memset(map,false,sizeof(map));
 for(i=1;i<=m;i++)
 {
 cin>>x>>y;
 map[x][y]=true;
 map[y][x]=true;
 }
 for(i=1;i<=n;i++)
 r[i]=i;
 found=false;
 perm(1,n);
 if(!found)
 cout<<"No solution!"<<endl; 
 return 0;
}

输入： 9 12 

1 2 

2 3 

3 4 

4 5

5 6

6 1 

1 7

2 7

3 8 

4 8 

5 9 

6 9 

输出： _________

第28题

( 过河问题 ) 在一个月黑风高的夜晚 , 有一群人在河的右岸 , 想通过唯一的一根独木桥走到 河的左岸 . 在伸手不见五指的黑夜里 , 过桥时必须借照灯光来照明 , 不幸的是 , 他们只有一盏灯 . 另外, 独木桥上最多能承受两个人同时经过 , 否则将会坍塌 . 每个人单独过独木桥都需要一定 的时间 , 不同的人要的时间可能不同 . 两个人一起过独木桥时 , 由于只有一盏灯 , 所以需要的时 间是较慢的那个人单独过桥所花费的时间 . 现在输入 N(2<=N<1000)和这 N 个人单独过桥需要 的时间 , 请计算总共最少需要多少时间 , 他们才能全部到达河左岸 . 

例如, 有 3 个人甲、乙、丙 , 他们单独过桥的时间分别为 1、2、4, 则总共最少需要的时 间为 7. 具体方法是 : 甲、乙一起过桥到河的左岸 , 甲单独回到河的右岸将灯带回 , 然后甲、丙 在一起过桥到河的左岸 , 总时间为 2+1+4=7.

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false; 
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
 if(a>b)
 return a;
 else
 return b;
} 
int go(bool stage)
{
 int i,j,num,tmp,ans;
 if(stage==RIGHT_TO_LEFT)
 {
 num=0;
 ans=0;
 for(i=1;i<=n;i++)
 if(pos[i]==RIGHT)
 {
 num++;
 if( hour[i]>ans)
 ans=hour[i];
 }
 if( ① ) 
 return ans;
 ans=INFINITY;
 for(i=1;i<=n-1;i++)
 if(pos[i]==RIGHT) 
 for(j=i+1;j<=n;j++)
 if(pos[j]==RIGHT)
 {
 pos[i]=LEFT;
 pos[j]=LEFT;
 tmp=max(hour[i],hour[j])+ ② ;
 if(tmp<ans)
 ans=tmp;
 pos[i]=RIGHT;
 pos[j]=RIGHT;
 }
 return ans;
 }
 if(stage==LEFT_TO_RIGHT)
 {
 ans=INFINITY;
 for(i=1;i<=n;i++)
 if( ③ )
 {
 pos[i]=RIGHT;
 tmp= ④ ;
 if(tmp<ans)
 ans=tmp;
⑤ ;
 }
 return ans;
 }
 return 0;
}
int main() 
{
 int i;
 cin>>n;
 for(i=1;i<=n;i++)
 {
 cin>>hour[i];
 pos[i]=RIGHT;
 }
 cout<<go[RIGHT_TO_LEFT)<<endl;
 return 0;
}

第29题

（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。 一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在 某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传 递，在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传 递。 

例如，有 5 个烽火台，他们发出信号的代价依次为 1，2，5，6，2，，且 m为 3，则总共最少 花费代价为 4，即由第 2 个和第 5 个烽火台发出信号。

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
 pos[SIZE],home[SIZE],opt[SIZE];
 //hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值
 //pos[i] 表示 opt[i] 在堆 heap中的位置，即 heap[pos[i]]=opt[i]
 //home[i] 表示 heap[i] 在序列 opt 中的位置，即 opt[home[i]]=heap[i]
void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素
{
 int tmp;
 pos[home[i]]=j;
 pos[home[j]]=i; 
 tmp=heap[i];
 head[i]=head[j];
 heap[j]=tmp;
 tmp=home[i];
 home[i]=home[j];
 home[j]=tmp; 
}
void add(int k)// 在堆中插入 opt[k]
{
 int i;
 r++;
 heap[r]= ① ;
 pos[k]=r;
② ;
 i=r;
 while( (i>1) && (heap[i]<heap[i/2]) )
 {
 swap(i,i/2);
 i/=2;
 }
}
void remove(int k)// 在堆中删除 opt[k]
{
 int i,j;
 i=pos[k];
 swap(i,r);;
 r--;
 if(i==r+1)
 return ;
 while( (i>1)&&(heap[i]<heap[i/2]) )
 {
 swap(i,i/2); 
 i/=2;
 }
 while(i+i<=r)
 {
 if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
 j=i+i+1;
 else
③ ;
 if(hea[i]>heap[j])
 {
④ ;
 i=j;
 }
 else
 break;
 }
} 
int main()
{
 int i;
 cin>>n>>m;
 for(i=1;i<=n;i+++)
 cin>>value[i];
 r=0;
 for(i=1;i<=m;i++)
 {
 opt[i]=value[i];
 add(i);
 }
 for(i=m+1;i<=n;i++)
 { 
 opt[i]= ⑤ ;
 remove( ⑥ );
 add(i);
 } 
 cout<<heap[1]<<endl;
 return 0;
}