向错题说声谢谢——刷2010年初赛题有感

时间：2020-05-16 23:43:56 阅读：100 评论：0 收藏：0 [点我收藏+]

　　今天我做了一套NOIP2010年初赛的真题，由于在空闲时间中爸爸给我讲了很多初赛可能考到的计算机常识，所以这次的刷题比之前的有所进步，28道题考了71分，错了4个，但还有进步的空间，希望大家多多指教。下面呢我就整理一下我的错题。虽然错题是你成功路上的绊脚石，但是也要对错题说声：谢谢！因为它好不留情面地告诉了你现在的不足。

　　错题1：

　　双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是（）。

　　 A. p->rlink->llink = p->rlink;

　　　　p->llink->rlink = p->llink; delete p;

　　 B. p->llink->rlink = p->rlink;

　　　　p->rlink->llink = p->llink; delete p;

　　 C. p->rlink->llink = p->llink;

　　　　p->rlink->llink->rlink = p->rlink; delete p;

　　 D. p->llink->rlink = p->rlink;

　　　　p->llink->rlink->llink = p->llink; delete p;

　　正确答案： A

　　这道题所涉及的双向链表我还没学到，在此不做过多的讲解，我先通过博客方式记住它。我真想抓紧把D2，D3的课程学完呀！

　　错题2：

　　关于拓扑排序，下面说法正确的是（）。

　　 A. 所有连通的有向图都可以实现拓扑排序
　　 B. 对同一个图而言，拓扑排序的结果是唯一的
　　 C. 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面
　　 D. 拓扑排序结果序列中的第一个结点一定是入度为0的点

　　正确答案： D

　　这道题要考的拓补排序我也没有学到，哎，书到用时方恨少，出道太晚还是不行呀！

　错题3：

　　完善程序：

　　（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     const int SIZE = 1000;
 7         
 8     int n, r, p[SIZE], i, j, k, ans;
 9     bool tmp;
10     
11     cin>>n;
12     r = 1;
13     p[1] = 2;
14     for (i = 3; i <= n; i++) {
15         [    ①    ];
16         for (j = 1; j <= r; j++)
17             if (i % [     ②   ]  == 0) {
18                 tmp = false;
19                 break;
20             }
21         if (tmp) {
22             r++;
23             [    ③   ] ;
24         }
25     }
26     
27     ans = 0;
28     for (i = 2; i <= n / 2; i++) {
29         tmp = false;
30         for (j = 1; j <= r; j++)
31             for (k = j; k <= r; k++)
32                 if (i + i == [     ④   ] ) {
33                     tmp = true;
34                     break;
35                 }
36         if (tmp)
37             ans++;
38     }
39     cout<<ans<<endl;
40     return 0;
41 }

若输入n为2010，则输出[ ⑤ ]时表示验证成功，即大于2且不超过2010的偶数都满足哥德巴赫猜想。

　　正确答案： tmp=1 / tmp=true

　　正确答案： p[j]

　　正确答案： p[r]=i

　　正确答案： p[j]+p[k] / p[k]+p[j]

　　正确答案： 1004

　　哥德巴赫猜想的代码我之前写过，只需要写一个判断质数的函数，再循环枚举判断就行，但这道题的思路我怎么也没看明白，最后导致没做上。

　　错题4：

　　完善程序：
　　**(过河问题）**在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n（2≤n<100）和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为2+1+4=7。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int SIZE = 100;
 5 const int INFINITY = 10000;
 6 const bool LEFT = true;
 7 const bool RIGHT = false;
 8 const bool LEFT_TO_RIGHT = true;
 9 const bool RIGHT_TO_LEFT = false;
10 
11 int n, hour[SIZE];
12 bool pos[SIZE];
13 
14 int max(int a, int b)
15 {
16     if (a > b)
17         return a;
18     else
19         return b;
20 }
21 
22 int go(bool stage)
23 {
24     int i, j, num, tmp, ans;
25     if (stage == RIGHT_TO_LEFT) {
26         num = 0;
27         ans = 0;
28         for (i = 1; i <= n; i++)
29             if (pos[i] == RIGHT) {
30                 num++;
31                 if (hour[i] > ans)
32                     ans = hour[i];
33             }
34         if ([    ①    ])
35             return ans;
36         ans = INFINITY;
37         for (i = 1; i <= n - 1; i++)
38             if (pos[i] == RIGHT)
39                 for (j = i + 1; j <= n; j++)
40                     if (pos[j] == RIGHT) {
41                         pos[i] = LEFT;
42                         pos[j] = LEFT;
43                         tmp = max(hour[i], hour[j]) +[     ②    ];
44                         if (tmp < ans)
45                            ans = tmp;
46                         pos[i] = RIGHT;
47                         pos[j] = RIGHT;
48                     }
49         return ans;
50     }
51     if (stage == LEFT_TO_RIGHT) {
52         ans = INFINITY;
53         for (i = 1; i <= n; i++)
54             if ([    ③    ]) {
55                 pos[i] = RIGHT;
56                 tmp =[    ④    ];
57                 if (tmp < ans)
58                     ans = tmp;
59             [        ⑤    ];
60             }
61         return ans;
62     }
63     return 0;
64 }
65 
66 int main()
67 {
68     int i;
69         
70     cin>>n;
71     for (i = 1; i <=n; i++) {
72         cin>>hour[i];
73         pos[i] = RIGHT;
74     }
75     cout<<go(RIGHT_TO_LEFT)<<endl;
76     return 0;
77 }

　　正确答案： num <= 2 / num < 3|num == 2

　　正确答案： go(LEFT_TO_RIGHT)

　　正确答案： pos[i] == LEFT / LEFT == pos[i]

　　正确答案： hour[i] + go(RIGHT_TO_LEFT) / go(RIGHT_TO_LEFT) + hour[i]

　　正确答案： pos[i] = LEFT

　　这次71分，虽然距离满分还差很远，但是对我个人已经进步不小了，因为上周第一次刷仅仅53分。成绩的提升因为我这几天学习了一些计算机常识知识，所以这次常识类题目没有出错，看来闲暇时光多去看看书还是非常受益的。每天进步一点点，More and more！我会继续努力的！

向错题说声谢谢——刷2010年初赛题有感

原文：https://www.cnblogs.com/yanxinyi-cpp/p/12902571.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)