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

第21题

平面图是可以画在平面上、且它的边仅在顶点上才能相交的简单无向 图。 4 个顶点的平面图至多有 6 条边，如右图所示。那么， 5 个顶点的平面 图至多有 ________ 条边。

第22题

定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符 串”BCA”，可以将 A 移到 B 之前，变成字符串 ”ABC”。如果要将字符串 ”DACHEBGIF ”变成 "ABCDEFGHI" ，最少需要 ________ 次操作。

第23题

#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int main(){
  int n, i, sum, x, a[SIZE];
  cin>>n;
  memset(a, 0, sizeof(a));
  for (i = 1; i <= n; i++) {
    cin>>x;
    a[x]++;
  }
  i = 0; sum = 0;
  while (sum < (n / 2 + 1)) {
    i++;
    sum += a[i];
  }
  cout<<i<<endl;
  return 0;
}

输入： 

11 

4 5 6 6 4 3 3 2 3 2 1 

输出： _________

第24题

#include <iostream>
using namespace std;
int n;
void f2(int x, int y);
void f1(int x, int y){
    if (x < n)f2(y, x + y);
}
void f2(int x, int y){
    cout<<x<<' ';
    f1(y, x + y);
}
int main(){
    cin>>n;
    f1(0, 1);
    return 0;
}

输入： 30 

输出： _________

第25题

#include <iostream>
using namespace std;
const int V = 100;
int n, m, ans, e[V][V];
bool visited[V];
void dfs(int x, int len){
    int i;
    visited[x] = true;
    if (len > ans)ans = len;
    for (i = 1; i <= n; i++)
    if ((! visited[i]) && (e[x][i] != -1))
        dfs(i, len + e[x][i]);
    visited[x] = false;
}
int main(){
    int i, j, a, b, c;
    cin>>n>>m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            e[i][j] = -1;
    for (i = 1; i <= m; i++){
        cin>>a>>b>>c;
        e[a][b] = c;
        e[b][a] = c;
    }
    for (i = 1; i <= n; i++)
        visited[i] = false;
    ans = 0;
    for (i = 1; i <= n; i++)
        dfs(i, 0);
    cout<<ans<<endl;
    return 0;
}

输入： 

4 6 

1 2 10

2 3 20 

3 4 30 

4 1 40 

1 3 50 

2 4 60

输出：________

第26题

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int SIZE = 10000;
const int LENGTH = 10;
int n, m, a[SIZE][LENGTH];
int h(int u, int v){
    int ans, i;
    ans = 0;
    for (i = 1; i <= n; i++)
        if (a[u][i] != a[v][i])
            ans++;
    return ans;
}
int main(){
    int sum, i, j;
    cin>>n;
    memset(a, 0, sizeof(a));
    m = 1;
    while (1){
        i = 1;
        while ((i <= n) && (a[m][i] == 1))
            i++;
        if (i > n) break;
        m++;
        a[m][i] = 1;
        for (j = i + 1; j <= n; j++)
            a[m][j] = a[m - 1][j];
    }
    sum = 0;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
            sum += h(i, j);
    cout<<sum<<endl;
    return 0;
}

输入： 7 

输出：______

第27题

（大整数开方 ）输入一个正整数 n（1<=n<10 ¹⁰⁰ ），试用二分法计算它的平方根的整 数部分。

【程序清单】

#include <iostream>
#include <string>
using namespace std;
const int SIZE = 200;
struct hugeint {
    int len, num[SIZE];
};
//其中 len 表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推
hugeint times(hugeint a, hugeint b) {
    //计算大整数 a 和 b 的乘积
    int i, j; hugeint ans;
    memset(ans.num, 0, sizeof(ans.num));
    for (i = 1; i <= a.len; i++)
        for (j = 1; j <= b.len; j++)
            ①+= a.num[i] * b.num[j];
    for (i = 1; i <= a.len + b.len; i++) {
        ans.num[i + 1] += ans.num[i] / 10;
        ②;
    }
    if (ans.num[a.len + b.len] > 0)
        ans.len = a.len + b.len;
    else
        ans.len = a.len + b.len - 1;
    return ans;
}
hugeint add(hugeint a, hugeint b){
    //计算大整数 a 和 b 的和
    int i; hugeint ans;
    memset(ans.num, 0, sizeof(ans.num));
    if (a.len > b.len)
        ans.len = a.len;
    else
        ans.len = b.len;
    for (i = 1; i <= ans.len; i++) {
        ans.num[i] +=③;
        ans.num[i + 1] += ans.num[i] / 10;
        ans.num[i] %= 10;
    }
    if (ans.num[ans.len + 1] > 0) ans.len++;
    return ans;
}
hugeint average(hugeint a, hugeint b){
    //计算大整数 a 和 b 的平均数的整数部分
    int i; hugeint ans;
    ans= add(a, b);
    for(i = ans.len; i >= 2; i--) {
        ans.num[i  - 1] += (④) * 10;
        ans.num[i] /= 2;
    }
    ans.num[1] /= 2;
    if (ans.num[ans.len] == 0) ans.len--;
    return ans;
}
hugeint plustwo(hugeint a) {
    //计算大整数 a 加 2 后的结果
    int i; hugeint ans;
    ans = a;
    ans.num[1] += 2;
    i = 1;
    While ((i <= ans.len) && (ans.num[i] >= 10)) {
        ans.num[i + 1] += ans.num[i] / 10;
        ans.num[i] %= 10;
        i++;
    }
    if (ans.num[ans.len + 1] > 0)⑤;
    return ans;
}
bool over(hugeint a, hugeint b){
    //若大整数 a>b 则返回 true，否则返回 false
    int i;
    if (⑥) return false;
    if (a.len > b.len) return true;
    for (i = a.len; i >= 1; i--) {
        if (a.num[i] < b.num[i])return false;
        if (a.num[i] > b.num[i]) return true;
    }
    return false;
}
int main(){
    string s;
    int i;
    hugeint target, left, middle, right;
    cin>>s;
    memset(target.num, 0, sizeof(target.num));
    target.len = s.length();
    for (i = 1; i <= target.len; i++)
        target.num[i]= s[target.len  - i] - ⑦;
    memset(left.num, 0, sizeof(left.num));
    left.len = 1;
    left.num[1] = 1;
    right = target;
    do {
        middle = average(left, right);
        if (over(⑧))right = middle;
        else left = middle;
    } while (!over(plustwo(left), right));
    for (i = left.len; i >= 1; i--)
        cout<<left.num[i];
    cout<<endl;
    return 0;
}

第28题

（笛卡尔树 ）对于一个给定的两两不等的正整数序列， 笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即 除了根结点外， 每个结点的权值都大于父结点的权值； 其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。 现输入序列的规模 n（1<=n<100 ） 和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶节 点的深度为 d 。 

【程序清单】

#include <iostream>
using namespace std;
const int SIZE = 100+5;
const int INFINITY = 1000000;
int n, a[SIZE], maxDeep, num;
void solve(int left, int right, int deep){
    int i, j, min;
    if (deep > maxDeep) {
        maxDeep = deep;
        num = 1;
    }else if (deep == maxDeep)
        ①;
    min = INFINITY;
    for (i = left; i <= right; i++)
        if (min > a[i]) {
            min = a[i];
            ②;
        }
    if(left < j)③;
    if(j < right)④;
}
int main(){
    int i;
    cin>>n;
    for (i = 1; i <= n; i++)
        cin>>a[i];
    maxDeep = 0;
    solve(1, n, 1);
    cout<<maxDeep<<' '<<num<<endl;
    return 0;
}