2024 Fall，CS101 PA 又变回了算法竞赛风格，真是 OO 又 II 啊。
UPD (2025/01/10):
被喷了。
能看出 TA 这么说是出于 “想让这门课变好”，可能写到最后有些激动，责任心致使他觉得我描述的不清楚的部分都是在批评他的成果。
- 我没有要求 CS101 为没学会 C/C++ 还债，并且我提到的两种路径之一：对 shitty code 宽容（类似现在的状态）本身就是为了减少代码方面负担，另一种路径则是为题目提供更多的引导（如提供代码模板），从而几乎杜绝 shitty code 问题。
至于 OJ 的反馈，23f 我就提出了这个问题，我相信你们也有那个某位学长怒骂半分钟的语音回复。
所以说评测机制在 23f 就有机会改，相信以后也有机会改。
- 继续滑坡，“课程没人在意” 这个现象是结构性的烂，我们能做的就是在可能的范围内做一些让自己开心的事情，比如说尽力讲一些自己认为有意义的东西。既然 SI100B 讲 AI，代码量少，CS100 太 language lawyer，不够好，那么 CS101 到底要承担怎样的责任？每个人有不同的答案，我所不满的主要是 PA 中 OI 内容的回归以及部分助教的态度问题。
UPD (2025/01/11):
你说 OI 的回归让你很不满意，但是你提出的议题是 “去除期末考试”“改为 proj” 或是 “取消 quiz” 这种明显利好于 OIer 的设计让我觉得你才是想要让 OI 回归的那个。
...
我之前也提到，23fPA2 就是我很满意的 PA，难道那次 PA 不也是 OIer 比非 OIer 快吗？
我开篇即提到，OI 的回归是 PA 中 OI 风格题目的回归。除此之外，就像 TA 的回答中描述自己学习 CS101 的部分，OI 经历让一个人可以 “不需要系统性的认真学”，靠复习就可以掌握，既然 OIer 已经不考虑怎么学了，更需要重视的是没有竞赛经历的同学的体验。如果有更多的 PA，那么这些同学的 “缺乏实现能力” 的问题会减轻，但是这么改确实和一些同学期望的重视算法的推理的方向背道而驰。
“OI 回归” 本身就是一个伪命题，并且从你说的话，我无法理解你想表达的去除 OI 化，或是 OI 的不回归想体现在哪里。
OI 的部分题目有一个特点：不考虑时间复杂度，只有 “TLE” 和 “能卡过去” 两种复杂度。例如 PA1 的第一题，目标是考察链表，但是由于问题限制较少，链表在任意位置插入删除复杂度优秀的特性只是一种适合通过题目的方式，一个循环队列也有 PA1 第一题需要的数据结构的特性，因此才有的后面临时加上禁用 std::queue 以及在题目描述补充实现一个队列来解题的情况。
另一个 OI 化的特点就是 shitty code，很多同学在后续 debug 的时候会发现很难在原先的代码上进行修改，例如有一位同学在实现 PA3 第三题时存储了所有的路径并且在每次寻找可以被当前点松弛的节点的时候都遍历了所有的路径的每一个站点导致超时，此时想要不改变原来的松弛部分的同时加上 “让每个节点能只考虑经过此节点的一步 “比较复杂。此时如果有一个给出一定限制的代码框架（例如 PA2 AVL），可以让同学们理解到如何设计才能更好地实现算法。
你还提到，讲解是额外占用同学时间的，难道添加提示思考不也是增加同学的时间吗？（甚至还加多了同学的思考量，在没有引导的情况下，占用的时间只会更多。）
因为难度不当导致需要临时加讲解就是额外占用了同学时间，如果要滑坡成我认为讲解是额外占用时间那我应该连习题课也反对。
在 PA 3 的第一题就采取了在题目内给予引导的形式，你们不也认为给出引导带来的思考量是包含在题目内的吗？
另一方面，经典的考题与思想概念属实不多（稻草人除外），但是我们的原创和复用都不同程度地被不同角度地抨击。大部分原创的题被喷表述不清不知道出题人的思路，复用的题被指责逼着学生去网上抄答案。
我都想让 PA 有模板题了，我的意思肯定不是让同学抄答案啊。
关于 PA1 第二题和 PA2 第三题的描述：
前者在描述登陆和放出怪物的流程上比较反直觉，例如为了说明 RMQ 区间的特性用了 “每个玩家按照登录顺序退出” 和 “第 i 次登录的 ID 为 i” 两条，可以在题目描述和输出格式部分用 “第 i 个登陆的玩家” 来表述，不需要再描述 id，而适合用 id 表示的 “怪兽的种类” 描述不够明确，于是很多同学初看样例输入的 1 5 1 2 3 4 5 一行时没法很快意识到 1 2 3 4 5 是说有
放出了五次怪物，放出的怪物的类型（的号码）分别为 1,2,3,4,5。
后者每个节点既有 id 又有权值，在实现阶段需要按权值关键字排序后 id 的序列，比较容易在这个阶段混淆，实际在排序完后权值就无关紧要，不能算作题干问题（我的我的），但是这可以引出一个我认为需要 Project 的原因：
课上学到的是重视逻辑与推理的，不受实现影响的算法，而 PA 则是让同学实现一个内部 “包含” 了一个算法实现的黑盒。除了黑盒对输入输出的表现符合预期，黑盒内的结构也是重要的，能把流程抽象出来正是理解了算法的表现之一，例如 Dijkstra's algorithm 在代码里就应该体现为一个输入为一张图和源点，输出到每个点的最短路径的黑盒，内部的细节和题目其他部分解耦，例如 PA3 第一题，如果同学能想到把 MST 单独拎出来作为一个函数（这一点大家应该都能想到），使用 Kruskal 的同学能想到把并查集用一个 struct / class 的方式独立出来，在实现这些部分的时候不需要考虑题中的一些类似 “特殊边” 的条件，理解抽象的算法和对实现进行抽象，这是我的认识中的一个重点。
因此 LeetCode 式交互的模板题可以让同学大概理解如何抽象，可能一个 Project 的代码量仅和一次 PA 总代码量相当，但是 Project 可以强调把实现之间解耦，这样实现的部分就更接近课上的算法的理论形式。
教学
上课朗读 slides，slides 对课程来说还不错，有较为良好的引入。
但是不适合作为自学材料，所有引入和叙述逻辑全都糊上去了，太啰嗦。
考核
TA 对考核内容是否用心极大程度上决定了你的体验。
2024 秋学期有几位拟人 TA，导致体验较差。
有一名助教习题课习惯性爆粗；超过两次讲解算法出现事实性错误，被同学当场指出；总是比其他助教早结束 20 分钟，疑似自己懒得讲就摆烂了。
UPD (2025/01/06): 一位和我习题课同班的同学表示这位被同学纠正过的助教讲课挺不错的，但是同习题课班级的另一位助教的讲解混乱，没有重点。
作业
必须要和上课使用的 convention 达成一致。
优点是可以治疗部分竞赛生只会 “感性理解” 的毛病，贴合课程内容，值得一做。
缺点是由于题都是人出的不可能完美，并且你还可能见到：搬运原题，不会排版，带有歧义的描述等，令人忍俊不禁。
PA
2024 秋学期三次 PA 内容如下：
- PA1
- A. 简单链表模拟题，名义上禁用了多个 STL 容器，但是由于没有其他限制，最简单的方式是使用巨大的全局数组糊一堆垃圾代码上去
- B. 题目描述几乎不说人话。要求学生自己翻视频号看如何使用单调队列进行 RMQ
- C. 比较有含金量的题目，需要理解快速排序的原理
- D. JOISC 2012，需要学生自己悟出来类似 cdq 分治 + 单调栈维护凸包，后面 TA 团队发现题目太难（这种题为什么不是在出题阶段就被毙掉）组织了讲解
- PA2
- A. 树哈希，几种不同的思路都能通过，难度适中
- B. 哈夫曼树 & 结合额外信息做贪心，比较好的考察了贪心算法的一题
- C. 老生常谈的给两种遍历建出原二叉树，
输入输出格式烂
- D. AVL 树模板题，给了代码框架，填空完成剩余内容
- PA3
- A. wqs 二分 + MST，难度较高，因此题干里面以类似 “大题的第一小问” 的形式，用几个不需要提交的简答题给出提示
- B. 排序不等式贪心
- C. 转化题目为单源最短路径，比较好的一题
- D. 数位 DP & 二分查找计算第 k 个符合条件的数，后一问由于取模的关系容易写出 bug，后面加上了提示
- E. 类似背包问题的三个小问题合集，但是由于性质不同需要想出当前问题贪心即可解决 / 需要 DP，模板题
总结：
从身边同学 coding & debugging 的过程来看，CS100 的代码量和问题深度尚不足以让同学们完全掌握 明确问题逻辑 -> 抽象、分解求解过程 -> 使用编程语言进行实现 类似这样一条完整路径。但是对于只是体验到了 C/C++ 中内存管理、指针、OO 等特性的同学来说，让他们直接写出优雅的代码是不现实的。
此时对作为后继的 CS101 而言，有两种不同的路径：
- 换一门更简单的语言，比如 Python。包容 shitty code，算法能实现出来就行，重点放在算法的 “人类智慧” 上
- 继续使用 C/C++，但是需要提供更多的帮助，比如提供代码模板，降低题目难度
对于 C/C++ 到底是不是底层语言，以及用 C/C++ 实现算法是否会带来更多的心智负担，我的结论是：前者否，后者是。C/C++ 唯一的贴合本课程算法与数据结构之处就是有 O (1) 访问的 unboxed 数组。
无论选择何种路径，2024 秋学期的 PA 难度都是不合适的，reference code 也是某种程度上 “放弃” 了 CS100 所学内容的 shitty OI code.
除此之外，还有一点能够改进之处：OJ。
应当减少 OJ 黑箱程度，目前评测的反馈过少，只有每个测试点的状态，应该考虑使用 SPJ 加上更多的反馈信息，比如 WA 的时候给出与正解相差在哪等信息。
使用类似 leetcode 那样的实现一个函数的提交方式，而不是现在的从标准输出输入流读写（本学期出现 TA 发现启用流同步的 cin / cout 可能超时于是选择在题干呼吁大家使用 scanf / printf / getchar / putchat 而不是提高测试时间上限的幽默行为）
Quiz
可以看出题目已经尽量向着能多简单就多简单来出，但是已经有作业了，Quiz 没有意义。
展望
由于课程给分竞争总是存在，有竞赛基础的同学无论如何都会占据优势。
个人认为更好的考核方式为：
- 取消 Quiz
- 课后作业全部改为 PA 的形式
- PA 增加次数 & 题目量，增加模板题，减少竞赛风格题目（或为难度较高的题目添加提示，不用讲解额外占用同学时间）
- 只允许在难题中出现 shitty code
- 保留期中，取消期末考试，改为 Project
或者
- 放弃 PA, 作业全部为理论作业
- 取消期末考试，改为 Project
- 允许任何 shitty code
或者（并不现实的答案）
- 直接在全校的编程入门阶段课程放弃 C/C++，但这对于想就业的同学是不友善的，C/C++ 使用率仍然很高。
- 加入类似 SICP 的课程（我们 CS 专业也是学上自己的哲学导论了）
关于如何正确的学这门课
再次强调，有竞赛基础的同学会占据优势，但是这种同学无论如何都占极少数。
于是当你已经失去了绝对优势，你就必须要珍惜你的比较优势。
竞赛生（可能的）绝对优势：
- 本身就会算法，不需要去上课
- 实现过自己学过的算法，更理解算法的逻辑
- 很可能会 LaTeX，写作业比你更快
你的比较优势：
- 你有之前的竞赛生总结的内容，例如 oi-wiki.org （很多 convention 与课程描述不相符，但是对部分算法有更直观的描述）
- 在课程上花了时间，convention 和课程 / 考核要求一致
- 你这学期在学他们也学的课程，并且你学得比他们好
- 他们可能会因为认为自己学会了而懈怠，和他们讨论，从他们那里学到知识
- 你依然可以以纸质形式完成作业，不像概率论那样强制 LaTeX（只适合在 “用 LaTeX 严重影响你完成作业效率” 的情况下，其他时候最好能学会 LaTeX）
- 你在物质条件上有比较优势
- 你相信 CS100 学完的东西是有意义的
无法弥补的部分：
知识的诅咒是存在的，竞赛生通过提早学习构造的壁垒也是存在的，即使全年级的 OIer/XCPCer 都帮你学 CS101，你也不太可能在短时间内全部掌握怎么解题和怎么写出 “好的” 代码。
总之，别想着和竞赛生卷生卷死，上文描述的全部困难都可以靠多讨论多提问而不是折磨自己内心来克服。
最后的最后
我支持 Gkxx 的改进方式，并且非常不理解为什么本学期选择与已经完成的改进背道而驰。
