有趣的一道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”
比赛时候万人题，呵呵，没想到转换成histogram来做。貌似转化之后暴力都可以，n*m^2，气哭aaaaaaaaaaaaaaaaaaa
然后自己写了单调栈n*m做法，需要注意的是要同时保存一段height的左端点和右端点，因为要求数量的话，用单调栈只保存一个的话会忽略掉中间的“高点”，只保存一个端点就无法正确计算了。。。emm，代码写得时候脑子也很乱，还是需要多写写单调数据结构的题目。
继续阅读“[比赛][单调栈][histogram] 2018ICPC 南京网络赛 B The writing on the wall 求柱状图中有多少个矩形”
这题真的好鸡儿简单。。。差不多是除了第一题之外最简单的了。比赛的时候没看这个，iSika说很难就没做，唉
题意：给n个房间，当还有房间的灯没有被换成节能灯的时候每个月开始会买入m个节能灯，然后从左向右在列表中找小于m的房间换掉，如果当月的节能灯没有用完的话可以留给下个月。然后给q个询问问d第几个月结束的时候有多少个房间被换成了节能灯，以及手里剩下了多少节能灯。
解法：用value表示当前总共有多少个节能灯，把q个询问都读进来排序后从小到大操作（就是从第一个月开始模拟）。每次都找列表中<=value的最左边的值，找的方法是用线段树维护区间minv 信息，如果左子树minv<=value的话就向左走否则向右，如果小于minv[1]就不找，直接把当月的算出来。找到的话，令找到的房间的计数器+1，value-=找到的值，然后更新线段树这个点的minv为INF就行了。由于每个节点最多被修改一次，修改一次的代价为logn，所以总共的代价为qlogn，case closed！ 继续阅读“[比赛][线段树][模拟] 2018南京网络赛 G Lpl and Energy-saving Lamps”
