课程名称︰算法设计方法论
课程性质︰选修
课程教师︰陈健辉
开课学院：电机资讯学院
开课系所︰资工所
考试日期（年月日）︰2018/12/17
考试时限（分钟）：3小时
以下包含期中考题和测资，以供学弟妹练习，
每题共有十笔测资，置于文末的Github连结。
试题 :
所有题目均为程试题，语言限制C/C++：
1. Longest Common Subsequence (Dynamic Programming)
Description
一个字串的子序列是由字串中若干个字符(不一定连续)以相同的顺序所组成的字串，例如
：AB、ACE、E 都是 ABCDE 的子序列。
两个字串的最长共同子序列即为两个字串的共同子序列中字符个数最大者。
Input Format
每组测资包含两个字串，每个字串长度不超过 100，且全部都是由大写英文字母组成。
Output Format
第一行请输出最长共同子序列的长度和个数，下一行开始请依字典顺序输出所有的最长共
同子序列。注意答案中可能包含相同的子序列，因为同一个子序列在两个输入字串中的位
置可能不同。保证最长共同子序列的个数不超过 200000 个，LCS长度 >0。
Hint
需要输出大量的答案，请避免使用缓慢的 I/O 函式。
每笔时限为 1000ms，内存上限为 64000KB，保证正确输出的档案大小在 32000KB 以内
。
2. 2-Dimensional Linear Programming (Prune & Search)
Description
在二维平面上，使用prune and search技巧，实作线性规划
Input Format
第一行包含一个正整数 n<=10^5，代表限制条件的个数，
下一行开始每行包含三个整数 -300<=a,b,c<=300，代表 ax+by<=c , 其中 a^2+b^2>0。
Output Format
请输出满足所有限制条件的最小 y 值(四舍五入至整数)，若没有解，请输出 NA，若为负
无限大，请输出 -INF。
Hint
需使用 P & S，否则不予计分。
每笔时限为 1000ms，内存上限为 64000KB。
3. The 0/1 Knapsack Problem (Branch & Bound)
Description
请使用 branch & bound 策略解决 0/1 背包问题。
Input Format
第一行包含两个正整数，分别代表背包大小 5 ×10^6，和物品个数<=1000，下一行开始
每行包含两个正整数，分别代表物品价值 <=10^5，和物品重量 <=10^5。
Output Format
请输出最大收益。
Hint
请使用 branch & bound 策略，其余作法(e.g. dynamic programming)不予计分。
4. The 2-Dimensional Closest Pair Problem (Divide & Conquer)
Description
请在二维平面中找出所有最近点对及其距离。
Input Format
每组测资第一行包含一个正整数 2<=n<=2 ×10^5，代表点的个数，接下来 n 行开始每行包
含两个整数|x|,|y|<=10^9，代表该点的座标，保证所有点的座标皆相异。
Output Format
第一行请输出两个数字分别代表最近点对距离的平方以及个数，下一行开始请输出所有的
配对。每组配对有两个整数，分别代表两点输入时的顺序，且第一点为序号较小者。输出
时请依第一点序号递增排序，若第一点序号相等，则依第二点序号递增排序。
Hint
需使用 divide & conquer 策略，而且 time complexity 必须为 O(nlogn+slogs)，其
中 s 为配对数，否则不予记分。
请注意： int 能存取的范围。
测资下载：
https://bit.ly/2TO26mN