发表于 | 分类于 | | + s

hdu 3440

差分约束，由于求最大差，故建立$a-b<=c$的不等式，跑最短路
h数组排序后，依次连接两个相邻的数，注意绝对值的问题

ps: INF要开0x7fffffff

阅读全文 »

发表于 | 分类于 | | + s

hdu 2825
题意：给出$m$个模式串，求至少包含$k$个模式串长为$n$的主串个数。
用模式串建立AC自动机，设$dp(i,j,S)$为主串前$i$个字符，在AC自动机上$j$点，当前存在模式串状态的方案数。
$$dp(i,v,S|val_v)=dp(i-1,j,S)$$
因为有用的只有两层，所以其中可以运用滚动数组节省空间

阅读全文 »

发表于 | 分类于 | | + s

$Day0$
坐了4个小时的车才到酒店，酒店真是高端。。
然后去了东华吃晚餐，这都是素菜。。？
晚上浪浪浪
$Day1$
直到闹钟叫才醒。。真是睡得够死。。酒店早餐西式自助真不错。。
7点半到东华，学校真大找半天路。。
然后进去机房无力吐槽。。真是挤。。挺不舒服的

开考了，解压密码HaveANice51。。
t1，怎么这么难，跳。(结果是题目读错了，裸kmp)
t2，3000字题面，还有完整版5000字题面，真是丧心病狂。。mex定义和题目所求真是够乱。。然后刚开始理解成求子树最小值了。。后来发现错了改了。。结果之后有个同学求子树最小值得了60、。。真是。。
t3，好像很难，但是貌似dp能有20分，没打真是可惜
t4，???
day1考完真是感觉差，觉得要爆0了。。
之后发现t1还骗到10分？真是奇怪。。
day1 10分滚粗

阅读全文 »

发表于 | 分类于 | | + s

hdu 3336
如果$next[j] = i$, 那么说明$[0, i-1]$与$[j-i, j-1]$部分相同
并且$i,j$之间没有更多的前缀
设$dp[i]$为前$i$个字符中前缀出现次数
$dp[i] = dp[next[i]]+1 $

阅读全文 »

发表于 | 分类于 | | + s

bzoj 3191
题意：见上。

根据题目，我们可以从终态入手。考虑什么状态下概率已定。(期望概率题入手套路)
这里可以发现只有一个人时，必定他会胜利，所以我们可以按照「人数」划分阶段。
那么可以设$dp(i,j)$为有$i$个人时，庄家开始数第$j$个人胜利的概率。(也可以设更加明显的三维状态)
那么$dp(i-1)$可以转移到$dp(i)$
从$i-1$到$i$, $i$下$j$的这个人是不动的。考虑$i$时淘汰一个人，即枚举$a[k]$使得$c=a[k] \mod i$，$c-1$是淘汰的人相对当前$i$庄家的位置。
然后因为淘汰了一个人庄家就是这个人的下一个，那么考虑两种情况
第一种，庄家跑不到$j$的后面，那么这时$dp(i,j)=\frac{dp(i-1,j-c)}m$，画图可知
第二种，庄家会跑到$j$的后面，那么这时$dp(i,j)=\frac{dp(i-1,j+(i-c))}m$，画图可知

那么最后$dp(n)$即为答案。

知识点：
1、从终态入手，来判断怎么划分DP状态

阅读全文 »