[原博客] POI系列(4)

正规、严谨、精妙。 -POI

  BZOJ 1531 : [POI2005]Bank notes

  裸的背包,可以二进制拆分一下。一个物品比如说有n个,可以拆成 1,2,4,8,16...个。
OJ上没有样例,这里附上原题样例。

In:
3
2 3 5
2 2 1
10
Out:
3

样例解释:略。

  BZOJ 2084 : [Poi2010]Antisymmetry

  根据定义,回文串的长度必定是偶数,然后可以用回文串算法Manacher,因为是“反对称”只需把条件改成!=即可。

  BZOJ 2276 : [Poi2011]Temperature !

  单调队列,记录最小值递减,然后,队尾不合适的退出,更新答案。 详细

  BZOJ 1526 : [POI2005]ban- Bankomat

  注意是求满足所有的录像带的串一共有多少种。反着扫一遍,记录每个录像在i之后最早出现某个数字是在什么地方,然后枚举所有可能的编码,判断是否符合这段录像。当某个编码符合的录像数达到n时,ans++。输出ans即可。

  BZOJ 1535 : [POI2005]Sza-Template

  二分+KMP算法,满足题意的串肯定是该串的一个前缀,同时也是该串的一个后缀,可以用kmp找出这样的所有串,可以证明如果一个串成立,那么比它长的串也成立,然后二分就行了,需要注意一些细节。  


以上。

上一篇:ytu 1064: 输入三个字符串,按由小到大的顺序输出(水题,字符串处理)


下一篇:串String(2):串的实现(堆分配存储表示法)