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: 通用分组无线服务 (英语:G eneral P acket R adio S ervice,缩写: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 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #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 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #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 题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #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 分)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #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 ; 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] 则最短路长度发生改变