作者tinhanho (アーニャ宝)
看板Grad-ProbAsk
标题[理工] 109 中央 资演选择对答案
时间Thu Jan 12 23:20:32 2023
板上好像没有 或者是我找不到QQ
题目
https://rapid.lib.ncu.edu.tw/cexamn/exam/EC02_109_01.pdf
复选
1. ABD
2. C
3. A
4. CD
ABCD
5. A
6. C
是非
7. B
8. B
9. B
10. A
11. B
申论题不太会写qq
第1题
想法是一个从顶端push 一个从底部push
第2题
▼错的
for(j=1;j<=n;j++)
swap...;
perm(list[i], i+1, n);
swap...;
▼正确
for(j=i;j<=n;j++)
swap...;
perm(list, i+1, n);
swap...;
第3题
a Kruskal, time:O(ElogE)
b 不会写 google的->
https://web.ntnu.edu.tw/~algo/SpanningTree2.html
第4题
看板上有一篇说用DP做
但我应该还是写不出来
自己写的答案 有错烦请指正 感激不尽 祝大家金榜题名
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.224.161.235 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1673536834.A.E8E.html
※ 编辑: tinhanho (36.224.161.235 台湾), 01/12/2023 23:21:15
1F：→ ping990579: 4.ABCD 01/13 10:13
好像做错了 ABCD没错 感谢~
2F：→ ping990579: 两个stack 一个由上往下另一个反之 判断一下push时top 01/13 10:15
3F：→ ping990579: 是否一样为满 01/13 10:15
4F：→ ping990579: 第三题我想法是kruskal先找一个mst，然後找剩下的边 01/13 10:17
5F：→ ping990579: 最小的加入mst必会产生cycle,在cyle内闪掉最小边得到 01/13 10:18
6F：→ ping990579: 次小mst 01/13 10:18
※ 编辑: tinhanho (36.224.128.72 台湾), 01/13/2023 10:55:24
7F：→ ping990579: 我不是用dfs求欸我用定义 01/13 10:58
8F：→ ping990579: 在图论中，由一个有向无环图的顶点组成的序列 01/13 10:58
9F：→ ping990579: 若且唯若满足下列条件时，才能称为该图的一个拓扑排序 01/13 10:59
10F：→ ping990579: 序列中包含每个顶点，且每个顶点只出现一次； 01/13 10:59
11F：→ ping990579: 若A在序列中排在B的前面，则在图中不存在从B到A的路径 01/13 11:00
我用洪毅的indegree来写 後来有写出来~ 感谢
图论的部分不太熟@@ 图论真的蛮难的
※ 编辑: tinhanho (36.224.128.72 台湾), 01/13/2023 11:02:18
12F：→ ping990579: 第四题 想法大概是排序s成上升序列 用一个二维阵列c( 01/13 11:19
13F：→ ping990579: i,j)表示前i个和等於j的方法数 判断i与j大小关系定义 01/13 11:19
14F：→ ping990579: 递回 01/13 11:19
16F：→ ping990579: 感觉有点像背包那样吧 有错请指教 01/13 11:20
17F：→ ping990579: 不对 是元素个数才对 01/13 11:22
18F：→ ping990579: 上面是错的 01/13 11:23
20F：→ ping990579: T(i,j,a)才对 排序多余的 01/13 12:02
21F：→ ping990579: 拍谢Mst那题应该没办法是次小，我查geek上https://im 01/13 13:06
22F：→ ping990579: gur.com/ci9D3hu 01/13 13:06
23F：推 jim881115: 申论2.填空我写的是: 01/13 13:53
24F：→ jim881115: for(j=i;j<n;j++) 01/13 13:53
25F：→ jim881115: swap 01/13 13:53
26F：→ jim881115: perm(list, i+1, n); 01/13 13:53
27F：→ jim881115: swap 01/13 13:53
你是对的 但应该是<=n
https://imgur.com/6KbVUrX
写题目写到有点累 摸一下程式
题外话 swap的地方搞有点久 我的指标还是一样烂 qqqqqq
※ 编辑: tinhanho (36.224.128.72 台湾), 01/13/2023 22:34:18