2016 Multi-University Training Contest 5

2016年8月3日1,4511

本场抱住卓神大腿最后过了7题。。。感觉把pku的牌子砸了。。。

我做了1001 1005 1011

随便口胡几句。。。

1010看起来像后缀数组。。。但是交wa了几发不知道什么情况

1001 ATM Mechine

这题似乎0元钱也要取1次1元的来确认一下,不然没法解释样例

\(f(i,j)\)表示有i元以内的钱,j次warning的机会

然后枚举询问点k,有t种可能warning,那么转移给\(f(t-1,j-1)\)

有i-k+1种可能取钱,转移给\(f(i-t,t)\)

边界j为1的情况,有k元钱需要询问k+1次

发现warning次数太多也没什么用,直接将其对30取min即可

也可以用决策的单调性加速转移

1005 Interesting

回文自动机裸题

求出以i结尾的回文串个数和回文串总长度

枚举j计算

1011 Two

\(f(i,j)表示\)第一个序列以a[i]结尾,第二个以b[j]结尾的方案数

用前缀和加速转移