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

第21题

本题中，我们约定布尔表达式只能包含 p, q, r三个布尔变量，以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p,q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。

例如，(p∨q)∨r 和 p∨(q∨r) 等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有____个。

第22题

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有____个不同的独立集。

第23题

#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main(){
    cin>>n;
    for (i = 1;i <= n;i++)
        cin>>a[i];
    for (i = 1;i <= n - 1;i++)
        if (a[i] > a[i + 1]) {
            temp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = temp;
        }
    for (i = n;i >= 2;i--)
        if (a[i] < a[i - 1]) {
            temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
        }
    sum = 0;
    for (i = 2;i <= n - 1;i++)
        sum += a[i];
    cout<<sum / (n - 2)<<endl;
    return 0;
}

输入：

8

40 70 50 70 20 40 10 30

输出：____

第24题

#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b){
    if (a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
int main(){
    cin>>n;
    ans = 0;
    for (i = 1;i <= n;i++)
        if (gcd(n,i) == i)ans++;
    cout<<ans<<endl;
}

输入：120

输出：____

第25题

#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge(){
    data[h-1] = data[h-1] + data[h];
    h--;
    ans++;
}
int main(){
    cin>>n;
    h = 1;
    data[h] = 1;
    ans = 0;
    for (i = 2;i <= n;i++){
        h++;
        data[h] = 1;
        while (h > 1 && data[h] == data[h-1])
            merge();
    }
    cout << ans << endl;
}

1、输入：8

输出：____

2、输入：2012

输出：____

第26题

#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep){
    ans = ans + dep*(s1[x] - 'A' + 1);
    if (lefts[x] >= 0) calc(lefts[x], dep+1);
    if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x){
    if (lefts[x] >= 0) check(lefts[x]);
    s3 = s3 + s1[x];
    if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th){
    if (th == n){
        s3 = "";
        check(0);
        if (s3 == s2){
            ans = 0;
            calc(0, 1);
            cout<<ans<<endl;
        }
        return;
    }
    if (lefts[x] == -1 && rights[x] == -1){
        lefts[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        lefts[x] = -1;
    }
    if (rights[x] == -1){
        rights[x] = th;
        father[th] = x;
        dfs(th, th+1);
        father[th] = -1;
        rights[x] = -1;
    }
    if (father[x] >= 0)dfs(father[x], th);
}
int main(){
    cin>>s1;
    cin>>s2;
    n = s1.size();
    memset(lefts, -1, sizeof(lefts));
    memset(rights, -1, sizeof(rights));
    memset(father, -1, sizeof(father));
    dfs(0, 1);
}

输入：

ABCDEF

BCAEDF

输出：____

第27题

（排列数）输入两个正整数 n,m(1≤n≤20,1≤m≤n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。

例如输入：

3 2

输出：

1  2

1  3

2  1

2  3

3  1

3  2

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main(){
    cin>>n>>m;
    memset(used, false, sizeof(used));
    for (i = 1; i <= m; i++){
        data[i] = i;
        used[i] = true;
    }
    flag = true;
    while (flag){
        for (i = 1; i <= m-1; i++)cout<<data[i]<<"";
        cout << data[m] << endl;
        flag =①;
        for (i = m; i >= 1; i--){
            ②;
            for (j = data[i]+1; j <= n; j++)
                if (!used[j]){
                    used[j] = true;
                    data[i] =③;
                    flag = true;
                    break;
                }
            if (flag){
                for (k = i+1; k <= m; k++)
                    for (j = 1; j <=④; j++)
                        if (!used[j]){
                            data[k] = j;
                            used[j] = true;
                            break;
                        }
                ⑤;
            }
        }
    }
}

第28题

（壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。

#include <iostream>
using namespace std;
const int NSIZE = 100000,CSIZE = 1000;
int n, c, r, tail, head, s[NSIZE], q[CSIZE];
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标
bool direction, empty;
int previous(int k){
    if (direction)
        return ((k + c - 2) % c) + 1;
    else
        return (k % c) + 1;
}
int next(int k){
    if (direction)
        ①;
    else
        return ((k + c - 2) % c) + 1;
}
void push(){
    int element;
    cin>>element;
    if (next(head) == tail) {
        n++;
        ②;
        tail = next(tail);
    }
    if (empty)
        empty = false;
    else
        head = next(head);
    ③= element;
}
void pop(){
    if (empty) {
        cout<<"Error: the stack is empty!"<<endl;
        return;
    }
    cout<<④<<endl;
    if (tail == head)
        empty = true;
    else {
        head = previous(head);
        if (n > 0) {
            tail = previous(tail);
            ⑤= s[n];
            n--;
        }
    }
}
void reverse(){
    int temp;
    if (⑥== tail) {
        direction = !direction;
        temp = head;
        head = tail;
        tail = temp;
    }else
        cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;
}
int main(){
    cin>>c;
    n = 0;
    tail = 1;
    head = 1;
    empty = true;
    direction = true;
    do{
        cin>>r;
        switch (r) {
            case 1: push();break;
            case 2: pop();break;
            case 3: reverse();break;
        }
    } while (r != 0);
    return 0;
}