2019-10-11

解题报告

16 minutes read (About 2352 words)

解题报告-NOIP2016提高组初赛

NOIP 2016 提高组初赛试题不完全解读！

完结~

第 4 题

与二进制小数 0.1 相等的八进进制数是（）。

A. 0.8 B. 0.4 C. 0.2 D. 0.1

二进制与八进制、十六进制之间可以使用技巧进行转化

第 5 题

以比较作为基本运算，在 N 个数中找最小数的最少运算次数为（）。

A. N B. N−1 C. N^2 D. logN

第二个数至第 N 个数依次比较

第 6 题

表达式 a*(b+c)-d 的后缀表达形式为（）。

A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

中缀表达式对应二叉树的中序遍历；后缀表达式对应后根遍历

第 8 题

G 是一个非连通简单无向图，共有 28 条边，则该图至少有（）个顶点。

A. 10 B. 9 C. 8 D. 7

对于连通的简单无向图，点数为 n，则最多有 n(n-1)/2 条边。

对于本题，构造 8 个节点的完全图再附带一个节点即可

第 9 题

某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（）的内存。

A. 2GB B. 4GB C. 8GB D. 16GB

可以寻址的最大地址为 2^32 B。

2^32 B = 2 ^ 22 KB = 2 ^ 12 MB = 4 GB

第 11 题

有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（）种放法。

A. 7 B. 8 C. 21 D. 3^7

暴力枚举

第 13 题

周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切菜 10 分钟，最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（）分钟。

A. 90 B. 60 C. 50 D. 40

问题转化，求拓扑排序最长路

第 16 题

以下属于无线通信技术的有（）。

A. 蓝牙 B. WiFi C. GPRS D. 以太网

GPRS: 通用分组无线服务（英语：General Packet Radio Service，缩写：GPRS）是GSM移动电话用户可以使用的一种移动数据业务/技术。它经常被描述成“2.5G”，意指这项技术介于第二代（2G）与第三代（3G）移动通讯技术之间。它是利用GSM网络中未使用的TDMA信道，提供中速的数据传输服务。起初有人想通过扩展GPRS来覆盖其他标准，只是这些网络都正在转而使用GSM标准，这样GSM就成了GPRS唯一能够使用的网络。GPRS在Release 97之后被集成进GSM标准，起先它是由ETSI标准化，但是现在已经移交3GPP负责。——中文维基百科

以太网（英语：Ethernet）是一种计算机局域网技术。IEEE组织的IEEE 802.3标准制定了以太网的技术标准，它规定了包括物理层的连线、电子信号和介质访问层协议的内容。以太网是当前应用最普遍的局域网技术，取代了其他局域网标准如令牌环、FDDI和ARCNET。

以太网的标准拓扑结构为总线型拓扑，但当前的快速以太网（100BASE-T、1000BASE-T标准）为了减少冲突，将能提高的网络速度和使用效率最大化，使用交换机（Switch hub）来进行网络连接和组织。如此一来，以太网的拓扑结构就成了星型；但在逻辑上，以太网仍然使用总线型拓扑和CSMA/CD（Carrier Sense Multiple Access/Collision Detection，即载波多重访问/碰撞侦测）的总线技术。 ——中文维基百科

第 21 题

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

$f[i][0/1]$ 表示前 $i$ 个方格，最后一个方格为黑/白的方案数。

化简状态转移方程发现 $f[i][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;
}

输出：_____

观察程序。找出最多的形如 axxxbxxxcxxxcxxxbxxxa中出现的字符

第 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
输出：_____

求树的重心。

第 28 题

(交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。对于每一个城市 i，假定只有第 i 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。我们采用邻接表的方式存储图的信息，其中 head[x]表示顶点 x 的第一条边的编号，next[i]表示第 i 条边的下一条边的编号，point[i]表示第 i 条边的终点，weight[i]表示第 i 条边的长度。（第一空 2 分，其余 3 分）

#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;
}

第 5 空：如果被断掉的边在最短路上即 dis[u]+weight=dis[v] 则最短路长度发生改变

解题报告-NOIP2016提高组初赛

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!