江苏省常中Day6

T1 蛋糕

题意:一块n*m的蛋糕切成1*1的蛋糕,问有几种切法。

题解:考虑dp,枚举切的第一刀,f[i][j]加上切出的两部分相乘即可。

T2 找钱

题解:考虑付钱中不能有小于找钱数额的纸币是什么意思。这说明如果你付的钱中最小面值是a,那么你最多付给店员X+a-1元钱。这一部分多重背包即可求出付给店员i元钱的方案数,然后找钱同样多重背包即可。复杂度O(nX)。

还未改出。。

T2 城镇

题意:每次建造一条道路,询问该道路所在连通块距离最远的两个点。

题解:等于需要维护每一个连通块的直径。当连接两个连通块时,可以证明新的直径的两个端点只会在原来两个连通块直径端点之间产生,因此我们只需判断要连接的两个点所在的连通块的直径的四个端点两两之间是否存在更大的值。

END.

发表评论

电子邮件地址不会被公开。 必填项已用*标注