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

2017年2月19日7,8380

「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

拆点+最大流

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

 

avatar
  Subscribe  
提醒
nervending
nervending

/01 /01
对于poj【poj2528】Mayor’s poster这道题…
样例
1
1 10
1 3
6 10
的答案应该是3
(1-3,4-5,6-10)而不是2