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

第21题

一个 1×8 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_____种填涂方案。

第22题

某中学在安排期末考试时发现，有 7 个学生要参加 7 门课程的考试，下表列出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_____个不同的考试时间段才能避免冲突？

第23题

#include <iostream>
using namespace std;

int main() {
    int a[6] = {1, 2, 3, 4, 5, 6};
    int pi = 0;
    int pj = 5;
    int t , i;
    while (pi < pj) {
         t = a[pi];
        a[pi] = a[pj];
        a[pj] = t;
        pi++;
        pj--;
    }
    for (i = 0; i < 6; i++)
        cout << a[i] << ",";
    cout << endl;
    return 0;

}

输出 ：____

第24题

#include <iostream>
using namespace std;

int main() {
    char a[100][100], b[100][100];
    string c[100];
    string tmp;
    int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
    cin >> n;
    getline(cin, tmp);
    for (i = 0; i < n; i++) {
        getline(cin, c[i]);
        total_len[i] = c[i].size();
    }
    for (i = 0; i < n; i++) {
        j = 0;
        while (c[i][j] != ':') {
            a[i][k] = c[i][j];
            k = k + 1;
            j++;
        }
        length[i][1] = k - 1;
        a[i][k] = 0;
        k = 0;
        for (j = j + 1; j < total_len[i]; j++) {
            b[i][k] = c[i][j];
            k = k + 1;
        }
        length[i][2] = k - 1;
        b[i][k] = 0;
        k = 0;
    }
    for (i = 0; i < n; i++) {
        if (length[i][1] >= length[i][2])
            cout << "NO,";
        else {
            k = 0;
            for (j = 0; j < length[i][2]; j++) {
                if (a[i][k] == b[i][j])
                    k = k + 1;
                if (k > length[i][1])
                    break;
            }
            if (j == length[i][2])
                cout << "NO,";
            else
                cout << "YES,";
            }
    }
    cout << endl;
    return 0;
}

输入 :

3

AB:ACDEbFBkBD

AR:ACDBrT

SARS:Severe Atypical Respiratory Syndrome

输出 : ____

（注：输入各行前后均无空格）

第25题

#include<iostream>
using namespace std;

int lps(string seq, int i, int j) {
    int len1, len2;
    if (i == j)
        return 1;
    if (i > j)
        return 0;
    if (seq[i] == seq[j])
        return lps(seq, i + 1, j - 1) + 2;
    len1 = lps(seq, i, j - 1);
    len2 = lps(seq, i + 1, j);
    if (len1 > len2)
        return len1;
    return len2;
}

int main() {
    string seq = "acmerandacm";
    int n = seq.size();
    cout << lps(seq, 0, n - 1) << endl;
    return 0;
}

输出 ：____

第26题

#include <iostream>
#include <cstring>
using namespace std;

int map[100][100];
int sum[100], weight[100];
int visit[100];

int n;

void dfs(int node) {
    visit[node] = 1;
    sum[node] = 1;
    int v, maxw = 0;
    for (v = 1; v <= n; v++) {
        if (!map[node][v] || visit[v])
            continue;
        dfs(v);
        sum[node] += sum[v];
        if (sum[v] > maxw)
            maxw = sum[v];
    }
    if (n - sum[node] > maxw)
        maxw = n - sum[node];
    weight[node] = maxw;
}

int main() {
    memset(map, 0, sizeof(map));
    memset(sum, 0, sizeof(sum));
    memset(weight, 0, sizeof(weight));
    memset(visit, 0, sizeof(visit));
    cin >> n;
    int i, x, y;
    for (i = 1; i < n; i++) {
        cin >> x >> y;
        map[x][y] = 1;
        map[y][x] = 1;
    }
    dfs(1);
    int ans = n, ansN = 0;
    for (i = 1; i <= n; i++)
        if (weight[i] < ans) {
            ans = weight[i];
            ansN = i;
        }
    cout << ansN << " " << ans << endl;
    return 0;
}

输入 :

11

1 2

1 3

2 4

2 5

2 6

3 7

7 8

7 11

6 9

9 10

输出 : ____

第27题

（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。 现在有 n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里，那么这名身高为1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。

由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。

#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647

int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; int rank[MAXN];
int n;

void sort(int l, int r) {
    int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
    while (i <= j)
    {
        while (height[rank[i]] < x) i++;
        while (height[rank[j]] > x) j--;
        if ( ___(1)___ ) {
            temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;
             i++; j--;
        }
    }
    if (i < r) sort(i, r);
    if (l < j) sort(l, j);
}

int main()
{
    cin >> n;
    int i, higher, shorter;
    for (i = 1; i <= n; i++) {
        cin >> height[i];
        rank[i] = i;
    }
    sort(1, n);
    for (i = 1; i <= n; i++) {
        previous[rank[i]] = rank[i - 1];
           ___(2)___ ;
    }
    for (i = n; i >= 2; i--){
        higher = shorter = infinity;
        if (previous[i] !=0)
            shorter = height[i] - height[previous[i]];
        if (next[i] != 0)
            ___(3)___ ;
        if ( ___(4)___ )
            answer[i] = previous[i];
        else
            answer[i] = next[i];
        next[previous[i]] = next[i];
        ___(5)___ ;
    }
    for (i = 2; i <= n; i++)
        cout << i << ":" << answer[i];
    return 0;
}

第28题

(交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1) 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。

对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。

我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 x 的第一条 边的编号，next[i] 表示第 i 条边的下一条边的编号, point[i] 表示第 i 条边的终点，weight[i] 表示第 i 条边的长度。

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647

int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];

int n, m, x, y, z, total = 0, answer;

void link(int x,int y,int z) {
    total++;
    next[total] = head[x]; head[x] = total; point[total] = y; weight[total] = z; total++;
    next[total] = head[y]; head[y] = total; point[total] = x; weight[total] = z;
}

int main() {
    int i, j, s, t; cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        link(x, y, z);
    }
    for (i = 1; i <= n; i++) dist[i] = infinity;
    ___(1)___ ;
    queue[1] = 1;
    visit[1] = 1;
    s = 1;
    t = 1;
    // 使用 SPFA 求出第一个点到其余各点的最短路长度
    while (s <= t) {
        x = queue[s % MAXN];
        j = head[x];
        while (j != 0) {
            if ( ___(2)___ ) {
                dist[point[j]] = dist[x] + weight[j];
                if (visit[point[j]] == 0) {
                    t++;
                    queue[t % MAXN] = point[j];
                    visit[point[j]] = 1;
                }
            }
            j = next[j];
        }
        ___(3)___ ;
        s++;
    }
    for (i = 2; i <= n; i++) {
        queue[1] = 1;
        memset(visit, 0, sizeof(visit));
        visit[1] = 1;
        s = 1;
        t = 1;
        while (s <= t) { // 判断最短路长度是否不变
            x = queue[s];
            j = head[x];
            while (j != 0) {
                if (point[j] != i && ___(4)___ &&visit[point[j]] == 0) {
                    ___(5)___ ;
                    t++;
                    queue[t] = point[j];
                }
                j = next[j];
            }
            s++;
        }
        answer = 0;
        for (j = 1; j <= n; j++)
            answer += 1 - visit[j];
        cout << i << ":" << answer - 1 << endl;
    }
    return 0;

}