【计算机本科补全计划】CCF计算机职业资格认证 2017-03 试题初试
【计算机本科补全计划】CCF计算机职业资格认证 2017-03 试题初试
正文之前
我在之前的文章中提到过，我的老师要求我的CCF 考试考个280分来打个底，（没错，我就是那个横跨考研、工作、保研三大领域的男人）相当于是测试下我的能力，所以虽然不知道近期有没有相关的考试，但是我还是开始准备。这种等级考试，当然就是从刷题开始了！！至于什么大纲，什么宝典，见鬼去吧~ 不信这玩意，题海战术从小用到大，骨子里都习惯了。当然还是直接怼题目来得爽了 ~ ~ 而且还可以实践自己的各种知识积淀，自己看书看一遍，简书写笔记写一遍，最后写题写一遍，考试然后再被轮一遍，这么下来还没有十足长进我就不信了！！
正文
2017-03-01题
试题编号 | 2017-03-1 |
|---|---|
试题名称 | 分蛋糕 |
时间限制 | 1.0 s |
内存要求 | 256M |
- 问题描述： 小明今天生日，他有n块蛋糕要分给朋友们吃，这n块蛋糕（编号为1到n）的重量分别为a1, a2, …, an。小明想分给每个朋友至少重量为k的蛋糕。小明的朋友们已经排好队准备领蛋糕，对于每个朋友，小明总是先将自己手中编号最小的蛋糕分给他，当这个朋友所分得蛋糕的重量不到k时，再继续将剩下的蛋糕中编号最小的给他，直到小明的蛋糕分完或者这个朋友分到的蛋糕的总重量大于等于k。 请问当小明的蛋糕分完时，总共有多少个朋友分到了蛋糕？？
- 输入格式 输入的第一行包含了两个整数n, k，意义如上所述。 第二行包含n个正整数，依次表示a1, a2, …, an。
- 输出格式 输出一个整数，表示有多少个朋友分到了蛋糕。
- 样例输入 6 9 2 6 5 6 3 5
- 样例输出 3
- 样例说明 第一个朋友分到了前3块蛋糕，第二个朋友分到了第4、5块蛋糕，第三个朋友分到了最后一块蛋糕。
- 评测用例规模与约定 对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 10000，1 ≤ ai ≤ 1000。
本题标准答案（提交后分数为100分）
/* CCF201703-1 分蛋糕 */
#include <iostream>
using namespace std;
int main()
{
int n, k, count=0, val, sub=0;
cin >> n >> k;
for(int i=1; i<=n; i++) {
cin >> val;
if((sub += val) >= k) {
count++;
sub = 0;
}
}
if(sub > 0)
count++;
cout << count << endl;
return 0;
}我的答案：
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int n,k;
cout<<"First Line:";
cin>>n>>k;
vector<int > cake;
cout<<"Second Line:";
while(n--)
{
int x;
cin>>x;
cake.push_back(x);
}
int Num=0,weight=0;
for (vector<int>::const_iterator iter = cake.begin();iter != cake.end(); ++iter)
{
weight+=*iter;
if (weight>=k)
{
++Num;
weight=0;
}
}
if(weight!=0)
++Num;
cout<<"一共 "<<Num<<" 人获得了 "<<k<<" g 重量的蛋糕"<<endl;
return 0;
}可以看到，思想很接近，只是我做了些许的修缮，所以显得很长，另外，满分答案是直接在输入的时候进行了计算，没有使用数组，向量等容器，确实是优秀答案。而我则是多用了一个vector向量，并且把输入与计算分离（因为有了容器存储，自然可以分离）。好吧，后面拿来一看。发现我的就是个弱鸡，人家对内存的要求比我低得多！！而且最关键的是：速度比我的快，但是我算了下时间复杂度，应该没太大的差别才对，难道读写向量很困难？？？？那我就卧了个大槽了~~~~
搞了半天输入有点偏差，所以后来自己动手写了120个混乱数字，然后直接复制进入算作输入，120个数字，占用了608k，至于用时，我个人感觉还挺快的。
时间我没办法。只能是用sublime的gcc自带的计时，算出来不到一秒。感动~ 但是每次超过500感觉就会直接爆炸，程序直接原地不动了。最后exit 9 ，估计是内存不够？不至于哇！不管了不管了！
完成编译使用时间是0.6s，然后运行的时候我感觉还是很快的，但是这个内存泄漏的问题估计也就是上面的那种满分解法了~ 不知道数组怎么样。我试试。好吧，一样的，看样子vector跟数组都突破不了500这个大关？？？那怎么办。这会0分的吧！！！三题我要280！！！怎么破？？没办法！只能继续怼了!
2017-03-02题
试题编号 | 2017-03-1 |
|---|---|
试题名称 | 学生排队 |
时间限制 | 1.0 s |
内存要求 | 256M |
- 问题描述： 体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。 例如，下面给出了一组移动的例子，例子中学生的人数为8人。 0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8； 1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8； 2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7； 3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。 小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？ * 请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。*
- 输入格式 输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。 第二行包含一个整数m，表示调整的次数。 接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。
- 输出格式 输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。
- 样例输入 8 3 3 2 8 -3 3 -2
- 样例输出 1 2 4 3 5 8 6 7
- 评测用例规模与约定 对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。
提交后得一百分的C++版本的代码（简洁版）:
/* CCF201703-2 学生排队 */
#include <iostream>
using namespace std;
const int N = 1000;
int sno2pos[N+1]; // 学号所在位置
int pos2sno[N+1]; // 位置上的学号
int main()
{
int n, m, p, q;
// 输入数据
cin >> n >> m;
// 初始化
for(int i=1; i<=n; i++) {
sno2pos[i] = i;
pos2sno[i] = i;
}
// 模拟移动过程
for(int i=1; i<=m; i++) {
int pos1, pos2, sno2;
cin >> p >> q;
if(q != 0) {
int move = (q > 0) ? 1 : -1;
int end = (q > 0) ? q : -q;
pos1 = sno2pos[p];
for(int i=1; i<=end; i++) {
sno2 = pos2sno[pos1 + move];
pos2 = sno2pos[sno2];
pos2sno[pos1] = sno2;
sno2pos[sno2] = pos1;
pos1 = pos2;
}
pos2sno[pos2] = p;
sno2pos[p] += q;
}
}
// 输出结果
cout << pos2sno[1];
for(int i=2; i<=n; i++)
cout << " " << pos2sno[i];
cout << endl;
return 0;
}复杂版本的100分标准C++答案代码：
#include <iostream>
using namespace std;
//#define DEBUG
const int N = 1000;
int sno2pos[N+1]; // 学号所在位置
int pos2sno[N+1]; // 位置上的学号
int main()
{
int n, m, p, q;
cin >> n >> m;
for(int i=1; i<=n; i++) {
sno2pos[i] = i;
pos2sno[i] = i;
}
for(int i=1; i<=m; i++) {
int pos1, pos2, sno2;
cin >> p >> q;
if(q != 0) {
int move, end;
if(q > 0) {
move = 1;
end = q;
} else {
move = -1;
end = -q;
}
pos1 = sno2pos[p];
for(int i=1; i<=end; i++) {
sno2 = pos2sno[pos1 + move];
pos2 = sno2pos[sno2];
pos2sno[pos1] = sno2;
sno2pos[sno2] = pos1;
pos1 = pos2;
}
pos2sno[pos2] = p;
sno2pos[p] += q;
}
// if(q > 0) {
// pos1 = sno2pos[p];
// for(int i=1; i<=q; i++) {
// sno2 = pos2sno[pos1+1];
// pos2 = sno2pos[sno2];
// pos2sno[pos1] = sno2;
// sno2pos[sno2] = pos1;
// pos1 = pos2;
// }
// pos2sno[pos2] = p;
// sno2pos[p] += q;
// } else if(q < 0){
// pos1 = sno2pos[p];
// for(int i=1; i<=-q; i++) {
// sno2 = pos2sno[pos1-1];
// pos2 = sno2pos[sno2];
// pos2sno[pos1] = sno2;
// sno2pos[sno2] = pos1;
// pos1 = pos2;
// }
// pos2sno[pos2] = p;
// sno2pos[p] += q;
// }
#ifdef DEBUG
cout << "son: ";
for(int i=1; i<=n; i++)
cout << pos2sno[i] << " ";
cout << endl;
cout << "pos: ";
for(int i=1; i<=n; i++)
cout << sno2pos[i] << " ";
cout << endl;
#endif
}
cout << pos2sno[1];
for(int i=2; i<=n; i++)
cout << " " << pos2sno[i];
cout << endl;
return 0;
}我的答案：
#include <iostream>
using namespace std;
int main()
{
int a,b,m,n;
cin>>n;
int s[n+1];
for (int i = 1; i <=n; ++i)
s[i]=i;
cin>>m;
while(m--)
{
int x,y;
cin>>x>>y;
a=s[x];
if(s[x]<=y)
{
s[x]=1;
y=s[x]-1;
}
else // if (y>0||s[x]<y)
s[x]-=y;
for(int i=1;i<=n;++i)
{
if (i!=x)
{
if(s[i]<=a&&s[i]>=(a-y))
++s[i];
}
}
}
for (int i =1 ; i <=n; ++i)
for (int j = 1; j <= n; ++j)
{
if(s[j]==i)
cout<<j;
}
return 0;
}
下面推演一下看看正确性： 1 2 3 4 5 6 这是本来的顺序 1 4 2 3 5 6 第一次 4 2 之后的顺序 1 4 3 2 5 6 第二次 3 1 之后的顺序 1 4 3 6 2 5 第三次 6 2 之后的顺序 完美符合题目要求，全体仅仅使用一个数组用于存储。时间复杂度为O(n^2)不知道时间上能否通过要求，空间复杂度的话 256M应该是够用了！
我因为时间所迫。所以只做了正向移动，也就是只向前，不向后的运动！思想与标准答案千里之差，但是我觉得我的比较简洁而且看起来应该简单易懂一些！
正文之后
程序改变现实，软件统治世界。程序员需要有精益求精的工匠精神，追求逻辑的极简、时间的最少和存储的最省，并且懂得其中的平衡。 数据表示需要优先考虑，对于许多问题，找到表示该问题的数据结构，问题自然就解决了。 CCF计算机职业资格认证的每一道试题都十分经典，覆盖现实世界中方方面面的问题。这个历年试题解全部用C++语言编写，程序中附有注释，力求解题思路清晰简洁，值得珍藏与模仿。 希望获得100分，仅仅使用原题的样例来测试是不够的，需要自己设计一些样例，并且需要考虑特殊的边界条件。 使用STL的包装类和算法是十分必要，这会简化程序逻辑。 ---以上出自某提供试题与答案的博客~