7.8总结
前言
首先，关于新评测机：
它死了
状态那里积了15页的pending
得分情况
估分：0+100+50=150
实际：0+100+19=119
Rank12
T1签到题没做出来，凉凉
T1
题目大意
除去对铁质盔甲强烈的热爱，Brunhilda是一个正常的7岁女孩。近期，她正在策划一个完美的生日派对。她发明了如下的一个游戏：所有的孩子在一个数k被宣读之前不停地跑来跑去。当这个数字k宣读后，所有的孩子将形成人数恰好为k的若干群体，且保证剩余的孩子数目小于k。最后，这不足k个的孩子将从游戏中被淘汰。紧接着，比赛将继续进行，并公布一个新的数字k。游戏将在所有的孩子都被淘汰后结束。
Brunhilda请她的父亲Wotan在游戏中来宣读数字。Wotan不喜欢这个游戏，当然也不希望在游戏的第一轮就宣布一个正无穷（PS：宣布正无穷等于将所有的孩子都从游戏中淘汰）。 Brunhilda认为这在派对上是相当尴尬的情形，所以她给了她父亲一串共计m个素数的列表。这样，她的父亲便可以从中进行选择。当然，相同的数字在游戏中可以被多次宣读。
Wotan想尽快结束比赛，因为他有一张他最喜欢的足球俱乐部 FC Asgard的比赛门票。不幸的是，Brunhilda不知道派对上参加游戏的孩子数目。现在，对于Q个不同的数n1，...，nQ个儿童，Wotan要预先知道他所需宣读的最少数字，以便他尽早结束游戏。
20%的数据：m,nj,Q<=10000.
另有20%的数据:Q=1
100%的数据：1<=m,Q<=100 000,1<=nj<=10 000 000,2<=pi<=10 000 000
比赛时没注意到前20%nj<=10000，没打暴力，丢了20分
正解：
对于20分的dp，我们有方程f[i]=min(f[i-i%p[j]])
观察到f是单调不下降的，f[i]>=f[j]|(i>j)，因为如果f[i+1]<f[i]，则更新i+1的点一定可以更新到i，矛盾。
设p为k的质因子（p是题目中给定的一个质数），f[k]—>f[k+1~k+p-1]
现在只要找出每个数的最大的，题目给定的质因数（设为ma[k]）就能枚举k，把能转移到的区间往后更新，O(n)转移了
设k=a*b,ma[k]=max(ma[a],ma[b])，ma[pi]=pi
类似筛法搞搞就行
T2
题目大意
森林里有一片长方形的草地，在清晨的大雪过后被一层厚厚的积雪所掩盖（下图左）。
住在森林里的兔子和狐狸，穿越草地，都会在雪地上留下他们的踪迹。他们总是从左上角进入，并从右下角离开草地。在这两者之间，他们可以来回走动，在雪地里玩，甚至在同一个地方多次留下踪迹。在任何时候，最多只有一只动物在草地上，且所有的动物都只进入草地一次。这些动物的运动踪迹可以被简单的利用横纵坐标来描述。它们不会斜着走，也不会跳越一个单元格。当新的动物进入单元格，旧的足迹都将被新的足迹所覆盖。
你将在一段时间后，得到一张描述草地上每个单元格的状态的地图。请写一个程序，计算可能出现的动物数目的最小值N。30%的数据满足：动物数N<=200,H,W<=500
100%的数据满足：1<=H,W<=4000
签到题。
现在在（1，1）的动物一定是最后走的，为了使答案最小，我们像细胞那样， 把相邻的同种动物的脚印都标记上。同时记录相邻的另一种动物的脚印，下次从那些脚印扩展就好了。
T3
Victor 正在使用 vim 编辑他的文章，他的文章只包含
abcdefghij这 个字母，他想把他文章中所有的e都删除。Victor 并不是很熟悉 vim，它只懂得下面几个操作：
x：删除光标所在的字母，光标位置不变。h：光标向左移。如果已经是行首就不会移。f：后面还会跟一个字母 c，表示跳到下一个字母 c 的位置。如果不存在那么就不会跳。悲剧的是 Victor 的键盘上
e按键突然坏掉了……请问：Victor 最少需要按多少个键才能把所有的e删除。例如，如果当前的文本是
jeff[i]ehadabigidea，则
x操作后文本将变为jeff[e]hadabigideah操作后文本将变为jef[f]iehadabigideafi操作后文本将变为jeffiehadab[i]gidea
想打50分dp,结果打挂了只有19分，死活调不出来
现在调出来了。O（\(n^3*10\)）要吸氧才能拿48分
正解
线头dp??!
有这四篇题解写的很好
jzoj3320vim题解—“线头”dp.pptx By严禹韬
下面是我自己的理解：
线头dp就是找出一些关键点，每个关键点有一些线头，通过连接这些线头来计算答案
听起来就超级抽象
对于这一道题，一段连续的‘e’之后的那个字符是必须经过的，所以它们就是关键点。
答案就是经过这些关键点的路径长加上‘e’的个数*2。
设f[i][j]表示当前在i位置，并且i,i+1之间的这条线段被覆盖的次数为1次的接下来要跳到j字母的最小代价。设g[i][j][k]表示当前在i位置，i,i+1要覆盖三次，因为被覆盖三次所以会有两次向后跳的操作，第一次跳到了j字符，第二次跳到了k字符的最小代价。注意到这个状态中，并不代表着是从i位置往后跳j，而是从i位置之前的某个位置到达i之后j字符的最小代价。
事实上，f和g的代价只计算了1~i的点向后跳的代价以及1~i+1的点往回走的代价
转移参考上面的博客。
初始化f[0][s[1]]=0
假设我们的字符集a~j编号为0~9，那么我们将10视为一个没出现过的字符，最后dp出的ans就是f[n][10]-2
因为10不存在，所以可以把f[n][10]视作将绳子拉向一个无限远的点
又因为这样代价为2，而实际上我们并不需要这样做，所以减去2
感受一下就好了，估计以后也挺难遇到的
花絮
- 古爷拿金牌回来啦！
- 新OJ叫GMOJ,Gold Medal Online Judge
金牌OJ