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

第21题

有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下 表所示，则城市 1 到城市 6 的最短距离为 _____________ 。

第22题

书架上有 21 本书，编号从 1 到 21 ，从其中选 4 本，其中每两本的编号都不相邻的 选法一共有 ______ 种。

第23题

#include<stdio.h>
int main()
{
  int i, a, b, c, d, f[4];
  for(i = 0; i < 4; i++)
   scanf("%d", &f[i]);
  a = f[0] + f[1] + f[2] + f[3];
  a = a / f[0];
  b = f[0] + f[2] + f[3];
  b = b / a;
  c = (b * f[1] + a) / f[2];
  d = f[(b / c ) % 4];
  if(f[(a + b + c + d) % 4] > f[2])
    printf("%d\n", a + b);
  else
    printf("%d\n", c + d);
  return 0;
}

输入： 9 19 29 39 

输出： _______________

第24题

#include<stdio.h>
void foo(int a, int b, int c)
{
  if(a > b) 
   foo(c, a, b);
  else
   printf("%d,%d,%d\n", a, b, c);
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  foo(a, b, c);
  return 0;
}

输入： 2 1 3 

输出 :__________

第25题

#include<stdio.h>
void f(int a, int b, int c)
{
  printf("%d%d%d/", a, b, c);
  if(a == 3 && b == 2 && c == 1)
return;
  if(b < c)
    f(a, c, b);
  else if(a < b)
  {
    if(a < c)
      f(c, a, b);
    else
      f(b, c, a);
  }
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  f(a, b, c);
  printf("\n");
  return 0; 
}

输入 : 1 3 2 

输出： ________________________

第26题

#include <stdio.h>
#include <string.h>
int i,j,len;
char s[50];
int main()
{
  scanf("%s", s);
  len = strlen(s);
  for (i = 0;i < len; ++i)
  {
     if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a';
  }
  for (i = 0;i < len; ++i)
  {
     if (s[i] < 'x') s[i] += 3; else s[i] += -23;
  }
  printf("%s/", s);
  for (j = 1;j < 4;j ++)
  {
     for (i = 0;i < len-j; i = i + j)
     {
        s[i] = s[i + j] ;
     }   
  }
  printf("%s\n", s);
  return 0;
}

输入： ABCDEFGuvwxyz 

输出： __________________________

第27题

( 找第 k 大的数 ) 给定一个长度为 1,000,000 的无序正整数序列，以及另一个数 n(1<=n<=1000000) ，接下来以类似快速排序的方法找到序列中第 n 大的数 （关于第 n 大 的数：例如序列 {1 ，2， 3， 4，5，6} 中第 3 大的数是 4）。

#include <stdlib.h>
#include <stdio.h>
int a[1000001],n,ans = -1;
void swap(int *a,int *b)
{
  int c;
  c = *a; *a = *b; *b = c;
}
int FindKth(int left, int right, int n)
{
  int tmp,value,i,j;
  if (left == right) return left;
  tmp = rand()% (right - left) + left;
  swap( &a[tmp], &a[left] );
  value = ①
  i = left;
  j = right;
  while (i < j)
  {
    while (i < j && ② ) j --;
    if (i < j) {a[i] = a[j]; i ++;} else break;
    while (i < j && ③ ) i ++;
    if (i < j) {a[j] = a[i]; j - -;} else break;
  }
   ④
  if (i < n) return FindKth( ⑤ );
  if (i > n) return ⑥
  return i;
}
int main()
{
  int i; 
  int m = 1000000;
  for (i = 1;i <= m;i ++)
   scanf("%d", &a[i]);
  scanf("%d", &n);
  ans = FindKth(1,m,n);
  printf("%d\n", a[ans]);
  return 0;
}

第28题

（矩阵中的数字） 有一个 n*n(1<=n<=5000) 的矩阵 a， 对于 1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1] 。即矩阵中左右相邻的两个元素，右边 的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵 a 中的一个数字 k，找出 k 所在的行列（注意：输入数据保证矩阵中的数各不相同） 。

#include <stdio.h>
int n,k,answerx,answery;
int a[5001][5001];
void FindKPosition()
{
  int i = n,j = n;
  while (j > 0)
  {
    if (a[n][j] < k) break;
    j --;
  }
    ①
  while (a[i][j] != k)
  {
    while ( ② && i > 1) i --;
    while ( ③ && j <= n) j ++;
  }
    ④
    ⑤
}
int main() 
{
  int i,j;
  scanf( "%d", &n );
  for (i = 1;i <= n;i ++)
  for (j = 1;j <= n;j ++)
  scanf( "%d", &a[i][j]);
  scanf( "%d", &k );
  FindKPosition();
  printf("%d %d\n", answerx, answery);
  return 0;
}