边缘坐标的编程入门日志

这两节课，同学们学习了STL的各种容器的使用，以及基本的算法函数。STL可以提高我们编程的效率，和降低编程难度，因此同学们应学会常用容器的基本使用方法，以及算法库的几种主要算法。

特别提醒下，课上遇到的set、prority_queue等容器的自定义排序方法，实际上是因为这些容器用的比较器不是函数而是类，因此调用格式不一样，但由于类方法是(）的运算符重载，使用看起来像一个普通函数，因此造成了混乱。这些面向对象编程的方法同学们暂时不用深究，算法竞赛没有这方面的内容，仅在使用STL时遇到这些，只要会用即可。
课后我整理了目前采用的方法，列在下面，大家参考下：

1、sort使用的是函数名或函数指针，例如：
	sort(ar,ar+n);
	sort(ar,ar+n,mycmp);	//自定义函数mycmp
	也可以使用类方法，如：
	sort(ar,ar+n,greater<int>());//greater<int>是一个类，类方法()和函数相同，也是一个函数指针

2、容器使用的是类：
	set<int> s;
	set<int ,greater<int>>;//greater<int>>是一个类，不需要带()
	
	set<int,structcmp>;//自定义类structcmp
	可定义最简单的类structcmp:
	struct structcmp{
		bool operator()(int a,int b){
			return a>b;
		}
	};
	如果set元素是一个pair，可以这样做：
	set<pair<int,int>,structcmp>;//自定义类structcmp
	可定义类structcmp，这个比较器用来解决例程坐标排序问题:
	struct structcmp{
		bool operator()(pair<int,int>a,pair<int,int>b){
			if(a.first==b.first)return a.second>b.second;
			return a.first<b.first;
		}
	};

进一步的使用，可以在上面的简单例程上修改即可。

竞赛班期末总结：

竞赛班暑期课程结束，同学们已经完整学完了CCF教材的入门和基础部分。
这两册不算厚的教材，涉及到所有必要的基础知识和算法，包括递推、递归、枚举、搜索、回溯、动规等算法，包含线性数据结构如数组、链表、栈、队列等，涵盖了普及组考试范围，还同时包含了常用STL算法。

同学们在整个学习过程中，能看出来，大多数时候并不算轻松，部分问题可能需要思考数天，才能吃透，可能有些问题，到学期结束，就算能做出来，但也可能未充分理解或不能举一反三。

这是正常的！希望同学们不要因此影响信心。

算法牵涉面广泛，一个简单问题，可能背景是艰深的数学和工程问题，而这些问题，过去的数学家和计算机学家可能耗费了多年的心血做了各种探索，获得成果并形成各种题型，但甚至一些问题至今都无优秀解，我们不要寄希望于一朝能全部破解。

实际上，在学习过程中，老师感觉到同学们水平一直在提升。到学期末，几乎所有同学，对于以前棘手的C语言普通题目，都能轻松应对迅速解决。大多数同学对低难度的算法题，都能在短时间内解决。部分优秀同学对于中等难度的算法题，也有办法解决。

当然，咱们也要认识到，所学课程还是在普及组范围内，如果要想攻克提高组的难题，目前还不能做到，即使是普及组的难题，要想做到不出错和不超时，得到满分，也有较大困难。这表明，即使知识已经具备，但灵活运用和综合运用却是另一回事，这些解题能力需要更长时间的打造。

总的来说，咱们竞赛班的同学年级普遍较低，大部分同学均在初一或小学，只有少数同学超过初二。理解力、数学基础、知识广度仍有待提高。

后续学习的建议：

1、王潇茗等高年级同学领悟力强，在我部学习成绩优秀，已经具备良好的知识基础和自学能力。由于各自学校课程压力较大，时间紧张，建议参加各自高中的奥赛训练班，重在训练和累积经验。
我部后期也有计划组织短期提高组集训课程，可以参加补充新知识，该课程将集中讲解数据结构和高级算法、离散数学等提高组内容。

2、其他同学，强烈建议再次参加竞赛班课程。
由于年级较低，虽然有较强编程能力，但综合能力不强，相关知识也未达到提高组阶段要求。虽然少数家长期望现在就学习提高组内容，但从我部教学经验看，低年级同学现在就学习提高组内容并不合适，会造成消化不良信心受挫，效果并不好，这也是我部本期暂不开设提高组课程的原因。

一方面加深理解综合运用，增加训练提升解题能力，一方面也等待年龄和其他课程知识的增长，这是相当必要的，编程不仅是编程，也是综合技能。从我部教学经验看，即使优秀同学，复习一次，温故知新，水平提升都是相当明显的。

3、所有同学，保持持续的OJ训练都是相当必要的。

算法竞赛的魅力在于，算法难，但它是科学发展的迫切需要，攻关是勇敢而激动人心的。
我们要做的，就是不断提升理解力和解题能力。
将来，无论我们是否参加算法竞赛或是否获得名次，这都不是评判的唯一标准，最终，我们现在所学的这些强大技术会转化成我们的能力，并体现在未来的工作和事业中，这才是真正的意义所在。祝所有同学百尺竿头，更进一步！

第一节课：

第一课课后任务：
1、浏览入门篇1-2章内容，并完成这两章所有例程。
2、在CCF OJ上注册账号（免费），网址: http://oj.noi.cn/oj/#main/home。
3、1-2章所有习题。
4、CCF OJ ：1011到1015。
练习范围：1002-1010，按照要求，提交程序并通过。

第二节课：

第二课课后任务：
1、下载并安装NOILinux竞赛环境（win7及以上系统，采用虚拟机方式安装），如条件不具备，
可不安装，以后在学校电脑上练习。
关于这部分内容，请等老师另发通知。
2、第3章所有例程

第3组增加任务：
3、CCF OJ:1050之前，1-2级题目
    
第1、2组增加任务：
3、第3章所有习题。
4、CCF OJ ：1050之前，3级及以内的题目

第三节课：

第三节课课堂：
1.安装noilinux。

第四课课后任务：
基本任务：
1、2016年合肥市市赛小学组试卷中的全部题目
2、完成2017年NOIP初赛试题,完成后对照答案
3、完成2018NOIP复赛第2题并用测试数据通过

附加任务：
1、完成2016年NOIP初赛试题，边做边对照答案
2、2018年NOIP复赛第3题，至少通过前50%测试数据

第五课课后任务：
结合课上试卷讲解，深入理解并重做以下试题：
基本任务：
1、选择题，重点理解2、5、7、8、13、14题。
2、阅读程序题1和2，重点第2题的模拟运行过程。
3、完善程序第1题
附加任务：
1、阅读程序第3题，了解题意后，闭卷自己独立编程解决问题。
2、完善程序第2题，深刻理解并完成以下任务：
1）完成一维数组的计数排序
2）完成结构体数组的排序，结构体包括两个整数关键字s和t，要求s按照从大到小，t按照从小到大顺序，完成对结构体排序，排序优先级s高于t。

通过CSP初试的同学，建议每天都进行编程练习。练习的内容主要是教材第二册的课上例程和习题，题目不要太大，仍然以基础训练为主。
下节课，所有同学都需要带笔和练习本，进行课堂练习。

第六课课后任务：
基本任务：
2018年NOIP复赛第三题分解任务，任务的前提数据均包括n和m，以及n个同学的等车时间，任务是相互独立的，分别完成。
样例输入：
5 2
11 3 7 3 1

1、任务1：分段
将题目等车人数分段，按间隔时间分段，如果间隔小于2m，则属于同一段，每段人数最少1个人。间隔达到或超过2m，属于不同段。输出所有分段，
输出的每段格式为每段头和尾的下标，头尾下标用空格隔开。如果一段只有一个数，即头尾下标相同，也要同时输出。
分段样例输出：
1 3
4 4
5 5

2、任务2：计算两个时点之间所有同学的等车时间之和
现有多个询问。每次询问包含两个整数，即开始时点和乘巴士离开的时点，回答为一个整数，值为这两个时点之间的闭区间范围内，
所有来乘车的同学，到乘车离开时的等车时间之和。
样例输入：
1 2
2 5
3 11
样例输出：
1
4
20

附加任务：
和基本任务的数据相同。
3、对任务进行改造，使得时间复杂度为O(1)，即无须循环，直接通过计算得到结果。

4、对无须分段的测试数据（测试数据前50%），用动态规划递推求解。

第七课课后任务：
对于竞赛班的同学来说，在OJ上做题和训练是提高水平的必经之路。洛谷是国内首屈一指的开放OJ网站，请同学们在洛谷网站注册用户，开始进行OJ训练。

基本任务：
1、2014-2018年五年NOIP普及组复赛试卷的第1题和第2题。
附上试卷，请对照试卷题目，自行在以下页面查找对应题目，进行OJ：
https://www.luogu.org/problem/list?keyword=&page=1
以上题目，要求达到100%通过率。如果不能通过，出现各种提示，请参考后面错误代码。

2、如果完成以上试题，仍有时间，则按照课上所说方法：
1）求解第3题部分AC或可能的情况下全部AC。
2）尝试对第3题和第4题进行技巧得分，部分AC。

OJ中常见错误：

Accepted(AC)
    恭喜您的程序正确。
Presentation Error(PE)
    您的程序已接近AC，但是这个输出的格式有点问题。请检查程序的输出是否多了或者少了空格（' '）、制表符（'\t'）或者换行符（'\n'）。
Time Limit Exceeded(TLE)
    您的程序运行的时间已经超出了本题的时间限制。
Memory Limit Exceeded(MLE)
    您的程序运行的内存已经超出了本题的内存限制。
Wrong Answer(WA)
    输出与答案不符，请考虑特殊数据，算法正确性等。
Runtime Error(RE)
    运行时错误，这个一般是程序在运行期间执行了非法的操作造成的。数组下标异常，整数，小数，栈溢出等。
Output Limit Exceeded(OLE)
    您的程序输出内容太多，超过了本题的输出限制。
Compile Error(CE)
    您的程序语法有问题，编译器无法编译。
System Error(SE)
    OJ内部出现错误。我们的OJ可能存在一些小问题，所以出现这个信息请原谅，同时请及时与管理员联系

本次CSP-J初赛小结和复赛展望：
这次我部总有超过10人入围复赛，入围比率约70%，通过比例合乎预期。令人惊喜的是有三位新生通过初赛，另外陈睿羽同学得到82分高分。
没有入围的同学包括其他报名的新生，这些同学本来就抱着尝试的态度，落选不奇怪。遗憾的是，有几位基础还不错的同学被初赛淘汰，这是要重点分析和关注的。
客观来说，本次CSP-J初赛内容难度不算大。考前，我们还组织了两节课的试卷详细讲解，基本上，基础良好的同学，如果考前认真做了五张以上试卷，通过是比较有把握的。

事后分析本次考试情况，发现有两方面需要改进：

1、不重视或训练不足问题
从课上以及课后了解的情况看，被淘汰的几位同学基础还不错，但这些同学疏于大意和懒惰，并没有按老师要求去做课后练习。家长普遍反映孩子有自满倾向，平时不做或很少
做训练，基本就是靠我部每周一个下午课程进行训练。如果这样，那么考出这样的成绩也不奇怪。
另外，除少数同学外，本次通过的同学考分并不高，这也是训练不足的问题。既有同学们的问题，也有我部教学上不够重视的问题。考前学校做了两次课的备考讲解和训练，
也布置了课后练习任务，但考前是国庆长假和中秋假期，间隔时间长，如果同学不够重视，就会导致训练不足，现在看来是需要我部组织进一步针对性的集训的。

得益于考前对试卷的详细讲解，以及自身的良好基础和对考试的重视，本次有三位新生通过了初赛。对比能够发现，被淘汰的几位复习同学是怎样的大意和疏懒。

针对以上训练不足问题，明年我部会安排考前进行针对性集训；同时，同学们一定要提高自我要求，平时加大训练量，最少每周在课后训练两次；
家长则需要在精神上给予鼓励和督促，在时间和条件上给予支持。

2、分析本次初赛内容，发现范围比我们教学使用的标准CCF教材内容范围要广一些，涉及到部分提高组的内容，大约影响分为20分左右。考前我们讲解了其中部分内容，
大约能解决10分，另一部分内容，如果考生认真做布置的试卷，会遇到类似问题并有准备。但可能被淘汰同学并没有认真去做，这样，就可能被影响10分左右。
对此，按计划，我部将在明年暑期开设提高组课程，这是为了适应绝大多数同学的年级情况，这里大多数同学的年级在初一上下。明年暑期学习必要的提高组知识基础，
秋季参赛CSP-J，相信得分肯定会再提高。即使明年参加CSP-S的考试，在基础知识上也不会欠缺。

CSP-J复赛展望：
今年入围复赛的同学，除了在课上认真听课理解，课后按要求完成练习外，应抽更多时间进行OJ训练。由于大部分同学年级仍较低，因此训练还是应该侧重于基础题，
避免做大题，做任务目标单纯而明确的训练，加强基本功，尤其在解题速度和准确性上下功夫。
由于没有提高组的知识储备，今年仍是打基础的一年，我部对同学们的期望得分不高，但希望同学们在应会题型上拿到高分，在较难题型上获得部分分。
如果这样，按近年评奖方式，基础良好的入围同学会拿到一等奖，其他入围同学会获得二等奖。

第八课课后任务：
1、重做2019年CSP-J复赛试题2，要求自己制作符合要求的数据，并进行测试。测试数据应考虑特殊情况，尤其是边界数据和极端数据情况。
2、试题3部分数据分解为以下两个小题：
1）给出1种物品的t天价格，求期末最大价值。
思路是求出各个上涨段，再对每个上涨段计算升值。第一段的投入金额就是期初金额，前一段的期末价值等于后一段的投入金额。最后一段的期末价值就是期末最大价值。
2）给出n种物品的2天价格，求期末最大价值。
这个首先用深度搜索方式做，测试时间复杂度的上限数据。
再尝试用动态规划方式完成。思路是用物品的价格进行组合，比较，自小到大得到每一个金额上的最大收益。这是一个背包问题，暂未学到，请同学们先自己思考，后面课程会讲到。

第九课课后任务：
1、所有同学重做2019年合肥市赛小学组试题1-5题，其他同学不限制时间。如果课上有题目已经通过测试，则跳过。复习同学应争取在半个小时内完成1题，做完后，应在NOILinux平台上编译通过，并自制数据仔细测试通过。
另上节课序列分段没有完成的同学，继续完成。

2、复习同学完成小学组试题第6题。  
解题提示：可以使用用队列模拟排队情况，用队列数组模拟窗口排队情况。

3、下节课需要用到以下内容，请提前准备。  
1）在以下网站注册登录用户，具体操作请自行查看网站说明：  
CCF：http://oj.noi.cn
洛谷：https://www.luogu.com.cn

2）教材和草稿本、笔

本节课课上当堂测试了市赛的部分题目。从测试情况看，陈睿羽等少数同学满分或高分。虽然复习同学普遍比较熟练，解题思路正确，但细节上出错较多，成功率低，部分同学疏忽严重，甚至两次测试结果均为0分。
此外新生同学由于刚学习竞赛知识，测试不理想，属于正常情况。

小学组的题目，不牵涉到算法，测试不理想的原因一是语法基本功方面仍然欠缺，二是对于竞赛环境缺乏经验，三是不重视程序后续检验。平时课上老师演示的不光是思路和编程过程，也在演示检查方法以及对于错误的处理方法。但不少同学显然没有跟进老师教学，并没有按照老师的方法来做，部分提交的答卷根本不能通过样例测试就可以看出。

为此，下节课开始调整学习方法，适当减少演示时间，增加课上测试时间，以更多暴露和纠正学生存在的问题。

第十课课后任务：
教材第2章全部例程和习题
OJ，请自主练习，根据自己时间不限数量，必须测试通过，实在有疑问的，可以查看其他人的解答。提醒，个别OJ题数据有问题。
全部同学：CCF OJ 1-2级练习题
复习同学：CCF OJ 1-3级练习题

本次CSP-J竞赛的回顾
本次CSP-J竞赛初评成绩已出来，部分同学的分数可能会有些变化，但总体上不会有大差别。
本次竞赛成绩有亮点和惊喜，但就本届同学来说，成绩不如预期，因此这里不谈成绩，重点谈不足。深入分析一下原因，以及后面的改进方法。

首先说下各题得分情况，共4题每题100分满分400分，第1、3、4题和预期的得分相当，第2题和预期得分有较大差别。
第1题是很简单的入门题，几乎所有同学都拿到了满分，但也有个别极度草率的同学丢分。
第3、4题按目前我们的学习进度，只能完成部分分数。事实上，我部同学们都拿到了部分分数，基本符合要求。这两题，对比其他培训学校的考生，得分相当。
事实上，全省能正确做出第3和第4题的同学，也只有不到30人。

第2题和预期差异较大，也是同学和老师都需要深刻反思的。在上节课已经讲解过，这道题并不太难，我部几位基础好的同学完全能得满分，但事实上只拿了很少分数或0分。课上分析了班上四个同学的答卷，错误有代表性，是什么样的情况：
张鸿翎题解正确但忽略了优化，只得到45分。
俞越看错题目，10分；
陈睿羽考虑到优化，但题解错误，0分；
秦浩然则弄错输出文件名，0分。
可见，这些同学把这道基础题搞砸了！！！这是老师赛前最担心的事情，反复在课上叮嘱，但还是这样。对此老师也在反思，为什么会出这么大的bug？关于问题的原因，后面进一步分析。
作为对比，曾经在我部学习的两位成绩不错的同学（夏同学和黄同学），虽然第3、4题同样也是部分分，差距不大，但第2题是满分，这样一下子就拉开了上百分的差距。

下面来分析为什么第2题的失败原因？
几位同学赛完后，都觉得这题能得满分，至少也是高分。结果出来后不敢相信，甚至要申诉。几位已经毕业离校的同学，本次考试也是类似情况，自信满满却大失所望。
确实，0分不代表同学的能力，错误甚至微不足道，但结果却很惨烈。

但，这恰说明学生的训练不足，或训练方式存在问题。

这学期，为了上完预定课程内容，我们课上基本上是老师在演示和讲解，每次课老师要讲解和演示3个小时差不多要吐血，这样，课上给同学练习的时间不多，基本上要靠同学们课后练习和OJ补足训练环节。但问题就出在这里，很多同学课上听和看懂例程后，就很自信觉得会了，很少在课后进一步练习和OJ，知识不少，但OJ太少，导致眼高手低，细节上漏洞很多。平时看不出这些问题，但一旦用数据测试，漏洞就出来了。
在上节课，我们用小学组的非常简单的题目来做课堂测试，结果也是很惨，很多同学自己都不相信。

很多家长不知道OJ，OJ就是网上对程序进行严格的数据测试。做OJ是很重要的环节，可以帮助自己查错，这个每次课上和课后都有要求，但有多少同学课后认真OJ ？从了解的情况看，竞赛前每次课上询问作业完成情况，只有不超过5人举手，作业如此，OJ可想而知。

作为对比，我部优秀毕业生孙乐然同学，本次竞赛成绩非常好，这次是提高组高分一等奖。据老师了解，在课程紧张的高中，他仍然每天OJ超过3小时！
上面提到的夏同学和黄同学，从了解的不多信息看，他们平时课后训练的时间也要远远超过我们本届的同学。

平时训练不足，测试不严格，从而程序细节不完善，在用严格数据测试时就会丢分到很惨，结果就是这样！

因此，后面课程，我们会增加课程次数，大幅增加课堂的训练和测试比例，从根本上改变训练不足状况。