壹牛家长圈-

标题: 解析 | 全国青少年信息学奥林匹克联赛初赛 提高组 [打印本页]
作者: 甜甜圈    时间: 2018-10-23 13:53
标题: 解析 | 全国青少年信息学奥林匹克联赛初赛 提高组
本帖最后由 甜甜圈 于 2018-10-23 14:20 编辑


第二十四届
全国青少年信息学奥林匹克联赛初赛
提高组解析


一、单项选择题（每题2分，共20分）


1. 下列四个不同进制的数中，与其它三项数值上不相等的是（D）。
A.(269)16
B.(617)10
C.(1151)8
D.(1001101011)2

解析：
这道题也是普及组的第二题：
1)方法一：是把4个都换成10进制来比较
2)方法二：直接通过二进制转八、十六进制的快速转换方法来判断
二进制转八进制是3个并1个、转十六进制是4个并1个
对D的二进制数分析：
(1001 101 011)2 = (1153)8
(100110 1011)2 = (26B)16

显然，与其它不符的只能是D


2. 下列属于解释执行的程序设计语言是（D）。
A. C
B. C++
C. Pascal
D. Python

解析：
Python是解释型语言，其它三个都是编译型语言


3. 中国计算机学会于（B）年创办全国青少年计算机程序设计竞赛。
A.1983
B.1984
C.1985
D.1986

解析：
这道题也是普及组的第5题。
1984年，邓小平说计算机的普及要从娃娃抓起，那一年的中国科协和计算机协会一起举办了全国青少年程序设计大赛

4. 根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（A）个结点。

解析：
这是普及组的第7题：
1）假设h=2，k=2，画出完美二叉树，共7个节点。


2）对4个答案代入运算，结果为A

  
如果想理解和推导公式：
5. 设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）及T(0) = 1，则该算法的时间复杂度为（D）。
A. O(logn)    B. O(nlogn)    C. O(n)   D. O(n*n)
  
解析：
这是2015年的第19题：
T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) +(n-2) + (n-1) + n
= ….
    = T(0) +1 + 2 + … + n = 1+n*(n+1)/2


取最高项，得到时间复杂度为O(n*n)

6. 表达式a * d - b * c 的前缀形式是（B）。
A. a d * b c * -
B. - * a d * b c
C. a * d - b * c
D. - * * a d b c

解析：
1) 基于（中缀）表达式画出二叉树

2) 然后用先序遍历得到前缀表达式：- * a d * b c

7. 在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（B）。
A. 1 / 2
B. 1 / 3
C. 2 / 3
D. 3 / 5

解析:
1）假设[0, 1]区间，a、b均匀分布
2）假设a固定为0，随机取1个点b：
显然，两个点的期望长度|b-a|会小于|b-0|的期望，可以大胆猜测答案为B。

如果还想彻底推导，继续往下看：

3）距离t = |a-b| = max(a,b) – min(a, b)
4）max(a, b)的期望计算：
5）min(a, b)的期望计算：
6）距离t的期望为Emax(a, b) – Emin(a, b) = 1/3

8. 关于Catalan数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（A）。
A. Cn 表示有n+ 1 个结点的不同形态的二叉树的个数。
B. Cn 表示含n对括号的合法括号序列的个数。
C. Cn 表示长度为n 的入栈序列对应的合法出栈序列个数。
D. Cn 表示通过连接顶点而将n + 2 边的凸多边形分成三角形的方法个数。

解析：
1） 如果不懂Catalan数，取个n=1代入得到Cn=1，然后四个选项对下：
2）如果知道Catalan数，那么就会知道A是错的，应为n个结点的二叉树形态个数

9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（D）。
A. 1 : 2
B. 2 : 1
C. 1 : 3
D. 1 : 1

解析：

10. 为了统计一个非负整数的二进制形式中1 的个数，代码如下： _
intCountBit(int x)
{
intret = 0;
while(x)
{
ret++;
___________;
}
returnret;
}
则空格内要填入的语句是（ _）。 _
A.x >>= 1
B.x &= x - 1
C.x |= x >> 1
D.x <<= 1

解析：
这道题也是普及组的第14题：

二、多项选择题（每题2分，共10分）

1. NOIP 初赛中，选手可以带入考场的有（AB）。
A. 笔
B. 橡皮
C. 手机（关机）
D. 草稿纸

解析：
《noi竞赛规则》：
以上如果记不住，就从防止作弊的角度考虑一下。

2.  2-3树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同。
如果一棵2-3 树有10个叶结点，那么它可能有（CD）个非叶结点。
A. 5
B. 6
C. 7
D. 8

解析：
1）最多的非叶结点：
2）最少的非叶结点：

3. 下列关于最短路算法的说法正确的有（ABD）。
A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
B. 当图中不存在负权边时，调用多次Dijkstra 算法能求出每对顶点间最短路径。
C. 图中存在负权回路时，调用一次Dijkstra 算法也一定能求出源点到所有点的最短路。
D. 当图中不存在负权边时，调用一次Dijkstra 算法不能用于每对顶点间最短路计算。

解析：

4. 下列说法中，是树的性质的有（ABD）。
A. 无环
B. 任意两个结点之间有且只有一条简单路径
C. 有且只有一个简单环
D. 边的数目恰是顶点数目减1

解析：

5. 下列关于图灵奖的说法中，正确的有（BCD）。
A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。
B. 目前获得该奖项的华人学者只有姚期智教授一人。
C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称.
  
解析：
来自百度百科：

二、问题求解（每题5分，共10分）

1. 甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲_____（去了/没去）(1分)，乙_____（去了/没去）(1分)，丁_____（去了/没去）(1分)，周末_____（下雨/没下雨）(2分)。

答案：去了，没去，没去，没下雨


解析：
这题同普及组问题求解第1题



2. 方程 a*b =(a or b)  *  (a andb)，在a, b都取[0、中的整数时，共有______组解。（* 表示乘法；or表示按位或运算；and表示按位与运算）

答案：454

解析：
1) 位运算分析
位与运算&：每个二进制位比对，两个1才为1，否则为0
   例如：
1010 & 1101 = 1000 ，结果小于min(1010, 1101)
1010 & 0010 = 0010，b是a的子集，结果等于b

       子集的定义：a里某些1变成0，结果和b一样，则b是子集。
       例如：a=1101,  b=1001

位或运算|：每个二进制位比对，两个0才为0，否则为1

例如：
1010 | 1101 = 1111 ，结果大于max(1010,1101)
1010 | 0010 = 1010，b是a的子集，结果等于a

2) 试题分析
不妨假设a>=b，假如b是a的子集，有a&b=b, a|b=a，则a*b = (a|b) *(a&b)成立

如果b不是a的子集，能否找到a、b使得方程成立呢？
例如：a=a1*a2,  b=b1*b2 并且 a&B=a1*b1,  a|b=a2*b2，则方程也成立
由于题目限制了［0， 31］，直接取几个数验证：
例如a=3*7, b=2*5，a&b = 21&10= 16,  a|b= 21|10 = 31方程不成立
于是，我们就可以按照b是a的子集的方式来计算解的数量。
3) 计算数量
先假设a>=b，
C(5,0)*2^0 +C(5,1)*2^1+…+C(5,5)*2^5
= 1*1 + 5*2 + 10*4 + 10*8 + 5*16 + 1*32
= 243

然后还要考虑两个角度：

最后结果：2*243 – 32 = 452


三、阅读程序写结果（每题8分，共32分）

1. 这道题同普及组第2题


#include <cstdio>
int main() {
  intx;
  scanf("%d",&x);
  intres = 0;
  for(int i = 0; i < x; ++i) {
    if(i * i % x == 1) {
      ++res;
    }
  }
  printf("%d",res);
  return0;
}

输入：15
输出：_________

解析：
答案：4


4. 这道题同普及组第4题


#include <cstdio>
int n, d[100];
bool v[100];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", d + i);
    v = false;
}
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (!v) {
      for (int j = i; !v[j]; j = d[j]) {
        v[j] = true;
      }
      ++cnt;
    }
  }
  printf("%d\n", cnt);
  return 0;
}

输入：10 7 1 4 3 2 5 9 8 0 6
输出：_________


解析：
第一步（模拟）：
1）输入：
2）模拟：枚举的代码，如果没有写过类似代码，就先模拟看能否理解。
3）如果还没有理解，就继续模拟。
第二步（理解）：
          用表格表示d数组，第一行为下标0..9，第二行为输入值
i
0
1
2
3
4
5
6
7
8
9
d
7
1
4
3
2
3
9
8
0
6
         画出图如下：


现在结合刚才的模拟过程，如果你能理解代码的意思，就会知道这是找连通分量数（连通分量是指极大连通子图），答案是6个:


第三步（继续模拟）：
如果根据模拟理解不出代码的含义，也没有关系，继续往下模拟，最后也能得出答案为6（这个过程就不细述了，请自己实现）。



3.
#include <iostream>
using namespace std;
string s;
long long magic(int l, int r) {
  longlong ans = 0;
  for(int i = l; i <= r; ++i) {
    ans= ans * 4 + s -'a' + 1;
  }
  returnans;
}

int main() {
  cin>> s;
  intlen = s.length();
  intans = 0;
  for(int l1 = 0; l1 < len; ++l1) {
    for(int r1 = l1; r1 < len; ++r1) {
      boolbo = true;
      for(int l2 = 0; l2 < len; ++l2) {
       for (int r2 = l2; r2 < len; ++r2) {
         if (magic(l1, r1) == magic(l2, r2)
           && (l1 != l2 || r1 != r2)) {
           bo = false;
         }
       }
      }
      if (bo) {
       ans += 1;
      }
    }
  }
  cout << ans << endl;
  return0;
}

输入：abacaba
输出：_________

解析：
1）首先看一下magic函数：

对指定范围的每个字符，计算出一个数字（相对于’a’字符），将这些数字按照四进制规则累加起来返回。

然后看一下magic函数被调用的地方，if (magic(l1, r1) == magic(l2, r2)



显然，magic函数被用来识别l、r范围内的字符子串是否相等，这是一个哈希函数。



2）main函数：

代码理解：读入字符串，枚举所有子串（通过l1、r1），将此子串与其他所有子串比较哈希，如果哈希相等（重复），就让po为false，然后对po为true的计数加1。

意思：找出所有没有重复的子串。

3） 题解
对abacaba 找出没有重复的子串数：

结果为16
4.
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];

bool isSmall() {
  for(int i = 1; i <= n; ++i)
    if(a != b) return a < b;
  returnfalse;
}

bool getPermutation(int pos) {
  if(pos > n) {
    returnisSmall();
  }

  for(int i = 1; i <= n; ++i) {
    if(!isUse) {
      b[pos]= i; isUse = true;
      if(getPermutation(pos + 1)) {
       return true;
      }
      isUse= false;
    }
  }

  returnfalse;
}

void getNext() {
  for(int i = 1; i <= n; ++i) {
    isUse= false;
  }
  getPermutation(1);
  for (int i = 1; i <= n; ++i) {
    a= b;
  }
}

int main() {
  scanf("%d%d",&n, &t);
  for(int i = 1; i <= n; ++i) {
    scanf("%d",&a);
  }
  for(int i = 1; i <= t; ++i) {
    getNext();
  }
  for(int i = 1; i <= n; ++i) {
    printf("%d",a);
    if(i == n) putchar('\n'); else putchar(' ');
  }
  return0;
}

输入1：6 101 6 4 5 3 2
输出1：_________（3分）
输入2：6 2001 5 3 4 2 6
输出2：_________（5分）

解析：
第一步（代码结构理解）
  
如果看代码结构能理解这是找下一个大排列，那么第二步就可以不看了，直接看第三、四步。

如果看不懂代码的含义，就跟着第二步做小数据模拟，通过模拟来理解代码。

第二步（小数据模拟）
       用小数据模拟有两个好处，一是理解代码，二是找到排列变换的规则。
   
       我们先用三个数字看看，例如输入：3 1 1 2 3
      
初始：n=3, t=1, a=[1,2,3]
首先，main->getNext ->getPermutation(1)，为了下面描述方便，我们用p(i)代替getPermutation(i)。

以下表格描述了一次p(1)的递归调用，最后返回后的b=1 3 2

过程描述：
以上每一级p(i)里面调用下一级p(i+1)来查找全排列，通过后往前变换排列的方式来找到第一个大于a的b。

第三步（解输入1）
       对输入1：6 10 1 6 4 53 2 求解
       n=6,t=10,  a=1 6 4 5 3 2
       按照模拟的思路，找到第10个大的排列 213564

以上，刚开始几行用模拟的思路从左到右找到下一个大的b。

（吐槽，这个程序每次从123456开始枚举，不知道是谁写的代码….）
熟悉了以后就每次针对a序列快速找到下一个。

输入1的答案：2 1 3 5 6 4

第四步（解输入2）
       对输入2：6 200 1 5 34 2 6
       n=6,t=200, a= 1 5 3 4 2 6
需要从上面模拟里面找出规律，才能推出答案。
例如：

由于t=200，所以结果不到365421，到265431用掉了
120+24+6+6+3=159，剩余41次，265431之后的步骤：
   
最后输入2的答案是：3 2 5 6 1 4

四、完善程序（共28分）
1.右侧第一个更大值（这道题同普及组第2题）

对于一个1到n的排列P（即1到n中每一个数在P中出现了恰好一次），令qi为第i个位置之后第一个比Pi值更大的位置，如果不存在这样的位置，则qi = n+ 1。
举例来说，如果n = 5且P为1 5 4 2 3，则q为2 6 6 5 6。

下列程序读入了排列P，使用双向链表求解了答案。试补全程序。（第二空2 分，其余3分）

数据范围 1 ≤ n≤ 105。

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
   (1) ;
  }
  for (int i = 1; i <= n; ++i) {
    R = (2) ;
    L = i - 1;
  }
  for (int i = 1; i <= n; ++i) {
    L[ (3) ] = L[a];
    R[L[a]] = R[ (4) ];
  }
  for (int i = 1; i <= n; ++i) {
    cout << (5) << "";
  }
  cout << endl;
  return 0;
}

解析：
对于本题，如果不理解代码的算法，也可以直接猜答案，因为这道题的线索提示比较明显。至少可以猜对4个空！


1）第一个for：
2）第二个for：
3）第三个for：
4）第四个for：


本题还有一种分析方法，如果想彻底理解和学习算法，点击查看《补充分析 | 普及组完善程序最后一题》。


2.小猪买物品一只小猪要买N 件物品（N不超过1000）。
它要买的所有物品在两家商店里都有卖。第i 件物品在第一家商店的价格是a，在第二家商店的价格是b，两个价格都不小于0 且不超过10000。如果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95 折(价格变为原来的0.95 倍)。

求小猪买齐所有物品所需最少的总额。

输入：第一行一个数N。接下来N行，每行两个数。第i 行的两个数分别代表a，b。
输出：输出一行一个数，表示最少需要的总额，保留两位小数。 _
试补全程序。（第一空2 分，其余3 分）

#include <cstdio>
#include <algorithm>
using namespace std;

const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;

int n, a[maxn], b[maxn];
bool put_a[maxn];
int total_a,total_b;
double ans;
intf[threshold];

int main() {
  //第一部分
  scanf("%d",&n);
  total_a= total_b = 0;
  for(int i = 0; i < n; ++i) {
    scanf("%d%d",a + i, b + i);
    if(a <= b) total_a += a;
    elsetotal_b += b;
  }
  ans =total_a + total_b;
  total_a= total_b = 0;

  //第二部分
  for(int i = 0; i < n; ++i) {
    if( (1) ) {
      put_a= true;
      total_a+= a;
    }else {
      put_a= false;
      total_b+= b;
    }
  }
  if ((2) ) {
    printf("%.2f",total_a * 0.95 + total_b);
    return0;
  }

  //第三部分
  f[0]= 0;
  for(int i = 1; i < threshold; ++i)
    f= Inf;
  inttotal_b_prefix = 0;
  for(int i = 0; i < n; ++i)
    if (!put_a) {
      total_b_prefix += b;
      for (int j = threshold - 1; j >= 0; --j) {
if ( (3) >= threshold && f[j] != Inf)
   ans = min(ans, (total_a + j +a) * 0.95
           + (4) );
        f[j] = min(f[j] + b, j >= a ? (5) :Inf);
      }
    }
  printf("%.2f",ans);
  return0;
}

解析：首先，代码结构理解和1、2空。阅读代码，分成三块来理解：
第一部分：
主要第一个for，接收输入，按照比价策略（贪心），计算总额ans。
比价策略：对每个物品，哪个店价格低就去哪个店购买。
第二部分:
       主要第二个for，按照折后比价策略（贪心），计算总额（total_a*0.95+total_b）。如果a店总额满足打折条件，总额就是最优价格。
       折后比价策略：对每个物品，按a店打95折的价格，再看哪个价格低就去那个店购买。
       假如a店总额不满足打折条件，则问题转化为0-1背包问题，进入第三部分。
      
第三部分：
       主要第4个for，按照动态规划(背包问题)的策略，计算总额ans。
这三部分对应了三种渐进的贪心思路，可能是想输出三种方法的结果进行比较。
空1和空2就在第二部分，按照折后比较策略填写：
3）动态规划策略
假如第二部分累加的total_a小于50000，不能打折，需要将部分b店物品放到a店购买，以便a店累加起来可以打折，并且总额度最小。
对于第二部分算出来到b店购买的每个物品，都可选择转到a店，或不转，要求总额最小，这就是一个01背包问题。
f(j)为动态规划状态，表示前i个物品，有若干个要把原b店物品转到a店购买，在a店购买j的情况下（额度超过50000可打折），还在b店购买的的最小金额。
理解：原b店购买的物品，继续在b店购买为0，转到a店购买为1。
空3从下面的折扣计算公式里可以得到a店总金额：  total_a+ j + a  

空4在min的后半部分计算从b转移到a购买后的新的总额的里面，即b店总金额：
    total_b  + f[j] -  total_b_prefix

空5为状态转移： f[j – a[j]]

特别推荐：信息学在往后的生活中将会越来越重要，这也是信息学奖项被各大高校作为自主招生条件的原因，想以信息学作为孩子自主招生突破口的家长，可以联系管理员微微妹qq:985052335咨询，我们有非常优秀的师资推荐，金牌教练在手，奖项不怕没有！



【壹牛】2019高考家长2群 702946449（限2019年高考生家长加入）
【壹牛】2020 高考家长3群704328650（限2020年高考生家长加入）
【壹牛】2021高考家长2群714481580（限2021年高考学生家长加入）
【壹牛】2019 中考家长2群524951461（限2019年中考学生家长加入）
【壹牛】2020 中考家长群 602378231（限2020年中考学生家长加入）
【壹牛】2021中考家长2群701640084（限2021年中考学生家长加入）
【壹牛】2019小升初家长2群933288861（限2019年小升初学生家长加入）
【壹牛】2020小升初家长群153776075（限2020年小升初学生家长加入）
【壹牛】小学家长群 122284038（限4年级及以下学生家长加入）
【壹牛】留学自助交流群 606486338（限关注国际高中、出国留学的学生家长加入）






作者: Cappuccino    时间: 2018-10-27 09:23
谢谢分享，辛苦了
作者: 世君虹宇    时间: 2019-6-30 07:23
学习了，谢谢分享。
作者: 双鱼YY    时间: 2019-11-25 14:51
谢谢分享，辛苦了
作者: 841789857    时间: 2020-1-2 17:34
非常感谢楼主的分享.3Q
作者: tbh_01    时间: 2020-1-13 10:29
谢谢分享！！
作者: tbh_01    时间: 2020-1-13 10:40
谢谢分享！！
作者: tbh_01    时间: 2020-10-28 17:09

楼主辛苦了，多谢资料！



欢迎光临 壹牛家长圈- (http://www.16jzq.com/bbs/) Powered by Discuz! X3.2