2015程序设计实习实验班免修考试(校内)

2017年2月19日2,0480

【poj1037】decorative fence

用f(i,j)表示长度为i,开头为j,开头为上升的序列
用g(i,j)表示长度为i,开头为j,开头为下降的序列
考虑在序列的第二位放一个数字,改变上升/下降
预处理完之后,一位位枚举贪心

【poj1011】Sticks

经典的搜索剪枝

1.长度取值范围是木棍的最长长度到长度总和之间。
2.长度总和一定可以整除原来的长度。
3.从大到小排序搜索。
4.某次组合时,如果不能加入某根木棍,同种长度的木棍也不再尝试。
5.如果在组合过程中,当前可选的第一根木棍没用上,返回。

【poj1286】Necklace of Beads

Polya定理,考虑顺时针转i个珠子或按照某个对称轴翻折

【poj1704】Georgia and Bob

阶梯博弈,把棋子按位置升序排列后,从后往前它们两两看成一对。
一对棋子中,如果一方移动前一个,另一方总能对后一个移动相同的步数。

于是只需要考虑同一对的两个棋子之间的空格数,转换为nim问题。

【poj4105】拯救公主

状压宝石 bfs

【poj2528】Mayor’s poster

离散化后线段树染色

【poj3436】ACM Computer Factory

拆点+最大流

枚举每对机器,判断是否能够传输