有趣的一道dp，让我想起了msc面试的时候问的扔杯子的问题。
首先，如果确定了对于长度为n的代码要写x个printf，那么这x个一定是尽量均匀分布（数学显然）才能使得最坏情况最好！因此，可以写出递推式：f(n)=min(f(ceil(1.0*n/i))+r+i*p);记忆化搜索暴力转移即可。
这个复杂度分析很数学：[n/i]的只有O(sqrt(n))种可能，每种可能的情况递归下去的话[n/ab]=[[n/a]/b],仍然是在那sqrt(n)种可能里面。所以总共有sqrt(n)个点会往下递归，每个递归点又最多有sqrt(n)次，相乘的话相当于O(n)； 继续阅读“[DP][复杂度分析] Gym – 101485D Debugging”
这个题当时tle到哭，心态爆炸，也几乎直接导致了没去看很简单的G，心情复杂。
这个判重刚好卡unordered_set，怎么都过不了，只能自己手写Hash判重。另外一个优化的点就是一定要边Manachar边计算，我一开始写的跑一遍Manacher之后枚举中点然后计算左右端点（那不就退化成n^2了嗯我当时就这么傻）。一边Manacher一边做，好处就是关于某个点对称的重复的回文串只会被算一次！这也是Manacher自身的算法决定的。。这个题其实出题人就是想让这么做的，不然要想计算所有出现的回文串的（不判重）MOD，应该是只能n^2吧。。（或许SAM可以？我没想过）。
需要巩固的地方：字符串Hash，字符串子串预处理（取模等），Manacher的原理的深刻理解。
继续阅读“[字符串][Manacher][Hash] 2018ICPC 南京网络赛 I Skr”
