SXKDZ

Category: 竞赛练习题

  • NOIp初赛总结——选择题

    计算机基础知识复习

    CPU：包括控制器和运算器。运算器：算术、逻辑（部件：算术逻辑单元、累加器、寄存器组、路径转换器、数据总线）；控制器：复位、使能（部件：计数器、指令寄存器、指令解码器、状态寄存器、时钟发生器、微操作信号发生器）。

    主频：CPU的主频，即CPU内核工作的时钟频率（CPU Clock Speed）。通常所说的某某CPU是多少兆赫的，而这个多少兆赫就是“CPU的主频”。很多人认为CPU的主频就是其运行速度，其实不然。CPU的主频表示在CPU内数字脉冲信号震荡的速度，与CPU实际的运算能力并没有直接关系。

    字长：电脑技术中对CPU在单位时间内能一次处理的二进制数的位数叫字长。所以能处理字长为8位数据的CPU通常就叫8位的CPU。同理32位的CPU就能在单位时间内处理字长为32位的二进制数据。当前的CPU大部分是32位的CPU。

    【例1】关于CPU下面哪些说法是正确的：

    A) CPU全称为中央处理器（或中央处理单元）。

    B) CPU能直接运行机器语言。

    C) CPU最早是由Intel公司发明的。

    D) 同样主频下，32位的CPU比16位的CPU运行速度快一倍。

    【答案】AB

    【解析】C选项中第一个CPU由杰克在1958年研制出人类历史上第一块集成晶体管“微芯片”；D选项中CPU字长不能代表速度。

    【例2】主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（    ）。

    A. 寄存器          B. 高速缓存          C. 闪存          D. 外存

    【答案】B

    图灵机：是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。

    【例3】关于图灵机下面的说法哪个是正确的：

    A) 图灵机是世界上最早的电子计算机。

    B) 由于大量使用磁带操作，图灵机运行速度很慢。

    C) 图灵机只是一个理论上的计算模型。

    D) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

    【答案】C

    【解析】A、B项中图灵机只是理论模型，不是最早的电子计算机，最早的电子计算机是埃尼阿克； D项中是阿兰·图灵本人为破译德军的密码发挥了重要作用。

    冯·诺依曼：冯·诺依曼计算机的设计思想：存储程序；逻辑组成：五大部分（运算器、控制器、存储器及输入输出设备）。

    【例4】提出“存储程序”的计算机工作原理的是（    ）。

    A. 克劳德·香农   B. 戈登·摩尔    C. 查尔斯·巴比奇    D. 冯·诺依曼

    【答案】D

    广告题目：CCF官网：http://www.ccf.org.cn/；NOI官网：http://www.noi.cn/；NOIp推荐IDE：GUIDE、Dev-C++、FreePascal。

    HTML：超文本标记语言（英文：HyperText Markup Language，HTML）是为“网页创建和其它可在网页浏览器中看到的信息”设计的一种标记语言。HTML是一种规范，一种标准，它通过标记符号来标记要显示的网页中的各个部分。网页文件本身是一种文本文件，通过在文本文件中添加标记符，可以告诉浏览器如何显示其中的内容（如：文字如何处理，画面如何安排，图片如何显示等）。浏览器按顺序阅读网页文件，然后根据标记符解释和显示其标记的内容，对书写出错的标记将不指出其错误，且不停止其解释执行过程，编制者只能通过显示效果来分析出错原因和出错部位。但需要注意的是，对于不同的浏览器，对同一标记符可能会有不完全相同的解释，因而可能会有不同的显示效果。HTML之所以称为超文本标记语言，是因为文本中包含了所谓“超级链接”点。所谓超级链接，就是一种URL指针，通过激活（点击）它，可使浏览器方便地获取新的网页。这也是HTML获得广泛应用的最重要的原因之一。Html由此可见，网页的本质就是HTML，通过结合使用其他的Web技术（如：脚本语言、CGI、组件等），可以创造出功能强大的网页。因而，HTML是Web编程的基础，也就是说万维网是建立在超文本基础之上的。

    HTML 5目前仍为草案，并已被W3C接纳。

    【例5】在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（    ）。

    A. <a url=”http://www.noi.cn”>欢迎访问NOI网站</a>

    B. <a href=”http://www.noi.cn”>欢迎访问NOI网站</a>

    C. <a>http://www.noi.cn</a>

    D. <a name=”http://www.noi.cn”>欢迎访问NOI网站</a>

    【答案】B

    【解析】A项语法不正确； C项无用；D项为标签。

    网络：IP地址：所谓IP地址就是给每个连接在Internet上的主机分配的一个32bit地址。按照TCP/IP协议规定，IP地址用二进制来表示，每个IP地址长32bit，比特换算成字节，就是4个字节。例如一个采用二进制形式的IP地址是“00001010000000000000000000000001”，这么长的地址，人们处理起来也太费劲了。为了方便人们的使用，IP地址经常被写成十进制的形式，中间使用符号“.”分开不同的字节。于是，上面的IP地址可以表示为“10.0.0.1”。

    现有的互联网是在IPv4协议的基础上运行的。IPv6是下一版本的互联网协议，也可以说是下一代互联网的协议，它的提出最初是因为随着互联网的迅速发展，IPv4定义的有限地址空间将被耗尽，而地址空间的不足必将妨碍互联网的进一步发展。为了扩大地址空间，拟通过IPv6以重新定义地址空间。IPv4采用32位地址长度，只有大约43亿个地址，估计在2005～2010年间将被分配完毕，而IPv6采用128位地址长度，几乎可以不受限制地提供地址。

    分类：A、B、C3类由InternetNIC在全球范围内统一分配，D、E类为特殊地址。

    【例6】关于计算机网络，下面的说法哪些是正确的：

    A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。

    B) 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。

    C) TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。

    D) 互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。

    【答案】C

    【例7】 TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（   ）。

    A. 链路层         B．网络层          C. 传输层       D. 应用层         E.会话层

    【答案】B

    各种编程语言： 最早编程语言：机器语言；最早面向过程的编程语言：Fortran；最早面向对象的编程语言：Smalltalk；C、C++、Pascal均属于面向过程的语言（C++、Object Pascal也是面向对象语言）、都需要编译。

    【例8】Pascal语言、C语言和C++语言都属于（    ）。

    A. 面向对象语言      B. 脚本语言      C. 解释性语言      D. 编译性语言

    【答案】D

    大事件：（今年指2011年）苹果前CEO乔布斯去世、Skype被微软收购、微软拟发布Win8同时能在平板电脑上运行……

    【例9】今年（2010年）发生的事件有（   ）。

    A.惠普实验室研究员Vinay Deolalikar自称证明了P≠NPB.英特尔公司收购计算机安全软件公司迈克菲（McAfee）

    C.苹果公司发布iPhone 4手机

    D.微软公司发布Windows 7操作系统

    【答案】C

    【例10】 在以下各项中，（  ）不是操作系统软件。

    A. Solaris      B. Linux      C. Sybase      D. WindowsVista      E. Symbian

    【答案】C

    系统软件：在计算机软件中最重要且最基本的就是操作系统（OS）。它是最底层的软件，它控制所有计算机运行的程序并管理整个计算机的资源，是计算机裸机与应用程序及用户之间的桥梁。没有它，用户也就无法使用某种软件或程序。操作系统是计算机系统的控制和管理中心，从资源角度来看，它具有处理机、存储器管理、设备管理、文件管理等4项功能。操作系统如我们常用的Windows、Linux、Dos、Unix（开源）、Mac和Ubuntu（开源）等，而Foxpro、Access、Orale、Sybase、DB2和Informix等则是数据库系统。

    【例11】Linux下可执行文件的默认扩展名为（   ）。

    A. exe           B. com           C. dll           D. 以上都不是

    【答案】D

    【解析】扩展名是Windows的概念。

    编程基础知识

    布尔表达式：是一段代码声明，它最终只有true（真）和false（假）两个取值。从最基本的层次来说，所有的布尔表达式，不论它的长短如何，其值只能是true或false。 运算符号：¬ — not；∧— and；∨ – or。

    集合：组具有某种共同性质的数学元素。

    【例12】以下逻辑表达式的值恒为真的是（    ）。

    A. P∨(¬P∧Q)∨(¬P∧¬Q)           B. Q∨(¬P∧Q)∨(P∧¬Q)

    C. P∨Q∨(P∧¬Q)∨(¬P∧Q)         D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)

    【答案】A

  • 坑爹一题

    伊甸园日历游戏

    【题目描述】
    Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：
    1：把日期的天数加1，例如1900.1.1变到1900.1.2；
    2：把月份加1，例如：1900.1.1变到1900.2.1。
    其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。
    谁先将日期变到2001.11.4谁就赢了。
    每次游戏都是Adam先操作，问他有没有必胜策略？

    【输入格式】
    本题仅一个测试点，有多组数据。
    第一行为数据组数N。
    接下来每一行有3个整数X、Y、Z，表示X年Y月Z日。

    【输出格式】
    输出“YES”or“NO”（不包括引号），表示亚当是否有必胜策略。

    【样例输入】
    3
    2001 11 3
    2001 11 2
    2001 10 3

    【样例输出】
    YES
    NO
    NO

    【注释】
    建议先把所有情况都算出来。

    【题目来源】
    Vijos

     

    题目分析

    【关键算法】
    记忆化搜索、纯模拟或者数学方法。

    【分析】
    这里说说博弈论：博弈一个重要的定义：一个状态它的孩子状态全是必胜状态，则它就一定是必败状态。如果有孩子状态有一个为必败状态，则它就是必胜状态了。
    2001.11.4是一个必败状态，所以我们可以从2001.11.4递推到1900.1.1，将所有状态的情况都给计算出来，这样读入数据直接写即可。

    最后送上某大神写的代码：
    [cpp]
    #include
    using std::cin;
    using std::cout;
    int n, y, m, d;
    int main(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> y >> m >> d;
    if ((d == 30 && (m == 11 || m == 9)) || ((m + d) % 2 == 0)) {
    cout << "YES"; } else { cout << "NO"; } cout << endl ; } return 0; } [/cpp]

    以下是这个算法的解释（Link）

    这是这个算法的解释：伊甸园日历游戏其实是游戏论的内容，这是所谓的平等组合游戏。
    什么是“平等组合游戏”？

    •  两人游戏。
    • 有一个状态集，而且通常是有限的。
    • 规定哪些状态转移是允许的。
    • 所有规定对于两人来说是一样的。
    • 两人轮流走步。
    • 有一个终止状态，到达终止状态后游戏即告终止。
    • 游戏可以在有限步内终止。

    P状态和N状态：
    就像第一是刚才走步的人的必胜状态，我们称之为P状态；而1，2，3，5，6，7，……都是下一个走步的人的必胜状态，我们称之为N状态。我们可以从终止状态出发，推出每一个状态，指出它是P状态还是N状态。就拿第一个游戏举例：
    步骤一 将所有终止状态设为P状态。
    步骤二 将所有一步之内可以到达一个P状态的状态设为N状态。
    步骤三 如果一个状态，不管怎么走都只能走到N状态，那么就将这个状态设为P状态。
    步骤四 返回步骤二。
    如果能够走到P状态，就能获胜。因为安照上面的定义，对手不管如何选择，只可能走到N状态。接下来总存在一个P状态你可以走到。这样一直走到终止状态，你获胜。当然这里所说得都是指对于最后走步的人获胜的游戏。
    我们严格的来定义P状态和N状态

    • 所有的终止状态都是P状态；
    • 对于任何的N状态，肯定存在一种方式可以一步转到一个P状态；
    • 对于任何的P状态，不管怎么走步，都只能转到N状态。

    而对于最后走步的人失败的游戏，只要将所有终止状态改成N状态，然后开始倒推就可以了。当然，必胜状态是N状态。也就是说，如果想胜利，就希望面对N状态，转移到P状态。
    2001.11.4 n
    2001.11.3 2001.10.4 p
    2001.11.2 2001.10.3 2001.09.4 n
    2001.11.1 2001.10.2 2001.09.3 2001.08.4 p
    2001.10.31 2001.10.1 2001.09.2 2001.08.3 2001.07.4 n
    2001.10.30 2001.09.30 2001.09.1 2001.08.2 2001.07.3 2001.06.4 p
    由此看出 当month+day mod 2=0 then p状态
    若month=9 day=30 then p状态

  • [动态规划练习题]潜水

    【问题描述】
    潜水员用特殊的装备潜水，需要两个容器的钢瓶：一个装氧气，另一个装氮气。根据潜水员要待在水下的时间和所潜的深度，他需要不同量的氧气和氮气。提供给潜水员一定数量的钢瓶，每个钢瓶由它的重量和它所容纳的气体的体积描述。为了完成任务，潜水员需要特定量的氧气和氮气，需要求他完成任务所需的钢瓶的最少重量是多少？
    例如，潜水员能够使用的5个钢瓶描述如下，每个描述包含：氧气的体积，氮气的体积（每个值都是以升为单位）和钢瓶的重量。
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119
    如果潜水员需要5升氧气和60升氮气，那么他必须带两个总重量为249的钢瓶（例子中的第1与第2或者第4与第5）。

    【任务】
    读入潜水员的氧气和氮气的需求量，提供的钢瓶的数目及它们的描述；
    计算潜水员完成任务所需要的钢瓶最少重量；
    注：提供的钢瓶总能够完成给定的任务。 
       
    【输入格式】
    第一行有两个整数T，A，它们由空格隔开，1≤T≤100，1≤A≤100，它们分别表示氧气的体积和氮气的体积，这些是完成任务需要的。第二行有一个整数N，1≤N≤1000，表示提供钢瓶的总数量，接下来的N行是对每个钢瓶的描述，第I+2行包含3个整数，TI，AI，WI，它们由空格隔开，其中1≤TI≤100，1≤AI≤100，1≤WI≤800；它们分别表示第I个钢瓶内氧气的体积、氮气的体积以及该钢瓶的重量，1≤I≤N。  

    【输出格式】
    输出只有一个整数，就是潜水员完成任务所需钢瓶的最少总重量。 

    【样例输入】
    5 60
    5
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119

    【样例输出】
    249

    【时间限制】
    每个测试点1s。

    【解析】

    • 状态：f[j][k]表示氧气为j，氮气为k时的钢瓶最小重量
    • 状态转移方程：f[j+t[i]][k+a[i]] = min(f[j+t[i]][k+a[i]], f[j][k]+c[i])
    • 答案：f[T][A]
    • 时间复杂度：O(N*T*A)

    [cpp]#include <cstdio>
    int T, A, N, f[200][200], t[1020], a[1020], v[1020];
    int main(void)
    {
        scanf(“%d%d%d”, &T, &A, &N);
        for (int i=1; i<=N; ++i)
            scanf(“%d%d%d”, &t[i], &a[i], &v[i]);
        for (int i=0; i<=T; ++i)
            for (int j=0; j<=A; ++j)
                f[i][j]=10000000;
        f[0][0]=0;
        for (int i=1; i<=N; ++i)
            for (int j=T; j>=0; –j)
                for (int k=A; k>=0; –k)
                {
                    int o1, o2;
                    if (t[i]+j > T)
                        o1=T;
                    else
                        o1=t[i]+j;
                    if (a[i]+k > A)
                        o2=A;
                    else
                        o2=a[i]+k;
                    if (f[o1][o2]>f[j][k]+v[i])
                        f[o1][o2]=f[j][k]+v[i];
                }
        printf(“%d\n”, f[T][A]);

        return 0;
    }

    [/cpp]