相聚壹牛，和更多牛爸牛妈们一起交流！
您需要 登录 才可以下载或查看，没有帐号？注册
x
本帖最后由 甜甜圈 于 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：
- F(x)=x, 0<=x<=1
- F(x)=0, x<0
- F(x)=1, x>1
- 概率密度函数为：f(x)=1,0<=x<=1, 其它为0
- 期望为： = 1/2
显然，两个点的期望长度|b-a|会小于|b-0|的期望，可以大胆猜测答案为B。
如果还想彻底推导，继续往下看：
3）距离t = |a-b| = max(a,b) – min(a, b)
4）max(a, b)的期望计算：
- 分布函数为F(x)^2 =x^2
- 概率密度函数为f(x) =2x
- Emax(a, b)= = 2/3
5）min(a, b)的期望计算：
- 分布函数为1-[1-F(x)]^2= 2x-x^2
- 概率密度函数为f(x) =2-2x
- Emin(a, b) = = 1/3
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个结点的二叉树有两个，一个有左子结点，另一个有右子结点
- 其它三个选项都是1个
2）如果知道Catalan数，那么就会知道A是错的，应为n个结点的二叉树形态个数
9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（D）。
A. 1 : 2
B. 2 : 1
C. 1 : 3
D. 1 : 1
解析：
- 任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一，说明每轮、每次抽取都互不影响。那么抽中篮球继续抽，下一轮也是等概率，总比例肯定接近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题：
- 如果知道x = x&(x-1)是二进制从后往前去掉1个1的话，答案B自然知道。
- 如果不知道的话，就自己模拟一下吧，比如用一个数5=(101)2
- A选项模拟，结果为3
- B选项模拟，结果为2
- C选项模拟，死循环
- D选项模拟，死循环
二、多项选择题（每题2分，共10分）
1. NOIP 初赛中，选手可以带入考场的有（AB）。
A. 笔
B. 橡皮
C. 手机（关机）
D. 草稿纸
解析：
《noi竞赛规则》：
- 选手可以携带书写工具，如钢笔、铅笔等，以及手表和适量的衣物等进入赛场。
- 选手不可以携带上述规定之外的其它物品，如纸张、书籍、食品、饮料等进入赛场。选手被严格禁止携带软盘、光盘、U盘等存储设备和介质，以及手机、电子辞典、PDA等电子及通信设备。
以上如果记不住，就从防止作弊的角度考虑一下。
2. 2-3树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同。
如果一棵2-3 树有10个叶结点，那么它可能有（CD）个非叶结点。
A. 5
B. 6
C. 7
D. 8
解析：
1）最多的非叶结点：
- 最底层按2个一组，则倒数第二层有5个
- 5个按2、3分，则倒数第三层有2个
- 然后是根
- 一共5+2+1=8个
2）最少的非叶结点：
- 最底层按3、3、2、2分，则倒数第二层有4个
- 倒数第二层按2、2分，倒数第三层有2个
- 然后是根
- 一共4+2+1=7个
3. 下列关于最短路算法的说法正确的有（ABD）。
A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。
B. 当图中不存在负权边时，调用多次Dijkstra 算法能求出每对顶点间最短路径。
C. 图中存在负权回路时，调用一次Dijkstra 算法也一定能求出源点到所有点的最短路。
D. 当图中不存在负权边时，调用一次Dijkstra 算法不能用于每对顶点间最短路计算。
解析：
- Dijkstra是单源最短路算法，用来求某个顶点到其它各点的最短路径，多次调用可求出所有顶点间的最短路径。
- 当有负权回路或负权边时，最短的计算会不正确，就不能用此算法了。
4. 下列说法中，是树的性质的有（ABD）。
A. 无环
B. 任意两个结点之间有且只有一条简单路径
C. 有且只有一个简单环
D. 边的数目恰是顶点数目减1
解析：
- 这都是树的常识，连通、无环、n顶点、n-1边，任意两点仅一条简单路径
5. 下列关于图灵奖的说法中，正确的有（BCD）。
A. 图灵奖是由电气和电子工程师协会（IEEE）设立的。
B. 目前获得该奖项的华人学者只有姚期智教授一人。
C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。
D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称.
解析：
来自百度百科：
- 图灵奖由美国计算机协会（ACM）于1966年设立，专门奖励那些对计算机事业作出重要贡献的个人 。
- 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。
- 因此它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
- 获奖者里面，华人学者目前仅有2000年图灵奖得主姚期智一人。
二、问题求解（每题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
- 如果a、b有某个位分别为0、1，则结果比原带1的数小
- 存在关系式：a &b <= min(a, b)
- 当a、b存在子集关系时，a&b== min(a, b)
例如：
1010 & 1101 = 1000 ，结果小于min(1010, 1101) 1010 & 0010 = 0010，b是a的子集，结果等于b
子集的定义：a里某些1变成0，结果和b一样，则b是子集。
例如：a=1101, b=1001
位或运算|：每个二进制位比对，两个0才为0，否则为1
- 如果a、b有某个位分别为0、1，则结果比原带0的数大
- 存在关系式：a | b>= max(a, b)
- 当a、b存在子集关系时，a|b== max(a, b)
- 由于或运算不会进位，存在关系式：a|b < 2*max(a, b)
例如： 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， - a的取值以1的个数来定，即从5里面取i个1，i从0到5。每个i都是一个C(5, i)
- 对于每个i（1的个数）的a，其子集数目为2^i次（即某个1要不要）
- 根据乘法原理和加法原理：
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
然后还要考虑两个角度： - 243是假设a>=b的，对于a<=b的也是类似，所以要乘以2
- 乘以2实际对于a==b的重复计算了，0-31共32个重复，要减去。
最后结果：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
输出：_________
解析：
- 枚举i从0到x-1的数，如果i*i % x == 1就计数，输出计数。
- 直接模拟（x=15），一共4个++：
答案：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）输入：
- 先输入n = 10
- 再输入10个数给d数组
- 初始化v数组都为false
2）模拟：枚举的代码，如果没有写过类似代码，就先模拟看能否理解。
- 模拟枚举里的i=0（第一轮）
- 初始：cnt=0，v[0] = false，if判断成立，进入分支
- for：
- j=0，判断!v[0]成立，v[0]设为true，然后j=d[0]=7
- j=7，判断!v[7]成立，v[7]设为true，然后j=d[7]=8
- j=8，判断!v[8]成立，v[8]设为true，然后j=d[8]=0
- j=0,，判断!v[0]不成立，退出循环
- cnt加1，变成1
- 注意v数组变化，已经访问过的下标0、7、8、9都为true
3）如果还没有理解，就继续模拟。
- 模拟枚举里的i=1（第二轮）
- 初始：cnt=1, v[1]=false，if判断成立，进入分支
- for：
- j=1，判断!v[1]成立，v[0]设为true，然后j=d[1]=1
- j=1，判断!v[1]不成立，退出循环
- cnt加1，变成2
- 注意v数组变化，现在0、1、7、8、9都为true
第二步（理解）：
- d数组，下标i=0..9表示节点，d表示i节点连接的节点
用表格表示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个:
- 0 -> 7 -> 8 -> 0
- 1 -> 1
- 2 -> 4 -> 2
- 3 -> 3
- 5 -> 3
- 6 -> 9 -> 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 找出没有重复的子串数：
- 一个字符：a b a c a b a，共1个
- 两个字符：ab ba ac ca abba，共2个
- 三个字符：aba bac aca cab aba，共3个
- 四个字符：abac baca acab caba，共4个
- 五个字符：abaca bacab acaba，共3个
- 六个字符：abacab bacaba，共2个
- 七个字符：abacaba，共1个
结果为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分）
解析：
第一步（代码结构理解）
- isSmall函数：判断a数组是否比b小（字典比较）
- getPermutation：找出下一个比a大的排列b(怎么找先不管)
- next函数：调用getPermutation找出下一个比a大的排列b，然后让a等于b（为下次再往后找做准备）
- main：连续调用next函数（t次），找出下t个大的排列，然后输出
如果看代码结构能理解这是找下一个大排列，那么第二步就可以不看了，直接看第三、四步。
如果看不懂代码的含义，就跟着第二步做小数据模拟，通过模拟来理解代码。
第二步（小数据模拟）
用小数据模拟有两个好处，一是理解代码，二是找到排列变换的规则。
我们先用三个数字看看，例如输入：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(1)：i从1开始，b[1]=1，isUse[1]=true,然后调用p(2)
- p(2)：isUse[1]是true所以跳过1，i=2，b[2]=2，然后调用p(3)
- p(3)：跳过1、2，i=3, b[3]=3，然后调用p(4)
- p(4)：判断a<b（1 2 3 < 12 3），返回false
- p(3)继续：i已经是3，退出循环，返回false
- p(2)继续：i是2，加为3，b[2]=3，然后再调用p(3)
- p(3)：跳过1，i=2，b[3]=2，然后调用p(4)
- p(4)：判断a<b（1 2 3 < 13 2），返回true
- p(3)继续：返回true
- p(2)继续：返回true
- p(1)继续：返回true
以上每一级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
需要从上面模拟里面找出规律，才能推出答案。 例如： - 153426->153462->153624->153642，共3次
- 153642 -> 154236 -> … -> 154632，共3!＝6次（后三位排列数）
- 154632 -> 156234 -> … -> 156432，共3! = 6次（后三位）
- 156432 -> 162345 -> … -> 165432，共4!=24次（后四位）
- 165432 -> 213456 -> … -> 265431，共5!=120次（后五位）
- 265431 -> 312456 -> … -> 365421，共5!=120次（后五位）
由于t=200，所以结果不到365421，到265431用掉了 120+24+6+6+3=159，剩余41次，265431之后的步骤： - 265431 -> 312456 -> … -> 316542，共24次（后四位）
- 316542 -> 321456 -> … -> 321654，共6次（后三位）
- 321654 -> 324156 -> … -> 324651，共6次（后三位）
- 324651 -> 325146 -> … -> 325614，共5次（后三位，少一个）
最后输入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：
- 意思：输入n个数，放到a数组
- 1 ⃣ -> a[x] = i ， 这个空猜不出来正常，可放弃
- 题目序列是P，代码里却是a，能根据这两点想到a和p不同的话，也许可以猜到答案。
2）第二个for：
- 初始化R数组和L数组（看不懂可以略过，没事，不影响猜答案）
- 看L = i – 1 就能猜出上一句： 2 ⃣ -> i+1
3）第三个for：
- 从小到大删除链表元素（看不懂可以略过，没事，不影响猜答案）
- 看R[L[a]] = R[ (4) ]猜上一句： 3 ⃣ -> R[a]
- 看L[ (3) ] = L[a] 猜下一句：4 ⃣ -> a
4）第四个for：
- 题目要求，找到右侧第一个更大的位置, 肯定是R数组（right的意思）。
- 猜输出： 5 ⃣ -> R
本题还有一种分析方法，如果想彻底理解和学习算法，点击查看《补充分析 | 普及组完善程序最后一题》。
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咨询，我们有非常优秀的师资推荐，金牌教练在手，奖项不怕没有！
【壹牛】2021中考家长2群701640084（限2021年中考学生家长加入） 【壹牛】2019小升初家长2群933288861（限2019年小升初学生家长加入）
|
发表于 2018-10-23 13:53:52
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
转播
分享
淘帖
支持
反对
发表于 2018-10-27 09:23:54
