第十八次CCF计算机软件能力认证总结与经验分享

成绩

首先晒一下成绩。
成绩
成绩单
成绩单

认证经历

这是第二次参加CCF认证,第一次是在大四的时候,部分考研的同学需要用CCF的成绩作为考研复试机试成绩,找班主任(也是院长)请假去其它学校参加考试。院长一听,就去了解一下CCF认证,觉得还不错,就向那边将我们学校申请为CCF考点,但是一次CCF考试的报名的人数需要达到一定人数才能进行,然后就出现了下面戏剧性的一幕:院长要求XX,XX和XX几个专业的所有大四学生必须参加第16次的CCF考试,并且免报名费,学院出钱。我就这样参加了CCF的考试。第一次参加CCF考试,经验不足。虽然平时有刷天梯赛和蓝桥杯的题目,但是两者的出题思路及考查点不太一样,特别是CCF第3题的题目长度在蓝桥杯和天梯赛基本见不到。并且第16次认证的题目比往年难多了,第2题求中缀表达式的值,这是栈的常见的应用,当时比较执拗,想的是如何用栈将中缀表达式转成后缀表达式,然后再用栈对后缀表达式的值,在这道题上花费了太长时间,到了最后才选择暴力的方法,看了第3题和第4题的题目,选择做了第4题,与进程死锁有关。当时很快有了模拟的思路,写完时间也差不多了,赛后第4题得了80分还不错。但是第1题却破天荒的错了,后来分析错误原因:用了g%的格式控制符。但最后提交只得了一点分,所以,这里需要提醒各位的是,考试建议使用常用的写法,有一些写法不同的编译器不一定能通过。总的来说,第一次认证考试体验感不是很好,题目长(3 4题都很大,并且涉及专业知识看了比较难受)并且题目有些问题,中途组委会通知改的。考试时采用的策略也不够明智,在第2道上花费太长时间,很大一部分时间是想着如何用常规解法去解题,而忽略了快捷的暴力解法。
周日参加的第二次CCF认证考试,题意很好理解。很快把1、2和4题做出来了(大概花了一个半小时),这里大概说一下解题思路。

201912-1报数 题解

题目大意是4个人轮流报数从1开始,遇到7的倍数或含7的数就跳过。题目输入是n表示的4个人总共报的数(不含跳过的数)。
思路很简单:模拟用idx表示当前报数人的编号,num表示当前报的数,i计数(不含路过的数)。如果当前数是7的倍数或含7的数,则idx跳过的数加1,然后i不变。反之,idx跳过的数不变,i+1。

201912-1报数 考试时代码(100分)

#include<bits/stdc++.h>
using namespace std;

bool judge(int num){
    if(num % 7 == 0){
        return true;
    }
    int tmp = num;
    while(tmp){
        if(tmp % 10 == 7){
            return true;
        }
        tmp = tmp / 10;
    }
    return false;
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, cnt[4], num = 0, idx = 0;
    memset(cnt, 0, sizeof(cnt));
    scanf("%d", &n);
    for(int i = 0; i < n;){
        ++num;
        if(judge(num)){
            ++cnt[idx];
        }
        else{
            ++i;
        }
        idx = (idx + 1) % 4;
    }
    for(int i = 0; i < 4; ++i){
        printf("%d\n", cnt[i]);
    }
    return 0;
}

201912-2回收站选址 题解

题目大意:先给所有垃圾堆的坐标,然后从这些垃圾堆中选出回收站,回收站需满足:首先上下左右必须都是垃圾堆,然后4个对角的垃圾堆的个数表示该回收站的分数。最后需要统计的是得分为0, 1, 2, 3, 4回收站的个数。
思路:首先选用map对所有垃圾堆的坐标进行标记(因为垃圾堆的坐标可能为负值,用int数组不能直接标记,除非用哈希函数映射),并用vector存下所有垃圾堆的坐标。然后遍历vector中按题目给出的要求判断即可。注意这里vector中的元素和map的键都是pair类型。

201912-2回收站选址 考试时的代码(100分)

#include<bits/stdc++.h>
using namespace std;

map<pair<int, int>, bool>myMap;
vector<pair<int, int>>vec;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int dir2[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
int cnt[5];
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, x, y, nx, ny;
    scanf("%d", &n);
    myMap.clear();
    vec.clear();
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &x, &y);
        vec.push_back(make_pair(x, y));
        myMap[make_pair(x, y)] = true;
    }
    for(int i= 0; i < n; ++i){
        x = vec[i].first;
        y = vec[i].second;
        bool flag = true;
        int num = 0;
        for(int i = 0; i < 4; ++i){
            nx = x + dir[i][0];
            ny = y + dir[i][1];
            if(myMap.find(make_pair(nx, ny)) == myMap.end()){
                flag = false;
                break;
            }
        }
        if(flag){
            for(int i = 0; i < 4; ++i){
                nx = x + dir2[i][0];
                ny = y + dir2[i][1];
                if(myMap.find(make_pair(nx, ny)) != myMap.end()){
                    ++num;
                }
            }
            cnt[num]++;
        }
    }
    for(int i = 0; i < 5; ++i){
        printf("%d\n", cnt[i]);
    }
    return 0;
}

201912-4区块链 题解

我的理解是:首先根据题意可以建图,然后图中的每个结点都维持了一条链,每个结点初始时,链上都有一个编号为0的初始块。然后有两个操作:查询操作和更新操作。在进行查询操作和更新操作都需要检查在此之前,是否存在其它节点的更新操作的信息传过来,如果有的话,则需要判断传播节点的主链l_1与当前节点的主链l_2关系,l_1的长度大于l_2的长度,直接令l_2 = l_1。如果len(l_1)=len(l_2)l_1的最后一个元素的值小于l_2的最后一个值,则令l_2 = l_1。注意,一旦结点维持的主链的信息更新,就需要将其传播给相邻节点(存在传播时长)。我考试的时侯是用一个队列来维持这个传播的更新信息,存储的元素包含节点值,信息到达节点的时刻,主链三个信息。我估计可能是数据太大的时候,队列可能会内存超限。

201912-4区块链 考试时的代码(70分)

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int time;
    int u;
    vector<int>vec;
};
queue<Node>que;
vector<vector<int>>gra(505, vector<int>());
vector<vector<int>>block(505, vector<int>());
void toNum(string s, vector<int>& res){
    res.clear();
    int num = 0;
    for(int i = 0; i < s.size(); ++i){
        if(isdigit(s[i])){
            num = num * 10 + s[i] - '0';
        }
        else{
            res.push_back(num);
            num = 0;
        }
    }
    if(num != 0)
        res.push_back(num);
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n, m, t, k;
    int u, v, a, b, c;
    string s;
    vector<int>res;
    while(!que.empty()){
        que.pop();
    }
    gra.clear();
    block.clear();
    for(int i = 0; i < 505; ++i){
        block[i].push_back(0);
    }
    scanf("%d%d",&n, &m);
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        gra[u].push_back(v);
        gra[v].push_back(u);
    }
    scanf("%d%d", &t, &k);
    getchar();
    for(int i = 0; i < k; ++i){
        getline(cin, s);
        toNum(s, res);
        while(!que.empty()){
            Node frt = que.front();
            if(frt.time <= res[1]){
                que.pop();
                int u = frt.u, v;
                for(int i = 0; i < gra[u].size(); ++i){
                    v = gra[u][i];
                    if(block[v].size() < frt.vec.size()){
                        block[v] = frt.vec;
                        Node tmp;
                        tmp.time = frt.time + t;
                        tmp.u = v;
                        tmp.vec = block[v];
                        que.push(tmp);
                    }
                    else if(block[v].size() == frt.vec.size()){
                        if(block[v].back() > frt.vec.back()){
                            block[v] = frt.vec;
                            Node tmp;
                            tmp.time = frt.time + t;
                            tmp.u = v;
                            tmp.vec = block[v];
                            que.push(tmp);
                        }
                    }
                }
            }
            else{
                break;
            }
        }

        if(res.size() == 3){//update
            block[res[0]].push_back(res[2]);
            Node tmp;
            tmp.time = res[1] + t;
            tmp.u = res[0];
            tmp.vec = block[res[0]];
            que.push(tmp);
        }
        else{
            int u = res[0];
            printf("%d", block[u].size());
            for(int i = 0; i < block[u].size(); ++i){
                printf(" %d", block[u][i]);
            }
            printf("\n");
        }
    }
    return 0;
}

201912-3化学方程式 题解

题目大意:化学方程式配平,检查两边的元素是否相等。
考试只考虑了60%的测试用例,带括号的一直调试不通(其实也算不上调试,我的调试有问题,只能用printf慢慢输出了)。具体见代码,过60%很容易。

201912-3化学方程式 考试时的代码(60分)

#include<bits/stdc++.h>
using namespace std;

map<string, int>myMap1, myMap2;

void deal(string s, map<string, int>& myMap){
    int num = 1, len = s.size();
    for(int i = 0; i < s.size(); ++i){
        if(isdigit(s[i])){
            num = 0;
            while(isdigit(s[i])){
                num = num * 10 + (s[i] - '0');
                ++i;
            }
            --i;
        }
        else if(isupper(s[i])){
            string tmp;
            int sum = num;
            tmp.push_back(s[i]);
            if(i < len - 1 && islower(s[i + 1])){
                ++i;
                tmp.push_back(s[i]);
            }
            if(i < len - 1 && isdigit(s[i + 1])){
                int tmpNum = 0;
                ++i;
                while(i < len && isdigit(s[i])){
                    tmpNum = tmpNum * 10 + (s[i] - '0');
                    ++i;
                }
                --i;
                sum = sum * tmpNum;
            }
            if(myMap.find(tmp) != myMap.end()){
                myMap[tmp] = myMap[tmp] + sum;
            }
            else{
                myMap[tmp] = sum;
            }
        }
    }

}
void cal(string s, map<string, int>& myMap){
    int idx = 0, tmp;
    string str;
    while((tmp = s.find('+', idx)) != -1){
        str = s.substr(idx, tmp - idx);
        deal(str, myMap);
        idx = tmp + 1;
    }
    str = s.substr(idx);
    deal(str, myMap);
//  for(auto iter = myMap.begin(); iter != myMap.end();++iter){
//      cout << iter->first << ":" << iter->second<<endl;   
//  }
}
int main(){
//  freopen("D://a.txt", "r", stdin);
    int n;
    string s;
    scanf("%d", &n);
    getchar();
    for(int i = 0; i < n; ++i){
        getline(cin, s);
        int idx = s.find('=');
        string str1 = s.substr(0, idx);
        string str2 = s.substr(idx+1);
        myMap1.clear();
        myMap2.clear();
        cal(str1, myMap1);
        cal(str2, myMap2);

        if(myMap1.size() != myMap2.size()){
            printf("N\n");
        }
        else{
            bool flag = true;
            for(auto iter1 = myMap1.begin(), iter2 = myMap2.begin(); iter1 != myMap1.end() && iter2 != myMap2.end(); ++iter1, ++iter2){
//              cout << iter1->first << ":" << iter1->second<<endl;
//              cout << iter2->first << ":" << iter2->second<<endl;
                if(iter1->first != iter2->first || iter1->second != iter2->second){
                    flag = false;
                    break;
                }

            }
            if(flag){
                printf("Y\n");
            }
            else{
                printf("N\n");
            }
        }
    }
    return 0;
}

这次在第3题仍然采用不太明智的策略,则开始就考虑了多重括号嵌套的情况,然后代码写了很长时间,真的很长时间,因为一直没有理清思路。后来写完了,运行一直有问题,排错很长时间无效,最后又只能放弃后40%的测试用例,专心调试前60%的用例,很快就通过。所以,在这里需要注意的是,对于用例层层递进的情形,代码如果一时不能处理所有情况,也可以逐渐完善,先保证通过最简单的测试用例,再考虑其它情况。

反思

可能是最后一次CCF,成绩离预期还是有点小差距,毕竟写题解的过程发现题目并不是很难,所以存在的问题还是要反省。
前一个半小时做完1,2,4题,后两个半小时做第3道题只得60分,对于时间利用率不高。做完1,2,4题大脑开始有点反应不过来(身体还是有点虚啊),第3题对于括号嵌套的情形迟迟没想清楚,导致代码Bug横生,如果及时调整思绪,从简单的情形做起,逐渐增加难度,完善代码,通过一重括号的测试用例应该没有问题。这里可以+20。第5题是大数模拟,听说水个20分没问题。用c++写个大数运算更应该没问题,只是麻烦,这里可以+20。最佳可达370+。
DEV的调试无法使用属于特殊情况,不应归咎。但个人的心态的调整,做题策略的更换,做题时间的分配却应该以时间,地点,条件为转移(巧妙将马克思原理应用于实践)。流水不腐,户枢不蠹。

经验分享

针对C++
1. 头文件用万能头文件避免include一堆其它头文件,带来记忆负担。代码如下:

#include<bits/stdc++>
using namespace std;
  1. 从文本读入数据,对于3, 4, 5题,题目的输入往往很长,而它的题目往往又是图片,不能用CV大法。这时,就能充分发挥文件读入的优势了。使用方法,在main函数的第一行加入以下代码freopen("D://a.txt", "r", stdin)然后将数据粘贴进入D盘下的a.txt,这个路径可以自定义,然后运行的时候,直接从文件输入,输出仍在控制台。
    注意:提交的时候freopen("D://a.txt", "r", stdin)一行一定要注释掉,一定要注释掉,一定要注释掉,重要的事情说三遍,不然提交会是0分。
    我常用的模板文件代码为:
#include<bits/stdc++>
using namespace std;

int main(){
    //freopen("E://a.txt", "r", stdin);
    return 0;
}
  1. 常用的stl的数据结构及函数一定要牢记,考试的时候能事半功倍。比如:数据结构:map(这次的2 3 题都有用到),setpairstackqueue(其中优先队列蛮香的),stringvector等。函数如sort(排序),binary_search(二分查找),cctype的字符判断函数isdigit(是否为数字),isupper(是否为大写字母),islower(是否为小写字母)等,stoi(string转int),atoi(字符串转int),sprintf等。
  2. c++11是真香的,里面有正则表达式,它能让字符串的处理更加简单。有unordered_mapunordered_set能有效解决查询超时的问题。
  3. 掌握常见的算法:DFSBFSPrimDijstra并查集等,虽然最近几次考的第4题模拟都能做的,不会涉及算法。

针对CCF考试
1. 做题策略:我一般是1 2 4 3的顺序,如果第3题的题意比较容易理解,容易模拟,可以先做。第5题可以过前面简单规模,简单逻辑的用例。
2. 考试的时候无任何反馈,类似于蓝桥杯,与pat的在线评测不同,所以对于1,2题需仔细设计测试用例,保证得满分。
3. 注意输入输出的格式, 这个有时候很致命,201903-2的中缀表达式的那一题,当时我一个同学就把乘号当成常见的*,实际是x(小写的x),结果可想而知。对于输出YESNO的,稍有不慎,会看成YesNo。 这种情况理应避免。
4. 平常多练,注重首次通过率。

我要分享就这么多,这次200+,满足毕业答辨的要求了,2019太过平淡无奇,也算完成了一个小目标。,明天继续一天一道 LeetCode打卡任务,暂时告别CCF。

转载请注明:Onwaier‘s Blog » 第十八次CCF计算机软件能力认证总结与经验分享