Skip to content

2022 秋季学期清华大学电子系数据与算法课程 OJ 参考解答

Notifications You must be signed in to change notification settings

DragonAura/EE_DA_OJ

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

2022 秋季学期《数据与算法》课程 OJ 参考答案

说明

由于笔者在 OJ 系统还开着的时候忘记了保留题目题干,因此部分题目没有原始题干,只有题目内容大致描述与最终提交的代码。

题目

1. 判断是否在平面上

印象里是判断所有输入的点是否都在一个平面上,不在的话就输出第一个不在平面上的点,否则什么都不输出(?题目很简单,暴力可解,参考代码见 OJ1.cc

2. 情报破译

大概是先后输入若干个结点,每个结点的输入内容包含一个字符串与其指向的下一个结点,最终会构成两个链表。难度印象里主要在找到头结点,开始构造链表上。暴力法可解,参考代码见 OJ2.cc(不确定是不是最终版本,但是思路肯定是对的)。

3. 找到最大连通子区域

给定一个图,找最大连通子区域,输出大小与区域内的各个点。两次 DFS 即可,很简单,参考代码见 OJ3.cc

4. 二叉树压缩

对一个二叉树做各种神奇的压缩,题目难度主要在读题,助教的题目描述非常谜语,题目本身暴力即可解,参考代码见 OJ4.cc

5. 双向路径

大概是要求找到图中一个点到其他各点的单源最短“路径”,这里的路径长度是指从起点出发到某个点加上从终点出发到这个点的路径总长度,因此不一定是直接从起点到终点。题目思路在于构造一个反向的图,想通了这点之后就是 Dijkstra,无本质难度。参考代码见 OJ5.cc

6. 字符串找不同(忘了叫什么了)

题目大概是一个字符串存在一定概率“写错”,比如多一个 l 或者少一个 l 之类的,如果两个字符串之间只差一个 l 就认为是同一个字符串,现在要统计出现次数最多的字符串。理论上讲要并查集慢慢处理,但是实际上样例很简单,输入时暴力去掉所有 l 即可过。此处给一种正常做法的代码,见 OJ6.cc

7. QR 分解迭代解方程组

很抽象的数值算法,就是爆写 QR 分解,然后迭代解方程组。理论上要用到 Givens 变换等复杂度更低的 QR 分解方法,但实际上 Gram-Schdmit + 调参 可过。参考代码见 OJ7.cc

8. FFT 解卷积

题目背景忘了,总之是用 FFT 算卷积。FFT 也没什么好的办法,大二不可能会自己写,网上偷一个版本改一改即可。参考代码见 OJ8.cc

9. 动态规划

很抽象的动态规划,大意是找到吃最少食物的营养组合,来使总营养值最大。内存卡得很死,要做各种抽象的优化,比如用滚动数组,用位运算来表示状态,用二进制压缩来表示食物的营养值等等。参考代码见 OJ9.cc

10. 走迷宫

暴力 BFS 即可,没有难度。参考代码见 OJ10.cc

About

2022 秋季学期清华大学电子系数据与算法课程 OJ 参考解答

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages