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

第21题

书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的， C和 D 是黑皮的。把这 4 本书摆在书 架上，满足所有黑皮的书都排在一起的摆法有 _____ 种。满足 A 必须比 C 靠左，所有红皮的书要摆放在 一起，所有黑皮的书要摆放在一起，共有 ______ 种摆法。

第22题

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

第23题

#include<iostream>
using namespace std;
int main()
{
  int i, a, b, c, d, f[4];
  for(i = 0; i < 4; i++) cin >> 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])
    cout << a + b<< endl;
  else
    cout << c + d << endl;
  return 0;
}

输入： 9 19 29 39 

输出： _______________

第24题

#include<iostream>
using namespace std;
void foo(int a, int b, int c)
{
  if(a > b)
    foo(c, a, b);
  else
    cout<<a<<','<<b<<','<<c<<endl;
}
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  foo(a, b, c);
  return 0;
}

输入: 3 1 2 

输出: __________

第25题

#include <iostream>
using namespace std;
void func(int ary[], int n ) 
{
  int i=0, j, x;
  j=n-1;
  while(i<j)
  {
  while (i<j&&ary[i]>0) i++;
  while (i<j&&ary[j]<0) j--;
  if (i<j)
  {
    x=ary[i];
    ary[i++]=ary[j];
    ary[j--]=x;
  }
  }
}
int main()
{
  int a[20], i, m;
  m=10;
  for(i=0; i<m; i++) 
  {
     in>>a[i];
  }
  func(a, m);
  for (i=0; i<m; i++)
  cout<<a[i]<<" ";
  cout<< endl;
  return 0;
}

输入： 5 4 -6 -11 6 -59 22 -6 1 10 

输出： ___________________________________

第26题

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100 
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
  int i, root_m;
  if(spos_f > epos_f)
  return;
  for(i = spos_m; i <= epos_m; i++)
  if(first[spos_f] == mid[i])
  {
     root_m = i;
     break;
  }
  solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
  solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
  cout << first[spos_f];
}
int main()
{
  char first[MAX], mid[MAX];
  int len;
  cin >> len;
  cin >> first >> mid;
  solve(first, 0, len - 1, mid , 0, len - 1);
  cout << endl;
  return 0;
}

输入： 7 ABDCEGF BDAGECF 

输出： ______________________________

第27题

（字符串替换） 给定一个字符串 S（S 仅包含大小写字母） ，下面的程序将 S 中的每个字母用规定的 字母替换，并输出 S 经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串 S， 第二个字符串 S’由 26 个字母组成，它是 a-z 的任一排列，大小写不定， S’规定了每个字母对应的替 换字母： S’中的第一个字母是字母 A 和 a 的替换字母，即 S 中的 A 用该字母的大写替换， S 中的 a 用 该字母的小写替换； S’中的第二个字母是字母 B 和 b 的替换字母， 即 S 中的 B用该字母的大写替换， S 中的 b 用该字母的小写替换；…… 以此类推。

#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
  int i;
  for (i = 0;i < 26;i ++)
  {
    if ( ① )
    change[i] -= 'A' - 'a';
  }
}
void ChangeString()
{
  int i;
  for (i = 0;i <strlen(str);i ++)
  {
     if ( ② )
       str[i] = change[str[i] - 'A'] -'a' + 'A';
     else
       ③
  }
}
int main()
{
   int i;
   cin >> str ;
   cin >> change;
   CheckChangeRule();
    ④
   cout << str << endl;
   return 0;
}

第28题

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

#include <iostream>
using namespace std;
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; 
}