Posted on

题解

这道题第一眼看是维护前缀后缀然后合并的，但是这样复杂度很高，据说可以水过

因此，不考虑合并。那么问题就是去掉每一个物品，做一次多重背包。这样的复杂度为\(O(n^2m)\)。

考虑以上算法的重复计算部分。可以发现有许多是重复计算了的。那么就可以考虑分治，因为分治可以省去许多重复计算。那么算法就显而易见了。

Read more »

Posted on

题意

给定一个字符串S，找到另外一个字符串T，T既是S的前缀，也是S的后缀，并且在中间某个地方也出现一次，并且这三次出现不重合。求T最长的长度。

Read more »

Posted on | Edited on

题意

我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。

然后输出$ _ {i = 1} ^ L (num[i] + 1) $

Read more »

Posted on | Edited on 
1
2
3
4
5
6
7
8
9
#include <cstdio>

int main()
{
	int x, y;
	scanf("%d%d", &x, &y);
	printf("%d\n", x + y);
	return 0;
}